Correlated Product Security from Any One-Way Function
Brett Hemenway, Steve Lu, 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 nnotion known as correlated Product secure functions. These functions. These functions have the property that a K-wise product of them remains one-way ever 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 SATOC 2008).
In this work we continue the study of correlated product security, and find many differences depending on whether the functions have trapdoors.
The first mail result of this work shows that a family of correlated product secure functions (without trapdoors) 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 is Decisional correlated Product ( DCP) secure if ƒ1(x1),.., ƒk(x1) is indistinguishable from ƒ1 (x1),..,ƒk(Xk) when x1..,xk are chosen uniformly at random.
When considering DCP secure functions with trapdoors, we give a construction based on lossy Trapdoor functions, and show that any DCP secure functions family with trapdoor satisfies 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 function by showing an example of a Deterministic Encryption function which according to the definition is not a DCP secure function.
comment: Cryptography 2012 PP:558-575
Fetch PDF file of the paper
| Back to Publications List |