Welcome to the resource topic for 2015/1149
Title:
An Asymptotically Optimal Method for Converting Bit Encryption to Multi-Bit Encryption
Authors: Takahiro Matsuda, 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).
ePrint: https://eprint.iacr.org/2015/1149
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .