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

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 encryp-tion), 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 Ω(k) jpkj and the ciphertext size Ω(k2) jcj, where k is a security parameter, and jpkj and jcj 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 jpkj and the ciphertext size (2k+o(k)) jcj. These sizes are asymptotically optimal in the sense that they are (except for a constant factor) the same as those of the simplest \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 \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 o