More Constructions of Lossy and Correlation-Secure Trapdoor Functions
Webpage for a paper by Freeman, Goldreich, Kiltz, Rosen, and 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.
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.
Material available on-line
- Version for
either Oded Goldreich's homepage.
or general list of papers.