Efficient Pseudorandom Functions via On-the-Fly Adaptation

Abstract

Pseudorandom functions (PRFs) are one of the most fundamental building blocks in cryptography with numerous applications such as message authentication codes and private key encryption. In this work, we propose a new framework to construct PRFs with the overall goal to build efficient PRFs from standard assumptions with an almost tight proof of security. The main idea of our framework is to start from a PRF for any small domain (i.e. poly-sized domain) and turn it into an $\ell$-bounded pseudorandom function, i.e., into a PRF whose outputs are pseudorandom for the first $\ell$ distinct queries to F. In the second step, we apply a novel technique which we call on-the-fly adaptation that turns any bounded PRF into a fully-fledged (large domain) PRF. Both steps of our framework have a tight security reduction, meaning that any successful attacker can be turned into an efficient algorithm for the underlying hard computational problem without any significant increase in the running time or loss of success probability.

Instantiating our framework with specific number theoretic assumptions, we construct a PRF based on k-LIN (and thus DDH) that is faster than all known constructions, which reduces almost tightly to the underlying problem, and which has shorter keys.Instantiating our framework with general assumptions, we construct a PRF with very flat circuits whose security tightly reduces to the security of some small domain PRF.

N. Döttling—The authors acknowledge support from the Danish National Research Foundation and The National Science Foundation of China (under the grant 61061130540) for the Sino-Danish Center for the Theory of Interactive Computation, within which part of this work was performed; and also from the CFEM research center (supported by the Danish Strategic Research Council) within which part of this work was performed.

N. Döttling—Supported by European Research Commission Starting Grant no. 279447.

D. Schröder—Supported by the German Federal Ministry of Education and Research (BMBF) through funding for the Center for IT-Security, Privacy and Accountability (CISPA, www.cispa-security.org) and also by an Intel Early Career Faculty Honor Program Award.

1 Introduction

Goldreich, Goldwasser, and Micali (GGM) introduced pseudorandom functions (PRFs) in 1984 [13]. Roughly, a PRF is a keyed deterministic function, whose output is indistinguishable from a random function. PRFs are one of the most fundamental building blocks in cryptography, with numerous applications such as private-key encryption, message authentication codes, key derivation, and many more, e.g., [2, 14, 22, 29, 32]. In this work, we propose a novel framework to construct PRFs with the overall goal of constructing efficient PRFs based on standard assumptions with an almost tight proof of security. The basic idea of this framework is to transform a PRF for a small domain (i.e., poly-size) into a fully fledged domain that handles large input spaces. This transformation tightly reduces to the underlying small domain PRF. The main steps of our framework and the novel techniques are shown in Fig. 1. We begin with a PRF that works over a small domain, say $\{0,1\}^{\log \ell }$, and which can be evaluated very efficiently in time $\mathsf poly (\lambda , \log \ell )$, for some parameter $\ell$.

Fig. 1.

Overview of the main steps and the techniques.

The first step in our framework is to extend the domain of a small-domain PRF into a bounded pseudorandom function (bPRF). A function F is an $\ell$-bounded pseudorandom function (for an $\ell \le \mathsf {poly}(\lambda )$), if the outputs of F are pseudorandom for the first $\ell$ distinct queries to F and if F can be computed “super efficiently” (i.e., in time $\mathsf {poly}(\lambda , \log (\ell ))$). In some sense, this primitive can be seen as the computational analogue to $\ell$-wise independent functions.

The second step in our framework is a reduction technique we call on-the-fly adaptation. The goal of this technique is to construct a PRF F in which we can dynamically embed an $\ell$-bounded PRF $F_\ell$ for every $\ell$ that grows at most polynomially. Now assume we have a PPT distinguisher $\mathcal {D}$ that distinguishes F from a truly random function. Since $\mathcal {D}$ is efficient, it sends at most $q = \mathsf {poly}(\lambda )$ queries to its oracle (for an a-priori unknown q). On-the-fly adaptation allows us to turn this distinguisher against F into a distinguisher $\mathcal {D}'$ against a bounded PRF $F_q$ that has the same advantage.

We will demonstrate this idea with a simple on-the-fly adaptation technique that works for any bounded PRF. The basic idea of this technique is to compute F as a sum of functions $F_\ell$, for an exponentially increasing $\ell$. An important point is that all $F_\ell$ have the same domain. The function F is computed by

$$ F(K,x) = \bigoplus _{i = 0}^t F_{2^i}(K_{2^i},x), $$

where $K = (K_{2^i})_{i = 1,\dots ,t}$. If we choose the parameter $t = \omega (\log (\lambda ))$ slightly super-logarithmic, we will be able to embed any $F_\ell$ into F. Notice that F can be computed efficiently, as we required that bounded PRFs can be computed in time $\mathsf {poly}(\lambda , \log (\ell ))$. To illustrate the main idea, assume that there exists a distinguisher $\mathcal {D}$ that makes at most $q = \mathsf {poly}(\lambda )$ queries distinguishes F from a truly random function. We will provide a reduction that turns this distinguisher into a distinguisher against the small domain PRF $F_{2^{\lceil \log {q} \rceil }}$. Observe that we can express F by

$$ F(K,x) = \bigoplus _{i = 0}^{\log {q} - 1} F_{2^i}(K_{2^i},x) \oplus F_{2^{\lceil \log {q} \rceil }}(K_{2^{\lceil \log {q} \rceil }},x) \oplus \bigoplus _{i = \log {q} + 1}^{t} F_{2^i}(K_{2^i},x). $$

The reduction can now replace the middle term $F_{2^{\lceil \log {q} \rceil }}(K_{2^{\lceil \log {q} \rceil }},x)$ by its own oracle and provide to $\mathcal {D}$ an oracle $\mathcal {O}'$ that computes the function

$$ \mathcal {O}'(x) = \bigoplus _{i = 0}^{\log {q} - 1} F_{2^i}(K_{2^i},x) \oplus \mathcal {O}(x) \oplus \bigoplus _{i = \log {q} + 1}^{t} F_{2^i}(K_{2^i},x). $$

Clearly, if $\mathcal {O}$ computes the function $F_{2^{\lceil \log {q} \rceil }}$, then $\mathcal {O}'$ computes the function F. On the other hand, if $\mathcal {O}$ is a random function, then $\mathcal {O}'$ also is a random function. This reduction is tight. Notice that it is crucial for this technique to work that all $F_\ell$ have the same input domain. Basically the domain extension step in our framework is geared towards equalizing the domains of small domain PRFs. This generic technique is similar to a transformation from non-adaptive to adaptive pseudorandom functions by Berman and Haitner [4]. The construction of [4] however yields no tight security proof (which was not the purpose of that work), as their construction does not start from bounded PRFs.

We will now discuss domain extension for arbitrary PRFs and provide a simple domain extension technique that uses only linear functions to pre- and post-process a small domain PRF. This, together with the generic on-the-fly adaptation technique described above yields a PRF construction from any small domain PRF. We will discuss an instantiation of this general construction based on LWE.

Domain Extension for Arbitrary PRFs. The problem of domain extension for pseudorandom functions was first considered by Levin [20]. Levin showed that if the domain of a certain PRF is already sufficiently large, then it can be extended by using a universal hash function to hash larger inputs into the domain of this PRF. However, this technique is vulnerable to a “birthday attack”, which means that after a certain number of queries there is a high probability of finding a collision in the hash function. Levin’s technique also fails for small domain PRFs, i.e., PRFs with domains of polynomial size. Jain, Pietrzak, and Tentes [19] provided a domain extension technique which also works for small domains, but has an unfavorable security loss in this case. Moreover, as mentioned by the authors, their technique does not seem to be directly applicable to efficient PRF such as the one’s based on DDH [19]. The work of Jain et al. [19] was refined by Chandran and Garg [8]. Berman et al. [5] also showed how to bypass the birthday barrier via Cuckoo hashing.

We provide a simple general domain extension technique that preserves the parallel complexity of an underlying small domain PRF. This domain extension technique is inspired by the construction of universal hash functions by Ishai et al. [18] and can be seen as an amplified version of Levin’s trick. For a small domain pseudorandom function $\mathsf {PRF}_\ell : \{0,1\}^{\log (2\lambda \ell )} \rightarrow \mathcal {Y}$, we construct a large domain bounded PRF $F_\ell : \mathcal {X} \rightarrow \mathcal {Y}$ by

