# Polynomial Interpolation of the Naor-Reingold Pseudo-Random Functions

Get Complete Project Material File(s) Now! »

## Pseudo-random functions

Suppose Alice wishes to authenticate herself to Bob, by proving she knows a secret that they share. With a PRG, they could proceed as follows. They both seed a PRG with the shared secret. Bob picks and sends to Alice some random number i, and Alice proves she knows the share secret by responding with the ith random number generated by the PRG. But this solution requires state, and they both have to compute i random numbers. Instead, we would like random access to the sequence. This is the intuition behind pseudo-random functions: Bob gives to Alice some random i, and Alice returns FK (i), where FK is indistinguishable from a random function. The notion of pseudo-random function family generalizes the notion of a pseudorandom generator.
In cryptography, a pseudo-random function family is a collection of functions (that can be evaluated eﬃciently using a secret-key) with the property that an adversary cannot eﬃciently observe any significant diﬀerence between the input-output behavior of a random instance of the family or that of a random function.
More formally, we consider collections of functions {Fn : Kn × Dn → Rn}n∈N that can be evaluated by a (deterministic) polynomial-time Turing Machine. We define an adversary as a (non-uniform) probabilistic polynomial-time oracle Turing machine with either access to:
• an oracle implementing a function F : Dn → Rn defined by picking uniformly at random a secret-key k ∈ Kn such that F (m) = Fn(k, m) for any m ∈ Dn;
• or an oracle simulating a truly random function F : Dn → Rn (i.e. whose outputs are sampled uniformly and independently at random).
This adversary can decide which queries to make to the oracle, perhaps based on answers received to previous queries and eventually, it outputs a single bit (which is its decision as to which function the oracle is implementing). The advantage of the adversary is the function of n defined as the diﬀerence of the probabilities (taken over the random choices made by the adversary and the oracle) that the adversary outputs 1 in the two cases. A collection of functions {Fn : Kn × Dn → Rn}n∈N is a pseudo-random function family if and only if no polynomial time adversary with advantage asymptotically larger than the inverse of a polynomial exists.
By combining the results of Goldreich, Goldwasser and Micali [GGM84] and Goldreich and Levin [GL89], the following result is known:
Theorem 1.2.1. Pseudo-random functions exist if and only if one-way functions exist.

Constructions

Pseudo-random functions from pseudo-random generators

Pseudo-random generators can be used to construct pseudo-random functions by the con-struction proposed by Goldreich, Goldwasser and Micali [GGM84]. Let G : {0, 1}s → {0, 1}2s be a PRG. Define G0, G1 to be the left and right halves of G, so that G(x) = G0 (x)||G1 (x), for x ∈ {0, 1}s, where || denotes the concatenation of G0(x) and G1(x) . For any secret key k ∈ {0, 1}s, define Fk : {0, 1}n → {0, 1}s by Fk(x1 . . . xn) = Gxn (Gxn−1 (. . . (Gx2 (Gx1 (k))))).
If G is a pseudo-random generator, then F : {0, 1}s × {0, 1}n → {0, 1}s is a pseudo-random function.

Number-theoretic constructions

