International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Non-Committing Encryption with Constant Ciphertext Expansion from Standard Assumptions

Yusuke Yoshida
Fuyuki Kitagawa
Keita Xagawa
Keisuke Tanaka
DOI: 10.1007/978-3-030-64834-3_2
Search ePrint
Search Google
Presentation: Slides
Abstract: Non-committing encryption (NCE) introduced by Canetti et al. (STOC '96) is a central tool to achieve multi-party computation protocols secure in the adaptive setting. Recently, Yoshida et al. (ASIACRYPT '19) proposed an NCE scheme based on the hardness of the DDH problem, which has ciphertext expansion $\mathcal{O}(\log\lambda)$ and public-key expansion $\mathcal{O}(\lambda^2)$. In this work, we improve their result and propose a methodology to construct an NCE scheme that achieves \emph{constant} ciphertext expansion. Our methodology can be instantiated from the DDH assumption and the LWE assumption. When instantiated from the LWE assumption, the public-key expansion is $\lambda\cdot\mathsf{poly}(\log\lambda)$. They are the first NCE schemes satisfying constant ciphertext expansion without using iO or common reference strings. Along the way, we define a weak notion of NCE, which satisfies only weak forms of correctness and security. We show how to amplify such a weak NCE scheme into a full-fledged one using wiretap codes with a new security property.
Video from ASIACRYPT 2020
  title={Non-Committing Encryption with Constant Ciphertext Expansion from Standard Assumptions},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  author={Yusuke Yoshida and Fuyuki Kitagawa and Keita Xagawa and Keisuke Tanaka},