**On the Lossiness of the Rabin Trapdoor Function**

*Yannick Seurin*

**Abstract: **Lossy trapdoor functions, introduced by Peikert and Waters (STOC~'08), are functions that can be generated in two indistinguishable ways: either the function is injective, and there is a trapdoor to invert it, or the function is lossy, meaning that the size of its range is strictly smaller than the size of its domain. Kakvi and Kiltz (EUROCRYPT 2012) proved that the Full Domain Hash signature scheme based on a lossy trapdoor function has a \emph{tight} security reduction from the lossiness of the trapdoor function. Since Kiltz, O'Neill, and Smith (CRYPTO 2010) showed that the RSA trapdoor function is lossy under the $\Phi$-Hiding assumption of Cachin, Micali, and Stadler (EUROCRYPT~'99), this implies that the RSA Full Domain Hash signature scheme has a \emph{tight} security reduction from the $\Phi$-Hiding assumption (for public exponents $e<N^{1/4}$). In this work, we consider the Rabin trapdoor function, \emph{i.e.} modular squaring over $\mathbb{Z}_{N}^*$. We show that when adequately restricting its domain (either to the set $\mathbb{QR}_{N}$ of quadratic residues, or to $(\mathbb{J}_{N})^+$, the set of positive integers $1\le x\le(N-1)/2$ with Jacobi symbol +1) the Rabin trapdoor function is lossy, the injective mode corresponding to Blum integers $N=pq$ with $p,q\equiv 3\bmod 4$, and the lossy mode corresponding to what we call pseudo-Blum integers $N=pq$ with $p,q\equiv 1 \bmod 4$. This lossiness result holds under a natural extension of the $\Phi$-Hiding assumption to the case $e=2$ that we call the 2-$\Phi/4$-Hiding assumption. We then use this result to prove that deterministic variants of Rabin-Williams Full Domain Hash signatures have a tight reduction from the 2-$\Phi$/4-Hiding assumption. We also show that these schemes are unlikely to have a tight reduction from the factorization problem by extending a previous ``meta-reduction'' result by Coron (EUROCRYPT 2002), later corrected by Kakvi and Kiltz (EUROCRYPT 2012). These two results therefore answer one of the main questions left open by Bernstein (EUROCRYPT 2008) in his work on Rabin-Williams signatures.

**Category / Keywords: **public-key cryptography / Rabin trapdoor function, lossy trapdoor function, Phi-Hiding assumption, provable security, Rabin-Williams signatures, meta-reduction

**Original Publication**** (with major differences): **IACR-PKC-2014
**DOI: **10.1007/978-3-642-54631-0_22

**Date: **received 5 May 2013, last revised 15 Apr 2014

**Contact author: **yannick seurin at m4x org

**Available format(s): **PDF | BibTeX Citation

**Note: **An abridged version of this paper appears in the proceedings of PKC 2014. This is the full version.

**Version: **20140415:160138 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]