Abstract
A family of functions is weakly pseudorandom if a random member of the family is indistinguishable from a uniform random function when queried on random inputs. We point out a subtle ambiguity in the definition of weak PRFs: there are natural weak PRFs whose security breaks down if the randomness used to sample the inputs is revealed. To capture this ambiguity we distinguish between public-coin and secret-coin weak PRFs.
We show that the existence of a secret-coin weak PRF which is not also a public-coin weak PRF implies the existence of two pass key-agreement (i.e. public-key encryption). So in Minicrypt, i.e. under the assumption that one-way functions exist but public-key cryptography does not, the notion of public-and secret-coin weak PRFs coincide.
Previous to this paper all positive cryptographic statements known to hold exclusively in Minicrypt concerned the adaptive security of constructions using non-adaptively secure components. Weak PRFs give rise to a new set of statements having this property. As another example we consider the problem of range extension for weak PRFs. We show that in Minicrypt one can beat the best possible range expansion factor (using a fixed number of distinct keys) for a very general class of constructions (in particular, this class contains all constructions that are known today).
Introduction

Weak Pseudorandom Functions
Informally, a pseudorandom function (PRF) is a function which cannot be distinguished from a uniform random function by any efficient distinguisher. PRFs have a wide range of applications in cryptography. Sometimes, however, the full power of a PRF is not needed and it is sufficient when the function cannot be distinguished when queried on random values. Such objects are referred to as weak PRFs.
to be practical 2 . In [23] , Naor and Reingold gave a quite efficient construction of a PRF relying on a number-theoretic assumption. More precisely, assuming that the so called decisional Diffie-Hellman (DDH) assumption holds in some cyclic group G = g of order q, they proposed a PRF (Z q ) n+1 × {0,
where (k 0 , . . . , k n ) is the secret key and a i denotes the i'th bit of a. As observed in [22] , if one just wants to construct a weak PRF, then even a much simpler construction exists: let G be a cyclic group of order q, then
is a weak PRF if the DDH assumption holds in G (the exponent k is the secret key). Note that compared to the Naor-Reingold construction, this construction has a much shorter key ( log(q) compared to (n + 1) log(q) ) and is more efficient (each evaluation requires one exponentiation, compared to one exponentiation and up to n multiplications).
Public-Coin vs. Secret-Coin Weak PRFs
A standard choice for the group G used in exp would be a large subgroup of Z * p (where p is some large prime) of prime order q (which exists if and only if q divides the order p − 1 of Z * p ). The DDH assumption is believed to hold in such groups if q is sufficiently large. 3 A natural way to sample an element from G is to choose an element r ∈ Z q uniformly at random and set a = g r for some generator g of G. 4 For a 1 , a 2 , . . . sampled this way, the tuples (a 1 , v 1 ), (a 2 , v 2 ), . . . computed by the weak PRF as v i = exp(k, a i ) = a k i are indistinguishable from (a 1 , u 1 ), (a 2 , u 2 ), . . . where each u i is a uniform random element in G. Now, assume that the distinguisher also gets to see the randomness used to sample the a i 's. Say r 1 , r 2 are such that a 1 = g r1 and a 2 = g r2 . Then one can easily distinguish
2 only holds with probability 1/q.
Thus the security of the weak PRF exp completely breaks down if the randomness used to sample the random inputs is revealed. We will call such a weak PRF a secret-coin weak PRF, as opposed to a public-coin weak PRF which stays secure even if the random coins used to sample the inputs are revealed. Whether a weak PRF is a public-coin or just secret-coin weak PRF depends on the input-sampling algorithm, which hence must be part of the definition of the weak PRF.
2 Even though progress has recently been made [10, 14] for achieving more efficient reductions of PRGs from one-way functions. 3 Say p − 1 = 2q where log(p) is at least our security parameter. 4 Alternatively one could sample random elements from Z * p until an element a is found where a q = a, but this is less efficient (the expected number of tries is q/(p − 1)), and only works if q 2 does not divide p − 1 as otherwise there is more than just one subgroup of order q).
Public-Coins=Secret-Coins in Minicrypt
As the function exp shows, the distinction between public-and secret-coin weak PRFs is meaningful and one can imagine many situations where the notion of a secret-coin weak PRF is not sufficient. In particular, this will always be the case when public randomness is used to sample the inputs.
It is not hard to see, that if a weak PRF is secret-but not public-coin, then the input-sampling algorithm must be a distributional one-way function [17] . 5 We further show that any secret-coin weak PRF which is not also a public-coin weak PRF must be very artificial, in the sense that one can construct a public-key encryption scheme from it:
Theorem 1. If there exists a secret-coin weak PRF which is not a public-coin weak PRF, then a (IND-CPA) secure public-key encryption scheme exists (see Section 1.4 for the disclaimer).
Thus it is not surprising that the DDH assumption required for the security of exp implies public-key encryption [4, 7] . So in Minicrypt (a name coined by Impagliazzo to denote the hypothetical world where one-way functions exist, but public-key cryptography does not [16] ), the notion of public-and secret-coin weak PRFs coincide.
In order to prove Theorem 1, we show how to construct a public-key encryption scheme from any secret-coin weak PRF F and a distinguisher D which can distinguish F from a uniform random function when additionally to the random input/output pairs it is provided with the randomness used by the input sampling algorithm S (such a D exists as by assumption F is not a public-coin weak PRF).
Uniform vs. Non-uniform and Negligible vs. Noticeable
There is a gap between what is generally considered a successful distinguisher (or any other kind of an adversary) and what one expects from a protocol like an encryption scheme: a system is usually considered broken even if only a nonuniform adversary exists, whereas a protocol should be uniform and achieve its task with overwhelming 6 probability to be considered useful. The encryption scheme we construct in order the prove Theorem 1 uses the distinguisher D as a black-box, and only if D is uniform and has noticeable advantage in distinguishing F from a uniform random function, we will get a useful (as described above) key-agreement protocol. But if D is non-uniform, also the key-agreement protocol will be non-uniform. Furthermore, if D has only non-negligible (but not noticeable) advantage, then our encryption scheme will only be secure for infinitely many values of the security parameter (and not as usual for all sufficiently large ones).
Range Extension for Weak PRFs
The problem of range extension for weak PRFs is the following: given a weak PRF f : K × X → X , construct a weak PRF F : K t × X → X s where F uses f as a black-box, t is the number of keys, and s is the so-called expansion factor. A trivial solution is to set
but this is not very satisfying as the expansion factor is only the number of keys (i.e. s = t). All efficient constructions for range extension of weak PRFs, that we are aware of [2, 21, 20] , are of the form that the i'th output block y i is computed as
for some i 1 , . . . , i q ∈ {1, . . . , t}. The construction from [20] achieves an expansion factor of s = 2 t − 1, and in [25] it is shown that this is tight: no construction (of the form as described above) with an expansion factor greater than 2 t − 1 can be proven secure via a black-box reduction. We show that it is possible to beat this bound in Minicrypt. For this, consider the following construction which uses two keys and has an expansion factor of 4 (which is more than 2 t − 1 = 3)
In [21] , it has been claimed that this function is indeed a weak PRF, but in fact it is not as observed in [20] . The function f = exp is a simple counterexample, as in this case the last two values of the output in (1) are identical, namely
In Section 4, we prove the following theorem:
Let F : K n × X n → X n , KeyGen : 1 n → K n denote a weak PRF as in Definition 1, with the additional property that the domain and range are identical, i.e. X n = Y n , and that the domain is of superpolynomial size, i.e. for all c there is an n 0 such that |X n | ≥ n c for all n > n 0 . In order to prove Theorem 2, we must show
is not a weak PRF, then a two-pass key-agreement protocol exists. If G is not a weak PRF, there exists an efficient distinguisher D, a polynomial q(.), and a non-negligible function φ(.), such that for
We now define three other functions G, H, H which will be used in the proof. The function G is defined almost as G, but with F(k , .) replaced by a URF. The systems H and H are defined like G and G respectively, but without the last term. For the rest of this section, we let R denote R Xn,Xn . 
Theorem 2. If there exists a weak PRF f with superpolynomial domain size for which the construction given by equation (1) is not a weak PRF, then a secure public-key encryption scheme exists (disclaimer is below).
The requirement that the domain size must be superpolynomial is necessary as otherwise the construction given in (1) is not a weak PRF even if f is a uniform random function. The reason is that the last two values of the output
, collide twice as often as for random elements. If now the domain size is not superpolynomial, collisions will occur with high probability after polynomially many input-output samples (allowing us to distinguish F from a uniform random function). In order to prove Theorem 2, we show how to construct a two-pass keyagreement protocol from any weak PRF f and a distinguisher D which can (for random keys
from random tuples. For this reduction, we have the same issue with uniform vs. non-uniform and negligible vs. noticeable, as discussed in Section 1.4.
Related Work
Adaptive Security in Minicrypt. The first positive cryptographic result proven to hold only in Minicrypt stated that the cascade of non-adaptively secure PRFs gives a construction with some weak form of adaptive security [24] . We have found more results since then, but all were about the adaptive security of some construction based on non-adaptively secure components. 7 The results of this paper show that weak PRFs give rise to a completely new class of statements that hold exclusively in Minicrypt.
Other Worlds. Wee [26] shows that some cryptography (i.e. "non-trivial" argument systems) is even possible in Pessiland, which is another of Impagliazzo's possible worlds [16] where not even one-way functions exist. Dent [3] explores the limits of cryptography in universes whose existence is conjectured in popular Science Fiction literature.
Win-Win. Our results can be viewed as "win-win" statements, where one shows that (at least) one of two "positive" cryptographic statements is true. For example we show that either every secret-coin weak PRF is a public-coin weak PRF or public-key crypto exists. Results of similar flavour have been given before, in particular Dziembowski shows that either "forward-secure storage" is possible or (a weak form of) oblivious transfer exists [6] . Dubrov and Ishai show that either every efficiently samplable distribution can be sampled using few random bits, or one-way functions imply collision-resistant hashing [5] .
Public vs. Secret Coins. That differentiating between the public-and secretcoin variants of primitives is meaningful and important has been shown for at least two important primitives, namely collision resistant hash functions (CRHF) and trapdoor permutations (TDP).
In [15] , Hsiao and Reyzin define public-and secret-coin families of CRHFs. The collision resistance of the latter requires the coins used to sample the function to be kept secret. They show that no black-box reduction from secret-coin to public-coin CRHFs exists.
The classical definition of a TDP states that it is hard to invert the permutation given a random element from the range of the permutation. In [8] , Goldreich observes that for many applications this is not enough, and in fact enhanced TDPs are needed. Those have the property that it is hard to invert a random element even when given the random coins used to sample this element. 7 For example, in [19] it was shown that the four round Feistel-network with nonadaptively secure round functions is not a pseudorandom permutation in general.
To be more precise, it was shown that there exists a non-adaptively secure function f (whose security is based on the inverse DDH assumption [1] ) for which the four-round Feistel-network with f as round function can be distinguished from a random permutation with two adaptive queries. Here, one can show that any such counterexample implies a three round key-agreement protocol (this is unpublished).
Basic Definitions
Throughout, let n ∈ N denote a security parameter. An entity (e.g. adversary) is efficient and uniform if it can be implemented by a probabilistic Turing machine whose running time is polynomial in the input length (which for us will always mean polynomial in n). It is efficient and non-uniform if it can be realized by a sequence of circuits (one for each n) of polynomial (in n) size.
For a set X , let x $ ← X denote that x is assigned a value from X haleysusan@example.com. Let x q denote the sequence x 1 , . . . , x q . For a function f : X → Y and
To the contrary, μ is non-negligible if for some c > 0 we have μ(n) ≥ 1/n c for infinitely many n. Throughout, negl(n) denotes a negligible function in n.
Note that non-negligible is not the same as noticeable. For example μ(n) def = n mod 2 is non-negligible but not noticeable. Bit-Agreement. Bit-agreement is a protocol between two efficient parties, which we refer to as Alice and Bob . They get the security parameter n in unary (denoted 1 n ) as a common input and can communicate over an authentic channel. Finally, Alice and Bob output a bit b A and b B , respectively. The protocol has correlation if for all n
Furthermore, the protocol is δ-secure if for any efficient adversary E, which can observe the whole communication C, and for all n
Key-Agreement. If (·) and δ(·) are overwhelming then such a protocol achieves key-agreement. Any protocol which achieves bit-agreement with noticeable correlation (·) and overwhelming security δ(·) can be turned into a key-agreement protocol without increasing the number of rounds using parallel repetition and privacy amplification [12, 13] . If (·) is only non-negligible (i.e. for any constant c > 0, (n) ≥ 1/n c for infinitely many n), then also the key-agreement protocol will only achieve correctness for infinitely many (and not for all sufficiently large) choices of the security parameter. 
KeyGen 
F is a weak pseudorandom function secure if for every efficient distinguisher D and any polynomial = (n)

|P[D(X , Y ) = 1] − P[D(X , Z ) = 1]| = negl(n).

Definition 2 (public-coin and secret-coin weak PRFs). Let F, KeyGen be efficient algorithms as in the previous definition, and let
R i $ ← {0, 1} s(n) X i ← Sample(R i ) Y i ← F(k, X i ) Z i ← R Xn,Yn (X i ).
The three algorithms F, KeyGen, Sample are a public-coin weak PRF if for all efficient D and any polynomial = (n)

|P[D(R , X , Y ) = 1] − P[D(R , X , Z ) = 1]| = negl(n) (i.e. the weak PRF, by Definition 1, stays secure even if the randomness used to sample the inputs is revealed). Furthermore, F, KeyGen, Sample are referred to as a secret-coin weak PRF if for all efficient D and any polynomial = (n)
Clearly, every public-coin weak PRF is a secret-coin weak PRF. Also if F, KeyGen is a weak PRF (by Definition 1) and the output of Sample is close to uniform, then F, KeyGen, Sample is a secret-coin weak PRF. Note that in the definitions above, secure means secure against efficient uniform adversaries. To get a (stronger) notion which implies security against non-uniform adversaries, one must just consider a sequence of poly-size circuits instead of the poly-time bounded Turingmachine D (cf. Section 1.4).
Protocol BitAgreement(n)
Alice Bob
Fig. 1.
A bit-agreement protocol from a secret-coin weak PRF which is not a publiccoin weak PRF
The Reduction
Let (F, KeyGen, Sample) be a secret-coin weak PRF which is not a public-coin weak PRF. For i = 1, 2, . . . consider the random variables r i , x i , y i , and
and u i $ ← Y n (i.e. u i is a random element from the range of F). Now, as F is not a public-coin weak PRF, there exist an efficient distinguisher D, a polynomial q(.), and a non-negligible function φ(.) such that
Further, as F is a secret-coin weak PRF we have for any efficient E that
In order to prove Theorem 1, we must construct a two-pass public-key encryption scheme from the weak PRF. As discussed in Section 2, it is sufficient to construct a two-pass bit-agreement protocol with non-negligible (or noticeable, see the discussion in Section 1.4) correlation and overwhelming security. Such a protocol BitAgreement is shown in Figure 1 . The idea behind the protocol is quite simple: First, Alice samples some random strings, on which she invokes Sample to get random inputs to the secret-coin weak PRF F. Then she sends the inputs to Bob, who either return the outputs of F on these inputs or random values depending on his randomly chosen bit b B . As Alice knows the randomness she used to sample the inputs, she can use the distinguisher D to get a guess b A on b B with non-negligible correlation, as shown in Claim 1 below. Furthermore, an adversary who does not know the randomness used to sample the inputs cannot distinguish the cases where Bob sends random values or values computed by F, as shown in Claim 2 below.
Claim 1. BitAgreement(n) has correlation φ(n), with φ as in (3).
Proof.
Proof. For any efficient adversary E
where the last step follows by (4) .
Proof (of Theorem 1).
The theorem follows from Claim 1 and 2 and the fact that one can construct a key-agreement protocol from any bit-agreement protocol which has noticeable correlation and overwhelming security without increasing the number of rounds (via parallel repetition and privacy amplification [12, 13] ).
Claim 3. If F is a weak PRF, then G is a weak PRF.
Proof. We have to show that for any polynomial q(.) and
are indistinguishable from random. Sample
As F is a weak PRF, the five tuples given by (8) are indistinguishable from random. We will now show that (8) is indistinguishable from (7) . First note that R(x 1 ), . . . , R(x q ) has the same distribution as x 1 , . . . , x q , unless x i = x j for some i = j, as q is polynomial and |X | is superpolynomial, the probability of this event is negligible. So we can safely replace R(x i ) in (7) with x i in (8) .
Similarly, we can replace R(F(k, x i )) with x i as this will make no difference unless F(k, x i ) = F(k, x j ) or F(k, x i ) = x j for some i = j, which only happens with negligible probability.
Claim 4. If F is a weak PRF, then H and H are weak PRFs.
Proof. That H is weakly pseudorandom follows directly from the fact that G is weakly pseudorandom (as shown by the previous claim). To show that H is weakly pseudorandom, we show that, for random x 1 , . . . , x q ∈ X n , the tuples
are indistinguishable from random. For this, it is sufficient by the triangle inequality, to show the following two facts. First, for random x 1 , . . . , x q ∈ X n , the tuples
are indistinguishable from (9), since F is a weak PRF and thus F(k, x i ) can be replaced by a random x i . That (10) is indistinguishable from random follows directly from the fact that F is a weak PRF.
Claim 5. BitAgreement2(n) has non-negligible correlation φ(n) − negl(n),
with φ as in (6) .
where the second last step follows as G is a weak PRF (as shown in Claim 3).
Proof. Consider any efficient adversary E who can observe the communication C = {r q , s q , t q , y q } between Alice and Bob . If b B = 0, then C has the same distribution as generated by H, and if b B = 1, then C has the same distribution as generated by H. The security now follows as an efficient E cannot distinguish H from H, since these are both weak PRFs (as shown in Claim 4). More formally,
Proof (of Theorem 2).
The theorem follows from Claim 5 and 6, and the fact that one can construct a key-agreement protocol from any bit-agreement protocol which has noticeable correlation and overwhelming security without increasing the number of rounds (via parallel repetition and privacy amplification [12, 13] ).
Can We Efficiently Deconstruct "Useful" Properties?
Black Box Falsification. What does it mean that some statement "holds in Minicrypt"? Trivially, it means that in order to falsify the statement, we must assume the existence of something at least as strong as key-agreement. As observed in [24] , the fact that no black-box reduction one-way functions to key-agreement exists [18] , implies that no "black-box falsification" for such statements can exist (in [24] this was called a "black-box break"). E.g. by Theorem 2, there is no black-box reduction from one-way functions to a weak PRF and a distinguisher, such that the distinguisher breaks the security of the construction given by (1) when instantiated with this weak PRF.
8
Deconstructing the Homomorphic Property. We showed that the statements of the theorems from this paper are non-trivial, by showing that they do no longer hold outside Minicrypt, or more precisely under the standard DDH assumption (which is false in Minicrypt as it implies key-agreement). These counterexamples use the homomorphic property of the group, i.e. that (
a . This is eminent in (2) which shows that the construction given by (1) does not give secure range extension outside of Minicrypt. Usually, a weak PRF which is homomorphic is a very useful thing to have, but clearly not if we want to use this PRF in the construction given in (1) . In order to safely use a weak PRF in (1), all we have to make sure is, that the protocol from Figure 2 is NOT a secure bit-agreement protocol. Intuitively, that should not be too hard.
Open Problem 1. Is there an efficient construction φ, such that for any weak PRF F, φ(F) is a weak PRF but the protocol from Figure 2 is NOT a secure bitagreement protocol when instantiated with φ(F) (and thus (1) is a secure range extension for φ(F)).
We can solve the above problem by first constructing a PRG from the weak PRF and then using the GGM reduction [9] to get a regular PRF (note that (1) is trivially secure for PRFs), but this is not really efficient: each evaluation of the PRF would make a linear (in the input length) number of invocations to the weak PRF. The above problem is somewhat antipodal to questions usually asked in cryptography, where one tries to construct something useful, like asking "can we construct key-agreement from PRFs via black-box reductions" (the answer is no [18] ). Whereas here we are looking for a way to make some particular construction insecure. Being more ambitious, we can ask if we can efficiently destroy any property of a weak PRF which could be used to get a key-agreement protocol.
Open Problem 2. Is there an efficient construction φ, such that for any weak PRF F, φ(F) is a weak PRF and any construction which is secure in Minicrypt when instantiated with a weak PRF, is secure (in the real world) when instantiated with φ(F)?
The general problem can be summarized as follows. We know several constructions for extending the range of weak PRFs, getting public-coin weak PRFs from secret-coin weak PRFs 9 , and achieving adaptive security from non-adaptive PRFs [24, 19] , that one can show to be secure in Minicrypt, but which are (under standard assumptions) not secure in the real world. As the constructions are secure in Minicrypt, each weak/non-adaptive PRF for which the construction actually is insecure can be used to construct a key-agreement protocol (via some particular black-box construction), and must hence have a lot of structure. The question is whether there is an efficient way to modify the weak/non-adaptive PRF, such that it still keeps its original security guarantee (of being a weak/nonadaptive PRF), but cannot be used anymore for the key-agreement protocols. Then this modified PRF can safely be used in the efficient constructions that have been proven to be secure in Minicrypt.

{'paper_id': '118835764', 'title': 'Weak Pseudorandom Functions in Minicrypt', 's2_url': 'https://api.semanticscholar.org/CorpusID:118835764', 'source': 'S2ORC'}