Lossy Trapdoor Permutations with Improved Lossiness

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 $\mathbb {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 to trapdoor functions with fixed domain.

The full version of this article can be found in the IACR eprint archive as article 2018/1183 at https://eprint.iacr.org/2018/1183.

1 Introduction

Lossy Trapdoor Functions. Lossy trapdoor functions (LTFs) are like classic (one-way) trapdoor functions but with strengthened security properties. Instances of an LTF can be created in two computationally indistinguishable ways: An instance generated with the standard key-generation algorithm describes an injective function that can be efficiently inverted using the trapdoor; and an instance generated with the lossy key-generation algorithm describes a “lossy” function, meaning its range is considerably smaller than its domain. The lossiness factor $L \ge 1$, defined as the ratio of the cardinalities of domain and range, measures the LTF’s quality.¹ The larger the lossiness factor, the better the cryptographic properties of the LTF. In case the non-lossy instances define permutations, we will refer to the whole object as a lossy trapdoor permutation (LTP).

Lossy trapdoor functions were introduced by Peikert and Waters [21, 22] who showed that they imply (via black-box constructions) fundamental cryptographic primitives such as classic trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen-ciphertext secure public-key encryption. Furthermore, LTFs have found various other applications, including deterministic public-key encryption [7], OAEP-based public-key encryption [17], “hedged” public-key encryption for protecting against bad randomness [2, 4], security against selective opening attacks [5], efficient non-interactive string commitments [20], threshold encryption [26], correlated-product secure trapdoor functions [24], adaptive trapdoor functions [16], and many others.

LTFs with index-dependent domains. In the original definition by Peikert and Waters, all instances of an LTF are defined over the same fixed domain $\{0,1\}^k$. That is, the domain is independent of the specific index output by the key-generation algorithm (‘index’ is used synonym with the public key describing the instance). Subsequently, LTFs were generalized to LTFs with index-dependent domains [11] where the domain may depend on the function’s index. To illustrate index-dependent domains, consider the well-known RSA trapdoor permutation $f_\textsc {RSA}:\mathbb {Z}_N \rightarrow \mathbb {Z}_N;\;x \mapsto x^e \bmod N$. Its index consists of a modulus $N=pq$ (of fixed bit-length k) and an exponent e; its domain is $\mathbb {Z}_N$, hence it is index-dependent. For $e \le 2^{k/4}$, permutation $f_\textsc {RSA}$ was proved to be lossy [17] with lossiness factor $L=e$ under the Phi-hiding assumption [9].² Similarly, constructions of trapdoor functions based on quadratic residuosity or Paillier’s assumption yield LTPs with index-dependent domains [10, 11].

As pointed out in [11], LTFs with index-dependent domains do not seem to be sufficient for constructing correlated-product secure trapdoor functions [24] or chosen-ciphertext secure public-key encryption [21]. The difficulty is that in these applications a fixed value has to be evaluated on many independently generated instances of the trapdoor function. It is therefore crucial that the domains are the same for all these instances. Furthermore, most constructions of deterministic encryption schemes (e.g., [3, 7, 8, 18, 23]) assume message distributions that do not depend on the public key and hence cannot be constructed from LTFs with index-dependent domains. Fortunately, however, LTFs with index-dependent domains turn out to be sufficient for many other applications.

In [11, Sect. 3.2], a general domain-extension technique was (implicitly) proposed that transforms an LTF $f:\mathbb {Z}_N \rightarrow \mathbb {Z}_N$ with index-dependent domain $\mathbb {Z}_N$ (with $2^{k-1} \le N < 2^k$) into an LTF $f_\mathrm {de}:\{0,1\}^k \rightarrow \{0,1\}^k$ with index-independent domain $\{0,1\}^k$ by defining

$$\begin{aligned} f_\mathrm {de}(x) := {\left\{ \begin{array}{ll} f(x) &{} 0 \le x< N\\ x &{} N \le x < 2^k \end{array}\right. }. \end{aligned}$$

(1)

However, this transform does bad in preserving lossiness, in particular in the case where N is close to $2^{k-1}$. Indeed, if the lossiness factor of f is L then the lossiness factor of $f_\mathrm {de}$ is about $L_\mathrm {de}=2 \cdot L/(L+1) < 2$. Note that such a small lossiness factor does not even imply one-wayness, i.e., the resulting LTF is, taken by itself, essentially useless. (Based on a result by Mol and Yilek [19] it can still be used to build IND-CCA secure encryption, but with considerably worse efficiency.) In [11, Sect. 4.4] also an alternative domain-extension technique was sketched that can be used to construct an LTF $f_\mathrm {de}$ with index-independent domain $\{0,1\}^{k + \log (L)}$ and lossiness factor $L_\mathrm {de}\approx L$. Here, every evaluation of $f_\mathrm {de}$ requires $\log (L)$ many applications of f. For interesting values of L this is again prohibitively inefficient.

All-but-one Lossy Trapdoor Functions. All-but-one lossy trapdoor functions (ABO-LTFs) are a generalization of LTFs. An ABO-LTF is associated with a set $\mathcal {B}r$ of branches. The corresponding generator algorithm is invoked on input a target branch $br ^* \in \mathcal {B}r$ and outputs a trapdoor and a family of functions $(f_{ br })_{ br \in \mathcal {B}r}$ with the property that $f_{ br }$ is injective for all $br \ne br ^*$ (and can be inverted using the trapdoor), but function $f_{ br ^*}$ is lossy. Moreover, the lossy branch is hidden (computationally) by the description of the function family. ABO-LTFs with just two branches are equivalent to LTFs, and, similarly to LTFs, ABO-LTFs can have index-independent or index-dependent domains. Using the techniques of Peikert and Waters [21] an ABO-LTF with exponentially large branch set can be constructed from any LTF, but the latter is required to have a sufficiently large lossiness factor L. (This transformation also works for LTFs with index-dependent domains.) Many of the mentioned applications of LTFs require in fact ABO-LTFs.

Known LTFs and ABO-LTFs. Roughly speaking, cryptographic assumptions are typically rooted in one out of three different environments: over cyclic groups, over lattices, or over RSA moduli. Over cyclic groups as well as over lattices, constructions of LTFs and ABO-LTFs are known [21]. They have index-independent domain and can be instantiated to have an arbitrarily large lossiness factor L. In the RSA setting, the situation is different.³ There are constructions known from the quadratic residuosity assumption [11], Paillier’s decisional composite residuosity assumption [11], and from the Phi-hiding assumption [9, 17] (for a fourth one, see below). All constructions have index-dependent domains (the transform sketched above fixes this, but the results are essentially useless due to the small lossiness factor). Unfortunately, for the constructions based on the Phi-hiding assumption and the quadratic residuosity assumption the lossiness factor cannot be made arbitrarily large and, in particular, it is not sufficient to construct efficient ABO-TDFs. However, both an index-independent LTF and an ABO-LTF based on the decisional composite residuosity assumption are known [11].

As it is quite general, we describe in more detail the technique from [21] for building LTFs. Starting with an additively homomorphic encryption scheme, function indices correspond with element-wise encryptions of the identity matrix. The range of the construction consists of vectors of ciphertexts. If ElGamal encryption is used to instantiate the encryption scheme one obtains an LTF with security based on DDH. Constructions of LTFs and ABO-LTFs in the same spirit, but that achieve smaller index sizes and output lengths, are proposed in [6, 15]. Using a generalization of the Goldwasser–Micali homomorphic encryption scheme [12] allows this construction, in contrast to processing the LTF input bit-by-bit, to consider input values sequences of numbers of some fixed bit-length. The construction’s security is based not only on the DDH assumption but also on the quadratic residuosity assumption for a restricted class of RSA moduli and an additional non-standard assumption, which can be removed by making further restrictions on the modulus.

While the described constructions from [6, 15, 21] achieve high lossiness factors, a common disadvantage is that their indices are ciphertext matrices and the function ranges are ciphertext vectors, and thus quite large. Further, [6, 15] require strong hardness assumptions in a quite restricted RSA setting.

As shown in [27], collision-resistant hash functions, CPA- and CCA-secure public-key encryption, and deterministic encryption can be constructed from adversary-dependent lossy trapdoor functions and ABO-LTFs, a variant of LTFs and ABO-LTFs with relaxed security conditions. The authors give index-independent constructions of these primitives from the factoring assumption for semi-smooth RSA moduli. The proposed instantiations achieve high lossiness factors and have compact indices and ciphertexts of roughly the size of an RSA modulus.

1.1 Our Results

In this work we propose a new general domain-extension transformation that can be used to transform index-dependent LTPs into index-independent LTPs without sacrificing much lossiness. Concretely, our transformation decreases the lossiness factor by at most by a factor of 2. For the special cases of the LTP based on the Phi-hiding assumption and the LTP from [11] based on the quadratic residuosity assumption, a more refined analysis even shows that the lossiness factor effectively stays invariant. That is, ultimately we construct an LTP with index-independent domain $\{0,1\}^k$ and lossiness factor as large as $L = 2^{k/4}$ from the Phi-hiding assumption, and an LTP with index-independent domain $\{0,1\}^k$ and lossiness factor 2 from the quadratic residuosity assumption. In comparison, the index-independent variants obtained via the transform implicitly given in [11] would result in lossiness factors of 2 and 4/3 respectively. Furthermore, in the full version [1] we apply our transformation to the index-dependent LTF and ABO-LTF of [11] based on the decisional composite residuosity assumption. As a result we obtain index-independent variants with slightly larger domain and lossiness factor than the index-independent constructions given in [11]. Finally we construct the first ABO-LTP from (a variant of) the Phi-hiding assumption. We highlight that in particular our Phi-hiding based construction has particularly compact indices (of the size of an RSA modulus) and range elements.

Domain extension for LTFs with index-dependent domains. We explain our domain extension technique for the special case of a LTF $f :\mathbb {Z}_{N} \rightarrow \mathbb {Z}_{N}$ with index-dependent domain $\mathbb {Z}_{N}$ (with $2^{k-1} \le N < 2^k$). We use a two-round construction in the spirit of Hayashi, Okamoto and Tanaka [13], who used a similar construction to extend the domain of the RSA one-way permutation. We define the function

$$\begin{aligned} f'_\mathrm {de}:\{0,1\}^k \rightarrow \{0,1\}^k, \quad f'_\mathrm {de}(x) := f_\mathrm {de}(\pi (f_\mathrm {de}(x))), \end{aligned}$$

(2)

where $f_\mathrm {de}$ is defined in (1) and permutation $\pi :\{0,1\}^k \rightarrow \{0,1\}^k$ is given as $\pi (x) = x-(N-1) \bmod 2^k$. The intuition of this construction is that the LTF f is applied to every $x \in \{0,1\}^k$ at least once. Indeed, if f is one-way, then $f'_\mathrm {de}$ defined in (2) is one-way [13]. Our first main result states that if f is a LTF with index-dependent domain and lossiness factor L, then $f'_\mathrm {de}$ is a LTF with index-independent domain $\{0,1\}^k$ and lossiness factor $L'_\mathrm {de}=L/2$.

In the case of the RSA-based LTF $f_\textsc {RSA}$ we can even prove that the lossiness factor of $f'_\mathrm {de}$ is completely preserved, i.e. $L'_\mathrm {de}=L$. Under the Phi-hiding assumption this gives us a LTP with index-independent domain and lossiness factor as large as $k^{1/4}$. We also show how to obtain index-independent LTPs from the quadratic residuosity and the decisional composite residuosity assumption (in the full version [1]), which have a larger lossiness factor than the constructions of [11].

An ABO-LTP in the RSA setting. Our second main result is the construction of an ABO-LTP with index-dependent domain from the Phi-hiding assumption. Our generic domain extension technique also works for ABO-LTFs, so it can be transformed into an ABO-LTP with index-independent domain $\{0,1\}^k$.

Our construction essentially follows [16, Sect. 5.2] who construct an adaptive trapdoor function from the instance-independent RSA assumption, a decisional version of the RSA assumption. It makes use of a new primitive that we call prime family generator (PFG), an abstraction that may be of independent interest. An instance of a PFG indicates a fixed sequence of (distinct) primes $e_{1}, \ldots , e_{2^n}$ of some specified bit-length $l \ge n/2$. A specific programmability feature allows embedding any given prime at any given position, where the position remains hidden (computationally) from the instance. We give an information-theoretic construction of a PFG that is based on work by Cachin, Micali, and Stadler [9]. A PFG instance consists of $l^2$ bits and we leave it as an open problem to construct a (computationally secure) PFG with improved parameters, for example by using the PRF-based construction as implicitly in the work of Hohenberger and Waters [14].

Given a PFG we define our new RSA-setting based ABO-LTP for a branch $br \in \{0,1\}^n$ as

$$ f_{ br }:\mathbb {Z}_N \rightarrow \mathbb {Z}_N; \quad f_{ br }(x):=x^{e_{ br }}, $$

where $e_{ br }$ is the $br$-th prime of the PFG prime sequence. To prove the ABO-LTF security property we first use the Phi-hiding assumption to change the distribution of the RSA modulus N to satisfy $e^* \mid \varphi _{N}$, for some random prime $e^*$. Next, we use the PFG’s programmability feature to make sure that $e_{ br ^*}=e^*$, meaning the function $f_{ br }(\cdot )$ is injective if $br \ne br ^*$ and $e^*$-to-1 if $br = br ^*$.⁴

Applications. Our constructions of index-independent LTFs and LTPs over domain $\{0,1\}^k$ (and our techniques to build them) are mostly of theoretical interest with potential future applications. Whereas with our current knowledge we are not able to present a killer application, let us still discuss possible minor applications. Most importantly, correlated-product secure trapdoor functions [24] and IND-CCA secure public-key encryption [21] can be constructed from index-independent LTFs over domain $\{0,1\}^k$. Both require the lossiness factor L to be larger than $2^{k/2}$, whereas our construction based on the Phi-hiding assumption cannot go beyond $L=2^{k/4}$. One can still apply the amplification result by Mol and Yilek [19] to build IND-CCA secure encryption. The efficiency loss will be smaller than with the previous constructions from the Phi-hiding assumption (having lossiness factor $L \approx 2$).

2 Preliminaries

2.1 Notation

If $a,b\in \mathbb {N},a<b,$ we use notations $[{a}{\,..\,}{b}]=\{a,\ldots ,b\}$, $[{b}]=[{1}{\,..\,}{b}]$, $\llbracket {a}{\,..\,}{b}\rrbracket =[{a}{\,..\,}{(b-1)}]$, and $\llbracket {b}\rrbracket =[{0}{\,..\,}{(b-1)}]$. We say $m\in \mathbb {N}$ is an l-bit number if $m\in \llbracket {2^{l-1}}{\,..\,}{2^l}\rrbracket$. For any set $M\subseteq \mathbb {N}$ we denote with $M_l:=M\cap \llbracket {2^{l-1}}{\,..\,}{2^l}\rrbracket$ its subset of l-bit elements. We write $\{0,1\}^l$ for the set of strings of length l and denote the bit-wise exclusive-or operation of same-length strings with $\oplus$. For all $l\in \mathbb {N}$ we assume a canonic bijection $\#:\llbracket {2^l}\rrbracket \rightarrow \{0,1\}^l$ and correspondingly denote with $\#x$ the interpretation of an element x of $\llbracket {2^l}\rrbracket$ as a string in $\{0,1\}^l$. The support of a randomized algorithm $\mathrm {A}$ on input x, i.e., the set of values it outputs with non-zero probability, is denoted by $[\mathrm {A}(x)]$. We annotate a disjoint union with .

2.2 (All-But-One) Lossy Trapdoor Permutations

We recall the concepts of lossy trapdoor functions and all-but-one lossy trapdoor functions as introduced by Peikert and Waters [21]. More precisely, we slightly deviate from their formalizations by restricting attention to permutations, supporting index-dependent domains [11], and considering permutations that are not perfectly correct.

Lossy Trapdoor Permutations. Let $\mathcal {X}$ be a domain, ${\mathcal {I}d}$ a universe of function indices, and for each index $id \in {\mathcal {I}d}$ let $\mathcal {X}( id )\subseteq \mathcal {X}$ be a specific (sub)domain. A lossy trapdoor permutation (LTP) for $\mathcal {X},{\mathcal {I}d}$ then consists of a trapdoor space ${\mathcal {T}d}$ and three efficient algorithms $\mathrm {F}=(\mathrm {FGen},\mathrm {FEv},\mathrm {FInv})$ for which the following hold: Algorithm

is a randomized instance generator. Its input $b\in \{0,1\}$ specifies whether the generated instance is injective ($b=1$) or lossy ($b=0$). We require $[\mathrm {FGen}(1)]\subseteq {\mathcal {I}d}\times {\mathcal {T}d}$ and $[\mathrm {FGen}(0)]\subseteq {\mathcal {I}d}\times \{\bot \}$. In injective mode, if $( id , td )\in [\mathrm {FGen}(1)]$, we refer to $td$ as the trapdoor corresponding to $id$. Algorithms

$$ {\mathcal {I}d}\times \mathcal {X}\rightarrow \mathrm {FEv}\rightarrow \mathcal {X}\qquad \text {and}\qquad {\mathcal {T}d}\times \mathcal {X}\rightarrow \mathrm {FInv}\rightarrow \mathcal {X}$$

are the evaluation and inversion algorithms, respectively. We require it hold $\mathrm {FEv}( id ,x)\in \mathcal {X}( id )$ for all $id \in {\mathcal {I}d}$ and $x\in \mathcal {X}( id )$. For correctness we further require that in injective mode the mapping $\mathcal {X}(id)\rightarrow \mathcal {X}(id)$ induced by $\mathrm {FEv}$ can be effectively inverted on (almost) all values if the trapdoor is known. Formally, we say that $\mathrm {F}$ is $(1-\epsilon _1)$-correct if

$$ \Pr [( id , td )\leftarrow _{\scriptscriptstyle \$}\mathrm {FGen}(1),x\leftarrow _{\scriptscriptstyle \$}\mathcal {X}( id ),y\leftarrow \mathrm {FEv}( id ,x):\mathrm {FInv}( td ,y)\ne x]\le \epsilon _1. $$

This means that for $\epsilon _1>0$ the function implemented by $\mathrm {FEv}( id ,\cdot )$ might technically not be a permutation. For security we require (a) that $\mathrm {FEv}$ lose information in lossy mode, and (b) that injective mode and lossy mode be indistinguishable. Concerning (a), we say the LTP is L-lossy if for all $( id ,\bot )\in [\mathrm {FGen}(0)]$ we have $|\mathrm {FEv}( id ,\mathcal {X}( id ))|\le |\mathcal {X}( id )|/L$.⁵ Concerning (b), we say the LTP is $(\tau ,\epsilon _2)$-indistinguishable if for all $\tau$-time distinguishers $\mathcal {D}$ we have

$$ \left|\begin{array}{l} \Pr [( id , td )\leftarrow _{\scriptscriptstyle \$}\mathrm {FGen}(1):\mathcal {D}( id )\Rightarrow 1] \\ \quad - \Pr [( id ,\bot )\leftarrow _{\scriptscriptstyle \$}\mathrm {FGen}(0):\mathcal {D}( id )\Rightarrow 1] \end{array} \right|\le \epsilon _2. $$

All-But-One Lossy Trapdoor Permutations. All-but-one LTPs are a generalization of LTPs where in addition to the universe of function indices there is a universe of branches; function $\mathrm {FEv}$ is lossy for one branch and injective for all others. In particular, a (regular) LTP is equivalent to an all-but-one LTP if the branch space consists of precisely two elements.

Let $\mathcal {B}r$ be a branch space, $\mathcal {X}$ a domain, ${\mathcal {I}d}$ a universe of function indices, and for each index $id \in {\mathcal {I}d}$ let $\mathcal {X}( id )\subseteq \mathcal {X}$ be a specific (sub)domain. An all-but-one lossy trapdoor permutation (ABO-LTP) for $\mathcal {B}r,\mathcal {X},{\mathcal {I}d}$ then consists of a trapdoor space ${\mathcal {T}d}$ and three efficient algorithms $\mathrm {A}=(\mathrm {FGen},\mathrm {FEv},\mathrm {FInv})$ for which the following hold: Algorithm

$$ \mathcal {B}r\rightarrow \mathrm {FGen}\rightarrow _{\scriptscriptstyle \$}{\mathcal {I}d}\times {\mathcal {T}d}$$

is an instance generator such that the invocation $( id , td )\leftarrow _{\scriptscriptstyle \$}\mathrm {FGen}( br )$, for a branch $br$, generates a function index $id$ with trapdoor $td$. Similarly as for LTPs, algorithms

$$ \mathcal {B}r\times {\mathcal {I}d}\times \mathcal {X}\rightarrow \mathrm {FEv}\rightarrow \mathcal {X}\qquad \text {and}\qquad \mathcal {B}r\times {\mathcal {T}d}\times \mathcal {X}\rightarrow \mathrm {FInv}\rightarrow \mathcal {X}$$

are the evaluation and inversion algorithms. We require that for all $br ,br^*\in \mathcal {B}r$ and $( id , td )\in [\mathrm {FGen}( br ^*)]$ and $x\in \mathcal {X}( id )$, if $y=\mathrm {FEv}( br , id ,x)$ then $y\in \mathcal {X}( id )$. We further require that the mappings $\mathcal {X}(id)\rightarrow \mathcal {X}(id)$ induced by $\mathrm {FEv}$ on all branches with exception of $br ^*$ can be effectively inverted (on almost all values) if the trapdoor is known. Formally, we say that $\mathrm {A}$ is $(1-\epsilon _1)$-correct if for all $br , br ^*\in \mathcal {B}r$, $br \ne br ^*$, we have

$$ \Pr \left[ ( id , td )\leftarrow _{\scriptscriptstyle \$}\mathrm {FGen}( br ^*),x\leftarrow _{\scriptscriptstyle \$}\mathcal {X}( id ):\mathrm {FInv}\left( br , td ,\mathrm {FEv}( br , id ,x)\right) \ne x\right] \le \epsilon _1. $$

For security we require that $\mathrm {FEv}$ lose information on its lossy branch, i.e., the branch $br ^*$ the instance was generated for. Further, it shall be unfeasible to identify the lossy branch. Concretely, we say the ABO-LTP is L-lossy if for all $br ^*\in \mathcal {B}r$ and $( id , td )\in [\mathrm {FGen}( br ^*)]$ we have $|\mathrm {FEv}( br ^*, id ,\mathcal {X}( id ))|\le |\mathcal {X}( id )|/L$, and we say it is $(\tau ,\epsilon _2)$-indistinguishable if for all $br _0, br _1\in \mathcal {B}r$ and all $\tau$-time distinguishers $\mathcal {D}$ (that may depend on $br _0, br _1$) we have

$$ \left|\begin{array}{l} \Pr [( id , td )\leftarrow _{\scriptscriptstyle \$}\mathrm {FGen}( br _0):\mathcal {D}( id )\Rightarrow 1] \\ \quad - \Pr [( id , td )\leftarrow _{\scriptscriptstyle \$}\mathrm {FGen}( br _1):\mathcal {D}( id )\Rightarrow 1] \end{array} \right|\le \epsilon _2. $$

Index-Dependent vs. Index-Independent LTPs/ABO-LTPs. In the above definition of LTPs, the domain $\mathcal {X}( id )\subseteq \mathcal {X}$ on which $\mathrm {FEv}( id ,\cdot )$ operates may depend on function index $id$. We say the LTP is index-independent if this restriction does not exist, i.e., if $\mathcal {X}( id )=\mathcal {X}$ for all $id$. For ABO-LTPs we say correspondingly. In later sections we show how to generically transform an index-dependent trapdoor permutation into an index-independent one.

2.3 Number Theoretic Assumptions

For $a,b\in \mathbb {N},a\ne 0,$ we write $a\mid b$ if a divides b, i.e., if there exists $d\in \mathbb {N}$ s.t. $b=da$. We further write $a\mathrel {\mid _1}b$ if a divides b exactly once, i.e., if $a\mid b\wedge a^2\not \mid b$. The greatest common divisor of a, b is denoted $\gcd (a,b)$. We denote the set of prime numbers with $\mathcal {P}$. Recall from Sect. 2.1 that $\mathbb {N}_l$ and $\mathcal {P}_l$ denote the sets of l-bit natural and prime numbers, respectively.

If k is an even number, a product $N=pq$ is a k-bit RSA modulus if $N\in \mathbb {N}_k$, $p,q\in \mathcal {P}_{k/2}$, and $p\ne q$. The order of the multiplicative group $\mathbb {Z}_{N}^*$ is $\varphi _N:=\varphi (N)=(p-1)(q-1)$. We denote the space of k-bit RSA moduli with $\mathcal {R}\mathcal {S}\mathcal {A}_k$. If we want to restrict attention to k-bit RSA moduli that fulfill a specific condition C, we write $\mathcal {R}\mathcal {S}\mathcal {A}_k[C]$. The set of k-bit Blum integers, i.e., RSA moduli where the prime factors satisfy $p\equiv q\equiv 3\bmod 4$, is denoted by $\mathcal {B}\mathcal {R}\mathcal {S}\mathcal {A}_k:=\mathcal {R}\mathcal {S}\mathcal {A}_k[p\equiv q\equiv 3\bmod 4]$.

Phi-Hiding Assumption. In standard RSA encryption, public exponent e is chosen constraint to $e\not \mid \varphi _N$ so that the mapping $x\mapsto x^e$ is a bijection. Some applications in addition use exponents $e\mathrel {\mid _1}\varphi _N$ and require that it be hard, given (N, e), to decide whether $e\mathrel {\mid _1}\varphi _N$ or $e\not \mid \varphi _N$. Roughly, the Phi-hiding assumption [9, 17] for a set of primes $\mathcal {E}$ says that $N\in \mathcal {R}\mathcal {S}\mathcal {A}_k$ can be generated such that for uniformly picked $e\in \mathcal {E}$ the cases $N\in \mathcal {R}\mathcal {S}\mathcal {A}_k[e\not \mid \varphi _N]$ and $N\in \mathcal {R}\mathcal {S}\mathcal {A}_k[e\mathrel {\mid _1}\varphi _N]$ are computationally indistinguishable. Formally, we say that the $(\tau ,\epsilon )$-Phi-hiding assumption holds for $(k,\mathcal {E})$ if for all $\tau$-time adversaries $\mathcal {D}$ we have

$$ \left|\begin{array}{l} \Pr [e\leftarrow _{\scriptscriptstyle \$}\mathcal {E};(N,\varphi _N)\leftarrow _{\scriptscriptstyle \$}\mathcal {R}\mathcal {S}\mathcal {A}_k[e\mathrel {\mid _1}\varphi _N]:\mathcal {D}(N,e)\Rightarrow 1] \\ \quad - \Pr [e\leftarrow _{\scriptscriptstyle \$}\mathcal {E};(N,\varphi _N)\leftarrow _{\scriptscriptstyle \$}\mathcal {R}\mathcal {S}\mathcal {A}_k[e\not \mid \varphi _N]:\mathcal {D}(N,e)\Rightarrow 1] \end{array} \right|\le \epsilon . $$

In the probability expressions we write $(N,\varphi _N)\leftarrow _{\scriptscriptstyle \$}\mathcal {R}\mathcal {S}\mathcal {A}_k[C]$ for an algorithm that generates a k-bit RSA modulus satisfying condition C, and also outputs $\varphi _N=|\mathbb {Z}_N^*|$.

In this paper we also need a variant of this assumption: An added restriction is that precisely one $e\in \mathcal {E}$ shall be a divisor of $\varphi _N$, and, as before, if e divides $\varphi _N$ then at most once.⁶ This is expressed by condition

$$ C(\mathcal {E},\varphi _N,e)\quad :\Longleftrightarrow \quad e\mid \varphi _N\wedge \gcd (\mathcal {E},\varphi _N/e)=1, $$

where the $\gcd$ term encodes that $\varphi _N/e$ is relative prime to all elements of $\mathcal {E}$; this in particular implies $e\mathrel {\mid _1}\varphi _N$. We say the unique-divisor $(\tau ,\epsilon )$-Phi-hiding assumption holds for $(k,\mathcal {E})$ if for all $\tau$-time adversaries $\mathcal {D}$ we have

$$ \left|\begin{array}{l} \Pr [e_0\leftarrow _{\scriptscriptstyle \$}\mathcal {E};(N,\varphi _N)\leftarrow _{\scriptscriptstyle \$}\mathcal {R}\mathcal {S}\mathcal {A}_k[C(\mathcal {E},\varphi _N,e_0)]:\mathcal {D}(N,e_0)\Rightarrow 1] \\ \quad - \Pr [e_0,e_1\leftarrow _{\scriptscriptstyle \$}\mathcal {E};(N,\varphi _N)\leftarrow _{\scriptscriptstyle \$}\mathcal {R}\mathcal {S}\mathcal {A}_k[C(\mathcal {E},\varphi _N,e_0)]:\mathcal {D}(N,e_1)\Rightarrow 1] \end{array} \right|\le \epsilon . $$

Quadratic Residuosity Assumption. Roughly, the quadratic residuosity assumption says that it is hard to distinguish quadratic residues modulo a Blum integer from quadratic non-residues that have positive Jacobi symbol.

Formally, for all $N\in \mathbb {N}$ denote with $\mathcal {Q}\mathcal {R}_N\subseteq \mathbb {Z}_N^*$ the set of quadratic residues modulo N and with $\mathcal {J}_N \subseteq \mathbb {Z}_N^*$ the set of numbers with positive Jacobi symbol. (In particular we have $\mathcal {Q}\mathcal {R}_N\subseteq \mathcal {J}_N$.) We say that the $(\tau ,\epsilon )$-quadratic residuosity assumption holds for k if for all $\tau$-time adversaries $\mathcal {D}$ we have

$$ \left|\begin{array}{l} \Pr [(N,p,q)\leftarrow _{\scriptscriptstyle \$}\mathcal {B}\mathcal {R}\mathcal {S}\mathcal {A}_k,x\leftarrow _{\scriptscriptstyle \$}\mathcal {Q}\mathcal {R}_N:\mathcal {D}(N,x)\Rightarrow 1] \\ \quad - \Pr [(N,p,q)\leftarrow _{\scriptscriptstyle \$}\mathcal {B}\mathcal {R}\mathcal {S}\mathcal {A}_k,x\leftarrow _{\scriptscriptstyle \$}\mathcal {J}_N\setminus \mathcal {Q}\mathcal {R}_N:\mathcal {D}(N,x)\Rightarrow 1] \end{array} \right|\le \epsilon . $$

In the probability expressions we write $(N,p,q)\leftarrow _{\scriptscriptstyle \$}\mathcal {B}\mathcal {R}\mathcal {S}\mathcal {A}_k$ for an algorithm that generates a k-bit Blum integer and also outputs its prime factors. Note that sampling elements of $\mathcal {Q}\mathcal {R}_N$ and $\mathcal {J}_N\setminus \mathcal {Q}\mathcal {R}_N$ can be done efficiently if these factors are known.

3 From Index-Dependence to Index-Independence

Many natural constructions of lossy trapdoor permutations are index-dependent, i.e., for each index $id$ the function $\mathrm {FEv}( id ,\cdot )$ operates on an individual set $\mathcal {X}( id )\subseteq \mathcal {X}$. However, for applications it might be necessary that there is only one domain: $\mathcal {X}( id )=\mathcal {X}$ for all $id$. In this section we convert index-dependent LTPs into index-independent LTPs. Some transforms of this type have been proposed before. For instance, [11] implicitly uses the somewhat trivial approach of leaving elements in $\mathcal {X}\setminus \mathcal {X}( id )$ untouched (i.e., elements in $\mathcal {X}( id )$ are processed with the LTP, the others are passed through without modification). As discussed in the introduction, the performance of this conversion is generally rather poor: In the worst case, if $|\mathcal {X}( id )|\ll |\mathcal {X}|$, lossiness is bounded by $L=1$.

Fig. 1.

Transformation of index-dependent LTP into index-independent LTP. To make algorithm $\mathrm {FInv}_{\mathrm {ii}}$ well-defined we assume implicitly that trapdoor $td$ contains a copy of function index $id$. A visualization of the construction is in Fig. 2.

Below we study a two-round construction that was first proposed in [13], in a different context. There, the goal was to extend the domain of the RSA trapdoor permutation; aspects of lossiness were not studied. Further, our exposition is more generic. The idea behind the transformation is to ensure that $\mathrm {FEv}$ is applied to every point of $\mathcal {X}$ at least once. In both rounds the points of $\mathcal {X}( id )$ are permuted with $\mathrm {FEv}$ while the remaining points of $\mathcal {X}$ stay unchanged. To achieve the property stated above, after the first round a permutation $\pi _{ id }$ is used to move into $\mathcal {X}( id )$ all those points that have not yet been touched by $\mathrm {FEv}$.

Let $\mathrm {F}=(\mathrm {FGen},\mathrm {FEv},\mathrm {FInv})$ be a LTP with domain $\mathcal {X}$ and index space ${\mathcal {I}d}$. Assume $\mathrm {F}$ has index-dependent domains. For all $id \in {\mathcal {I}d}$ write $\overline{\mathcal {X}( id )}=\mathcal {X}\setminus \mathcal {X}( id )$ and let $\pi _{ id }:\mathcal {X}\rightarrow \mathcal {X}$ be an efficiently computable and efficiently invertible permutation satisfying $\pi _{ id }(\overline{\mathcal {X}( id )})\subseteq \mathcal {X}( id )$ or, equivalently, $\pi _{ id }^{-1}(\overline{\mathcal {X}( id )})\subseteq \mathcal {X}( id )$. (Note that such a $\pi _{ id }$ can exist only if $|\mathcal {X}( id )|\ge |\mathcal {X}|/2$ for all $id$.) From $\mathrm {F}$ and $(\pi _{ id })_{ id \in {\mathcal {I}d}}$ we construct a LTP $\mathrm {F}_{\mathrm {ii}}=(\mathrm {FGen}_{\mathrm {ii}},\mathrm {FEv}_{\mathrm {ii}},\mathrm {FInv}_{\mathrm {ii}})$ with index-independent domain $\mathcal {X}$, i.e., $\mathcal {X}({ id })=\mathcal {X}$ for all $id$. The algorithms are specified in Fig. 1 and illustrated in Fig. 2. The analysis is in Lemma 1 (which is proved in the full version [1]).

Fig. 2.

Working principle of transformation of index-dependent LTP into index-independent LTP. The corresponding algorithms are in Fig. 1. Note that $\pi _{ id }$ is chosen such that every point in $\mathcal {X}$ is permuted by $\mathrm {FEv}$ at least once.

Lemma 1

Let $\mathrm {F}$ be a $(1-\epsilon _1)$-correct, $(\tau ,\epsilon _2)$-indistinguishable L-lossy trapdoor permutation with index-dependent domain. Furthermore, let $(\pi _{ id })_{ id \in {\mathcal {I}d}}$ be a family of permutations on $\mathcal {X}$ as described. Then $\mathrm {F}_{\mathrm {ii}}$ is an $(1-2\epsilon _1)$-correct, $(\tau ,\epsilon _2)$-indistinguishable L/2-lossy trapdoor permutation with index-independent domain $\mathcal {X}$. In particular, if $\mathrm {F}$ is 1-correct, then so is $\mathrm {F}_{\mathrm {ii}}$.

Analogously to the construction in Fig. 1 we can transform an index-dependent ABO-LTP $\mathrm {A}=(\mathrm {FGen},\mathrm {FEv},\mathrm {FInv})$ into an index-independent ABO-LTP $\mathrm {A}_{\mathrm {ii}}=(\mathrm {FGen},\mathrm {FEv}_\mathrm {ii},\mathrm {FInv}_\mathrm {ii})$. Note that $\mathrm {A}_{\mathrm {ii}}$ uses the same instance generator as $\mathrm {A}$. Algorithms $\mathrm {FEv}_\mathrm {ii}$ and $\mathrm {FInv}_\mathrm {ii}$ work as their counterparts for LTPs defined in Fig. 1, the only difference being the use of the additional input $br$ to evaluate $\mathrm {FEv}$ and $\mathrm {FInv}$. We obtain the following.

Lemma 2

Let $\mathrm {A}$ be a $(1-\epsilon _1)$-correct, $(\tau ,\epsilon _2)$-indistinguishable L-lossy ABO-LTP with index-dependent domain. Let $(\pi _{ id })_{ id \in {\mathcal {I}d}}$ be a family of permutations on $\mathcal {X}$ as described. Then $\mathrm {A}_{\mathrm {ii}}$ is an $(1-2\epsilon _1)$-correct, $(\tau ,\epsilon _2)$-indistinguishable L/2-lossy ABO-LTP with index-independent domain $\mathcal {X}$. In particular, if $\mathrm {A}$ is 1-correct, then so is $\mathrm {A}_{\mathrm {ii}}$.

4 Lossy Trapdoor Permutations from Phi-Hiding

Fix an RSA modulus N and let $e\ll \varphi _N$ be prime. We say e is injective for N if $e\not \mid \varphi _N$ and that it is lossy for N if $e\mathrel {\mid _1}\varphi _N$. In the injective case the mapping $E:\mathbb {Z}_N\rightarrow \mathbb {Z}_N;\,x\mapsto x^e$ is inverted by $D:y\mapsto y^d$, where d is such that $ed=1\bmod \varphi _N$. In the lossy case, the restriction $E\vert _{\mathbb {Z}_N^*}$ of E to domain $\mathbb {Z}_N^*$ is e-to-1, i.e., we have $|E(\mathbb {Z}_N^*)|/ |\mathbb {Z}_N^*|=1/e$. The Phi-hiding assumption from Sect. 2.3 then precisely says that it is hard to decide whether a candidate exponent e is injective or lossy for N.

We propose two LTPs in the RSA setting, both with security based on the Phi-hiding assumption. The first construction is quite natural but has index-dependent domains. The second construction is the index-independent analogue of the first, obtained via the transformation from Sect. 3. Here, our contribution is establishing a better bound on the lossiness than is possible with the generic result. (Our arguments are based on structures specific to the RSA setting.)

Fig. 3.

LTPs $\mathrm {F}$ and $\mathrm {F}^*$ from Phi-hiding assumption (with index-dependent domains).

4.1 Index-Dependent Domain LTP from Phi-Hiding Assumption

Let k be an even number indicating a desired bit length of RSA moduli. Let $\mathcal {E}$ be a distribution of prime numbers such that the $(\tau ,\epsilon )$-Phi-hiding assumption holds for $(k,\mathcal {E})$. Consider the constructions of LTPs $\mathrm {F}=(\mathrm {FGen},\mathrm {FEv},\mathrm {FInv})$ and $\mathrm {F}^*=(\mathrm {FGen},\mathrm {FEv}^*,\mathrm {FInv})$ given by the algorithms in Fig. 3. Observe that condition $e\mathrel {\mid _1}\varphi _N$ in line 02 implies that no element of $\mathcal {E}$ can be longer than k/2 bits. Further, to protect from known attacks it is necessary that $\max \mathcal {E}\le 2^{k/4}$.

The working principle of $\mathrm {F}$ is as follows: Function indices $id$ correspond with RSA parameters (N, e). The domain corresponding to index $id$ is $\mathcal {X}( id )=\mathbb {Z}_N$. In injective mode, (N, e) are chosen such that e is invertible modulo $\varphi _N$, i.e., such that a corresponding decryption exponent d exists. The $\mathrm {FEv}$ and $\mathrm {FInv}$ algorithms, in this case, are the standard RSA mappings $x\mapsto x^e$ and $y\mapsto y^d$ (lines 10 and 13). In lossy mode, e is a divisor of $\varphi _N$. In this case, mapping $x\mapsto x^e$ is e-to-1 for elements in $\mathbb {Z}_N^*$. The resulting overall lossiness (i.e., for full $\mathbb {Z}_N$) is analyzed in Lemma 3.

We next discuss $\mathrm {F}^*$. This variant achieves better lossiness by building on the fact that given an element of $\mathbb {Z}_N\setminus \mathbb {Z}_N^*$ it is possible to effectively determine whether the function index  (N, e) is injective or lossy. In the first case $\mathrm {FEv}^*$ uses the standard RSA map; in the second case elements in $\mathbb {Z}_N\setminus \mathbb {Z}_N^*$ are detected and explicitly mapped to 0. The identification of lossy indices and elements in $\mathbb {Z}_N\setminus \mathbb {Z}_N^*$ is handled in lines 17–21. Observe that the condition in line 17 can be checked efficiently.

We analyze constructions $\mathrm {F}$ and $\mathrm {F}^*$ in Lemma 3 (the proof of which is in the full version [1]). While the second LTP is more complicated to implement, the achieved lossiness bound is easier to work with.

Lemma 3

If for $(k,\mathcal {E})$ the $(\tau ,\epsilon )$-Phi-hiding assumption holds and $L\le \min \mathcal {E}$ is a lower bound on the elements in the support of $\mathcal {E}$, LTP $\mathrm {F}$ is a 1-correct, $(\tau ,\epsilon )$-indistinguishable $(1/L+2^{-k/2+3})^{-1}$-lossy trapdoor function. Furthermore, LTP $\mathrm {F}^*$ is a 1-correct $(\tau ,\epsilon )$-indistinguishable L-lossy trapdoor function. Both LTPs have index-dependent domain.

4.2 Index-Independent Domain LTP from Phi-Hiding Assumption

The LTP $\mathrm {F}^*$ from Sect. 4.1 has index-dependent domains: for function index $id =(N,e)$, algorithm $\mathrm {FEv}^*( id ,\cdot )$ operates on domain $\mathcal {X}( id )=\mathbb {Z}_N$. By construction we have $N\in \llbracket {2^{k-1}}{\,..\,}{2^k}\rrbracket$ and thus $\mathcal {X}( id )\subseteq \mathcal {X}$ for $\mathcal {X}=\llbracket {2^k}\rrbracket$. To obtain an LTP $\mathrm {F}_{\mathrm {ii}}$ with index-independent domain $\llbracket {2^k}\rrbracket$ we can apply to $\mathrm {F}^*$ the generic transform of Sect. 3. By Lemma 1, assuming appropriately chosen permutations $(\pi _{ id })$, if $\mathrm {F}^*$ is L-lossy, then $\mathrm {F}_{\mathrm {ii}}$ is L/2-lossy. The contribution of the current section is to show that for a specifically defined family $(\pi _{ id })$ using direct (non-generic) arguments this result can be strengthened: If $\mathrm {F}^*$ is L-lossy, then also $\mathrm {F}_{\mathrm {ii}}$ is L-lossy. In other words, there is no price to pay for switching from index-dependent domains to index-independent domains. (This holds for the lossiness; computation time might double.)

Fig. 4.

Illustration of Phi-hiding based LTP $\mathrm {F}_{\mathrm {ii}}$ with index-independent domain.

As a first step we identify a family $(\pi _{ id })$ of permutations on $\mathcal {X}$ that suits the conditions of the transform from Sect. 3, namely $\pi _{ id }(\overline{\mathcal {X}( id )})\subseteq \mathcal {X}( id )$ for all $id \in {\mathcal {I}d}$. Hence let $\mathcal {X}=\llbracket {2^k}\rrbracket$ and $(N,e)= id \in {\mathcal {I}d}$, where $N\in \llbracket {2^{k-1}}{\,..\,}{2^k}\rrbracket$. We define $\pi _{ id }:\mathcal {X}\rightarrow \mathcal {X};x\mapsto x-(N-1)\bmod {2^k}$. Then $\pi _{ id }$ is a permutation on $\mathcal {X}$ and we have $N\le x<2^k \Rightarrow 1\le \pi _{ id }(x)\le 2^k-N<N$ (the last inequality follows from $2^{k-1}\le N<2^k$); this establishes $\pi _{ id }(\overline{\mathcal {X}( id )})\subseteq \mathcal {X}( id )$. We illustrate the transform from Fig. 2 in conjunction with this family of bijections $(\pi _{ id })$ in Fig. 4. In the following, we first state the generic result obtained by applying Lemma 1 to this setup. We then give the one established directly. The proof of Lemma 4 is in the full version [1].

Corollary 1

Let $\mathcal {E}$ be a prime distribution and $L\le \min \mathcal {E}$. Further, let $\mathrm {F}^*=(\mathrm {FGen},\mathrm {FEv}^*,\mathrm {FInv})$ be the L-lossy LTP defined in Fig. 3, $(\pi _{ id })_{ id \in {\mathcal {I}d}}$ the permutation family defined above, and $\mathrm {F}_{\mathrm {ii}}$ the conversion of $\mathrm {F}^*$ via Fig. 1. If for $(k,\mathcal {E})$ the $(\tau ,\epsilon )$-Phi-hiding assumption holds, then $\mathrm {F}_{\mathrm {ii}}$ is a 1-correct, $(\tau ,\epsilon )$-indistinguishable L/2-lossy trapdoor function with index-independent domain $\mathcal {X}=\llbracket {2^k}\rrbracket$.

Lemma 4

Let $\mathcal {E}$ be a prime distribution and $L\le \min \mathcal {E}$. Further, let $\mathrm {F}^*=(\mathrm {FGen},\mathrm {FEv}^*,\mathrm {FInv})$ be the L-lossy LTF defined in Fig. 3, $(\pi _{ id })_{ id \in {\mathcal {I}d}}$ the permutation family defined above, and $\mathrm {F}_{\mathrm {ii}}$ the conversion of $\mathrm {F}^*$ via Fig. 1. If for $(k,\mathcal {E})$ the $(\tau ,\epsilon )$-Phi-hiding assumption holds, then $\mathrm {F}_{\mathrm {ii}}$ is a 1-correct, $(\tau ,\epsilon )$-indistinguishable $L/(1+2^{-k/2})$-lossy trapdoor function with index-independent domain $\mathcal {X}=\llbracket {2^k}\rrbracket$.

5 Lossy Trapdoor Permutations from Quadratic Residuosity Assumption

In this section we recall the index-dependent lossy trapdoor function $\mathrm {F}$ of [10] based on the quadratic residuosity assumption and show how the transform of Sect. 3 can be used to obtain an index-independent variant $\mathrm {F}_{\mathrm {ii}}$. Since $\mathrm {F}$ has a lossiness factor of 2, using the generic bound is of no use in this case. However, by exploiting the algebraic structure of the construction we are able to establish that $\mathrm {F}_{\mathrm {ii}}$ has essentially the same lossiness factor as $\mathrm {F}$. This improves on the index-independent variant given in [10], which achieves a lossiness factor of 4/3.

5.1 Index-Dependent Domain LTP from Quadratic Residuosity

Let p, q be primes of bit length k/2 satisfying $p\equiv 3\bmod 4$ and $q\equiv 3\bmod 4$. Consider the functions $j_N:\mathbb {Z}\rightarrow \{0,1\}$ and $h_N:\mathbb {Z}\rightarrow \{0,1\}$ defined by

$$\begin{aligned} j_N(x)&= {\left\{ \begin{array}{ll} 0, &{}\text {if } x\in \mathcal {J}_N\cup \left( \mathbb {Z}_N\setminus \mathbb {Z}_N^*\right) \\ 1, &{}\text {if } x\in \mathbb {Z}_N^*\setminus \mathcal {J}_N \end{array}\right. }\\ h_N(x)&= {\left\{ \begin{array}{ll} 0, &{}\text {if } x\le N/2\\ 1, &{}\text {if } x>N/2 \end{array}\right. } . \end{aligned}$$

Note that both $j_N$ and $h_N$ can be efficiently computed given N. Let $d_j,d_h\in \{0,1\}$. Then—as pointed out in [10]—for each $y\in \mathcal {Q}\mathcal {R}_N$ exactly one of the four solutions of the equation $x^2=y\bmod N$ satisfies $j_N(x)=d_j$ and $h_N(x)=d_h$. We denote this square root of y by $R_{d_j,d_h}$. Furthermore for every $y\in \mathbb {Z}_N\setminus \mathbb {Z}_N^*$ with $y\in \mathcal {Q}\mathcal {R}_p\vee y\in \mathcal {Q}\mathcal {R}_q$ the equation $y=x^2\bmod N$ has exactly two solutions—one being the negative of the other. Hence both solutions satisfy $j_N(x)=0$ and for $d_h\in \{0,1\}$ exactly one of the solutions satisfies $h_N(x)=d_h$. Analogous to the situation above we denote this solution by $R_{0,d_h}$. In [10] the authors construct a lossy trapdoor permutation with index-dependent domain $\mathbb {Z}_N$. The LTP’s algorithms are depicted in Fig. 5. The idea of the construction is to map elements $x\in \mathbb {Z}_N$ to $x^2$, which is afterwards multiplied by some appropriately chosen group elements, which allow to reconstruct $x^2$ as well as both $j_N(x)=:d_j$ and $h_N(x)=:d_h$. Then the LTF can be inverted by computing $R_{d_j,d_h}$.

Lemma 5

([10]). Let $\mathrm {F}=(\mathrm {FGen},\mathrm {FEv},\mathrm {FInv})$ the LTP of Fig. 5. If the $(\tau ,\epsilon )$-Quadratic residuosity assumption holds for k, then $\mathrm {F}$ is an $(\tau ',\epsilon )$-indistinguishable 2-lossy trapdoor function with index-dependent domain $\mathcal {X}((N,r,s))=\mathbb {Z}_N\subseteq \llbracket {2^k}\rrbracket =\mathcal {X}$, where $\tau '\approx \tau$.

5.2 Index-Independent Domain LTP from Quadratic Residuosity

In [10] the authors propose to modify the LTP $\mathrm {F}$ of Sect. 5.1 in the following way to obtain an LTP $\mathrm {F}_{ii}^*$ with index-independent domain $\llbracket {2^k}\rrbracket$. This is done by letting $\mathrm {F}_{ii}^*\vert _{\mathcal {X}( id )}( id ,\cdot ):=\mathrm {F}( id ,\cdot )$ and . The resulting LTP $\mathrm {F}_{ii}^*$ is a 4/3-lossy trapdoor function. In this section we show that using our transformation of Sect. 3 with an appropriate permutation yields an index-independent LTP based on the quadratic residuosity assumption having essentially the same lossiness factor as the underlying LTP $\mathrm {F}$.

Fig. 5.

LTP $\mathrm {F}$ from Quadratic residuosity assumption (with index-dependent domains).

To be able to use our transformation we need a family of permutations on $\mathcal {X}$ that suits the conditions of Sect. 3. Since—as in the construction based on the Phi-hiding assumption—the index-dependent domain $\mathcal {X}( id )$ for some $id =(N,r,s)$ is $\mathbb {Z}_N$, we are able to use the same family of permutations. Hence for $id =(N,r,s)\in {\mathcal {I}d}$ define $\pi _{ id }:\mathcal {X}\rightarrow \mathcal {X};x\mapsto x-(N-1)\bmod {2^k}$. Then $\pi _{ id }$ is a permutation on $\mathcal {X}$ and as in Sect. 4.2 we obtain $\pi _{ id }(\overline{\mathcal {X}( id )})\subseteq \mathcal {X}( id )$.

Note that applying Lemma 1 would only yield a bound of $2/2=1$ on the lossiness factor of the transformed LTP, which is of no use. However, we are able to establish a desirable result directly using techniques similar to the ones used in the proof of Lemma 4. The proof of Lemma 6 is in the full version [1].

Lemma 6

Let $\mathrm {F}=(\mathrm {FGen},\mathrm {FEv},\mathrm {FInv})$ be the 1-correct, 2-lossy LTP defined in Fig. 5, $(\pi _{ id })_{ id \in {\mathcal {I}d}}$ the permutation family defined above, and $\mathrm {F}_{\mathrm {ii}}$ the transformation of $\mathrm {F}$ via Fig. 1. If the $(\tau ,\epsilon )$-Quadratic residuosity assumption holds for k, $\mathrm {F}_{\mathrm {ii}}$ is a 1-correct $(\tau ',\epsilon )$-indistinguishable $2/(1+2^{-k/2})$-lossy trapdoor function with index-independent domain $\mathcal {X}=\llbracket {2^k}\rrbracket$, where $\tau '\approx \tau$.

6 Prime Family Generators

In Sect. 7 we construct all-but-one lossy trapdoor permutations from the unique divisor Phi-hiding assumption. As a building block we use prime family generators, a tool that deterministically derives prime numbers from a randomly picked seed. While this concept already appeared in [9], we need a variant of the tool with different functionality and security properties. Below, we first define syntax and functionality of prime family generators, and then give a construction based on polynomial evaluation.

Let $\mathcal {Q}\subseteq \mathcal {P}$ be a finite set of prime numbers and let $L\le |\mathcal {Q}|$. For $(\mathcal {Q},L)$, any instance of a prime family generator (PFG) indicates a sequence of distinct primes $q_1,\ldots ,q_L\in \mathcal {Q}$. A specific programmability feature allows for embedding any given prime at any given position. Formally, an $(\epsilon _1,\epsilon _2)$-PFG for $(\mathcal {Q},L)$ consists of a seed space $\mathcal {S}d$ and three algorithms $\mathrm {PGen},\mathrm {PGet},\mathrm {PProg}$ such that

$$ \mathrm {PGen}\rightarrow _{\scriptscriptstyle \$}\mathcal {S}d\quad \text {and}\quad \mathcal {S}d\times [{L}]\rightarrow \mathrm {PGet}\rightarrow \mathcal {Q}\quad \text {and}\quad [{L}]\times \mathcal {Q}\rightarrow \mathrm {PProg}\rightarrow _{\scriptscriptstyle \$}\mathcal {S}d. $$

For functionality we demand (a) programmability: for all $i\in [{L}]$ we require

$$ \Pr [q\leftarrow _{\scriptscriptstyle \$}\mathcal {Q}; sd \leftarrow _{\scriptscriptstyle \$}\mathrm {PProg}(i,q):\mathrm {PGet}( sd ,i)\ne q]\le \epsilon _1. $$

(b) distinctness of outputs: for all $i\in [L]$ we require

$$\Pr [ sd \leftarrow _{\scriptscriptstyle \$}\mathrm {PGen}:\exists j\in [{L}],i\ne j:\mathrm {PGet}( sd ,i)=\mathrm {PGet}( sd ,j) ]\le \epsilon _2. $$

For security we require perfectly indistinguishable programmability: We demand that for all $i\in [{L}]$ and every distinguisher $\mathcal {D}$ (running in arbitrary time) we have

$$ \left|\begin{array}{l} \Pr [ sd \leftarrow _{\scriptscriptstyle \$}\mathrm {PGen}:\mathcal {D}( sd )\Rightarrow 1] \\ \quad - \Pr [q\leftarrow _{\scriptscriptstyle \$}\mathcal {Q}; sd \leftarrow _{\scriptscriptstyle \$}\mathrm {PProg}(i,q):\mathcal {D}( sd )\Rightarrow 1] \end{array} \right|=0. $$

6.1 Construction Based on Polynomial Evaluation

The PFG we construct here outputs (l-bit) primes from $\mathcal {Q}=\mathcal {P}_l$. While the construction is similar to one by [9], their PFG would also output primes shorter than l bits. Further, our analysis of probabilities is different, for being tailored towards our application: the construction of ABO-LTPs.

Concretely, for a set of chosen parameters $l,n,d,\lambda \in \mathbb {N}$ we construct a $(2^{-(\lambda +1)},2^{-\lambda })$-PFG for $\mathcal {Q}=\mathcal {P}_l$ and $L=2^n$. The construction is based on a family $\{F_ sd \}$ of d-wise independent hash functions and, roughly, works as follows (see Fig. 6). The PFG’s seed space $\mathcal {S}d$ is equal to $\{F_ sd \}$’s key space. For $sd \in \mathcal {S}d$ and $i\in [{2^n}]$, natural numbers are generated by evaluating $F_{ sd }$ at up to d / 2 distinct points. $\mathrm {PGet}( sd ,i)$’s output is the first prime found. Since numbers of bit length l are tested for primality, the prime number theorem guarantees that $\mathrm {PGen}$ will succeed in finding a prime on average after roughly l attempts. Furthermore, if d is chosen large enough finding a prime in this way will succeed except with some negligible error probability. Concretely, we instantiate $\{F_{ sd }\}$ with polynomial evaluation of degree d over the field $\mathrm {GF}(2^{l-1})$. Programming a prime q into a particular point i is done by sampling a sequence of d-many values $a_j$ in the image of $F_{ sd }$. Then—if existent—the first prime in this sequence is replaced by q. By polynomial interpolation it is possible to find a seed $sd$ such that $F_{ sd }$ evaluated at the j’th point equals $a_j$. The technical challenge is to prove that if q was a uniformly distributed prime then resulting seed $sd$ has the correct distribution and, furthermore, with high probability satisfies $q=\mathrm {PGet}( sd ,i)$.

Fig. 6.

PFG based on polynomial evaluation

We now specify the construction in detail. We start by imposing necessary restrictions on its parameters. Let $l,n,d,\lambda \in \mathbb {N}$ with d even and $l\ge 25$ such that

$$\begin{aligned}&n\le l-\lambda -\log _2(l)-2\end{aligned}$$

(3)

$$\begin{aligned}&2l(\lambda +1)/\log _2(e)\le d<2^{l-1-n} \end{aligned}$$

(4)

where $e$ is Euler’s number. The first inequality ensures the probability of two primes sampled uniformly from $\mathcal {P}_l$ colliding is small, the second inequality makes sure d on one hand is large enough that $\mathrm {PGet}$ finds a prime with high probability and on the other hand small enough, that numbers smaller than d can be encoded with few bits. Note that for $l=\mathcal {O}(\lambda )$ and $n=l/2$ Eq. (3) will typically be fulfilled and results in d being of order $\mathcal {O}(\lambda ^2)$. The family of hash functions used in our construction is defined as follows. For $sd \in \mathrm {GF}(2^{l-1})^{d}$ let

$$ F_{ sd }:\; \{0,1\}^{l-1}\rightarrow \llbracket {2^{l-1}}\rrbracket ;\; x\mapsto \textstyle \sum _{k=0}^{d-1} sd _kx^k. $$

Here x is interpreted as element of $\mathrm {GF}({2^{l-1}})$. Note that the function family $(F_{ sd })_{ sd \in \mathcal {S}d}$ is a d-wise independent hash function [25]. Finally, we define an algorithm $\mathrm {FindC}$ as follows. $\mathrm {FindC}$ receives as input a tuple $(i,a_1,\dots ,a_d)$, where $i\in \llbracket {2^n}\rrbracket$ and $a_1,\dots ,a_d\in \llbracket {2^{l-1}}\rrbracket$. It then uses Lagrange interpolation to find $sd _0,\dots , sd _{d-1}\in \mathrm {GF}(2^{l-1})$ such that $F_{ sd }(\#i\Vert \#j)=a_j$ for all $j\in [{d}]$, where $sd :=( sd _0,\dots , sd _{d-1})$ (see Sect. 2.1 for the $\#$ notation). Here we assume $\#j\in \{0,1\}^{l-1-n}$, which is possible since by Eq. 4 we have $j\le d<2^{l-1-n}$. $\mathrm {FindC}$’s output is $sd$. Note that for every $i\in \llbracket {2^n}\rrbracket$ the function implemented by $\mathrm {FindC}(i,\cdot )$ is a bijection between $\llbracket {2^{l-1}}\rrbracket ^{d}$ and $\mathcal {S}d$. The description of the PFG $\mathrm {P}$ may be found in Fig. 6.

Note that in the definition we formally do not allow $\mathrm {PGet}$ to return elements that are not in $\mathcal {Q}$. However, $\mathrm {P}$ returns $\bot$ if after d tests no prime has been found. This issue could be solved by letting $\mathrm {PGet}$ return some fixed prime $q\in \mathcal {Q}$ in this case. We obtain the following result (the proof of which is in the full version [1]).

Fig. 7.

ABO from Phi-hiding assumption. $C(e^*,\varphi _N)$ denotes the condition defined in Sect. 2.3.

Theorem 1

Let $l,n,d,\lambda \in \mathbb {N}$ as above. Then $\mathrm {P}= (\mathrm {PGen},\mathrm {PGet},\mathrm {PProg})$ from Fig. 6 is a $(2^{-(\lambda +1)},2^{-\lambda })$-PFG for $(\mathcal {P}_l,2^n)$ with seed space $\mathcal {S}d=\mathrm {GF}(2^{l-1})^d$.

7 ABO-LTP with Index-Independent Domain from Unique-Divisor Phi-Hiding

We use a prime family generator (for instance the one from Sect. 6) to construct an ABO-LTP with index-independent domain, which can be shown secure under the unique-divisor Phi-hiding assumption. The construction resembles [16, Sect. 5.2] who build an adaptive trapdoor function. As a starting point we first specify an ABO-LTP $\mathrm {A}$ having index-dependent domains. Using the transform from Sect. 3, $\mathrm {A}$ can be made index-independent. Due to the result of Lemma 4 the transformed ABO-LTP has essentially the same lossiness factor as $\mathrm {A}$.

Index-Dependent ABO-LTP from Unique-Divisor Phi-Hiding. Let $n,l\in \mathbb {N}$. Consider the ABO-LTP defined in Fig. 7. We obtain the following result (the proof of which is in the full version [1]).

Lemma 7

Let $n,l\in \mathbb {N}$ and let $\mathrm {P}= (\mathrm {PGen},\mathrm {PGet},\mathrm {PProg})$ be a $(\epsilon _1,\epsilon _2)$-PFG for $(\mathcal {P}_l,2^n)$. Consider $\mathrm {A}= (\mathrm {FGen},\mathrm {FEv},\mathrm {FInv})$ from Fig. 7. If the unique-divisor $(\tau ,\epsilon )$-Phi-hiding assumption holds for $(k,\mathcal {P}_l)$, A is a $(1-\epsilon _2)$-correct, L-lossy, $(\tau ',2(\epsilon +\epsilon _1)/(1-\epsilon _1))$-indistinguishable ABO-LTP with index-dependent domain $\mathcal {X}=\llbracket {2^k}\rrbracket$, where $L=2^{l-1}$ and $\tau '\approx \tau$. Further, $\mathrm {A}$ has branching set $\mathcal {B}r=[{2^n}]$.

Index-Independent ABO-LTP from Unique-Divisor Phi-Hiding. Using the technique from Sect. 3 it is possible to transform $\mathrm {A}$ into an index-independent ABO-LTP $\mathrm {A}_{\mathrm {ii}}$. Using the improved bound on the lossiness from Lemma 4 we obtain the following.

Corollary 2

Let $n,l,k\in \mathbb {N}$ and $\mathrm {A}=(\mathrm {FGen},\mathrm {FEv},\mathrm {FInv})$ be the ABO defined in Fig. 7. Further, for $(N, sd )= id \in {\mathcal {I}d}$ let $\pi _{ id }$ the permutation

$$ \pi _{ id }:\llbracket {2^k}\rrbracket \rightarrow \llbracket {2^k}\rrbracket ;x\mapsto (x-N+1)\bmod {N}. $$

Let $\mathrm {A}_{\mathrm {ii}}$ be the conversion of $\mathrm {A}$ via Fig. 1. If the unique-divisor $(\tau ,\epsilon )$-Phi-hiding assumption holds for $(k,\mathcal {P}_l)$, then $A_{\mathrm {ii}}$ is a $(1-2\epsilon _2)$-correct, L-lossy, $(\tau ',2(\epsilon +\epsilon _1)/(1-\epsilon _1)))$-indistinguishable index-independent ABO-LTP with domain $\llbracket {2^k}\rrbracket$ and branching set $[{2^n}]$, where $L= 2^{l-1}/(1+2^{-k/2})$ and $\tau '\approx \tau$.