Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems.
Brett Hemenway, Rafail Ostrovsky · 2009
In STOC ’08, Peikert and Waters introduced a powerful new primitive called Lossy Trapdoor Functions (LTDFs). Since their introduction, lossy trapdoor functions have found many uses in cryptography. In the work of Peikert and Waters, lossy trapdoor functions were used to give an efficient construction of a chosen-ciphertext secure (IND-CCA2) cryptosystem. Lossy trapdoor functions were then shown to imply deterministic encryption by Bellare, Fischlin, O’Neill and Ristenpart in CRYPTO ’08. In TCC ’09, Rosen and Segev showed that lossy trapdoor functions are correlated product secure, meaning that they remain one-way even when evaluated on correlated inputs. In their work, Peikert and Waters gave constructions of LTDFs from the Decisional Diffie-Hellman (DDH) assumption and lattice assumptions. Bellare et al., and Rosen and Segev also gave (identical) efficient constructions of LTDFs from Paillier’s Decisional Composite Residuosity (DCR) assumption. To date, these remain the only known constructions of lossy trapdoor functions. In this work we extend the notion of smooth hash proof systems as defined by Cramer and