$$ F_\ell (K',x) = \bigoplus _{j = 1}^\lambda \mathsf {PRF}_\ell (K,\mathsf {BIN}(j) \Vert H_j(x)), $$

where $K' = (K,H_1,\dots ,H_\lambda )$, $H_1,\dots ,H_\lambda \leftarrow _{{\$}}\mathcal {H}$ are randomly chosen universal hash functions from a family $\mathcal {H}$ that maps $\mathcal {X}$ to $\{0,1\}^{\log (2\ell )}$ and $\mathsf {BIN}(j)$ is the $\log (\lambda )$ bit binary representation of an integer $j \in \{1,\dots ,\lambda \}$.

1.1 A General Transformation

Above we described our on-the-fly adaptation technique that works for any bounded PRF. Combining this technique with a general domain extension technique, we obtain large domain pseudorandom function with almost tight security (i.e., only a logarithmic loss) from any suitable small domain PRF. In a nutshell, a small domain PRF is suitable for this technique if its security loss only depends on the size of its input domain, but not (polynomially) on the number queries a distinguisher sends¹. The computational problems from which PRFs with such a small security loss can be constructed usually have one feature in common: they support a statistical random self-reduction. Candidate PRFs with this property are PRFs based on the LWE [28, 30] problem, such as the PRF of Banerjee, Peikert, and Rosen [1]. Using the BPR PRF as small domain PRF in our general construction, we obtain a large domain PRF which is secure under a weaker assumption, which has a tighter proof of security, and a shallower evaluation circuit than instantiating the BPR scheme with a large domain directly.

In the remaining part of this section, we discuss more efficient instantiations based on DDH and k-LIN. Here, we exploit specific number theoretic properties in order to improve the efficiency and security of the resulting PRF.

1.2 Efficient PRFs Based on DDH and k-LIN

One appealing property of our framework is that it yields several new constructions of PRFs based on weak standard assumptions, such as k-LIN (and thus DDH) with an almost tight proof of security. A tight reduction means that a successful attacker can be turned into an efficient algorithm for the hard computational problem without any significant increase in the running time or significant loss of success probability². We will provide a specific on-the-fly adaptation technique that exploits algebraic properties of the underlying number theoretic assumptions. We can thus avoid the blow up of the general on-the-fly adaptation technique described in the last paragraph and obtain PRFs that improve upon known constructions in terms of efficiency, security, and key-size.

Instantiation Based on DDH. In the following we discuss our construction based on the DDH assumption. Our underlying small domain PRF is the Naor-Reingold PRF based on DDH [26]. For an input domain $\{0,1\}^n$, the Naor Reingold PRF $\mathsf {NR}: \mathcal {K}_n \times \{0,1\}^n \rightarrow \mathbb {G}$ is defined by

$$ \mathsf {NR}_n(K,x) = g^{a \prod _{j = 0}^{n-1} s_j^{x_j}}, $$

where $K = (a,s_0,\dots ,s_{n-1})$ and $a,s_0,\dots ,s_{n-1} \leftarrow _{{\$}}\mathbb {Z}_p$. In the first step, we turn the small domain PRF $\mathsf {NR}_{\log (\ell )}$, which has a domain of size $\ell$ into an $\ell$-bounded PRF that has input domain $\mathbb {Z}_p$, i.e., a large input domain. In contrast to our generic construction (that we will discuss later), we can exploit specific number theoretic properties in order to improve the efficiency, the tightness of the security reduction, and the key-size. The bounded PRF $F_\ell : \mathcal {K} \times \mathbb {Z}_p \rightarrow \mathbb {G}$ is defined as follows:

$$\begin{aligned} F_\ell (K,x) = g^{a \prod _{j = 0}^{\log (\ell ) - 1}( s_j+x^{2^j})}. \end{aligned}$$

(1)

We will briefly discuss why security of this PRF tightly reduces to the security of $\mathsf {NR}_{\log (\ell )}$. Expanding the exponent of $F_\ell (K,x)$ yields

$$\begin{aligned} a \prod _{j = 0}^{\log (\ell ) - 1}( s_j+x^{2^j}) = \sum _{\mathbf {c} \in \{0,1\}^{\log (\ell )}} \underbrace{\left( a \prod _{j=0}^{\log (\ell )-1} s_j^{1 - c_j} \right) }_{E(\mathbf {c})} x^{\sum _{j=1}^t c_j 2^j} \end{aligned}$$

(2)

Now, observe that the term $E(\mathbf {c})$ on the right side is an exponent of the Naor Reingold PRF $\mathsf {NR}_{\log (\ell )}$. Specifically, it holds that $g^{E(\mathbf {c})} = \mathsf {NR}_{\log (\ell )}(\lnot \mathbf {c})$ (where $\lnot \mathbf {c}$ is the bitwise negation of $\mathbf {c}$). Changing the sum on the right side of (2) to run over all $j = 0,\dots ,2^{\lceil \ell \rceil } - 1$ and setting $\mathbf {c} = \mathsf {BIN}(j)$ (where $\mathsf {BIN}(j)$ is the $\log (\ell )$-bit binary representation of j), we get that $F_\ell$ can be equivalently computed as

$$\begin{aligned} F_\ell (K,x) = \prod _{j = 0}^{2^{\lceil \log (\ell ) \rceil } - 1} \left( \mathsf {NR}_{\log (\ell )}(K,\lnot \mathsf {BIN}(j)) \right) ^{x^j}. \end{aligned}$$

(3)

Notice that this expression can still be efficiently computed as long as $\ell \le \mathsf {poly}(\lambda )$. Now, observe that if we replace $\mathsf {NR}_{\log (\ell )}$ by a random function in this expression, then $F_\ell$ becomes an (information theoretic) $\ell$-wise independent function. We can therefore use this alternative description of $F_\ell$ to show that it is an $\ell$-bounded PRF.

The observation that functions of the form as $F_\ell$ in (3) can be computed in time $\log \ell$ via a closed form as (1) was previously made by Benadbbas, Gennaro, and Vahlis for the Naor-Reingold PRF [3] and Fiore and Gennaro for the Lewko-Waters PRF [12]. The fact that $F_\ell$ is a bounded PRF was independently observed by Hazay [15].

In the last step, we apply an “in-place” on-the-fly adaptation technique to this function. We will not use the generic technique described above, but one that exploits the specific algebraic properties of $F_\ell$. We define the full fledged PRF F by

$$ \mathsf {F}(K,x) = g^{a \prod _{j = 0}^{t-1}(s_j+x^{2^j})}, $$

where the parameter $t = \omega (\log (\lambda ))$ is chosen slightly super-logarithmic. Now, notice that we can embed the bounded PRF $F_\ell$ (for any $\ell \le \mathsf {poly}(\lambda )$) into F by

$$ \mathsf {F}(K,x) = \left( g^{a \prod _{j = 0}^{log(\ell )-1}(s_j+x^{2^j})} \right) ^{\prod _{j = \log (\ell )}^{t-1}(s_j+x^{2^j})} = (F_\ell (K_\ell ,x))^{{\prod _{j = \log (\ell )}^{t-1}(s_j+x^{2^j})}}. $$

In the security proof, we replace $F_\ell$ by a truly random function. The main part of the proof consists in showing that the exponent $\prod _{j = \log (\ell )}^{t-1}(s_j+x^{2^j})$ only accounts for a negligible error.

Comparison to Naor-Reingold [25]. Our full fledged PRF with input domain $\mathbb {Z}_p$ improves upon the Naor-Reingold PRF (NR-PRF) in terms of tightness of the security reduction and compactness. In contrast to the NR-PRF, the loss of our security reduction is only a factor of $\log (q)$ (where $q = \mathsf {poly}(\lambda )$ is the number of queries required by the distinguisher $\mathcal {D}$), compared to a factor n for the NR-PRF. Our PRF is very compact as it only requires $\omega (\log (\lambda ))$ $\mathbb {Z}_p$ elements for its key, whereas the Naor-Reingold needs n $\mathbb {Z}_p$ elements. Since the exponentiation is the dominating factor in the computation of both PRFs, the costs to evaluate both functions is roughly the same.

Instantiation Based on k -LIN. In the main body, we directly provide a PRF construction based on a family of weaker computational problems known as k-LIN [17, 31]. The decisional k-linear assumption becomes (generically) weaker as the parameter k grows, where the instance $k=1$ corresponds to DDH and $k=2$ to the linear assumption [6]. The main motivation for these assumptions is that groups are known where the DDH assumption is easy, but the computational Diffie Hellman problem is supposedly hard [16]. It is thus desirable to have constructions of cryptographic primitives based on the decisional k-linear assumption instead of DDH. Our generalized PRF is defined as follows: Let $k \ge 1$ be a positive integer, $\mathbb {G}= \langle g \rangle$ be a cyclic group of prime order p and $t = \omega (\log (\lambda ))$. The function $F: \mathcal {K} \times \mathbb {Z}_p \rightarrow \mathbb {G}^k$ is defined by

$$ F(K,x) = g^{\mathbf {a}^\top \cdot \prod _{j = 0}^{t-1} (\mathbf {S}_j + x^{2^j} \cdot \mathbf {I})}, $$

where $K =(\mathbf {a},\mathbf {S}_0,\dots ,\mathbf {S}_{t-1})$ with $\mathbf {a} \leftarrow _{{\$}}\mathbb {Z}_p^k$, $\mathbf {S}_0,\dots ,\mathbf {S}_{t-1} \leftarrow _{{\$}}\mathbb {Z}_p^{k \times k}$ and $\mathbf {I}$ the identity matrix. Clearly, if we only need a single group element as output, we can truncate the exponent and perform only 1 exponentiation.

Comparison to Lewko-Waters [21]. Our PRF improves upon the Lewko-Waters PRF (LW-PRF) in terms of efficiency, tightness of the security reduction, and compactness. A single evaluation of the LW-PRF involves n matrix multiplications and a single exponentiation. In our case, the computation requires only $t = \omega (\log (\lambda ))$ matrix multiplications and a single exponentiation. For larger k, the cost of the matrix multiplication dominates the cost of the exponentiation, so in this case our construction is more efficient. The security reduction of Lewko and Waters loses a factor of $k \cdot n$ while our reduction only losses a factor of $k \log q$. The keys of the LW-PRF consist of n $k \times k$ matrices over $\mathbb {Z}_p$, while ours consists merely of $t = \omega (\log \lambda )$ such matrices.

1.3 Other Related Work

Many number-theoretic PRF constructions follow the GGM paradigm [13], such as [1, 21, 25]. Naor and Reingold introduced pseudorandom synthesizer (PRS) that can be used to construct parallel computable pseudorandom function [1, 24]. A PRF construction that is not based on either the GGM or synthesizers paradigm is the PRF of Dodis-Yampolskiy, which is in fact a direct construction, but whose security is closely related to its underlying bilinear q-type assumption [10]. Recently, Chase and Meiklejohn showed that this q-type assumption can be reduced to the subgroup hiding assumption in composite order groups [9]. The PRF of Naor, Reingold, and Rosen is a clever variant of the Naor-Reingold PRF that is secure under the factoring assumption [27]. The work of Boneh, Montgomery, and Raghunathan combines a generalization of the GGM tree with the Dodis-Yampolskiy PRF to get a large-domain (simulateable) verifiable random function [7].

2 Preliminaries

Throughout this paper, we will use $\lambda$ to denote the security parameter. We will denote the concatenation of two bit strings x and y by $x \Vert y$. We will generally assume that logarithms are rounded to the next biggest integer, i.e., when we write $\log (\ell )$ we actually mean $\lceil \log (\ell ) \rceil$. To avoid confusion, we will sometimes still write $\lceil \log (\ell ) \rceil$, e.g. when we write $2^{\lceil \log (\ell ) \rceil }$ to indicate that this can be different from $\ell$.

Definition 1

(Pseudorandom Functions). Let $\mathcal {X}_\lambda$ and $\mathcal {Y}_\lambda$ be two finite sets depending on $\lambda$. We say that an efficiently computable keyed function $\mathsf {PRF}: \mathcal {K}_\lambda \times \mathcal {X}_\lambda \rightarrow \mathcal {Y}_\lambda$ with key-space $\mathcal {K}_\lambda$ is a pseudorandom function (PRF), if it holds for every PPT oracle distinguisher $\mathcal {D}$ that

$$ |\Pr [\mathcal {D}^{\mathsf {PRF}(K,\cdot )}(1^\lambda )=1] - Pr[\mathcal {D}^{R}(1^\lambda )=1] | \le \mathsf {negl}(\lambda ), $$

where $K \leftarrow _{{\$}}\mathcal {K}_\lambda$ and $R: \mathcal {X}_\lambda \rightarrow \mathcal {Y}_\lambda$ is a randomly chosen function. If $|\mathcal {X}| \le \mathsf {poly}(\lambda )$, then we say that $\mathsf {PRF}$ is a small-domain PRF, otherwise we call $\mathsf {PRF}$ a large-domain PRF.

We will usually omit the $\lambda$ subscript in the definition of $\mathcal {K}$, $\mathcal {X}$ and $\mathcal {Y}$. Moreover, we will henceforth implicitly assume that distinguisher gets $1^\lambda$ as an additional input without explicitly stating this.

As mentioned in the outline, bounded pseudorandom functions can be seen as a computational analogue of limited-wise independent functions. Basically, the difference between true PRFs and bounded PRFs manifests itself in their security guarantee. While a distinguisher against a true PRF can query the PRF an a-priori unbounded number of times, a distinguisher against an $\ell$-bounded PRF can query the PRF with at most $\ell$ distinct queries.

Definition 2

(Bounded Pseudorandom Functions). Let $\mathcal {X}$ and $\mathcal {Y}$ be finite sets (depending on $\lambda$). We say that a keyed function $F_\ell : \mathcal {K}_\ell \times \mathcal {X} \rightarrow \mathcal {Y}$ parametrized by a parameter $\ell$ is a bounded pseudorandom function (bPRF), if $F_\ell$ is computable in time $\mathsf {poly}(\lambda ,\log (\ell ))$ and if it holds for all efficiently computable $\ell ^*= \ell (\lambda ) \le \mathsf {poly}(\lambda )$ and all $\ell ^*$-query distinguishers $\mathcal {D}$ (i.e. distinguishers that send at most $\ell ^*$ distinct queries) that

$$ |\Pr [\mathcal {D}^{F_\ell (K,\cdot )}=1] - Pr[\mathcal {D}^{R}=1] | \le \mathsf {negl}(\lambda ), $$

where $K \leftarrow _{{\$}}\mathcal {K}_\ell$ and $R: \mathcal {X} \rightarrow \mathcal {Y}$ is a randomly chosen function.

Notice that in the definition of bounded PRFs we allow the key-space to depend on $\ell$, but $\mathcal {X}$ and $\mathcal {Y}$ are independent of $\ell$. Moreover, as we require that $F_\ell$ is computable in time $\mathsf {poly}(\lambda ,\log (\ell ))$, we implicitly also require that $|\mathcal {K}_\ell | \le \mathsf {poly}(\lambda ,\log (\ell ))$. Requiring that $F_\ell$ can be computed in time $\mathsf {poly}(\lambda ,\log (\ell ))$ allows us to evaluate $F_\ell$ for super-polynomial $\ell$, while we only require security for $\ell ^*$ which are at most polynomial.

The following lemma states that if a function F outputs uniformly random outputs under benign inputs, then the statistical distance from F to a uniformly random function $F'$ can be bounded by the probability that a non-adaptive sequence of inputs is not benign. Intuitively, an adaptive distinguisher $\mathcal {D}$ learns nothing about the set of bad inputs unless it finds such an input by chance, as otherwise the function F reveals no information about the set of bad inputs. This lemma is a simplified version of a more general statement due to Maurer [23].

Lemma 1

Let $\mathcal {X}$ and $\mathcal {Z}$ be two finite sets. Let $F_{K,\mathsf {aux}}: \mathcal {X} \rightarrow \mathcal {Z}$ be a function that takes two additional parameters $K \in \mathcal {K}$ and $\mathsf {aux} \in \mathsf {AUX}$. Let $\mathsf {good}(\cdot ,\cdot )$ be a predicate with the following property: If $\mathsf {good}(\{x_1,\dots ,x_i \},\mathsf {aux})$ holds, then $F_{K,\mathsf {aux}}(x_1),\dots ,F_{K,\mathsf {aux}}(x_i)$ are distributed uniformly at random over the choice of $K \leftarrow _{{\$}}\mathcal {K}$. Let $\mathcal {D}$ be a (possibly unbounded) distinguisher that makes at most $\ell$ distinct queries, $K \leftarrow _{{\$}}\mathcal {K}$, $\mathsf {aux} \leftarrow _{{\$}}\mathsf {AUX}$ and let $F'$ be a uniformly chosen function from $\mathcal {X}$ to $\mathcal {Z}$. Then it holds that

$$ |\Pr [\mathcal {D}^{F_{K,\mathsf {aux}}} = 1] - \Pr [\mathcal {D}^{F'} = 1] | \le \max _{S} \Pr [\lnot \mathsf {good}(S,\mathsf {aux})], $$

where S runs over all subsets of $\mathcal {X}$ of size at most $\ell$.

A proof of Lemma 1 can be found in the full version.

3 A Generic Construction

In this section, we will first provide an efficient construction of $\ell$-bounded pseudorandom function any small domain PRF with input space of (polynomial) size $n \cdot \ell$. Security of the $\ell$-bounded PRF follows tightly from the underlying small domain PRF. Second, we will provide a general construction of a PRF from $\ell$-bounded PRFs, where security also follows tightly.

3.1 Bounded PRFs via Domain Extension of Small Domain PRFs

We will need universal hash functions for our domain extension technique.

Definition 3

(Universal Hash Functions). Let $\mathcal {X}$ and $\mathcal {Y}$ be finite sets. We say that a family $\mathcal {H}$ of functions from $\mathcal {X}$ to $\mathcal {Y}$ is a family of universal hash functions, if it holds for all $x \ne x' \in \mathcal {X}$ that $\Pr [H(x) = H(x')] \le 1/ |\mathcal {Y} |$, where the probability is taken over the random choice of $H \leftarrow _{{\$}}\mathcal {H}$.

Universal hash functions can be constructed very efficiently, see e.g., [18].

Construction 1

Let $\mathsf {PRF}_\ell : \mathcal {K}_\ell \times \{0,1\}^{\log (2 \lambda \ell )} \rightarrow \{0,1\}^m$ be a keyed function with key space $\mathcal {K}_\ell$. Let $\mathcal {H}_\ell$ be a family of universal hash functions that map $\mathcal {X}$ to $\{0,1\}^{\log (2 \ell )}$. Let $\mathsf {BIN}(j)$ denote the $\log (\lambda )$ bit binary representation of a number $j \in \{1,\dots ,\lambda \}$. We define the keyed function $F_\ell : \mathcal {K}' \times \mathcal {X} \rightarrow \{0,1\}^m$ with key space $\mathcal {K}'_\ell = \mathcal {H}^\lambda \times \mathcal {K}_\ell$ by

$$ F_{\ell }(K',x) = \bigoplus _{j = 1}^\lambda \mathsf {PRF}_\ell (K,\mathsf {BIN}(j) \Vert H_j(x)), $$

where $H_j \leftarrow _{{\$}}\mathcal {H}_\ell$ for $j = 1,\dots ,\lambda$, $K \leftarrow _{{\$}}\mathcal {K}_\ell$ and $K' = (H_1,\dots ,H_\lambda ,K)$.

The following theorem states that $F_\ell$ is an $\ell$-bounded pseudorandom function if $\mathsf {PRF}_\ell$ is a pseudorandom function.

Theorem 1

Let $\mathsf {PRF}_\ell$ and $F_\ell$ be as in Construction 1. If $\mathsf {PRF}_\ell$ is a pseudorandom function, then $F_\ell$ is an $\ell$-bounded pseudorandom function. More specifically, assume there exists an $\ell ^*\le \mathsf {poly}(\lambda )$ and an $\ell ^*$-query PPT distinguisher $\mathcal {D}$ that distinguishes $F_{\ell ^*}$ from a truly random function with advantage $\epsilon$, then there exists a PPT distinguisher $\mathcal {D}'$ with essentially the same runtime as $\mathcal {D}$ that distinguishes $\mathsf {PRF}_{\ell ^*}$ from a truly random function with advantage at least $\epsilon - \ell ^*\cdot 2^{-\lambda }$.

The proof of Theorem 1 will be given in the full version.

3.2 PRFs via On-the-Fly Adaptation of Bounded PRFs

In this section we provide a generic on-the-fly adaptation technique which converts a bounded PRF into a standard PRF.

Construction 2

Let $t = \omega (\log (\lambda ))$ be slightly super-logarithmic. For a given parameter $\ell$, let $F_\ell : \mathcal {K}_\ell \times \mathcal {X} \rightarrow \{0,1\}^m$ be a keyed function with corresponding key space $\mathcal {K}_\ell$. Define the function $F: \mathcal {K} \times \mathcal {X} \rightarrow \{0,1\}^m$ with key-space $\mathcal {K} = \prod _{i = 0}^t \mathcal {K}_{2^i}$ by

$$ F(K,x) = \bigoplus _{i = 0}^t F_{2^i}(K_{2^i},x), $$

where $K_{2^i} \leftarrow _{{\$}}\mathcal {K}_{2^i}$ for $i = 1,\dots ,t$ and $K = (K_{2^i})_{i = 1,\dots ,t}$.

We will now show that F is in fact a pseudorandom function.

Theorem 2

Let $F_\ell$ and F be as in Construction 2. Assume that $F_\ell$ is an $\ell$-bounded PRF for every efficiently computable $\ell = \ell (\lambda )$. Then F is a pseudorandom function. Specifically, if $\mathcal {D}$ is a PPT distinguisher against F with advantage $\epsilon$ that makes at most $q = \mathsf {poly}(\lambda )$ distinct queries, then there exists a PPT distinguisher $\mathcal {D}'$ (with essentially the same runtime as $\mathcal {D}$) with advantage $\epsilon$ against $F_{\ell ^*}$, where $\ell ^*= 2^{\lceil \log (q) \rceil } \le 2q = \mathsf {poly}(\lambda )$.

Proof

Let $\mathcal {D}$ be a PPT distinguisher against F with advantage $\epsilon$ that makes at most q distinct queries. Note that since $q = \mathsf {poly}(\lambda )$ and $t = \omega (\log (\lambda ))$, it holds $\log (q) \le t$ (for a sufficiently large $\lambda$). We will now construct an $\ell ^*$-query distinguisher $\mathcal {D}'$ against $F_{\ell ^*}$, which is given in Fig. 2.

Notice first that $\mathcal {D}'$ sends at most $q \le 2^{\lceil \log (q) \rceil } = \ell ^*$ queries to its oracle, as $\mathcal {D}$ sends at most q oracle queries. We will now analyze the distinguishing advantage of $\mathcal {D}'$. First, assume that $\mathcal {D}'$’s oracle $\mathcal {O}$ implements the function $F_{\ell ^*}(K,\cdot )$ for a randomly chosen $K \leftarrow _{{\$}}\mathcal {K}_{\ell ^*}$. Then, the oracle $\mathcal {O}$ provided by $\mathcal {D}'$ to $\mathcal {D}$ implements exactly the function $F(K,\cdot )$ for a randomly chosen $K \leftarrow _{{\$}}\mathcal {K}$. On the other hand, if $\mathcal {O}$ behaves like a uniformly random function $R'$, then the oracle $\mathcal {O}'$ also implements a uniformly random function R, as $R'$ is independent of the $K_{2^i}$. Consequently, it holds that

$$\begin{aligned} \mathsf {Adv}(\mathcal {D}')&= |\Pr [{\mathcal {D}'}^{F_{\ell ^*}(K_{\ell ^*},\cdot )} = 1] - \Pr [{\mathcal {D}'}^{R'} = 1] |\\&= |\Pr [\mathcal {D}^{F} = 1] - \Pr [\mathcal {D}^{R} = 1] | = \epsilon , \end{aligned}$$

i.e. $\mathcal {D}'$ distinguishes $F_\ell$ from a uniformly random function $R'$ with advantage $\epsilon$. This concludes the proof.

Fig. 2.

The distinguisher $\mathcal {D}'$

3.3 Instantiations

Combining Theorems 1 and 2 yields the following

Theorem 3

Let $t = \omega (\log (\lambda ))$. Let $\mathsf {PRF}_\ell : \{0,1\}^{\log (2\lambda \ell )} \rightarrow \{0,1\}^m$ be a small domain PRF, let $\mathcal {H}_\ell : \mathcal {X} \rightarrow \{0,1\}^{\log (2 \ell )}$ be a family of universal hash functions. Define the keyed function $F: \mathcal {K} \times \mathcal {X} \rightarrow \{0,1\}^m$ by

$$ F(K,x) = \bigoplus _{i = 1}^t \bigoplus _{j = 1}^{\lambda } \mathsf {PRF}_{2^i}(K_{2^i},\mathsf {BIN}(j) \Vert H_{2^i,j}(x)), $$

where $K_{2^i} \leftarrow _{{\$}}\mathcal {K}_{2^i}$ for $i = 1,\dots ,t$ and $H_{2^i,j} \leftarrow _{{\$}}\mathcal {H}_{2^i}$ for $i = 1,\dots ,t$ and $j = 1,\dots ,\lambda$.

If $\mathsf {PRF}_\ell$ is a PRF for every $\ell = \mathsf {poly}(\lambda )$, then F is a PRF. More specifically, if there exists an distinguisher $\mathcal {D}$ that makes at most $q = \mathsf {poly}(\lambda )$ queries and distinguishes F with advantage $\epsilon$, then there exists a distinguisher $\mathcal {D}'$ with essentially the same runtime as $\mathcal {D}$ that distinguishes $\mathsf {PRF}_{2^{\lceil q \rceil }}$ with advantage $\epsilon - q \cdot 2^{-\lambda }$.

We will briefly discuss efficiency aspects of the construction provided in Theorem 3. First of all notice that the transformation preserves the parallel complexity of the underlying small domain PRF. Moreover, the pre- and post-processing steps are entirely linear, i.e. the computation of universal hash functions and XOR-ing the results.

We will now discuss an instantiation of this PRF using a small domain PRF based on lattice problems. As already mentioned in the introduction, the main purpose of our constructions is obtaining PRFs from standard assumptions that are as tight as possible. Since the construction in the last section allows reducing the security of the constructed large domain PRF to the security of an adversary specific small domain PRF, we need a family of small domain PRFs with security as tight as possible. The Naor-Reingold PRF with domain $\{0,1\}^n$ allows for a security loss of a factor of n, while the security loss of a comparable GGM PRF is $q \cdot n$. This holds because the DDH problem possesses a statistical random self-reduction which allows to compute an arbitrary number of DDH samples from a given sample. The learning with errors (LWE) problem enjoys a similar property, which is stated explicitly in the assumption.

Definition 4

(Decisional LWE [28, 30]). Let $p = p(\lambda )$ be a modulus, $k = k(\lambda ) = \mathsf {poly}(\lambda )$ be a positive integer and $\chi _r = D_{\mathbf {Z},r}$ be a gaussian distribution with noise parameter r . Let $\mathbf {s} \leftarrow _{{\$}}\mathbb {Z}_p^k$ be chosen uniformly at random. The goal of the $\mathsf {LWE}(p,n,\chi _r)$ problem is to distinguish an arbitrary number of samples $(\mathbf {a},\langle \mathbf {a},\mathbf {s} \rangle + e)$ where $\mathbf {a} \leftarrow _{{\$}}\mathbb {Z}_p^k$ and $e \leftarrow _{{\$}}\chi _\alpha$ from samples $(\mathbf {a},u)$ where $u \leftarrow _{{\$}}\mathbb {Z}_p$ is chosen uniformly at random.

Banerjee, Peikert and Rosen [1] constructed a PRF based on the LWE problem. The PRF has a structure which is similar to the Lewko-Waters PRF but uses a rounding operation instead of exponentiation. Let $p_1 \gg p_2$. For an $x \in \mathbb {Z}_{p_1}$ define $\lfloor x \rceil _{p_2} = \lceil (p_2 / p_1) \cdot x \rfloor \mod p_2$. For vectors $\mathbf {x} \in \mathbb {Z}_{p_1}^k$ define $\lfloor \cdot \rceil _{p_2}$ component-wise. We can now state the BPR PRF.

Theorem 4

Let $n = n(\lambda )$ be a positive integer, $r =r(n)$ be a noise parameter, $k = k(\lambda ) = \mathsf {poly}(\lambda )$ be a positive integer and let $p_1,p_2$ be moduli such that $p_1 \ge p_2 \cdot n \cdot (C r \sqrt{k} )^n \cdot k^{\omega (1)}$, where C is a universal constant. The keyed function $\mathsf {BPR}_n: \mathcal {K}_n \times \{0,1\}^n \rightarrow \mathbb {Z}_{p_2}^k$ with key space $\mathcal {K}_n = \mathbb {Z}_{p_2}^k \times \left( \mathbb {Z}_{p_2}^{k \times k} \right) ^n$ is defined by

$$ \mathsf {BPR}_n(K,x) = \left\lfloor \mathbf {a}^\top \prod _{j = 1}^n \mathbf {S}_j^{x_j} \right\rceil _{p_2}, $$

where $\mathbf {a} \leftarrow _{{\$}}\mathbb {Z}_{p_1}^k$ and $\mathbf {S}_1,\dots ,\mathbf {S}_n \leftarrow _{{\$}}\chi _\alpha ^{k \times k}$ and $K = (\mathbf {a},\mathbf {S}_1,\dots ,\mathbf {S}_n)$.

Assume that $\mathsf {LWE}(p_1,k,\chi _r)$ is hard. Then $\mathsf {BPR}_n$ is a pseudorandom function. Specifically, if there exists a distinguisher $\mathcal {D}$ that distinguishes $\mathsf {BPR}_n$ with advantage $\epsilon$ from a random function, then there exists a distinguisher $\mathcal {D}'$ with essentially the same runtime as $\mathcal {D}$ that distinguishes $\mathsf {LWE}(p_1,k,\chi _r)$ with advantage $\epsilon / (k \cdot n)$.

Observe that in Theorem 4 the underlying hardness assumption changes when we increase the input length n. More specifically, the smaller the term $p_1 / r$ is, the harder the underlying LWE problem $\mathsf {LWE}(p_1,k,\chi _r)$ becomes. The term $p_1 / r$ is dominated by $(C r \sqrt{k})^n$, thus we aim towards minimizing n. Observe that we can fix a modulus $p_2$ for the whole family $\mathsf {BPR}_n$, therefore all functions in this family have the same output domain. Plugging the $\mathsf {BPR}_n$ as small domain PRF in the construction of Theorem 3 yields that n never becomes larger than $\log (q)$ for some $q = \mathsf {poly}(n)$. Thus we can base the security of the PRF in Theorem 3 on $\mathsf {LWE}(p_1,k,\chi _r)$ with $p_1 = p_2 \cdot n \cdot (C r \sqrt{k} )^{\log (2\lambda q)} \cdot k^{\omega (1)}$, which is slightly super-polynomial (instead of sub-exponential). Moreover, since the $\mathsf {BPR}_n$ loses only a factor $k \cdot n$ in its security reduction to LWE, the resulting PRF from Theorem 3 loses only a factor of $k \cdot \log (2 \lambda q)$. We remark that using the more efficient and tighter Ring-LWE based PRF of [1], the security reduction to Ring-LWE loses only a factor of $\log (2 \lambda q)$.

While the construction from Theorem 3 preserves the parallel complexity of the small domain PRF, the overall complexity of evaluating the PRF may actually increase. We consider it an interesting problem to find a PRF construction which enjoys similar properties as the k-LIN based construction in Sect. 4, i.e. one improves the underlying small domain PRF in all aspects, in particular key size and evaluation complexity.

4 A Direct Construction from the k-LIN Problem

In this section, we will provide our efficient constructions of number-theoretic PRFs. As discussed above, we will first develop a specialized domain extension technique and then construct a large domain PRF using a tailor-made on-the-fly adaptation strategy.

4.1 Preliminaries

In this section, we will generally index vectors of length n with indices $0,\dots ,n-1$. We will denote the identity matrix in $\mathbb {Z}_p^{k \times k}$ by $\mathbf {I}$. For vectors $\mathbf {a} \in \mathbb {Z}_p^k$ we define exponentiation component-wise, i.e. $g^{\mathbf {a}} = (g^{a_0},\dots ,g^{a_{k-1}})$. The decisional k-linear assumption (k-LIN) [17, 31] generalizes the decisional DDH problem. The decisional k-Linear assumption becomes (generically) weaker when the parameter k grows, where the instance $k=1$ corresponds to DDH and $k=2$ to the linear assumption [6]. The main motivation for these assumptions is that groups are known, where the DDH assumption is easy, but the computational Diffie Hellman problem is supposedly hard [16].

Definition 5

(Decisional k -LIN Problem). Let $\mathbb {G}$ be a cyclic group of prime order p. Let $g_0,g_1,\dots ,g_k \leftarrow _{{\$}}\mathbb {G}$ and $s_1,\dots ,s_k,r \leftarrow _{{\$}}\mathbb {Z}_p$ be chosen uniformly at random. The goal of the k-LIN problem in $\mathbb {G}$ is to distinguish the distributions

$$ (g_0,\dots ,g_k,g_1^{s_1},\dots ,g_k^{s_k},g_0^{\sum _{i = 1}^k s_i}) \text { and } (g_0,\dots ,g_k,g_1^{s_1},\dots ,g_k^{s_k},g_0^r). $$

We will use the PRF construction of Lewko and Waters [21] as underlying small domain PRF in our construction.

Theorem 5

Let $k \ge 1$ be a positive integer, $\mathbb {G}= \langle g \rangle$ be a cyclic group of prime order p and $n = n(\lambda )$ be a positive integer. Define the keyed function $\mathsf {LW}_n: \mathcal {K}_n \times \{0,1\}^n \rightarrow \mathbb {G}$ with key space $\mathcal {K}_n = \mathbb {Z}_p^k \times \left( \mathbb {Z}_p^{k \times k} \right) ^n$ by

$$ \mathsf {LW}_n(K,x) = g^{\mathbf {a}^\top \cdot \prod _{j = 0}^{n-1} \mathbf {S}_j^{x_j}}, $$

where $\mathbf {a} \leftarrow _{{\$}}\mathbb {Z}_p^k$, $\mathbf {S}_0,\dots ,\mathbf {S}_{n-1} \leftarrow _{{\$}}\mathbb {Z}_p^{k \times k}$ and $K = (\mathbf {a},\mathbf {S}_0,\dots ,\mathbf {S}_{n-1})$. If the k-LIN problem is hard in $\mathbb {G}$, then $\mathsf {LW}_n$ is a pseudorandom function. More specifically, assume that there exists a PPT distinguisher $\mathcal {D}$ that distinguishes $\mathsf {LW}_n$ with advantage $\epsilon$ from a random function. Then there exists a PPT distinguisher $\mathcal {D}'$ that distinguishes the k-LIN problem with advantage $\epsilon / (k \cdot n)$.

The Lewko-Waters PRF $\mathsf {LW}$ as described in the construction in Theorem 5 outputs k group elements and therefore requires k exponentiations. We can truncate the output of the LW PRF to a single group element, thereby only requiring a single exponentiation.

4.2 A Bounded PRF From k-LIN

We will now provide an efficient construction of a bounded PRF from k-LIN. The security of this bounded PRF tightly reduces to the security of a small domain $\mathsf {LW}$ PRF and therefore to k-LIN with only a logarithmic loss.

Construction 3

Let $k \ge 1$ be a positive integer, $\mathbb {G}= \langle g \rangle$ be a cyclic group of prime order p. The keyed function $F_{\ell }: \mathcal {K}_\ell \times \mathbb {Z}_p \rightarrow \mathbb {G}$ with key space $\mathcal {K}_\ell = \mathbb {Z}_p^k \times \left( \mathbb {Z}_p^{k \times k} \right) ^{\log (\ell )}$ is defined by

$$ F_{\ell }(K_\ell ,x) = g^{\mathbf {a}^\top \cdot \prod _{j = 0}^{\log (\ell )-1} (\mathbf {S}_j + x^{2^j} \cdot \mathbf {I})}, $$

where $\mathbf {a} \leftarrow _{{\$}}\mathbb {Z}_p^k$, $\mathbf {S}_0,\dots ,\mathbf {S}_{\log (\ell )-1} \leftarrow _{{\$}}\mathbb {Z}_p^{k \times k}$ and $K_\ell = (\mathbf {a},\mathbf {S}_0,\dots ,\mathbf {S}_{\log (\ell )-1})$

For a bit $b \in \{0,1\}$ let $\lnot b = 1 - b$ denote the negation of b. For a bit-vector $\mathbf {c} \in \{0,1\}^m$ let $\lnot \mathbf {c}$ denote the bit-wise negation of $\mathbf {c}$. We will need the following technical lemma.

Lemma 2

Let p be a prime integer. It holds for all $r \in \mathbb {N}_{> 0}$, all matrices $\mathbf {S}_0,\dots ,\mathbf {S}_{r-1} \in \mathbb {Z}_p^{k \times k}$ and all $x \in \mathbb {Z}_p$ that

$$ \prod _{j = 0}^{r-1} (\mathbf {S}_j + x^{2^j} \mathbf {I}) = \sum _{\mathbf {c} \in \{0,1\}^r} \left( \prod _{j = 0}^{r-1} \mathbf {S}_j^{\lnot c_j} \right) x^{\sum _{j = 0}^{r-1} c_j 2^j}. $$

The proof of Lemma 2 works by inductively expanding the left side of the equation and can be found in the full version of this paper. We will now show that the function $F_\ell$ given in Construction 3 is a bounded PRF.

Theorem 6

Assume that the k-LIN problem is hard in $\mathbb {G}$. Then the function $F_{\ell }$ defined in Construction 3 is a bounded PRF. More specifically let $\ell ^*\le \mathsf {poly}(\lambda )$ and assume that $\mathcal {D}$ is an $\ell ^*$-query PPT distinguisher with advantage $\epsilon$ against the pseudorandomness of $F_{\ell ^*}$. Then there exists a distinguisher $\mathcal {D}'$ (with essentially the same runtime as $\mathcal {D}$) with advantage $\frac{\epsilon }{k \cdot \log (\ell ^*)}$ against k-LIN.

Proof

First observe that $F_\ell$ can be computed in time $\mathsf {poly}(\lambda ,\log (\ell ))$. Notice that $\mathsf {LW}_{\log (\ell )}$ and $F_\ell$ have identical key-spaces. Let $K = (\mathbf {a},\mathbf {S}_0,\dots ,\mathbf {S}_{\log (\ell ) - 1})$ be a key for $F_{\ell }$. It follows immediately by Lemma 2 that we can compute $F_{\ell }$ by

$$\begin{aligned} F_\ell (K,x)&= g^{\mathbf {a}^\top \cdot \prod _{j = 0}^{\log (\ell )-1} (\mathbf {S}_j + x^{2^j} \cdot \mathbf {I})}\\&= g^{\mathbf {a}^\top \cdot \sum _{\mathbf {c} \in \{0,1\}^{\log (\ell )}} \left( \prod _{i = 0}^{\log (\ell ) - 1} \mathbf {S}_i^{\lnot c_i} \right) x^{\sum _{i = 0}^{\log (\ell )-1} c_i 2^i}}\\&= \prod _{\mathbf {c} \in \{0,1\}^{\log (\ell )}} g^{\mathbf {a}^\top \cdot \left( \prod _{i = 0}^{\log (\ell )-1} \mathbf {S}_i^{\lnot c_i} \right) x^{\sum _{i = 0}^{\log (\ell )-1} c_i 2^i}}\\&= \prod _{\mathbf {c} \in \{0,1\}^{\log (\ell )}} \left( \mathsf {LW}_{\log (\ell )}(K,\lnot \mathbf {c}) \right) ^{x^{\sum _{i = 0}^{\log (\ell )-1} c_i 2^i}} \end{aligned}$$

For an integer $j \in \{0,\dots ,2^{\lceil \log (\ell ) \rceil }-1 \}$ let $\mathsf {BIN}(j)$ denote the $\log (\ell )$ bit binary representation of j, i.e. it holds that $j = \sum _{i = 0}^{\log (\ell )-1} \mathsf {BIN}(j)_i 2^i$. Thus, it holds that

$$\begin{aligned} F_\ell (K,x) = \prod _{j = 0}^{2^{\lceil \log (\ell ) \rceil } - 1} \left( \mathsf {LW}_{\log (\ell )}(K,\lnot \mathsf {BIN}(j)) \right) ^{x^j}. \end{aligned}$$

(4)

Now, let $\ell ^*\le \mathsf {poly}(\lambda )$ and assume that $\mathcal {D}$ is a $\ell ^*$-query PPT distinguisher that distinguishes $F_{\ell ^*}$ with advantage $\epsilon$ from a random function. We will construct a PPT distinguisher $\mathcal {D}'$ that distinguishes $\mathsf {LW}_{\log (\ell ^*)}$ from a random function with advantage $\epsilon$. Since the function table of a function $\{0,1\}^{\log (\ell ^*)} \rightarrow \mathbb {G}^k$ has size $2^{\lceil \log (\ell ^*)\rceil } \cdot k \log (|\mathbb {G}|) \le 2 \ell ^*k \log (|\mathbb {G}|) = \mathsf {poly}(\lambda )$, we can assume that $\mathcal {D}'$’s input is an explicit function table

First observe that $\mathcal {D}'$ is efficient as $\mathcal {D}$ is efficient and the oracle $\mathcal {O}$ can be implemented efficiently (as $2^{\lceil \log (\ell ^*) \rceil } \le 2\ell ^*$). We will now analyze the advantage of $\mathcal {D}'$. If $\mathcal {D}'$’s input T is a function $\mathsf {LW}_{\log (\ell ^*)}(K,\cdot )$ for a randomly chosen $K \leftarrow _{{\$}}\mathcal {K}_{\log (\ell ^*)}$, then clearly by (4) it holds that the oracle $\mathcal {O}$ implements exactly $F_{\ell ^*}(K,\cdot )$. On the other hand, if T implements a random function $R': \{0,1\}^{\log (\ell ^*)} \rightarrow \mathbb {G}^k$, then we can express $R'$ by $R'(\lnot \mathsf {BIN}(j)) = g^{\mathbf {a}^\top _j}$ for all $j = 0,\dots ,2^{\lceil \log (\ell ^*) \rceil -1}$, where the $\mathbf {a}_0,\dots ,\mathbf {a}_{2^{\lceil \log (\ell ^*) \rceil }-1} \leftarrow _{{\$}}\mathbb {G}^k$ are chosen uniformly at random. Thus, in this case the function computed by $\mathcal {O}$ is

$$\begin{aligned} \mathcal {O}(x)&= \prod _{j = 0}^{2^{\lceil \log (\ell ^*) \rceil }-1} g^{\mathbf {a}^\top _j x^j}\\&=g^{\sum _{j = 0}^{2^{\lceil \log (\ell ^*) \rceil } - 1} \mathbf {a}^\top _j x^j}, \end{aligned}$$

which is an $\ell ^*$-wise independent function. To see this, note that g-exponentiation is an isomorphism and the function in the exponent $\sum _{j = 0}^{2^{\lceil \log (\ell ^*) \rceil } - 1} \mathbf {a}^\top _j x^j$ is a random polynomial of degree $2^{\lceil \log (\ell ^*) \rceil } - 1 \ge \ell ^*- 1$, which is an $\ell ^*$-wise independent function. Thus, from the view of $\mathcal {D}$ the oracle $\mathcal {O}$ implements a random function R, as $\mathcal {D}$ sends at most $\ell ^*$ distinct queries. We conclude

$$\begin{aligned} \mathsf {Adv}(\mathcal {D}')&= |\Pr [{\mathcal {D}'}^{\mathsf {LW}_{\log (\ell ^*)}(K,\cdot )} = 1] - \Pr [{\mathcal {D}'}^{R'} = 1] |\\&= |\Pr [\mathcal {D}^{F_{\ell ^*}(K,\cdot )} = 1] - \Pr [\mathcal {D}^{R} = 1] | = \epsilon . \end{aligned}$$

