Paper 2010/100
Correlated Product Security From Any One-Way Function and the New Notion of Decisional Correlated Product Security
Brett Hemenway, Steve Lu, and Rafail Ostrovsky
Abstract
It is well-known that the k-wise product of one-way functions remains one-way, but may no longer be when the k inputs are correlated. At
TCC 2009, Rosen and Segev introduced a new notion known as Correlated Product secure functions. These functions have the property that a
k-wise product of them remains one-way even under correlated inputs. Rosen and Segev gave a construction of injective trapdoor functions
which were correlated product secure from the existence of Lossy Trapdoor Functions (introduced by Peikert and Waters in STOC 2008).
The first main result of this work shows the surprising fact that a family of correlated product secure functions can be constructed from any one-way function. Because correlated product secure functions are trivially one-way, this shows an equivalence between the existence of these two cryptographic primitives.
In the second main result of this work, we consider a natural decisional variant of correlated product security. Roughly, a family of functions are Decisional Correlated Product (DCP) secure if
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. A Preliminary Version of this work appeared in PKC 2012
- Keywords
- Correlated Product SecurityLossy Trapdoor FunctionsDeterministic Encryption
- Contact author(s)
- bhemen @ umich edu
- History
- 2012-03-22: revised
- 2010-03-01: received
- See all versions
- Short URL
- https://ia.cr/2010/100
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2010/100, author = {Brett Hemenway and Steve Lu and Rafail Ostrovsky}, title = {Correlated Product Security From Any One-Way Function and the New Notion of Decisional Correlated Product Security}, howpublished = {Cryptology {ePrint} Archive, Paper 2010/100}, year = {2010}, url = {https://eprint.iacr.org/2010/100} }