Chosen-Ciphertext Security via Correlated Products.
Alon Rosen, Gil Segev
Abstract We initiate the study of one-wayness under correlated products. We are interested in identify-ing 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 theconstruction 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 verynatural 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.We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions (Peikert and Waters, STOC '08) yield injective trapdoor functionsthat are secure under the above mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, weargue 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 aresecure under correlated products.
•Jan 1, 2008•0 citations