By Theorem 5, the distinguisher $\mathcal {D}'$ yields a distinguisher $\mathcal {D}''$ with advantage $\frac{\epsilon }{k \log (\ell ^*)}$ against k-LIN.

4.3 In-Place On-the-Fly Adaptation

While the general on-the-fly adaptation strategy we will provide in Sect. 3.2 needs to replicate the the underlying bounded PRF t times, we will now provide a specific on-the-fly adaptation technique for the bounded PRF $F_\ell$ provided in the last paragraph that involves no expansion whatsoever. Due to the special algebraic structure of $F_\ell$, this on-the-fly adaptation can be done in-place. To obtain an unbounded PRF from the bounded PRF of Construction 3, we will set the upper limit of the product in the exponent from $\log (\ell )$ to some $t = \omega (\log (\lambda ))$. We thereby ensure that t is large enough that we can embed $F_{\ell ^*}$ in this PRF for any $\ell ^*\le \mathsf {poly}(\lambda )$.

Construction 4

Let $k \ge 1$ be a positive integer and $\mathbb {G}= \langle g \rangle$ be a cyclic group of prime order p. Let $t = \omega (\log (\lambda ))$. The keyed function $F: \mathcal {K} \times \mathbb {Z}_p \rightarrow \mathbb {G}$ with key space $\mathcal {K} = \mathbb {Z}_p^k \times \left( \mathbb {Z}_p^{k \times k} \right) ^t$ is defined by

