Cryptology ePrint Archive: Report 2015/1149

An Asymptotically Optimal Method for Converting Bit Encryption to Multi-Bit Encryption

Takahiro Matsuda and Goichiro Hanaoka

Abstract: Myers and Shelat (FOCS 2009) showed how to convert a chosen ciphertext secure (CCA secure) PKE scheme that can encrypt only $1$-bit plaintexts into a CCA secure scheme that can encrypt arbitrarily long plaintexts (via the notion of key encapsulation mechanism (KEM) and hybrid encryption), and subsequent works improved efficiency and simplicity. In terms of efficiency, the best known construction of a CCA secure KEM from a CCA secure 1-bit PKE scheme, has the public key size $\Omega(k) \cdot |pk|$ and the ciphertext size $\Omega(k^2) \cdot |c|$, where $k$ is a security parameter, and $|pk|$ and $|c|$ denote the public key size and the ciphertext size of the underlying $1$-bit scheme, respectively.

In this paper, we show a new CCA secure KEM based on a CCA secure $1$-bit PKE scheme which achieves the public key size $2 \cdot |pk|$ and the ciphertext size $(2k + o(k)) \cdot |c|$. These sizes are asymptotically optimal in the sense that they are (except for a constant factor) the same as those of the simplest \lq\lq bitwise-encrypt'' construction (seen as a KEM by encrypting a $k$-bit random session-key) that works for the chosen plaintext attack and non-adaptive chosen ciphertext attack settings. We achieve our main result by developing several new techniques and results on the \lq\lq double-layered'' construction (which builds a KEM from an inner PKE/KEM and an outer PKE scheme) by Myers and Shelat and on the notion of detectable PKE/KEM by Hohenberger, Lewko, and Waters (EUROCRYPT 2012).

Category / Keywords: public-key cryptography / public key encryption, key encapsulation mechanism, chosen ciphertext security, double-layered construction, detectable PKE and KEM.

Original Publication (with major differences): IACR-ASIACRYPT-2015

Date: received 26 Nov 2015

Contact author: t-matsuda at aist go jp

Available format(s): PDF | BibTeX Citation

Version: 20151127:182835 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]