Paper 2008/116

Chosen-Ciphertext Security via Correlated Products

Alon Rosen and Gil Segev


We initiate the study of one-wayness under {\em correlated products}. We are interested in identifying necessary and sufficient conditions for a function $f$ and a distribution on inputs $(x_1, \ldots, x_k)$, so that the function $(f(x_1), \ldots, f(x_k))$ is one-way. The main motivation of this study is the construction of public-key encryption schemes that are secure against chosen-ciphertext attacks (CCA). We show that any collection of injective trapdoor functions that is secure under a very natural correlated product can be used to construct a CCA-secure public-key encryption scheme. The construction is simple, black-box, and admits a direct proof of security. It can be viewed as a simplification of the seminal work of Dolev, Dwork and Naor (SICOMP '00), while relying on a seemingly incomparable assumption. We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions (Peikert and Waters, STOC '08) yield injective trapdoor functions that are secure under the above mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, we argue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully-black-box construction of lossy trapdoor functions from trapdoor functions that are secure under correlated products.

Available format(s)
Publication info
Published elsewhere. SIAM Journal on Computing (preliminary version in TCC '09).
public-key encryptionchosen-ciphertext security
Contact author(s)
gil segev @ weizmann ac il
2010-03-19: last of 4 revisions
2008-03-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alon Rosen and Gil Segev},
      title = {Chosen-Ciphertext Security via Correlated Products},
      howpublished = {Cryptology ePrint Archive, Paper 2008/116},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.