Cryptology ePrint Archive: Report 2019/1151

Non-Committing Encryption with Quasi-Optimal Ciphertext-Rate Based on the DDH Problem

Yusuke Yoshida and Fuyuki Kitagawa and Keisuke Tanaka

Abstract: Non-committing encryption (NCE) was introduced by Canetti et al. (STOC '96). Informally, an encryption scheme is non-committing if it can generate a dummy ciphertext that is indistinguishable from a real one. The dummy ciphertext can be opened to any message later by producing a secret key and an encryption random coin which ``explain'' the ciphertext as an encryption of the message. Canetti et al. showed that NCE is a central tool to achieve multi-party computation protocols secure in the adaptive setting. An important measure of the efficiently of NCE is the ciphertext rate, that is the ciphertext length divided by the message length, and previous works studying NCE have focused on constructing NCE schemes with better ciphertext rates. We propose an NCE scheme satisfying the ciphertext rate $\mathcal{O}(\log \lambda)$ based on the decisional Diffie-Hellman (DDH) problem, where $\lambda$ is the security parameter. The proposed construction achieves the best ciphertext rate among existing constructions proposed in the plain model, that is, the model without using common reference strings. Previously to our work, an NCE scheme with the best ciphertext rate based on the DDH problem was the one proposed by Choi et al.~(ASIACRYPT '09) that has ciphertext rate $\mathcal{O}(\lambda)$. Our construction of NCE is similar in spirit to that of the recent construction of the trapdoor function proposed by Garg and Hajiabadi (CRYPTO '18).

Category / Keywords: public-key cryptography / Non-Committing Encryption, Decisional Diffie-Hellman Problem, Chameleon Encryption

Original Publication (with minor differences): IACR-ASIACRYPT-2019

Date: received 4 Oct 2019

Contact author: yoshida y aw at m titech ac jp, fuyuki kitagawa yh at hco ntt co jp, keisuke at is titech ac jp

Available format(s): PDF | BibTeX Citation

Version: 20191007:082217 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]