$$ F(K,x) = g^{\mathbf {a}^\top \cdot \prod _{j = 0}^{t-1} (\mathbf {S}_j + x^{2^j} \cdot \mathbf {I})}, $$

where $\mathbf {a} \leftarrow _{{\$}}\mathbb {Z}_p^k$, $\mathbf {S}_0,\dots ,\mathbf {S}_{t-1} \leftarrow _{{\$}}\mathbb {Z}_p^{k \times k}$ and $K = (\mathbf {a},\mathbf {S}_0,\dots ,\mathbf {S}_{t-1})$.

We still need the following auxiliary lemma which states that a randomly chosen matrix from $\mathbb {Z}_p^{k \times k}$ has full rank, except with small probability.

Lemma 3

Let p be a prime and $\mathbf {S} \leftarrow _{{\$}}\mathbb {Z}_p^{k \times k}$ be chosen uniformly at random. Then it holds that

$$ \Pr [\mathsf {rank}(\mathbf {S}) < k] \le \frac{1}{p-1}. $$

The proof of Lemma 3 is standard.

Theorem 7

Assume that the k-LIN problem is hard in $\mathbb {G}$. Then the function F defined in Construction 4 is a PRF. More specifically assume that $\mathcal {D}$ is PPT distinguisher that makes at most $q = \mathsf {poly}(\lambda )$ queries and distinguishes F with advantage $\epsilon$ from a uniformly random function. Then there exists a PPT distinguisher $\mathcal {D}^*$ (with essentially the same runtime as $\mathcal {D}$) with advantage $\frac{1}{k \cdot \log (q)} \cdot \left( \epsilon - \frac{qt}{(p-1)} \right)$ against k-LIN in $\mathbb {G}$.

