Dual Projective Hashing and Its Applications — Lossy Trapdoor Functions and More

We introduce the notion of dual projective hashing. This is similar to Cramer-Shoup projective hashing, except that instead of smoothness, which stipulates that the output of the hash function looks random on

no

instances, we require invertibility, which stipulates that the output of the hash function on

no

instances uniquely determine the hashing key, and moreover, that there is a trapdoor which allows us to efficiently recover the hashing key.

We show a simple construction of lossy trapdoor functions via dual projective hashing. Our construction encompasses almost all known constructions of lossy trapdoor functions, as given in the works of Peikert and Waters (STOC ’08) and Freeman et al. (PKC ’10).

We also provide a simple construction of deterministic encryption schemes secure with respect to hard-to-invert auxiliary input, under an additional assumption about the projection map. Our construction clarifies and encompasses all of the constructions given in the recent work of Brakerski and Segev (Crypto ’11). In addition, we obtain a new deterministic encryption scheme based on LWE.