Lossy Trapdoor Functions (LTFs) were introduced by Peikert and Waters in STOC '08 and since then have found many applications and have proven to be an extremely useful and versatile cryptographic primitive.
Lossy trapdoor functions were used to build the first injective trapdoor functions based on DDH, the first IND-CCA cryptosystems based on lattice assumptions, and they are known to imply deterministic encryption, collision resistant hash-functions, oblivious transfer and a host of other important primitives.
While LTFs can be instantiated under most known cryptographic hardness assumptions, no constructions until today existed based on generic
cryptographic primitives. In this work, we show that any Homomorphic Smooth Hash Proof System, introduced by Cramer and Shoup
in EUROCRYPT '02, can be used to construct LTFs. In addition to providing a connection between two important cryptographic primitives -- our construction implies the first construction of LTFs based on the QR assumption.

Smooth Hash Proof Systems (SHPs) can be seen as a generalization of the DDH assumption, yet can be built on other cryptographic assumptions, such as the DCR or QR assumptions.
Yet, until today, a ``translation'' of results proven secure under DDH to results under DCR or QR has always been fraught with difficulties.
Thus, as our second goal of this paper, we ask the following question: is it possible to streamline such translations from DDH to QR and other primitives?
Our second result formally provides this connection. More specifically, we define an Extended Decisional Diffie Hellman (EDDH) assumption, which is a simple and natural generalization of DDH.
We show that EDDH can be instantiated under both the DCR and QR assumptions. This gives a much simpler
connection between the DDH and the DCR and QR assumptions and provides an easy way to translate proofs from DDH to DCR or QR.
That is, the advantage of the EDDH assumption is that most schemes (including LTFs) proven secure under the DDH assumption can easily be instantiated under the DCR and QR assumptions with almost no change to their proofs of security.

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 Boldyreva, Fehr and O'Neill 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.
Boldyreva, Fehr and O'Neill, and Rosen and Segev also gave (identical) efficient constructions of LTDFs from Paillier's Decisional Composite Residuosity (DCR) assumption.
The concurrent, independent work of Freeman et al., gives constructions of LTDFs from the $d$-linear assumption, and slightly lossy trapdoor functions based on the Quadratic Residuosity (QR) 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 Shoup in Eurocrypt '02, to include an additional homomorphic property.
We call this primitive smooth homomorphic hash proof systems. We show that smooth homomorphic projective hash proof systems include all Diverse Group Systems as defined by Cramer and Shoup. Using this definition, we show that

Smooth homomorphic hash proof systems imply LTDFs.

Diverse group systems as defined in [CS02] imply LTDFs. These are the first known generic constructions of LTDFs.

Applying our generic construction the specific constructions of smooth hash proof systems given by Cramer and Shoup, we obtain the first construction of fully lossy trapdoor functions from the quadratic residuosity (QR) assumption. We also obtain a novel construction of LTDFs from Paillier's decisional composite residuosity (DCR) assumption.

Applying our results to the results of Boldyreva, Fehr and O'Neill. we obtain a construction of deterministic encryption from smooth homomorphic hash proof systems.

Applying our results to the results of Rosen and Segev, we obtain a construction of correlated product secure functions from smooth homomorphic hash proof systems.

Applying the black-box separation results of Rosen and Segev, we show that there is a black-box separation between smooth homomorphic hash proof systems and one-way trapdoor permutations.

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 Shoup in Eurocrypt '02, to include an additional homomorphic property. We call this primitive smooth homomorphic hash proof systems. We show that smooth homomorphic projective hash proof systems include all Diverse Group Systems as defined by Cramer and Shoup. Using this definition, we show that

Smooth homomorphic hash proof systems imply LTDFs.

Diverse group systems as defined in [CS02] imply LTDFs. These are the first known generic constructions of LTDFs.

Applying our generic construction the specific constructions of smooth hash proof systems given by Cramer and Shoup, we obtain the first construction of LTDFs from the quadratic residuosity (QR) assumption. We also obtain a novel construction of LTDFs from Paillier's decisional composite residuosity (DCR) assumption.

Applying our results to the results of Bellare et al. we obtain a construction of deterministic encryption from smooth homomorphic hash proof systems.

Applying our results to the results of Rosen and Segev, we obtain a construction of correlated product secure functions from smooth homomorphic hash proof systems. This provides the first construction of correlated product secure functions from the QR assumption.

Applying the black-box separation results of Rosen and Segev, we show that there is a black-box separation between smooth homomorphic hash proof systems and one-way trapdoor permutations.

While homomorphic encryption can never be IND-CCA2 secure, we notice that smooth homomorphic hash proof systems yield a homomorphic IND-CCA1 secure cryptosystem.