Proof

Let $\mathcal {D}$ be a distinguisher with advantage $\epsilon$ against the pseudorandomness of F which makes at most $q = \mathsf {poly}(n)$ queries. Note that since $q = \mathsf {poly}(\lambda )$ and $t = \omega (\log (\lambda ))$, it holds $\log (q) \le t-1$ (for a sufficiently large $\lambda$). We will define 3 hybrid experiments. In hybrid i $\mathcal {D}$ is given access to a function $F^{(i)}:\mathbb {Z}_p \rightarrow \mathbb {G}^k$.

• Hybrid $\mathfrak {H}_1$: In this experiment $\mathcal {D}$ is given oracle access to the function $F^{(1)}$ given by $F^{(1)}(x) = F(K,x)$ for a randomly chosen $K \leftarrow _{{\$}}\mathcal {K}$.

• Hybrid $\mathfrak {H}_2$: In this experiment $\mathcal {D}$ is given oracle access to the function $F^{(2)}$ defined by

  $$ F^{(2)}(x) = g^{\mathbf {r}(x)^\top \cdot \prod _{j = \log (q) }^t (\mathbf {S}_j + x^{2^j}\mathbf {I})}, $$

  where $\mathbf {r}: \mathbb {Z}_p \rightarrow \mathbb {Z}_p^k$ is a uniformly random function and $\mathbf {S}_{\log (q)},\dots ,\mathbf {S}_{t-1} \leftarrow _{{\$}}\mathbb {Z}_p^{k \times k}$.

