Paper 2011/230
AllButMany Lossy Trapdoor Functions
Dennis Hofheinz
Abstract
We put forward a generalization of lossy trapdoor functions (LTFs). Namely, allbutmany lossy trapdoor functions (ABMLTFs) are LTFs that are parametrized with tags. Each tag can either be injective or lossy, which leads to an invertible or a lossy function. The interesting property of ABMLTFs is that it is possible to generate an arbitrary number of lossy tags by means of a special trapdoor, while it is not feasible to produce lossy tags without this trapdoor. Our definition and construction can be seen as generalizations of allbutone LTFs (due to Peikert and Waters) and allbutN LTFs (due to Hemenway et al.). However, to achieve ABMLTFs (and thus a number of lossy tags which is not bounded by any polynomial), we have to employ some new tricks. Concretely, we give two constructions that employ ``disguised'' variants of the Waters, resp. BonehBoyen signature schemes to make the generation of lossy tags hard without trapdoor. In a nutshell, lossy tags simply correspond to valid signatures. At the same time, tags are disguised (i.e., suitably blinded) to keep lossy tags indistinguishable from injective tags. ABMLTFs are useful in settings in which there are a polynomial number of adversarial challenges (e.g., challenge ciphertexts). Specifically, building on work by Hemenway et al., we show that ABMLTFs can be used to achieve selective opening security against chosenciphertext attacks. One of our ABMLTF constructions thus yields the first SOCCA secure encryption scheme with compact ciphertexts (O(1) group elements) whose efficiency does not depend on the number of challenges. Our second ABMLTF construction yields an INDCCA (and in fact SOCCA) secure encryption scheme whose security reduction is independent of the number of challenges and decryption queries.
Note: Update (20110729): rearranged, fixed a small bug in proof of DCRbased construction, fixed typos. Update (20111010): improved lossiness analysis of DCRbased construction. (Lossiness actually already follows in rings Z_{N^s} for s>=3.) Update (20111230): incorporated referee comments. Update (20130318): Closed technical gap in discussion of SIMSOCCA security. (Previous description of Opener algorithm was much too oversimplified.) Update (20131029): added missing grant information. Update (20170404): corrected flaw in PKE construction and proof.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2012
 DOI
 10.1007/9783642290114_14
 Keywords
 lossy trapdoor functionspublickey encryptionselective opening attacks
 Contact author(s)
 Dennis Hofheinz @ kit edu
 History
 20170404: last of 7 revisions
 20110517: received
 See all versions
 Short URL
 https://ia.cr/2011/230
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/230, author = {Dennis Hofheinz}, title = {AllButMany Lossy Trapdoor Functions}, howpublished = {Cryptology ePrint Archive, Paper 2011/230}, year = {2011}, doi = {10.1007/9783642290114_14}, note = {\url{https://eprint.iacr.org/2011/230}}, url = {https://eprint.iacr.org/2011/230} }