International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Non-Committing Encryption with Constant Ciphertext Expansion from Standard Assumptions

Authors:
Yusuke Yoshida
Fuyuki Kitagawa
Keita Xagawa
Keisuke Tanaka
Download:
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 O(log⁡λ) and public-key expansion O(λ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 λ⋅poly(log⁡λ). 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
BibTeX
@article{asiacrypt-2020-30664,
  title={Non-Committing Encryption with Constant Ciphertext Expansion from Standard Assumptions},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  publisher={Springer},
  doi={10.1007/978-3-030-64834-3_2},
  author={Yusuke Yoshida and Fuyuki Kitagawa and Keita Xagawa and Keisuke Tanaka},
  year=2020
}