- 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.
Category / Keywords: public-key cryptography / Public-key encryption, lossy trapdoor functions, correlation-secure trapdoor functions Publication Info: full version of paper to appear in PKC 2010 Date: received 1 Dec 2009, last revised 24 May 2010 Contact author: dfreeman at cs stanford edu Available formats: PDF | BibTeX Citation Version: 20100525:002716 (All versions of this report) Discussion forum: Show discussion | Start new discussion