The Goldreich, Goldwasser and Micali construction is ineﬃcient so many direct constructions were proposed based on some hard problems.
• Naor-Reingold PRF. In 1997, Naor and Reingold [NR97; NR04] proposed a (candidate) pseudo-random function family which takes inputs in {0, 1}n (for some parameter n) and outputs an element in some (multiplicatively written) group G of prime order ` with generator g. The secret key is an n-dimensional vector a = (a1, . . . , an) ∈ ((Z/`Z)∗)n and the Naor-Reingold function is defined as:
fa : {0, 1}n −→ G n xi (x1, . . . , xn) 7−→ fa(x1, . . . , xn) = g Qi=1 ai mod `
The evaluation of fa is thus eﬃcient since it consists only in n modular multiplications in Z/`Z and one modular exponentiation in G. It is shown in [NR97; NR04] that the Naor-Reingold function is pseudo-random provided that certain standard cryptographic assumptions about the hardness of breaking the Decision Diﬃe-Hellman assumption holds. In cryptography, two interesting choices for G are a subgroup of the multiplicative group of a (prime) finite field and a subgroup of the points of an elliptic curve defined over a finite field. To lighten the notation, given an n-dimensional vector a = (a1, . . . , an) ∈ ((Z/`Z)∗)n and a variable x that will denote indiﬀerently an n-bit string (x1, . . . , xn) ∈ {0, 1}n or an integer x ∈ {0, 1, . . . , 2n−1} (which implicitly defines (x1 , . . . , xn) ∈ {0, 1}n the bit representation of x with extra leading zeros if necessary), we denote ax the element in F` defined by ax = ax11 • • • axnn mod `. With this notation, the Naor-Reingold function is simply defined by fa(x) = gax . Since proving that the Decision Diﬃe-Hellman assumption holds seems currently to be out of reach, several number-theoretic properties and complexity measures have been studied for the Naor-Reingold pseudo-random functions over finite fields as well as over elliptic curves: distribution (see [LSW14; Shp00b] and references therein), linear complexity (see [CGS10; GGI11; Shp00a; SS01]) and non-linear complexity (see [BGLS00]). These results are incomparable but they all support the assumption of the pseudo-randomness of the Naor-Reingold function.
• Dodis-Yampolskiy PRF. In 2005, Dodis and Yampolskiy [DY05] proposed an eﬃcient pseudo-random function family which takes inputs in {1, . . . , d} (for some parameter d ∈ N) and outputs an element in a group G (multiplicatively written) of prime order t with generator g. The secret key is a scalar x ∈ Z∗t and the pseudo-random function is defined by:
Vx : {1, . . . , d} −→ G
m 7−→ Vx(m) = g if x + m 6= 0 mod t and 1G otherwise.
x+m
The Dodis-Yampolskiy pseudo-random function family has found numerous applica-tions in cryptography (e.g., for compact e-cash [CHL05] or anonymous authentication [CHK+06]). Dodis and Yampolskiy showed that their construction is a verifiable random function (that is a pseudo-random function that provides a non-interactively verifiable proof for the correctness if its output) and has some very attractive security properties, provided that some assumption about the hardness of breaking the so-called Decision Diﬃe-Hellman Inversion problem holds in G [DY05]. In practice, two in-teresting choices for the group G are a subgroup of the multiplicative group of any finite field (in particular, for the so-called verifiable Dodis-Yampolskiy pseudo-random function in groups equipped with a bilinear map [DY05]) or a subgroup of points of an elliptic curve defined over a prime finite field. Very few results supporting the Decision Diﬃe-Hellman Inversion assumption hardness were proven (contrary to the Naor-Reingold pseudo-random function family [NR04] for which numerous results are known, e.g. distribution [LSW14], linear complexity [GGI11] and non-linear complexity [BGLS00]).

### Applications of pseudo-random functions

Pseudo-random functions have many applications in cryptography:
• they can be used for secret-key encryption as follows: Given a PRF F , pick random r, then for a secret key k and a message m, the ciphertext is Ek(m) = (Fk(r) ⊕ m, r). If F is a PRF, then E is semantically secure.
• they can be used to construct a secure block cipher by using the Luby-Rackoﬀ con-struction.
• they can be used as message authentication codes (MACs) [Gol04, Chapter 1]: M ACk(m) = Fk(m).
• they can also be used for key-exchange.

Our results

Polynomial Interpolation of the Naor-Reingold Pseudo-Random Functions

The polynomial interpolation is a question which is well studied for cryptographic believed hard functions to support their hardness. For breaking a hard function, it would be suﬃcient to have an easy multivariate polynomial f (namely a polynomial of low degree and low weight (the number of non-zero coeﬃcients of the polynomial) which is eﬃciently computable) and which from some known information can approximate the function. For instance, for the Computational Diﬃe-Hellman assumption, given an element g of order ` such a polynomial could satisfy the relation:
f(gx, gy) = gxy, for all (x, y) ∈ S, for a large subset S ⊆ {0, . . . , ` − 1}2. Lower bounds on the degree or weight of polynomials interpolating the discrete logarithm problem (see [CS00]) or the Computational and Decision Diﬃe-Hellman assumption (see [MS01; Win01; KW04; Shp03] and references therein) are known. In order to break the security of the Naor-Reingold function, it would be suﬃcient to have a k-variate polynomial f over a finite field (of low degree or low weight) with k ≥ 1 which reveals information on the functions values that is a k-variate polynomial f satisfying:
(f(gax1 , . . . , gaxk ) = gaxk+1 , for all a = (a1, . . . , an) S for a large subset S (F`∗)n, and for some known values x1, . . . , xk+1 ∈ {0, • • • , 2n − 1}) or (f(ga , ga 1 , . . . , ga t k−1 ) = ga k ∈ xx+t x x+t ⊆+ for many integers x ∈ {0, 1, . . . , 2n − 1}, and for some known values t1, . . . , tk and for some known secret key a). We refer the first case to the polynomial interpolation with variable secret key and the second case to the polynomial interpolation with fixed secret key. Our first constribution [MV17c; MV17b] is that low weight or degree k-variate polynomial cannot reveal information on the functions values. We consider the settings of a finite field and an elliptic curve and in both cases, we obtain lower bounds on the degree of polynomials interpolating the Naor-Reingold function with a fixed secret key and variable secret key.

Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function

The second contribution [MV16] of this thesis is about the distribution of the Dodis-Yampolskiy pseudo-random function over finite fields and over elliptic curves and the lower bounds on the degree of polynomials which interpolate these functions.
We prove that for almost all values of parameters, the Dodis-Yampolskiy pseudo-random function produces a uniformly distributed sequence. Our result is based on some recent bounds on character sums with exponential functions. We also prove that a low-degree univariate polynomial cannot reveal the secret key x when evaluated at Vx(m) (for some integer m ∈ {1, . . . , d}) for all x. These results can be regarded as first complexity lower bounds on the pseudo-randomness of the Dodis-Yampolskiy function families.

READ  Sources of biological diversity and randomness

#### Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves

As a third contribution [Mef16], we analyze the security of the elliptic curve linear congruential generator and of the elliptic curve power generator. We infer the EC-LCG sequence and the EC-PG sequence using Coppersmith’s method for calculating the small roots of multivariate polynomials modulo an integer. In the case where the composer is known, we showed that the EC-LCG is insecure if a proportion of at most 1/5 of the least significant bits of two consecutive values U0 and U1 of the sequence is hidden. This improves the previous bound 1/6 of Gutierrez and Ibeas [GI07]. We further improve this result by considering several consecutive values of the sequence. We showed that the EC-LCG is insecure if a proportion of at most 3/11 of the least significant bits of these values is hidden. To prevent the attacks of [GI07], one could output only the most significant bits of the abscissa of consecutive multiple values Ukn (for some fixed integer k) of the sequence. We consider this setting and use summation polynomials to infer the EC-LCG. These polynomials were used to solve elliptic curve discrete logarithm problem and we use it in this thesis to infer the EC-LCG when the attacks of [GI07] cannot work. We then showed that the EC-LCG is insecure if a proportion of at most 1/8 of the least significant bits of two values X(U0) and X(Uk) is hidden, where X(P ) denotes the abscissa of the point P on the curve. We further improve this result by considering several values Ukn, n ∈ N of the sequence. We showed that the EC-LCG is insecure if a proportion of at most 1/4 of the least significant bits of the abscissa of these values is hidden. In the case where the composer is unknown, we showed that the EC-LCG is insecure if a proportion of at most 1/24 of the least significant bits of two consecutive values U0 and U1 of the sequence is hidden. This improves the previous bound 1/46 of Gutierrez and Ibeas [GI07]. We further improve this result by considering suﬃciently many consecutive values of the sequence. We showed that the EC-LCG is insecure if a proportion of at most 1/8 of the least significant bits of these values is hidden. Finally, we also showed that the EC-PG is insecure if a proportion of at most 1/2e2 of the least significant bits of the abscissa of two consecutive values V0 and V1 of the sequence is hidden. We improve this bound by considering several consecutive values of the sequence and we showed that the EC-PG is insecure if a proportion of at most 1/e2 of the least significant bits of the abscissa of these values is hidden. To our knowledge such a result is not known in the literature for the EC-PG.

Lattice Attacks on Pairing-Based Signatures

The pairing-based signature schemes are very well-suited for resource-limited devices since they produce short signatures and their generation involves only one scalar multiplication on an elliptic curve. In the recent years, theoretical attacks against elliptic curves have shown little improvements whereas side-channel attacks became a major threat against elliptic curves implementations [Koc96; KJJ99]. These attacks are based on information gained from the physical leakage of a cryptosystem implementation (such as timing information, power consumption or electromagnetic leaks). For public-key cryptography on embedded systems, the core operation is usually group exponentiation – or scalar multiplication on elliptic curves – which is a sequence of group operations derived from the private-key that may reveal secret bits to an attacker (on an unprotected implementation). This can be the case when computing the exponent in order to compute the output of the Dodis-Yampolskiy pseudo-random function and more generally in well-known pairing-based signatures (Sakai-Kasahara signatures [SK03], Boneh-Boyen signatures [BB04a] and Gentry signatures [Gen06]) based on the exponent-inversion framework. Our last contribution [MV17a] is concerned with lattice attacks on these well-known Pairing-Based signatures and our approach is similar to lattice attacks [HS01; NS02; NS03] combined with template attacks [MHMP13] that were proposed against the standardized signature scheme DSA and ECDSA. We present lattice-based polynomial-time (heuristic) algorithms that recover the signer’s secret in popular pairing-based signatures when used to sign several messages under the assumption that blocks of consecutive bits of the corresponding exponents are known by the attacker. Our techniques relies upon Coppersmith’s methods and apply to all signatures in the so-called exponent-inversion framework in the standard security model (i.e. Boneh-Boyen and Gentry signatures) as well as in the random oracle model (i.e. Sakai-Kasahara signatures). The eﬃciency of our (heuristic) attacks has been validated experimentally.

Organization

This thesis is divided in two parts. The first part deals with some complexities measures of Naor-Reingold and Dodis-Yampolskiy Pseudo-Random Function and the second part deals with lattice attacks on pseudo-random generators and on pairing-based signatures based on exponent-inversion framework. The first part includes Chapters 2 , 3 and 4. Chapter 2 introduces some mathematical notions used throughout this thesis. Chapter 3 study the polynomial interpolation of the Naor-Reingold pseudo-random functions. Chapter 4 is about the distribution and polynomial interpolation of the Dodis-Yampolskiy pseudo-random function. The second part includes Chapters 5, 6 and 7. Chapter 5 provides short descriptions of Coppersmith’s methods and some analytic combinatorics to ease the methods. Chapter 6 presents the attacks on the linear congruential generator and the power generator on elliptic curves and Chapter 7 deals with lattice attacks on some pairing-based signatures. Finally, Chapter 8 concludes this thesis and raises some open questions.

1. Introduction
1.1. Pseudo-random generators
1.1.1. Constructions
1.1.2. Applications
1.2. Pseudo-random functions
1.2.1. Constructions
1.2.2. Applications of pseudo-random functions
1.3. Our results
1.3.1. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Functions
1.3.2. Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function
1.3.3. Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves
1.3.4. Lattice Attacks on Pairing-Based Signatures
1.4. Organization
I. Complexity Measures of Pseudo-Random Functions
2. Preliminaries
2.1. Notation
2.2. Finite fields
2.3. Elliptic Curves
2.3.1. Definition and addition law
2.3.2. Division polynomials of elliptic curves
2.3.3. Summation polynomials
2.4. Exponential Sums
2.4.1. Finite Fields and Exponential Sums
2.4.2. Elliptic Curves and Exponential Sums
2.5. Polynomial Approximation of the Discrete Logarithm
3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Functions
3.1. Naor-Reingold pseudo-random function
3.2. Auxiliary results
3.3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Finite Fields
3.3.1. Polynomial Interpolation with variable secret key
3.3.2. Polynomial Interpolation with fixed secret key
3.4. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Elliptic Curves
3.4.1. Polynomial Interpolation with fixed secret key
3.4.2. Polynomial Interpolation with variable secret key
4. Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function
4.1. Distribution of the Dodis-Yampolskiy Pseudo-Random Functions
4.1.1. Distribution of the Dodis-Yampolskiy Pseudo-Random Function over Finite Fields
4.1.2. Distribution of the Dodis-Yampolskiy Pseudo-Random Function over Elliptic Curves
4.2. Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function over Finite Fields
4.3. Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function over Elliptic Curves
II. Lattice-Based Cryptanalysis of Pseudo-Random Generators and Signatures
5. Preliminaries
5.1. Coppersmith’s methods
5.1.1. First method
5.1.2. Second method
5.2. Analytic Combinatorics
5.2.1. Introduction
5.2.2. Combinatorial Classes, Sizes, and Parameters
5.2.3. Counting the Elements: Generating Functions
5.2.4. Counting the Parameters of the Elements: Bivariate Generating Functions
5.2.5. Counting the Parameters of the Elements up to a Certain Size
5.2.6. Asymptotic Values: Transfer Theorem
5.3. Some useful applications of the technique
5.3.1. Counting the Bounds for the Monomials (Useful Examples)
5.3.2. Counting the Bounds for the Polynomials
6. Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves
6.1. Linear Congruential Generator and Power Generator on Elliptic Curves
6.2. Predicting EC-LCG Sequences for Known Composer
6.3. Predicting EC-LCG Sequences for Unknown Composer
6.3.1. Complexity of the attack
6.4. Predicting the Elliptic curve power generator
7. Lattice Attacks on Pairing-Based Signatures
7.1. Sakai-Kasahara, Boneh-Boyen and Gentry’s Pairing-Based Signatures Schemes
7.2. Lattice Attack On Gentry Signatures
7.2.1. Gentry Signatures
7.2.2. Description of the Attack
7.2.3. Experimental Results
7.3. Concrete Attack Examples against Gentry signatures
7.4. Lattice Attack on Boneh-Boyen Signatures
7.4.1. Boneh-Boyen Signatures
7.4.2. Description of the Attack
7.4.3. Experimental results
7.5. Lattice Attack on Sakai-Kasahara Signatures
7.5.1. Sakai-Kasahara Signatures
7.5.2. Description of the Attack
7.5.3. Experimental results
8. Conclusion and Open Questions
8.1. Conclusion
8.2. Open questions
Bibliography

GET THE COMPLETE PROJECT