Chosen Ciphertext Security via Correlated Products

演讲人: Alon Rosen IDC Herzliya
时间: 2009-04-09 15:00-2009-04-09 16:00
地点:FIT Building 4-603, Tsinghua University

In this talk I will present a new notion of security, called one-wayness under correlated products. The question we are interested in is what are necessary and sufficient conditions for a function f and a distribution on inputs (x1,...,xk), so that the function (f(x1),...,f(xk)) 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 very natural correlated products 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.

We provide evidence that security under correlated products is achievable by demonstrating that any collection of lossy trapdoor functions, a powerful primitive introduced by Peikert and Waters (STOC'08), yields a collection of injective trapdoor functions that is secure under the above mentioned natural correlated products. Although we eventually base security under correlated products on 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 loss trapdoor functions from trapdoor functions that are secure under correlated products.

This is joint work with Gil Segev.


Alon Rosen is a faculty member in the School of Computer Science at the Herzliya Interdisciplinary Center. Before that he spent two years as a postdoc in the Cryptography Group of MIT's Computer Science and AI Lab, and two years as a postdoc in the Center for Research on Computation and Society at Harvard's department of Electrical Engineering and Computer Science. Alon did his Ph.D. at the Weizmann Institute of Science, and graduated in 2003. His main fields of interest are Cryptography and Computational Complexity.