Paper 2009/590

More Constructions of Lossy and Correlation-Secure Trapdoor Functions

David Mandell Freeman, Oded Goldreich, Eike Kiltz, Alon Rosen, and Gil Segev


We propose new and improved instantiations of lossy trapdoor functions (Peikert and Waters, STOC '08), and correlation-secure trapdoor functions (Rosen and Segev, TCC '09). Our constructions widen the set of number-theoretic assumptions upon which these primitives can be based, and are summarized as follows: - Lossy trapdoor functions based on the quadratic residuosity assumption. Our construction relies on modular squaring, and whereas previous such constructions were based on seemingly stronger assumptions, we present the first construction that is based solely on the quadratic residuosity assumption. We also present a generalization to higher order power residues. - Lossy trapdoor functions based on the composite residuosity assumption. Our construction guarantees essentially any required amount of lossiness, where at the same time the functions are more efficient than the matrix-based approach of Peikert and Waters. - Lossy trapdoor functions based on the $d$-Linear assumption. Our construction both simplifies the DDH-based construction of Peikert and Waters, and admits a generalization to the whole family of $d$-Linear assumptions without any loss of efficiency. - Correlation-secure trapdoor functions related to the hardness of syndrome decoding.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. full version of paper to appear in PKC 2010
Public-key encryptionlossy trapdoor functionscorrelation-secure trapdoor functions
Contact author(s)
dfreeman @ cs stanford edu
2010-05-25: revised
2009-12-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Mandell Freeman and Oded Goldreich and Eike Kiltz and Alon Rosen and Gil Segev},
      title = {More Constructions of Lossy and Correlation-Secure Trapdoor Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2009/590},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.