Paper 2018/1183

Lossy Trapdoor Permutations with Improved Lossiness

Benedikt Auerbach, Eike Kiltz, Bertram Poettering, and Stefan Schoenen


Lossy trapdoor functions (Peikert and Waters, STOC 2008 and SIAM J. Computing 2011) imply, via black-box transformations, a number of interesting cryptographic primitives, including chosen-ciphertext secure public-key encryption. Kiltz, O'Neill, and Smith (CRYPTO 2010) showed that the RSA trapdoor permutation is lossy under the Phi-hiding assumption, but syntactically it is not a lossy trapdoor function since it acts on Z_N and not on strings. Using a domain extension technique by Freeman et al. (PKC 2010 and J. Cryptology 2013) it can be extended to a lossy trapdoor permutation, but with considerably reduced lossiness. In this work we give new constructions of lossy trapdoor permutations from the Phi-hiding assumption, the quadratic residuosity assumption, and the decisional composite residuosity assumption, all with improved lossiness. Furthermore, we propose the first all-but-one lossy trapdoor permutation from the Phi-hiding assumption. A technical vehicle used for achieving this is a novel transform that converts trapdoor functions with index-dependent domain into trapdoor functions with fixed domain.

Available format(s)
Publication info
Published elsewhere. Minor revision.CT-RSA 2019
lossy trapdoor functionsRSAphi-hidingindex-independent domain
Contact author(s)
bertram poettering @ rhul ac uk
2018-12-05: received
Short URL
Creative Commons Attribution


      author = {Benedikt Auerbach and Eike Kiltz and Bertram Poettering and Stefan Schoenen},
      title = {Lossy Trapdoor Permutations with Improved Lossiness},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1183},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.