• Hybrid $\mathfrak {H}_3$: In this experiment $\mathcal {D}$ is given oracle access to a uniformly random function $F^{(3)}$.

Clearly, it holds that

$$ |\Pr [\mathcal {D}^{F^{(1)}} = 1] - \Pr [\mathcal {D}^{F^{(3)}} = 1] | \ge \epsilon . $$

Define

$$\begin{aligned} \epsilon _1&= |\Pr [\mathcal {D}^{F^{(1)}} = 1] - \Pr [\mathcal {D}^{F^{(2)}} = 1] |\\ \epsilon _2&= |\Pr [\mathcal {D}^{F^{(2)}} = 1] - \Pr [\mathcal {D}^{F^{(3)}} = 1] |. \end{aligned}$$

By the triangle inequality it holds that

$$ \epsilon \le \epsilon _1 + \epsilon _2. $$

We will first show that $\epsilon _2 \le qt/(p-1)$. Define

$$ \mathbf {M}(x) = \prod _{j = \log (q)}^{t-1} (\mathbf {S}_j + x^{2^j}\mathbf {I}), $$

and observe that $F^{(2)}(x) = g^{\mathbf {r}^\top (x) \cdot \mathbf {M}(x)}$. Now, if it holds for distinct $x_1,\dots ,x_q \in \mathbb {Z}_p$ that $\mathsf {rank}(\mathbf {M}(x_i)) = k$ for $i = 1,\dots ,q$, then $\mathbf {r}^\top (x_1) \cdot \mathbf {M}(x_1),\dots ,\mathbf {r}^\top (x_q) \cdot \mathbf {M}(x_q)$ are distributed independently and uniformly at random. Thus it also holds that $F^{(2)}(x_1),\dots ,F^{(2)}(x_q)$ are distributed independently and uniformly at random. We can define the predicate $\mathsf {good}(\{x_1,\dots ,x_q \},\mathbf {M})$ to be true if and only if it holds $\mathsf {rank}(\mathbf {M}(x_i)) = k$ for $i = 1,\dots ,q$. Applying Lemma 1 yields

