Paper 2017/532

All-But-Many Lossy Trapdoor Functions from Lattices and Applications

Xavier Boyen and Qinyi Li


``All-but-many lossy trapdoor functions'' (ABM-LTF) are a powerful cryptographic primitive studied by Hofheinz (Eurocrypt 2012). ABM-LTFs are parametrised with tags: a lossy tag makes the function lossy; an injective tag makes the function injective, and invertible with a trapdoor. Existing ABM-LTFs rely on non-standard assumptions. Our first result is an ABM-LTF construction from lattices, based on the learning-with-errors (LWE) problem. Unlike the previous schemes which behaved as ``encrypted signatures'', the core of our construction is an ``encrypted, homomorphic-evaluation-friendly, weak pseudorandom function''. The weak pseudorandom function outputs matrices, where the lossy tags are preimages of the zero matrix, and the injective tags are preimages of random full-rank matrices. Our second result is a public-key system tightly secure against ``selective opening'' attacks, where an attacker gets many challenges and can ask to see the random bits of any of them. Following the steps of Hemenway et al. (Asiacrypt 2011) and Hofheinz (Eurocrypt 2012), our ABM-LTF gives the first lattice-based, compact public-key encryption (PKE) scheme that has indistinguishability against adaptive chosen-ciphertext and selective opening attacks (IND-SO-CCA2), with tight security, and whose public-key size and security reduction are independent of the number of decryption queries and ciphertext challenges. Meanwhile, this result provides an alternative solution to the problem of building pairing-free IND-CCA2 PKE schemes with tight security in the multi-challenge setting, which was firstly answered by Gay et al. (Eurocrypt 2016). Additionally, our ABM-LTF answers the open question of constructing all-but-many trapdoor function from lattices, first asked by Alperin-Sheriff and Peikert (PKC 2012).

Available format(s)
Publication info
Published by the IACR in CRYPTO 2017
all-but-many lossy trapdoor functionslatticeselective opening attacksCCA
Contact author(s)
qinyi li71 @ gmail com
2017-06-07: received
Short URL
Creative Commons Attribution


      author = {Xavier Boyen and Qinyi Li},
      title = {All-But-Many Lossy Trapdoor Functions from Lattices and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2017/532},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.