International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Alon Rosen
Gil Segev
Download:
URL: http://eprint.iacr.org/2008/134
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.
BibTeX
@misc{eprint-2008-17811,
  title={Efficient Lossy Trapdoor Functions based on the Composite Residuosity Assumption},
  booktitle={IACR Eprint archive},
  keywords={foundations / lossy trapdoor functions, composite residuosity assumption},
  url={http://eprint.iacr.org/2008/134},
  note={ gil.segev@weizmann.ac.il 13964 received 26 Mar 2008, last revised 26 Mar 2008},
  author={Alon Rosen and Gil Segev},
  year=2008
}