$$\begin{aligned} \epsilon _2&= |\Pr [\mathcal {D}^{F^{(2)}} = 1] - \Pr [\mathcal {D}^{F^{(3)}} = 1] |\\&\le \max _{x_1,\dots ,x_\ell } \Pr [\lnot \mathsf {good}(\{x_1,\dots ,x_q\},\mathbf {M})]\\&= \max _{x_1,\dots ,x_\ell } \Pr [\exists i: \mathsf {rank}(\mathbf {M}(x_i)) < k]. \end{aligned}$$

For a fixed x it holds that $\mathsf {rank}(\mathbf {M}(x)) < k$ if there exists a $j \in \{ \log {q},\dots ,t-1\}$ with $\mathsf {rank}(\mathbf {S}_j + x^{2^j} \mathbf {I}) < k$. Since $\mathbf {S}_j$ is chosen uniformly at random it holds by Lemma 3 that

$$ \Pr [\mathsf {rank}(\mathbf {S}_j + x^{2^j} \mathbf {I}) < k] = \Pr [\mathsf {rank}(\mathbf {S}_j) < k] \le \frac{1}{p-1}. $$

By a union bound over the j it holds that $\Pr [\mathsf {rank}(\mathbf {M}(x)) < k] \le \frac{t}{p-1}$. By another union bound over $i = 1,\dots ,q$ it holds that

