Our definition and construction can be seen as generalizations of all-but-one LTFs (due to Peikert and Waters) and all-but-N LTFs (due to Hemenway et al.). However, to achieve ABM-LTFs (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. Boneh-Boyen 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.
ABM-LTFs 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 ABM-LTFs can be used to achieve selective opening security against chosen-ciphertext attacks. One of our ABM-LTF constructions thus yields the first SO-CCA secure encryption scheme with compact ciphertexts (O(1) group elements) whose efficiency does not depend on the number of challenges. Our second ABM-LTF construction yields an IND-CCA (and in fact SO-CCA) secure encryption scheme whose security reduction is independent of the number of challenges and decryption queries.
Category / Keywords: public-key cryptography / lossy trapdoor functions, public-key encryption, selective opening attacks Date: received 10 May 2011, last revised 18 Mar 2013 Contact author: Dennis Hofheinz at kit edu Available formats: PDF | BibTeX Citation Note: Update (2011-07-29): rearranged, fixed a small bug in proof of DCR-based construction, fixed typos. Update (2011-10-10): improved lossiness analysis of DCR-based construction. (Lossiness actually already follows in rings Z_{N^s} for s>=3.) Update (2011-12-30): incorporated referee comments. Update (2013-03-18): Closed technical gap in discussion of SIM-SO-CCA security. (Previous description of Opener algorithm was much too oversimplified.) Version: 20130318:094727 (All versions of this report) Discussion forum: Show discussion | Start new discussion