Paper 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).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
Keywords
public key encryptionkey encapsulation mechanismchosen ciphertext securitydouble-layered constructiondetectable PKE and KEM.
Contact author(s)
t-matsuda @ aist go jp
History
2015-11-27: received
Short URL
https://ia.cr/2015/1149
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1149,
      author = {Takahiro Matsuda and Goichiro Hanaoka},
      title = {An Asymptotically Optimal Method for Converting Bit Encryption to Multi-Bit Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1149},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1149}},
      url = {https://eprint.iacr.org/2015/1149}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.