$$ \Pr [\exists i: \mathsf {rank}(\mathbf {M}(x_i)) < k] \le \frac{qt}{p-1} $$

We conclude $\epsilon _2 \le qt/(p-1)$ and therefore $\epsilon _1 \ge \epsilon - qt/(p-1)$.

Now let $\ell ^*= 2^{\lceil \log (q) \rceil }$. We will now construct a PPT distinguisher $\mathcal {D}'$ that distinguishes the bounded PRF $F_{\ell ^*}$ with advantage $\epsilon _2$. The distinguisher $\mathcal {D}'$ is given in Fig. 3.

Fig. 3.

The distinguisher $\mathcal {D}'$

First assume that $\mathcal {D}'$’s oracle $\mathcal {O}$ implements the function $F_{\ell ^*}(K_{\ell ^*},x) = g^{\mathbf {a}^\top \prod _{j = 0}^{\log (q)-1} (\mathbf {S}_j + x^{2^j}\mathbf {I})}$ where $K_\ell =(\mathbf {a},\mathbf {S}_0,\dots ,\mathbf {S}_{\log (q)-1})$ is a uniformly chosen key for $F_{\ell ^*}$. Then the oracle $\mathcal {O}'$ implements the function

$$\begin{aligned} \mathcal {O}'(x)&= \left( g^{\mathbf {a}^\top \prod _{j = 0}^{\log (q)-1} (\mathbf {S}_j + x^{2^j}\mathbf {I})} \right) ^{\prod _{j = \log (q)}^{t-1} (\mathbf {S}_j + x^{2^j}\mathbf {I})}\\&= g^{\left( \mathbf {a}^\top \prod _{j = 0}^{\log (q)-1} (\mathbf {S}_j + x^{2^j}\mathbf {I}) \right) \cdot \prod _{j = \log (q)}^{t-1} (\mathbf {S}_j + x^{2^j}\mathbf {I})}\\&=g^{\mathbf {a}^\top \prod _{j = 0}^{t-1} (\mathbf {S}_j + x^{2^j}\mathbf {I})}. \end{aligned}$$

Thus $\mathcal {O}'$ implements exactly $F^{(1)}$. On the other hand, if $\mathcal {D}'$’s oracle $\mathcal {O}$ implements a random function R with $R(x) = g^{\mathbf {r}(x)^\top }$, where $\mathbf {r}: \mathbb {Z}_p \rightarrow \mathbb {Z}_p^k$ is a random function, then the oracle $\mathcal {O}'$ implements the function

$$\begin{aligned} \mathcal {O}'(x)&= \left( g^{\mathbf {r}^\top (x)} \right) ^{\prod _{j = \log (q)}^{t-1} (\mathbf {S}_j + x^{2^j}\mathbf {I})}\\&= g^{\mathbf {r}^\top (x) \cdot \prod _{j = \log (q)}^{t-1} (\mathbf {S}_j + x^{2^j}\mathbf {I})}. \end{aligned}$$

Thus $\mathcal {O}'(x)$ implements exactly $F^{(2)}$. We conclude that

$$\begin{aligned} \mathsf {Adv}(\mathcal {D}')&= |\Pr [{\mathcal {D}'}^{F_{\ell ^*}(K_{\ell ^*},\cdot )} = 1] - \Pr [{\mathcal {D}'}^{R} = 1] |\\&= |\Pr [\mathcal {D}^{F^{(1)}} = 1] - \Pr [\mathcal {D}^{F^{(2)}} = 1] | = \epsilon _1 \ge \epsilon - \frac{qt}{p-1}. \end{aligned}$$

By Theorem 6 this yields a distinguisher $\mathcal {D}^*$ with advantage $\frac{1}{k \cdot \log (q)} \cdot \left( \epsilon - \frac{qt}{(p-1)} \right)$ against k-LIN in $\mathbb {G}$. This concludes the proof.

PRF with Shorter Keys. Escala et al. [11] suggested a framework that generalizes Diffie-Hellman like decisional assumptions and proposed a variant of the Lewko-Waters PRF with short keys based on the so-called Matrix-DDH (MDDH) assumption. The proof of Theorem 6 immediately generalizes to this setting. Theorem 7 also holds in this setting, given that the distribution of aggregated transformation matrices $\mathbf {T}$ corresponding to the matrix distribution $\mathcal {D}_{\ell ,k}$ (c.f. [11], Sect. 5.3) used in the MDDH problem satisfies $\Pr [\mathsf {rank}(\mathbf {T} + x \cdot \mathbf {I}) < k] \le \mathsf {negl}$ for all $x \in \mathbb {Z}_p$.