Paper 2010/100
Correlated Product Security From Any OneWay Function and the New Notion of Decisional Correlated Product Security
Brett Hemenway, Steve Lu, and Rafail Ostrovsky
Abstract
It is wellknown that the kwise product of oneway functions remains oneway, 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 kwise product of them remains oneway 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 oneway function. Because correlated product secure functions are trivially oneway, 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 $f_1(x_1),\ldots,f_k(x_1)$ is indistinguishable from $f_1(x_1),\ldots,f_k(x_k)$ when $x_1,\ldots,x_k$ are chosen uniformly at random. We argue that the notion of Decisional Correlated Product security is a very natural one. To this end, we show a parallel from the Discrete Log Problem and Decision DiffieHellman Problem to Correlated Product security and its decisional variant. This intuition gives very simple constructions of PRGs and INDCPA encryption from DCP secure functions. Furthermore, we strengthen our first result by showing that the existence of DCP secure oneway functions is also equivalent to the existence of any oneway function. When considering DCP secure functions with trapdoors, we give a construction based on Lossy Trapdoor Functions, and show that any DCP secure function family with trapdoor satisfy the security requirements for Deterministic Encryption as defined by Bellare, Boldyreva and O'Neill in CRYPTO 2007. In fact, we also show that definitionally, DCP secure functions with trapdoors are a strict subset of Deterministic Encryption functions by showing an example of a Deterministic Encryption function which according to the definition is not a DCP secure function.
Metadata
 Available format(s)
 Category
 Publickey 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
 20120322: revised
 20100301: 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 OneWay Function and the New Notion of Decisional Correlated Product Security}, howpublished = {Cryptology ePrint Archive, Paper 2010/100}, year = {2010}, note = {\url{https://eprint.iacr.org/2010/100}}, url = {https://eprint.iacr.org/2010/100} }