**Correlated Product Security From Any One-Way Function and the New Notion of Decisional Correlated Product Security**

*Brett Hemenway and 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 $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 Diffie-Hellman Problem to Correlated Product security and its decisional variant. This intuition gives very simple constructions of PRGs and IND-CPA encryption from DCP secure functions. Furthermore, we strengthen our first result by showing that the existence of DCP secure one-way functions is also equivalent to the existence of any one-way 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.

**Category / Keywords: **public-key cryptography / Correlated Product Security, Lossy Trapdoor Functions, Deterministic Encryption

**Publication Info: **A Preliminary Version of this work appeared in PKC 2012

**Date: **received 23 Feb 2010, last revised 22 Mar 2012

**Contact author: **bhemen at umich edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20120322:141746 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]