International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Efficient Lossy Trapdoor Functions based on the Composite Residuosity Assumption

Alon Rosen
Gil Segev
Search ePrint
Search Google
Abstract: Lossy trapdoor functions (Peikert and Waters, STOC '08) are an intriguing and powerful cryptographic primitive. Their main applications are simple and black-box constructions of chosen-ciphertext secure encryption, as well as collision-resistant hash functions and oblivious transfer. An appealing property of lossy trapdoor functions is the ability to realize them from a variety of number-theoretic assumptions, such as the hardness of the decisional Diffie-Hellman problem, and the worst-case hardness of lattice problems. In this short note we propose a new construction of lossy trapdoor functions based on the Damg{\aa}rd-Jurik encryption scheme (whose security relies on Paillier's decisional composite residuosity assumption). Our approach also yields a direct construction of all-but-one trapdoor functions, an important ingredient of the Peikert-Waters encryption scheme. The functions we propose enjoy short public descriptions, which in turn yield more efficient encryption schemes.
  title={Efficient Lossy Trapdoor Functions based on the Composite Residuosity Assumption},
  booktitle={IACR Eprint archive},
  keywords={foundations / lossy trapdoor functions, composite residuosity assumption},
  note={ 13964 received 26 Mar 2008, last revised 26 Mar 2008},
  author={Alon Rosen and Gil Segev},