Cryptology ePrint Archive: Report 2018/1183

Lossy Trapdoor Permutations with Improved Lossiness

Benedikt Auerbach and Eike Kiltz and Bertram Poettering and Stefan Schoenen

Abstract: 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.

Category / Keywords: foundations / lossy trapdoor functions, RSA, phi-hiding, index-independent domain

Original Publication (with minor differences): CT-RSA 2019

Date: received 4 Dec 2018

Contact author: bertram poettering at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20181205:144022 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]