Thierry Mefenza Nountu

Damien Vergnaud

Marcel Tonga

Michel Abdalla

Balthazar Bauer

Sonia Belaïd

Fabrice Benhamouda

Florian Bourse

Céline Chevalier

Jérémy Chotard

Mario Cornejo

Edouard Dufour Sans

Angelo De Caro

Geoffroy Couteau

Rafaël Del Pino

Aurélien Dupin

Pierre-Alain Dupont

Pooya Farshim

Houda Ferradi

Pierre-Alain Fouque

Georg Fuchsbauer

Romain Gay

Dahmun Goudarzi

Aurore Guillevic

Chloé Hébant

Julia Hesse

Hieu Duong

Louiza Phan

Pierrick Khati

Michele Méaux

David Minelli

Anca Naccache

Michele Nitulescu

Alain Orrù

Thomas Passelègue

David Peters

Thomas Pointcheval

Răzvan Prest

Mélissa Roşie

Sylvain Rossi

Adrian Ruhault

Bogdan Thillard

Damien Ursu

Hoeteck Vergnaud

Wee

Je Remercie Également

Marie Bivard

Isabelle Delais

Joëlle Isnard

Sophie Jaudon

Valérie Mongiat

Ludovic Ricardou

Etienne Assongmo

Hortense Boudjou

Serges Feukoua

Emmanuel Fouotsa

Alexandre Fotué

Albert Kadji

Maurice Kianpi

Blaise Koguep

Celestin Lélé

Cristophe Mouaha

Celestin Ndjeya

Bertrand Nguefack

Celestin Nkuimi

Amina Pecha

Hervé Tallé

Yannick Tenkeu

Daniel Tieudjo

Roméo Tioffo

Pseudo-Random Generators and Pseudo-Random Functions: Cryptanalysis and Complexity Measures

Keywords:

Randomness is a key ingredient in cryptography. For instance, random numbers are used to generate keys, for encryption and to produce nonces. They are generated by pseudo-random generators and pseudo-random functions whose constructions are based on problems which are assumed to be difficult. In this thesis, we study some complexity measures of the Naor-Reingold and Dodis-Yampolskiy pseudo-random functions and study the security of some pseudo-random generators (the linear congruential generator and the power generator on elliptic curves) and some pairing-based signatures based on exponent-inversion framework.

We show that the Dodis-Yampolskiy pseudo-random functions is uniformly distributed and that a low-degree or low-weight multivariate polynomial cannot interpolate the Naor-Reingold and Dodis-Yampolskiy pseudo-random functions over finite fields and over elliptic curves. The contrary would be disastrous since it would break the security of these functions and of problems on which they are based. We also show that the linear congruential generator and the power generator on elliptic curves are insecure if too many bits are output at each iteration.

Practical implementations of cryptosystems often suffer from critical information leakage through side-channels. This can be the case when computing the exponentiation 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, Boneh-Boyen signatures and Gentry signatures) based on the exponent-inversion framework. We present lattice-based polynomial-time (heuristic) algorithms that recover the signer's secret in the pairing-based signatures when used to sign several messages under the assumption that blocks of consecutive bits of the exponents are known by the attacker.

La réalisation de cette thèse n'aurait pas été possible sans le support inconditionnel de certaines personnes dont je ne peux décrire ici en quelques mots le rôle capital qu'elles ont pu jouer pour me permettre d'arriver à cette fin. Ainsi, j'adresse de tout mon coeur mes remerciements aux personnes qui m'ont aidées, encouragées, motivées afin de permettre la réalisation de cette thèse et je m'excuse d'avance auprès de ceux que j'ai oubliés.

Je remercie très chaleureusement mes directeurs de thèse Damien Vergnaud et Marcel Tonga d'avoir accepté d'encadrer cette thèse. Pendant ces trois années vous m'avez initié à la recherche, guidé dans mon travail, appris a être autonome, encouragé quand j'étais moins optimiste, énormément conseillé et je vous en suis très reconnaissant pour tout cela. Je voudrais remercier particulièrement Damien qui en plus de l'encadrement, a toujours été là pour m'aider lorsque j'avais des problèmes de visa et qui malgré parfois le fait que je sois au Cameroun, n'hésitait pas à travailler avec moi par Skype. Je le remercie également pour son aide pour l'obtention du financement qui m'a permis de terminer cette thèse dans des meilleures conditions.

J'adresse mes sincères remerciements à David Pointcheval qui m'a accueilli dans l'équipe Crypto de l'ENS et mis à ma disposition tout le matériel nécessaire pour la réalisation de ce travail.

Je remercie de tout coeur Sylvain Duquesne qui m'a mis en contact avec Damien et qui m'a invité en France pour la première fois en 2013 afin de discuter d'un éventuel sujet de thèse avec Damien.

Rapporter une thèse n'est pas toujours une chose facile car cela nécessite de la volonté, du temps et de la disponibilité. Ainsi, je voudrais remercier mes deux rapporteurs Sylvain Duquesne et Guénaël Rénault pour avoir lu attentivement et commenté cette thèse. Je témoigne aussi ma gratitude envers les autres membres de jury

Résumé

L'aléatoire est un ingrédient clé en cryptographie. Par exemple, les nombres aléatoires sont utilisés pour générer des clés, pour le chiffrement et pour produire des nonces. Ces nombres sont générés par des générateurs pseudo-aléatoires et des fonctions pseudo-aléatoires dont les constructions sont basées sur des problèmes qui sont supposés difficiles. Dans cette thèse, nous étudions certaines mesures de complexité des fonctions pseudo-aléatoires de Naor-Reingold et Dodis-Yampolskiy et étudions la sécurité de certains générateurs pseudo-aléatoires (le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques) et de certaines signatures à base de couplage basées sur le paradigme d'inversion.

Nous montrons que la fonction pseudo-aléatoire de Dodis-Yampolskiy est uniformément distribué et qu'un polynôme multivarié de petit dégré ou de petit poids ne peut pas interpoler les fonctions pseudo-aléatoires de Naor-Reingold et de Dodis-Yampolskiy définies sur un corps fini ou une courbe elliptique. Le contraire serait désastreux car un tel polynôme casserait la sécurité de ces fonctions et des problèmes sur lesquels elles sont basées. Nous montrons aussi que le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques sont prédictibles si trop de bits sont sortis à chaque itération.

Les implémentations pratiques de cryptosystèmes souffrent souvent de fuites critiques d'informations à travers des attaques par canaux cachés. Ceci peut être le cas lors du calcul de l'exponentiation afin de calculer la sortie de la fonction pseudo-aléatoire de Dodis-Yampolskiy et plus généralement le calcul des signatures dans certains schémas de signatures bien connus à base de couplage (signatures de Sakai-Kasahara, Boneh-Boyen et Gentry) basées sur le paradigme d'inversion. Nous présentons des algorithmes (heuristiques) en temps polynomial à base des réseaux qui retrouvent le secret de celui qui signe le message dans ces trois schémas de signatures lorsque plusieurs messages sont signés sous l'hypothèse que des blocs consécutifs de bits des exposants sont connus de l'adversaire.

v -

Introduction

Cryptography can be defined as the practice and study of techniques for secure communication in the presence of third parties called adversaries or eavesdroppers. Today, cryptography is very present in our daily life: emails, credit cards, electronic banking, online shopping, secure network communications, authentications, etc. The main goals of cryptography is to ensure privacy, integrity and authenticity. Suppose two people usually called Alice and Bob want to communicate through an insecure channel in the presence of an adversary called Eve. If Alice is the sender (the person who sends the message also called the plaintext) and Bob the receiver (the person who receives the message), then providing privacy means that the message sent by Alice to Bob should be hidden from Eve. Providing authenticity or integrity means that one wants Bob, upon receiving a communication supposed to be from Alice, to have a way of assuring itself that it really did originate from Alice and was not sent by Eve, or modified along the road by Eve. To achieve these goals (privacy, authenticity and integrity), Alice and Bob are supplied with a set of algorithms also called a protocol or a scheme or a cryptosystem. There is an algorithm for the sender to run also called the encryption algorithm that allow him to encrypt the message he wants to send (the encrypted message is also called the ciphertext) and an algorithm for the receiver that allows him to decrypt the ciphertext and get the message together if possible with an associated message telling him whether or not to regard it as authentic. These algorithms depends on some cryptographic keys (the key used to encrypt a message must be known to the sender and the one used to decrypt must be known to the receiver). The modern cryptography can be divided into two areas of study:

• Secret-key or symmetric cryptography: secret-key cryptography refers to encryption and decryption algorithms in which both the sender and the receiver share the same key (or, less commonly, in which their keys are different, but related in an easily computable way). This was the only kind of encryption publicly known until June 1976.

• Public-key or asymmetric cryptography: A significant disadvantage of symmetric cryptography is the key management necessary to use them securely. Specifically, each distinct pair of communicating parties must share a different key. The number of keys required increases as the square of the number of network members, which very quickly requires complex key management schemes to keep them all consistent and secret. The difficulty of securely establishing a secret key between two communicating parties, when a secure channel does not already exist between them is then a considerable practical obstacle for cryptography users in the real world. The idea of public-key cryptography Chapter 1. Introduction is due to Diffie and Hellman in 1976 [START_REF] Diffie | New directions in cryptography[END_REF]. In the public-key setting, a party possesses a pair of keys: a public key also denote pk (which is used by a sender to send a message to the party) and an associated secret key also denoted sk (which is used by the party to decrypt all the messages encrypted with his public key). A party's public key is made publicly known and bound to its identity. For example, a party's public key might be published in a phone book. A party's secret key is kept secret. The computation of one key (the private key) is computationally infeasible from the other (the public key), even though they are necessarily related. Most public-key algorithms involve operations such as modular multiplication and exponentiation in groups, which are much more computationally expensive than the operations use in most secret-key algorithms. So in practice, a fast symmetric-key protocol is used to secure communications and public-key protocols to share the secret key used.

The following question can then be addressed:

What is a secure protocol?

Perfect security. Intuitively, a secure protocol is one for which an encrypted message remains well hidden even after seeing its encryption. In other words, an encryption algorithm is perfectly secure if a ciphertext produced using it provides no information about the plaintext without knowledge of the key. That is, it cannot be broken even when the adversary has unlimited computing power. The adversary simply does not have enough information to break the encryption scheme. The one-time pad (given a n-bit string message m and a n-bit string key k, the ciphertext is simply c = m ⊕ k, where ⊕ denotes the bit-Xor) is known to achieve the perfect security. However, the one-time pad is not very practical, in the sense that the key must be as long as the message: if Alice wants to send a 10 GB file to Bob, they must already share a 10 GB key. Unfortunately, this cannot be avoided since it is proven that any perfectly secure cipher must have a key space at least as large as its message space. This fact provides the motivation for developing a definition of security for which the message remains well hidden but in the presence of limited computing power adversaries, and which allows one to encrypt long messages using short keys. Many other notions of security (for instance the semantic security) were then introduced and allow us to build secure schemes that use reasonably short keys.

Computational-complexity theory By considering weaker notions of security, modern cryptography now introduces adversaries who have limited computing power (probabilistic polynomial time adversaries). For practice purposes, symmetric and asymmetric primitives have security as long as adversaries do not have too much computing time. These primitives are breakable in principle but not in practice and are most often based on the computational complexity of hard problems, often from number theory. Among the hard problems we have:

• Discrete logarithm problem (DLP). Let g be a generator of a group G (denoted multiplicatively) of order q. Given g, h, the discrete logarithm problem is to find a such that h = g a . The DLP difficulty depends on the choice of the group G. 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. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz [N K87] in 1987 and by Victor S. Miller [Mil86] in 1985. Elliptic curves are increasingly used to instantiate public-key cryptography protocols, for example encryption, digital signatures, pseudo-random generators, key agreement and other tasks. They are also used in several integer factorization and primality testing algorithms that have applications in cryptography. The DLP takes sub-exponential time in F p and is even harder in the present state (with exponential time) in elliptic curves E(F p ) (we recall that if E is an elliptic curve over the finite field F p , P and Q are points in E(F p ), the elliptic curve discrete logarithm problem consists in finding n ∈ N such that Q = [n]P ). The size of the elliptic curve determines the difficulty of the problem. The primary benefit promised by elliptic curve cryptography is a smaller key size, reducing storage and transmission requirements i.e. that an elliptic curve group could provide the same level of security afforded by an RSA-based system with a large modulus and correspondingly larger key. For example a 256-bit elliptic curve public key should provide the same level of security as a 3072-bit RSA public key. The last record in solving the discrete logarithm problem (16 June 2016), using the number field sieve, is the computation of a discrete logarithm modulo a 232-digit prime which roughly corresponds to the factoring of a 768-bits safe prime. The hardness of the DLP is the foundation of several cryptographic systems (e.g. Diffie-Hellman key agreement [START_REF] Diffie | New directions in cryptography[END_REF], ElGamal encryption and signature [START_REF] Vaudenay | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] or the Schnorr signature [START_REF] Schnorr | Efficient Identification and Signatures for Smart Cards[END_REF]).

• Diffie-Hellman assumptions. Given a cyclic group G (denoted multiplicatively) generated by some element g, the computational Diffie-Hellman assumption states that it is difficult to compute the element g xy from known elements g x and g y (for x and y picked uniformly at random between 1 and the order of G). This assumption is the basis of the Diffie-Hellman key exchange [START_REF] Diffie | New directions in cryptography[END_REF] and the most efficient means known to solve this computational problem is to solve the standard discrete logarithm problem in G.

Unfortunately, even the computational Diffie-Hellman assumption by itself is generally not sufficient to assess the security of protocols proposed and used in cryptography.

Cryptographers have then proposed much stronger assumptions in order to analyze the security of cryptosystems. For instance, the decision Diffie-Hellman assumption [START_REF] Boneh | The Decision Diffie-Hellman Problem[END_REF] states that given a cyclic group G given some elements g, g x and g y , no efficient algorithm can distinguish between g xy and an element picked uniformly at random in G.

This assumption has been used to prove the security of many cryptographic protocols, most notably the ElGamal [START_REF] Vaudenay | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] and Cramer-Shoup cryptosystems [START_REF] Cramer | A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack[END_REF] and in numerous important cryptographic applications.

• Diffie-Hellman inversions assumptions. Given a cyclic group G generated by some element g, and the tuple (g, g x , . . . , g x q ), the q-Diffie-Hellman inversions assumption ( [START_REF] Dodis | A Verifiable Random Function with Short Proofs and Keys[END_REF] and the references there in) states that it is difficult to compute the element g 1/x . This assumption is non-standard and Cheon [START_REF] Hee | Discrete Logarithm Problems with Auxiliary Inputs[END_REF] proved that it is stronger than the classical discrete logarithm assumption in G. A much stronger assumption called the q-decisionnal bilinear Diffie-Hellman inversions assumption [DY05; SK03; BB04a] was proposed. Given a bilinear cyclic group G generated by some element g (that is the group action in G is efficiently computable, there exists a multiplicative group G 1 and an efficiently computable bilinear map e : G × G → G 1 and e(g, g) = 1 G 1 ), and the tuple (g, g x , . . . , g x q ), the q-decisionnal bilinear Diffie-Hellman inversions assumption states that it is difficult to distinguish e(g, g) from a random element. This assumption was shown in [START_REF] Dodis | A Verifiable Random Function with Short Proofs and Keys[END_REF] to be difficult in the generic group model and it was Chapter 1. Introduction used in [START_REF] Sakai | ID based Cryptosystems with Pairing on Elliptic Curve[END_REF][START_REF] Boneh | Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles[END_REF][START_REF] Gentry | Practical Identity-Based Encryption Without Random Oracles[END_REF] to construct secure identity based encryption schemes.

• Integer factorization problem (FACT). Given a positive integer N , the problem is to find its prime factors, i.e., find the pairwise distinct primes p i and positive integer powers e i such that N = p e 1 1 ...p en n . It is generally believed that the most difficult setting for the factorization problem is when N = pq is the product of only two primes p and q of the same large size since the difficulty of the factorization problem is nonuniform (i.e factoring integers N whose second largest prime factor is bounded by a polynomial in log N can be performed in polynomial time). It is straightforward to compute N = pq in O((log N ) 2 ) time and (presumedly) hard to invert this operation when p and q are pairwise distinct primes chosen randomly.

• The RSA Problem . Given (N, e, c) where c ∈ Z N , e an integer and N = pq, the RSA problem is to find x such that c = x e mod N . The RSA scheme relies on the difficulty for solving equations of the form x e = c mod N , where e, c, and N are known and x is an arbitrary number. In other words, the security of RSA relies on the assumption that it is difficult to compute e-th roots modulo N .

The RSA Problem is clearly no harder than the factorization problem since an adversary who can factor N can also compute the private key (p, q, d) from the public key (N, e), where d is an integer satisfying the equation ed = 1 mod (p -1)(q -1). However, so far there are no proofs that the converse is true meaning that the RSA problem is apparently as difficult as factoring: Whether an algorithm for solving the RSA Problem can be efficiently converted into an integer factoring algorithm is an important open problem. However, Boneh and Venkatesan [START_REF] Boneh | Breaking RSA May Not Be Equivalent to Factoring[END_REF] have given evidence that such a reduction is unlikely to exist when the public exponent is very small, such as e = 3 or 17.

It is important to know which parameter sizes to choose when the RSA problem serves as the foundation of a cryptosystem. The current record for factoring general integers was announced on December 12 in 2009, by a team including researchers from CWI, EPFL, INRIA and NTT. The consortium factored the RSA-768 (232-digit number) using the number field sieve (NFS) [START_REF] Kleinjung | Factorization of a 768-Bit RSA Modulus[END_REF]. This effort required the equivalent of almost 2000 computing years on a single core 2.2 GHz AMD Opteron. Now the NIST's recommendation is that future systems should use RSA keys with a minimum size of 3072 bits. In 1994, Peter Shor [START_REF] Shor | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[END_REF] introduced a quantum algorithm solving FACT in polynomial time.

These problems are unproven but are assumed to be difficult. And based on these problems, many cryptographic primitives and schemes with provable security have been proposed. These schemes and many other applications require random numbers or bits which are produced by random number and random bit generators, RNGs and RBGs. In cryptography, these generators are employed to:

• produce secret keys: computer cryptography uses integers for keys. The elementary method to read encrypted data without actually decrypting it is a brute force attack ( i.e. simply attempting every number, up to the maximum length of the key). Therefore, it is important to use a sufficiently long key bit length that is unpredictable in order to make the brute force attack impractical.

• encrypt messages: probabilistic encryption is particularly important when using publickey cryptography. Suppose that the adversary observes a ciphertext, and suspects that the plaintext is either "YES" or "NO", or has some information about the plaintext. When a deterministic encryption algorithm is used, the adversary can simply try encrypting each of his guesses under the receiver's public key, and compare each result to the target ciphertext. To prevent this attack, public key encryption schemes must incorporate an element of randomness, ensuring that each plaintext maps into one of a large number of possible ciphertexts.

• produce nonces: a nonce is an arbitrary number used only once in a cryptographic communication. They are used in some authentication protocols, hashing protocols and encryption schemes. Nonces should be unpredictable to ensure the security of the underline protocols.

Random numbers can be generated by true random numbers generators (TRNGs). TRNGs measure some physical phenomenon that is expected to be random and then compensates for possible biases in the measurement process. Example sources include measuring atmospheric noise, thermal noise, and other external electromagnetic and quantum phenomena. For example, cosmic background radiation or radioactive decay or the noise of a semiconductor diode as measured over short timescales represent sources of natural entropy. However TRNGs are often biased, this means for example that on average their output might contain more ones than zeros and therefore does not correspond to a uniformly distributed random variable. This effect can be balanced by different means, but this post-processing reduces the number of useful bits as well as the efficiency of the generator. Another problem is that some TRNGs are very expensive or need at least an extra hardware device. In addition, these generators are often too slow for the intended applications in cryptography. As a solution, cryptographers proposed methods to efficiently generating numbers that look random for adversaries with limited power of computations (probabilistic polynomial time adversaries) by using little or no randomness. Among these methods we have pseudo-random generators and pseudo-random functions.

Pseudo-random generators

Recall that for the one-time pad to be perfectly secure, the key should be as long as the message. However, we would like to use a key that is much shorter. So the idea is to instead use a short -bit seed s as the encryption key, where is much smaller than L ( L being the bit length of the message) and to stretch this seed into a longer, L-bit string that is used to encrypt the message and decrypt the ciphertext. The seed s is stretched using some efficient, deterministic algorithm G that maps -bit strings to L-bit strings. Thus, the key space for this modified one-time pad is {0, 1} , while the message and ciphertext spaces are {0, 1} L . For s ∈ {0, 1} and m, c ∈ {0, 1} L , encryption and decryption are defined as follows: E(s, m) := G(s) ⊕ m and D(s, c) := G(s) ⊕ c. This new scheme is called a stream cipher, and the function G is called a pseudo-random generator. A pseudo-random generator, or PRG for short, is an efficient deterministic algorithm G that, given as input a seed s ∈ S, computes an output r = G(s) ∈ R, where S, R are finite spaces. Our definition of security for a PRG captures the intuitive notion that if s is chosen at random from S and r is chosen at random from R, then no efficient adversary can effectively tell the difference between G(s)

Chapter 1. Introduction and r: the two are computationally indistinguishable. More formally, let G : S → R be a function. We say that G is a secure pseudo-random generator if G is efficiently computable and if for any polynomial-time adversary A, its advantage in the following algorithmic game is negligible. The game starts by picking a random challenge bit b and returns either G(s), for a randomly chosen s ∈ S if b = 0 or r, for a randomly chosen r ∈ R if b = 1. Finally, the adversary outputs a bit b , and its advantage is defined by 2P

Constructions

Many constructions of pseudo-random generators were proposed, some based on unproven but believed hard problems and these pseudo-random generators were proved to be secure if the underlined problem is difficult. Others constructions were proposed based on difficult problems but have not yet been proved to be secure if the underlined problem is difficult.

Proven constructions

• The Blum Blum Shub PRG. This PRG was proposed in 1986 by Blum, Blum and Shub [START_REF] Blum | A Simple Unpredictable Pseudo-Random Number Generator[END_REF]. The following sequence (x n ) is defined:

x n+1 = x 2 n mod N,
where N = pq is the product of two large primes p and q. At each step of the algorithm, some intermediate output which is part of the final output is derived from x n+1 : the intermediate output is commonly either the bit parity of x n+1 or one or more of the least significant bits of x n+1 . The final output is the concatenation of all the intermediate outputs. For instance if one bit is derived at each step, then if L is the bit length of the output of the generator, we will need L steps to actually compute the desired number of bits. The seed x 0 = 1 should be an integer that is coprime to N (i.e. p and q are not factors of x 0 ). Its security relies on the computational difficulty of solving the quadratic residuosity problem which states that given integers a and N = pq, it is difficult to decide whether a is a quadratic residue modulo N or not. When the primes are chosen appropriately, and O(log log N ) least significant bits of each x n are output, then if N is sufficiently large, distinguishing the output bits from random should be at least as difficult as solving the Quadratic residuosity problem modulo N .

• The Blum-Micali PRG. It is due to Blum and Micali [START_REF] Blum | How to Generate Cryptographically Strong Sequences of Pseudorandom Bits[END_REF] and its security relies on the discrete logarithm problem. Let p be an odd prime, and let g be a primitive root modulo p. Let x 0 be a seed, and let:

x n+1 = g xn mod p,
where the exponent x n is seen as an integer in {0, . . . , p -1}. The nth intermediate output of the algorithm is 1 if x n < p-1 2 and 0 otherwise. The final output is the concatenation of all the intermediate outputs.

• Dual-EC PRG. This generator is based on elliptic curve and was released by the National Institute of Standards and Technology (NIST) and the National Security Agency (NSA) in 2006. The basic Dual-EC algorithm works as follows; given a public elliptic curve E and two public points P and Q on E, the following sequences are defined:

s i+1 = x(s i P ), r i+1 = x(s i+1 Q) i ∈ N,
where x(A) denotes the abscissa of a point A, and s 0 is the seed. For each i ≥ 1, some output is derived from r i : for instance, for a n-bit string s 0 , the n least significant bits of r i could be computed at each step. The output of the generator is then the concatenation of the different outputs at each stage. Its security is based on the elliptic curve discrete logarithm problem. After its publication, it was criticized by experts for its poor design (it is very slower, its outputs are biased, it outputs too many bits and it is mathematically guaranteed to have a skeleton key d (with P = dQ) that makes the output entirely predictable to anyone in possession of the key). In 2007 Bruce Schneier wrote an article about Dual-EC in Wired Magazine and a pair of Microsoft researchers Dan Shumow and Niels Ferguson announced at the Crypto rump session in August 2007 that there was a possibility of a back door (secret knowledge that lets you predict outputs) in Dual-EC. By the end of 2007, for the public cryptographic community, Dual-EC was dead and gone. In 2013, The New York Times reported that documents in their possession appear to confirm that the backdoor was real and had been deliberately inserted by the NSA. NIST's list of DRBG (Deterministic Random Bit Generator) validations showed that Dual EC was provided in dozens of commercial cryptographic software libraries. Dual-EC was even the default pseudorandom number generator in RSA Security's BSafe library. How could an algorithm so criticized by the cryptographic community be present in widely used implementations? A partial explanation surfaced in December 2013, when Reuters reported that NSA paid RSA 10 million dollars in a deal that set Dual-EC as the preferred, or default, method for number generation in the BSafe software. In April 21, 2014, NIST withdrew Dual-EC from its draft guidance on random number generators.

Unproven constructions

We have some constructions based on elliptic curves which have not yet been proved to be secure but are widely used in practice:

• the elliptic curve linear congruential generator (EC-LCG). Given a modulus m and a multiplier a relatively prime to m, an increment b and a seed x 0 , the linear congruential generator (LCG) is the sequence x n defined by:

x n+1 = ax n + b mod m.
Chapter 1. Introduction

The elements a, b and m can be secret or not and in order to increase the resistance of the LCG, Knuth [START_REF] Knuth | Deciphering a linear congruential encryption[END_REF] proposed to output only most significant bits of each x n . In 1989, Boyar [START_REF] Boyar | Inferring sequences produced by a linear congruential generator missing low-order bits[END_REF] showed that one can recover the seed of this generator in the bit-size of m if few least significant bits of each x i are discarded when a, b and m are secret. Frieze et al [START_REF] Frieze | Reconstructing Truncated Integer Variables Satisfying Linear Congruences[END_REF] infer the LCG when few most significant bits of each

x n are output for known m and a. Joux and Stern [START_REF] Joux | Lattice reduction: A toolbox for the cryptanalyst[END_REF] proposed a lattice attack on the LCG when few most significant bits of each x n are output even for secret m and a.

Their attack constructs an appropriate lattice from known information and computes the shortest vector in that lattice. Due to the insecurity of the LCG, Hallgren [S H94] proposed in 1994 an elliptic curve analogue of the linear congruential generator known as the EC-LCG. Let E be an elliptic curve defined over a prime finite field F p and G ∈ E(F p ), the EC-LCG is a sequence U n of points defined by the relation:

U n = U n-1 ⊕ G = nG ⊕ U 0 , n ∈ N
where U 0 ∈ E(F p ) is the initial value or seed. We refer to G as the composer of the generator. One can notice that if two consecutive values U n , U n+1 of the generator are revealed, it is easy to find U 0 and G. So only the most significant bits of each coordinate of U n are output, n ∈ N in the hope that this makes the resulting output sequence difficult to predict. In the cryptography setting, the initial value U 0 and the constants G, a and b may be kept secret. Gutierrez and Ibeas [START_REF] Gutierrez | Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits[END_REF] consider two cases: the case where the composer G is known and a, b are kept secret and the case where the composer G is unknown and a, b are kept secret. In the first case, they showed that the EC-LCG is insecure if a proportion of at most 1/6 of the least significant bits of two consecutive values of the sequence is hidden. When the composer is unknown, they showed heuristically that the EC-LCG is insecure if a proportion of at most 1/46 of the least significant bits of three consecutive values of the sequence is hidden. Their result is based on a lattice basis reduction attack, using a certain linearization technique. In some sense, their technique can be seen as a special case of the problem of finding small solutions of multivariate polynomial congruences by using only linear relations on them. The Coppersmith's methods also tackle the problem of finding small solutions of multivariate polynomial congruences by taking products of the polynomials. Gutierrez and Ibeas due to the special structure of the polynomials involved claimed that "the Coppersmith's methods does not seem to provide any advantages", and that "It may be very hard to give any precise rigorous or even convincing heuristic analysis of this approach". We tackle this issue in this thesis.

• the elliptic curve power generator (EC-PG). Given a modulus m, an integer e and a seed v 0 , the power generator (PG) is the sequence v n defined by:

v n+1 = v e n mod m.
The integer e which is typically small (e = 3 or e = 2) is known and m which can be a prime number or an RSA modulus (the products of two prime numbers) can be secret or not. In order to increase the resistance of the PG, only some most significant bits of each v n are output at each iteration. For e = 2 and a prime m of bit-size n, Blackburn et al [START_REF] Gutierrez | Reconstructing noisy polynomial evaluation in residue rings[END_REF] showed that if 2/3n bits are output at each iteration, then they are able to recover the seed. Steinfeld et al [START_REF] Pieprzyk | On the provable security of an efficient RSA-based pseudorandom generator[END_REF] , uses Coppersmith's methods and generalized 1.2. Pseudo-random functions 9 this bound to e e+1 n. Herrmann and May [START_REF] Herrmann | Attacking Power Generators Using Unravelled Linearization: When Do We Output Too Much?[END_REF] improved this bound to e-1 e n by using Coppersmith's methods with a new technique called the unravelled linearization. In 2005, Lange and Shparlinski [START_REF] Lange | Certain Exponential Sums and Random Walks on Elliptic Curves[END_REF] proposed an elliptic curve analogue of the PG called the elliptic curve power generator (EC-PG). For a positive integer e > 1 and a point V 0 ∈ E(F p ) of order with gcd(e; ) = 1, the EC-PG is a sequence V n of pseudo-random numbers defined by the relation:

V n = eV n-1 = e n V 0 , n ∈ N
where V 0 ∈ E(F p ) is the initial value or seed. At each step, the algorithm outputs some most significant bits of each coordinate of V n . To the best our knowledge, no result on the cryptanalysis of the EC-PG are known.

In Chapter 6, we show that the EC-PG and the EC-LCG are insecure if too many bits are output at each iteration. Some secure PRGs constructions collect new inputs in addition to the seed and produce outputs that depend on the previous inputs. The designs of such secure PRGs are based on some cryptographic primitives such as ciphers and hash functions and on special-purposes designs (for instance the Yarrow algorithm, Fortuna algorithm, ANSI X9.17 standard etc.).

Applications

Pseudo-random generators have numerous applications in cryptography. As mentioned, pseudo-random generators are used to construct stream ciphers. They may also be used to construct symmetric-key schemes (where a large number of messages can be safely encrypted under the same key), for key generation, for nonces and signature schemes.

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 F K (i), where F K 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 efficiently using a secret-key) with the property that an adversary cannot efficiently observe any significant difference 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 {F n : K n × D n → R n } 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 : D n → R n defined by picking uniformly at random a secret-key k ∈ K n such that F (m) = F n (k, m) for any m ∈ D n ;

• or an oracle simulating a truly random function F : D n → R n (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 difference 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 {F n :

K n × D n → R n } n∈N is a pseudo-random
k ∈ {0, 1} s , define F k : {0, 1} n → {0, 1} s by F k (x 1 . . . x n ) = G xn (G x n-1 (. . . (G x 2 (G x 1 (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 inefficient 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 = (a 1 , . . . , a n ) ∈ ((Z/ Z) * ) n and the Naor-Reingold function is defined as:

f a : {0, 1} n -→ G (x 1 , . . . , x n ) -→ f a (x 1 , . . . , x n ) = g n i=1 a x i i mod
The evaluation of f a is thus efficient 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 Diffie-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 = (a 1 , . . . , a n ) ∈ ((Z/ Z) * ) n and a variable x that will denote indifferently an n-bit string (x 1 , . . . , x n ) ∈ {0, 1} n or an integer x ∈ {0, 1, . . . , 2 n -1} (which implicitly defines (x 1 , . . . , x n ) ∈ {0, 1} n the bit representation of x with extra leading zeros if necessary), we denote a x the element in F defined by a x = a x 1 1 • • • a xn n mod . With this notation, the Naor-Reingold function is simply defined by f a (x) = g a x . Since proving that the Decision Diffie-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 [START_REF] Ling | On the Multidimensional Distribution of the Naor-Reingold Pseudo-Random Function[END_REF][START_REF] Shparlinski | On the Naor-Reingold Pseudo-Random Function from Elliptic Curves[END_REF] and references therein), linear complexity (see [CGS10; GGI11; Shp00a; SS01]) and non-linear complexity (see [START_REF] Banks | Nonlinear Complexity of the Naor-Reingold Pseudo-random Function[END_REF]). 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 [START_REF] Dodis | A Verifiable Random Function with Short Proofs and Keys[END_REF] proposed an efficient 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:

V x : {1, . . . , d} -→ G m -→ V x (m) = g 1 x+m if x + m = 0 mod t and 1 G otherwise.
The Dodis-Yampolskiy pseudo-random function family has found numerous applications in cryptography (e.g., for compact e-cash [START_REF] Camenisch | Compact E-Cash[END_REF] or anonymous authentication [START_REF] Camenisch | How to win the clonewars: Efficient periodic n-times anonymous authentication[END_REF]). 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 Diffie-Hellman Inversion problem holds in G [START_REF] Dodis | A Verifiable Random Function with Short Proofs and Keys[END_REF]. In practice, two interesting 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 [START_REF] Dodis | A Verifiable Random Function with Short Proofs and Keys[END_REF]) or a subgroup of points of an elliptic curve defined over a prime finite field. Very few results supporting the Decision Diffie-Hellman Inversion assumption hardness were proven (contrary to the Naor-Reingold pseudo-random function family [START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF] for which numerous results are known, e.g. distribution [START_REF] Ling | On the Multidimensional Distribution of the Naor-Reingold Pseudo-Random Function[END_REF], linear complexity [START_REF] Gómez | On the linear complexity of the Naor-Reingold sequence[END_REF] 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

E k (m) = (F k (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-Rackoff construction.

• they can be used as message authentication codes (MACs) [Gol04, Chapter 1]:

M AC k (m) = F k (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 sufficient to have an easy multivariate polynomial f (namely a polynomial of low degree and low weight (the number of non-zero coefficients of the polynomial) which is efficiently computable) and which from some known information can approximate the function. For instance, for the Computational Diffie-Hellman assumption, given an element g of order such a polynomial could satisfy the relation:

f (g x , g y ) = g xy , 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 [START_REF] Coppersmith | On Polynomial Approximation of the Discrete Logarithm and the Diffie-Hellman Mapping[END_REF]) or the Computational and Decision Diffie-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 sufficient 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 (g a x 1 , . . . , g a x k ) = g a x k+1
, for all a = (a 1 , . . . , a n ) ∈ S for a large subset S ⊆ (F * ) n , and for some known values x 1 , . . . , x k+1 ∈ {0, • • • , 2 n -1}) or (f (g a x , g a x+t 1 , . . . , g a x+t k-1 ) = g a x+t k for many integers x ∈ {0, 1, . . . , 2 n -1}, and for some known values t 1 , . . . , t k 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 [START_REF] Mefenza | Polynomial interpolation of the Naor-Reingold pseudo-random function[END_REF][START_REF] Mefenza | Polynomial Approximation of the Generalized Diffie-Hellman and Naor-Reingold Functions[END_REF] 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 [START_REF] Mefenza | Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function[END_REF] 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 V x (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.

1.3. Our results

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

As a third contribution [START_REF] Mefenza | Inferring Sequences Produced by a Linear Congruential on Elliptic Curves using Coppersmith's Methods[END_REF], 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 U 0 and U 1 of the sequence is hidden. This improves the previous bound 1/6 of Gutierrez and Ibeas [START_REF] Gutierrez | Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits[END_REF]. 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 [START_REF] Gutierrez | Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits[END_REF], one could output only the most significant bits of the abscissa of consecutive multiple values U kn (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(U 0 ) and X(U k ) is hidden, where X(P ) denotes the abscissa of the point P on the curve. We further improve this result by considering several values U kn , 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 U 0 and U 1 of the sequence is hidden. This improves the previous bound 1/46 of Gutierrez and Ibeas [START_REF] Gutierrez | Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits[END_REF]. We further improve this result by considering sufficiently 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/2e 2 of the least significant bits of the abscissa of two consecutive values V 0 and V 1 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/e 2 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 Chapter 2.

Preliminaries

In this Chapter, we introduce the notation used throughout this manuscript. We recall some results on finite fields and elliptic curves that we use in Chapters 3 and 4. We also provide explicit upper-bounds for exponential sums with consecutive modular roots over a finite field and for analogous exponential sums over elliptic curves. These bounds will help us to study the distribution of the Dodis-Yampolskiy pseudo-random function in Chapter 4. We conclude this Chapter by recalling some known lower bounds on the polynomial interpolation on the discrete logarithm modulo a prime number p since the techniques will help us study the polynomial interpolation of the pseudo-random functions we consider in Chapters 3 and 4.

Notation

In this section, we recall the general notations that we use throughout this thesis. We denote by Z the set of integers and by N the set of non-negative integers. If z is a positive real number, log z denotes its binary logarithm and |z| its absolute value. If X, Y are two real numbers, X = O(Y ) and X Y denote that |X| ≤ cY , where c is a positive constant. If S is a finite set, |S| or S denotes its size. F q denotes a finite field of q elements and if q is a prime number, then the elements of F q are identified with the set of integers {0, • • • , q -1}.

F * q denotes the multiplicative group of F q that is the set of the invertible elements of F q which is of size q -1. If F q is a finite field, F q denotes the algebraic closure of F q . For a positive integer m ≥ 2 , (Z m , +, •) or Z m denotes the ring of integers modulo m which can be identified with the set of integers {0, . . . , m -1} and by Z * m the set of the invertible elements of Z m which consists of integers k ∈ Z m , with gcd(k, m) = 1. If R is a ring, then R[X 1 , . . . , X n ] denotes the ring of multivariate polynomials with n indeterminates with coefficients in R.

When n = 1, R[X] denotes the ring of univariate polynomials with coefficients in R. If

f ∈ R[X 1 , . . . , X n ],
then w(f ) denotes its weight (or sparsity) that is the number of its non-zero coefficients and deg(f ) its degree. For a real z, we use the notation e(z) = exp(2πiz) and e m (z) = exp(2πiz/m)

Finite fields

In this section, we collect some statements about finite fields that we will need throughout this thesis. The following lemma gives a lower bound of the weight of a univariate polynomial and we will need it in the next two chapters.

Lemma 2.2.1 ([LW02]

). Let γ ∈ F p be an element of order and F (X) ∈ F p [X] be a nonzero polynomial of degree at most -1 with at least b zeros of the form γ x with 0 ≤ x ≤ -1.

The weight of F (X) satisfies w(F ) ≥b

We will use the two following lemmas (see [START_REF] Kiltz | On the interpolation of bivariate polynomials related to Diffie-Hellman mapping[END_REF]) in Chapter 3 where Lemma 2.2.3 is a generalization of Lemma 2.2.1.

Lemma 2.2.2. Let D be an integral domain, n ∈ N and f ∈ D[X 1 , . . . , X n ] a polynomial of total degree d with at least N zeros in S n . If f is not the zero polynomial, then we have

d ≥ N |S| n-1 .
Lemma 2.2.3. Let γ ∈ F q be an element of order d, G the group generated by γ, n a positive integer, and f ∈ F q [X 1 , . . . , X n ] be a nonzero polynomial of local degree at most d -1 in each variable with at least N zeros in G n . Then for the weight w(f ) of f , we have :

w(f ) ≥ d n d n -N .

Elliptic Curves

In this section, we collect some results on elliptic curves. Later we will consider the settings where the pseudo-random functions in Chapters 3 and 4 are defined over an elliptic curve over a prime finite field and a pseudorandom number generator defined over an elliptic curve in Chapter 6.

Definition and addition law

Let p > 3 be an odd prime number, an elliptic curve E defined over F p (for more details on elliptic curves, see [START_REF] Blake | Elliptic curves in cryptography[END_REF][START_REF] Washington | Elliptic curves. Number theory and cryptography[END_REF]) is a rational curve given by the following Weierstrass equation

y 2 = x 3 + Ax + B, A, B ∈ F p , 4A 3 + 27B 2 = 0.
The set E(F p ) of the points of the curve defined over F p (including the special point O at infinity) has a group structure (denoted additively ) with an appropriate composition rule ⊕ where O is the neutral element. Let E/F p : y 2 = x 3 + ax + b be an elliptic curve over F p . For two points P = (x P , y P ) and Q = (x Q , y Q ), with P, Q = O, the point R = P ⊕ Q is geometrically obtained as follows:

• Draw the line L through P and Q or (the tangent to the curve E at The formulas for x R and y R with P ⊕ Q = R = (x R , y R ) are given as follows:

P if P = Q) • L intersects E in a third point R • Reflect R across the x-axis to obtain R.
• If x P = x Q , then x R = m 2 -x P -x Q , y R = m(x P -x R ) -y P , where m = y Q -y P x Q -x P (2.1) • If x P = x Q but y P = y Q , then R = O • If P = Q and y P = 0, then x R = m 2 -2x P , y R = m(x P -x R ) -y P , where m = 3x 2 Q + a 2y P • If P = Q and y P = 0, then R = O.
Given a P point of a curve E with prime order (with | | E(F p )|), we denote [r]P the scalar multiplication, i.e. the adding of the point P to itself r times:

Division polynomials of elliptic curves

We recall some basic facts on division polynomials of elliptic curves (see [START_REF] Washington | Elliptic curves. Number theory and cryptography[END_REF], Section 3.2). They provide a way to calculate multiples of points on elliptic curves. The division

polynomials ψ m (X, Y ) ∈ F p [X, Y ]/(Y 2 -X 3 -AX -B), m ≥ 0,
are recursively defined by:

ψ 0 = 0 ψ 1 = 1 ψ 2 = 2Y ψ 3 = 3X 4 + 6AX 2 + 12BX -A 2 ψ 4 = 4Y (X 6 + 5AX 4 + 20BX 3 -5A 2 X 2 -4ABX -8B 2 -A 3 ) ψ 2m+1 = ψ m + 2ψ 3 m -ψ m-1 ψ 3 m+1 , m ≥ 2 ψ 2m = ψ m (ψ m+2 ψ 2 m-1 -ψ m-2 ψ 2 m+1 )/ψ 2 , m ≥ 3, where ψ m is an abbreviation for ψ m (X, Y ). If m is odd, then ψ m (X, Y ) ∈ F p [X] is univariate and if m is even then ψ m (X, Y ) ∈ ψ 2 (X, Y )F p [X] = 2Y F p [X]. Therefore, as ψ 2 2 (X, Y ) = 4(X 3 + AX + B), we have ψ 2 m (X, Y ) ∈ F p [X] and ψ m-1 (X, Y )ψ m+1 (X, Y ) ∈ F p [X]
. In particular, we may write ψ 2m+1 (X) and ψ 2 m (X). As mentioned above, the division polynomials can be used to calculate multiples of a point on the elliptic curve E. Let P = (x, y) ∈ E with P = O, then the coordinates of [m]P if [m]P = O are given by

[m]P = θ m (x) ψ 2 m (x) , ω m (x, y) ψ 3 m (x, y)
,

where θ m (X) = Xψ 2 m -ψ m-1 ψ m+1 and ω m (X, Y ) = (4Y ) -1 (ψ m+2 ψ 2 m-1 -ψ m-2 ψ 2 m+1
). The zeros of the denominator ψ 2 m (X) are exactly the first coordinates of the non-trivial m-torsion points, i.e, the points

Q = (x, y) ∈ F p 2 \ {O} on E with [m]Q = O. Note,
(X) ∈ F p [X] is monic of degree m 2 .
In the next two chapters, we will make use of the two following technical lemmas.

Lemma 2.3.1. Let E : y 2 = x 3 + Ax + B be an elliptic curve over F p with A = 0 and B = 0.

Let F (X) ∈ F p [X] be a non-constant polynomial with F (X) = X and deg(F ) < p. Then there exists α ∈ F p such that ψ 2 2 (F (α)) = 0 and ψ 2 2 (α) = 0.

Proof. There are exactly three distinct zeros α 1 , α 2 , α 3 ∈ F p of ψ 2 2 (X) = 4(X 3 + AX + B). For all index i ∈ {1, 2, 3}, there exists at least one β i ∈ F p such that F (β i ) = α i , because F is not a constant polynomial. Since for all i, j ∈ {1, 2, 3}, i = j, we have α i = α j , then the system F (X) = α i and F (X) = α j has no solution. It follows that the polynomial ψ 2 2 (F (X)) has at least three different zeros.

Let d < p denote the degree of F and let us suppose that there does not exist α ∈ F p such that ψ 2 2 (F (α)) = 0 and ψ 2 2 (α) = 0. Then we have that ψ 2 2 (F (X)) has exactly three zeros which are the zeros of ψ 2 2 (X). If d = 1, putting F (X) = aX + b, we obtain that the polynomials X 3 + AX + B and a 3 X 3 + 3a 2 bX 2 + (3ab 2 + aA)X + b 3 + Ab + B have exactly the same three zeros. We then have 3a 2 b = 0 and a = 0. Thus b = 0, and if we suppose A = 0 and B = 0, we have a = 1 which is impossible since F (X) = X. If d ≥ 2, for all i ∈ {1, 2, 3}, the equation F (X) = α i has exactly one solution γ i of multiplicity d which is one of {α 1 , α 2 , α 3 }. Then γ 1 and γ 2 are the zeros of the (d -1)-derivative of F (X) which is of degree 1 and this is impossible because γ 1 = γ 2 . Hence in all cases, we obtain a contradiction. So there exists α ∈ F p such that:

ψ 2 2 (F (α)) = 0 and ψ 2 2 (α) = 0. Lemma 2.3.2. Let E : y 2 = x 3 + Ax + B be an elliptic curve over F p . Let k = 2 i for i > 0 an integer. Let F (X) ∈ F p [X] be a non-constant polynomial with deg(F ) ≥ 2. Then there exists α ∈ F p such that ψ 2 k (F (α)) = 0 and ψ 2 k (α) = 0.
Proof. The univariate polynomial ψ 2 k (X) has at least k 2 /2 distinct zeros because p k. For all α such that ψ 2 k (α) = 0, there exists at least one β ∈ F p such that F (β) = α and two such

Chapter 2. Preliminaries roots β (corresponding to two different α) are different. Let us suppose that there does not exist α ∈ F p such that ψ 2 k (F (α)) = 0 and ψ 2 k (α) = 0. Since deg(F ) ≥ 2, it follows that the equation F (X) = α, for some α zero of ψ 2 k (X) has at least two different solutions using the ideas of the later proof. Thus we obtain a contradiction and the desired result follows.

Summation polynomials

Index calculus algorithm [START_REF] Adleman | A Subexponential Algorithm for the Discrete Logarithm Problem with Applications to Cryptography[END_REF] is used to solve the discrete logarithm problem (DLP) over finite fields in sub-exponential time. For the elliptic curve discrete logarithm problem (EC-DLP), only exponential time algorithms were known to solve the problem. The idea of using index calculus to solve the EC-DLP was proposed by Semaev [START_REF] Semaev | Summation polynomials and the discrete logarithm problem on elliptic curves[END_REF] and Gaudry [START_REF] Gaudry | Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem[END_REF]. They proposed to decompose points by computing the zeroes of summation polynomials (which were first introduced in 2004 by Semaev [START_REF] Semaev | Summation polynomials and the discrete logarithm problem on elliptic curves[END_REF]). For some curves over extension finite fields, Gröbner basis were used to compute zeroes of such polynomials or their generalizations and sub-exponential algorithms solving the EC-DLP were obtained (see [Gau09; Die11; JV12; FPPR12]). For elliptic curves over prime fields or binary fields of prime extension degree, [START_REF] Semaev | New algorithm for the discrete logarithm problem on elliptic curves[END_REF] proposed improved algorithms solving the EC-DLP which compute the zeroes of summation polynomials by solving a system of boolean equations. In this thesis, we use summation polynomials in another context, namely to infer the elliptic curve linear congruential generator in Chapter 6. Below, we recall the summation polynomials (see [START_REF] Semaev | Summation polynomials and the discrete logarithm problem on elliptic curves[END_REF] for details and proofs). Let E : y 2 = x 3 + ax + b be an elliptic curve over a finite field F q (where q is a power of a prime number p = 2, 3). For n ∈ N, n ≥ 2, the n th summation polynomial f n (X 1 , X 2 , . . . , X n ) ∈ F q [X 1 , . . . , X n ] for E which is related to the arithmetic operation on E has the following property:

f n (x 1 , . . . , x n ) = 0, x i ∈ F q if and only if (there exists y 1 , . . . , y n ∈ F q such that (x 1 , y 1 ), . . . , (x n , y n ) ∈ E and (x 1 , y 1 ) ⊕ • • • ⊕ (x n , y n ) = O),
where O is the point at infinity.

Lemma 2.3.3 ([Sem04]

). Let E : y 2 = x 3 + ax + b be an elliptic curve over a finite field F q (where q is a power of a prime number p = 2, 3)). The summation polynomials for E are given as follows:

f 2 (X 1 , X 2 ) = X 1 -X 2 f 3 (X 1 , X 2 , X 3 ) = (X 1 -X 2 ) 2 X 2 3 -2 ((X 1 + X 2 )(X 1 X 2 + a) + 2b) X 3 + (X 1 X 2 -a) 2 -4b(X 1 + X 2 ) f n (X 1 , . . . , X n ) = Res X (f n-k (X 1 , . . . , X n-k-1 , X), f k+2 (X n-k , . . . , X n , X)), n ≥ 4
where the last equality holds for any constant k with 1 ≤ k ≤ n -3. The n th summation polynomial f n is an irreducible symmetric polynomial of degree 2 n-2 in each variable X i for any n ≥ 2.

Exponential Sums

In this section, we collect some statements about exponential sums over finite fields and elliptic curves that we use to study he distribution of the Dodis-Yampolskiy pseudo-random function in Chapter 4. We provide explicit upper bounds for exponential sums with consecutive modular roots over a finite field and for analogous exponential sums over elliptic curves [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF][START_REF] Ostafe | Twisted exponential sums over points of elliptic curves[END_REF]. The bound for exponential sums with consecutive modular roots over a general finite field is easily derived from [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF] and may be of independent interest.

Finite Fields and Exponential Sums

Let p be an odd prime number, r ≥ 1 an integer. Let g ∈ F * p r of order t, and ψ be a non-trivial character of F p r . For a ∈ F * p r and b ∈ Z t , we define the sum:

S a,b = n∈Z * t ψ(ag 1/n )e t (bn).
In the following lemmas, the implied constants in the symbols " " may occasionally depend on the integer parameters k, but are absolute otherwise.

In [START_REF] Bourgain | Distribution of consecutive modular roots of an integer[END_REF] Bourgain and Shparlinski proved, when r = 1, that for any > 0, there exists δ > 0 such that for t ≥ p , we have the bound S a,b t 1-δ . Shparlinski [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF](Theorem 3.1) gave an explicit form of this result (again when r = 1) for relatively large values of t; in the case t = p 1+o (1) , it takes the form S a,b t 127/128+o (1) . Using Shparlinski's methods, we generalize this bound on S a,b for any r ≥ 1.

Proposition 2.4.1. For any integers k ≥ 2, ≥ 1 we have for t ≥ q 1/2 (log q) 2 : (1) ,

S a,b ≤ t 1-α k, q β k, +o
where α k, = 1 2(2k+ ) -1 4k and β k, = 1 4(2k+ ) .
The proof follows the one of [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF]). In the proof of the Proposition 2.4.1, we use the two following lemmas.

Lemma 2.4.2 is the classical Weil bound for exponential sums which can be found in

[Wei48; NW01]. Lemma 2.4.2. Let F (x) be a non constant polynomial in F q [x] such that F (x) = h(x) p -h(x)
for any h(x) ∈ F q (x), where q is a power of p. We have

x∈Fq ψ(F (x)) ≤ (deg(F ) -1)q 1/2
We then deduce the following simple lemma: Lemma 2.4.3. For any pairwise distinct positive integers 1 ≤ r 1 , . . . , r υ ≤ R, we have

max (a 1 ,...,aυ)∈F υ p r (a 1 ,...,aυ) =(0,...,0) t n=1 ψ υ i=1 a i g r i n ≤ Rq 1/2 .
Proof. Let s = (q -1)/t. We have g = θ s , where θ is a primitive root in F q and

t n=1 ψ υ i=1 a i g r i n = t n=1 ψ υ i=1 a i θ sr i n = 1 s q-1 n=1 ψ υ i=1 a i θ sr i n = 1 s   x∈Fq ψ υ i=1 a i x sr i -1   Applying Lemma 2.4.2 with the polynomial F (x) = υ i=1 a i x sr i , we obtain : max (a 1 ,...,aυ)∈F υ p r (a 1 ,...,aυ) =(0,...,0) t n=1 ψ υ i=1 a i g r i n ≤ 1 s ((Rs -1)q 1/2 + 1) ≤ Rq 1/2 .
Chapter 2. Preliminaries

Now we are ready to prove Proposition 2.4.1.

Proof. For any integer k ≥ 2, we have

S a,b k = n 1 ,...,n k ∈Z * t ψ   a k j=1 g 1/n j   e t   b k j=1 n j   .
For m ∈ Z t , we collect together the terms with

n 1 + • • • + n k ≡ m mod t, getting: |S a,b | k ≤ m∈Zt n 1 ,...,n k ∈Z * t n 1 +•••+n k ≡m mod t ψ   a k j=1 g 1/n j   .
By the Cauchy inequality, we can upper-bound |S a,b | 2k by

t m∈Zt n 1 ,...,n k ∈Z * t n 1 +•••+n k ≡m mod t ψ   a k j=1 g 1/n j   2 = t (n 1 ,...,n 2k )∈N k ψ   a 2k j=1 (-1) j g 1/n j  
where the outside summation is taken over the set of vectors

N k = {(n 1 , . . . , n 2k ) ∈ (Z * t ) 2k : n 1 + • • • + n 2k-1 ≡ n 2 + n 4 + • • • + n 2k mod t)}.
One can see that for any m ∈ N with gcd(m, t) = 1, we have

(n 1 ,...,n 2k )∈N k ψ   a 2k j=1 (-1) j g 1/n j   = (n 1 ,...,n 2k )∈N k ψ   a 2k j=1 (-1) j g m/n j   .
Let us fix some parameter

Q with Q ≥ 2 log t. Let Q be the set of primes m ≤ Q with gcd(m, t) = 1. Averaging over all m ∈ Q, we obtain |S a,b | 2k ≤ t Q m∈Q (n 1 ,...,n 2k )∈N k ψ   a 2k j=1 (-1) j g m/n j   .
The number w(t) of prime divisors of t satisfies w(t) ≤ (1 + o( 1))(log t)/(log log t) (which can be seen from the trivial inequality w(t)! ≤ t and the Stirling formula). By the prime number theorem, we have (since Q ≥ 2 log t):

Q ≥ (1 + o(1)) Q log Q -(1 + o(1)) log t log(log t) ≥ 0.5 Q log Q , provided that t is large enough. We have N k ≤ t 2k-1 .
Using the Hölder inequality and then extending the region of summation, we obtain that for any integer ≥ 1:

|S a,b | 4k ≤ t 2 Q 2 ( N k ) 2 -1 n 1 ,...,n 2k ∈Z * t m∈Q ψ   a 2k j=1 (-1) j g m/n j   2 t 4k -2k+1 log 2 Q Q 2 t n 1 ,...,n 2k =1 m∈Q ψ   a 2k j=1 (-1) j g mn j   2 = t 4k -2k+1 log 2 Q Q 2l t n 1 ,...,n 2k =1 m 1 ,...,m 2 ∈Q ψ   a 2k j=1 2 h=1 (-1) j+h g m h n j   = t 4k -2k+1 log 2 Q Q 2 m 1 ,...,m 2 ∈Q t n=1 ψ a 2 h=1 (-1) h g m h n 2k . For O( Q )=O(Q log -Q) tuples (m 1 , . . . , m 2 ) ∈ Q 2 such
that the tuple of the elements on the odd positions (m 1 , . . . , m 2 -1 ) is a permutation of the elements on the even positions (m 2 , . . . , m 2 ), we estimate the inner sum trivially as t.

For the remaining O(( Q) 2 ) = O(Q 2 (log Q) -2
) tuples, we use the bound of Lemma 2.4.3. Therefore,

|S a,b | 4k t 4k -2k+1 log 2 Q Q 2l (Q log -Qt 2k + Q 2 log -2 Q(Qq 1/2 ) 2k ) = t 4k -2k+1 (Q -log Qt 2k + Q 2k q k ). Taking Q = 2t 2k/(2k+ ) q -k/(2k+ ) (log q) /(2k+ ) and if t ≥ q 1/2 (log q) 2 , one can see that Q ≥ 2 log t and we obtain |S a,b | 4k t 4k -(2k -2k-)/(2k+ ) q k /(2k+ ) (log q) /(2k+ )
and the result follows.

Elliptic Curves and Exponential Sums

Let E be an elliptic curve and P ∈ E(F p ) be a point of order t ≥ 1. For a ∈ F * p and b ∈ Z t , we define the following exponential sum which is an analogous of the sum S a,b over an elliptic curve:

Ŝa,b =

n∈Z * t e p aX 1 n P e t (bn),
where X(P ) denotes the abscissa of the point P .

In [OS11, Theorem 6], Ostafe and Shparlinski obtained an upper-bound on Ŝa,b (with 1) ,

H(X) = X -1 following the notation from [OS11]): Proposition 2.4.4 ([OS11]). For any integers k ≥ 2, ≥ 1 we have for t ≥ q 1/2 (log q) 2 : Ŝa,b ≤ t 1-α k, p β k, +o (
where α k, = 1 2(4k+ ) -1 4k and β k, = 1 4(4k+ ) .
Chapter 2. Preliminaries

In the proof, we need the following lemma which is a special case of the bound of Bombieri see [Bom66]: Lemma 2.4.5. Let s ≥ 1 be an integer. For any integers 1 ≤ u 1 < • • • < u s ≤ U and elements c 1 , . . . , c s ∈ F p with c s = 0, the following bound holds:

R∈H,R =O e p s i=1 c i X(u i R) U 2 p 1/2
where H is a subgroup of E(F p ) of order t such that gcd(t, u 1 , . . . , u s ) = 1.

Next we then prove Proposition 2.4.4.

Proof. Following the same path as in the finite fields case by replacing the multiplicative law by an additive one and applying the Lemma 2.4.5 rather than Lemma 2.4.3, we obtain:

|S a,b | 4k t 4k -2k+1 (Q -log Qt 2k + Q 4k p k ).
Taking 4k+) and the result follows.

Q = 2t 2k/(4k+ ) p -k/(4k + ) (log p) /(4k+ ) , we obtain Ŝa,b 4k t 4k -2k+1+8k 2 /(4k+ ) p k /(4k+ ) (log p) 4k /(

Polynomial Approximation of the Discrete Logarithm

In Chapters 3 and 4, we study the polynomial interpolation and we use the same techniques as in the polynomial approximation of the discrete logarithm problem. In this section, we recall some known lower bounds on the degree and weight of polynomial interpolating the discrete logarithm modulo a prime number p due to Coppersmith and Shparlinski (see [START_REF] Coppersmith | On Polynomial Approximation of the Discrete Logarithm and the Diffie-Hellman Mapping[END_REF] for details). The technique works as follows: from the initial polynomial, one constructs a non zero polynomial having a certain number of roots and whose lower bounds on its degree or weight (which can be obtained from some known lemmas) allow us to obtain lower bounds on the degree or weight of the initial polynomial . Let us fix a primitive root g modulo a prime number p ≥ 3. For an integer x such that gcd(x, p) = 1, we denote by ind x its discrete logarithm, that is, the smallest non-negative integer u with g u = x mod p. In public-key cryptography, the discrete logarithm problem is considered as a hard problem and to break this problem modulo p, it would be sufficient to have a univariate polynomial f polynomial over F p of low degree which computes the discrete logarithm for almost all elements in {1, . . . , p -1}, that is, f (x) = ind x mod p, for x ∈ S ⊆ {1, . . . , p -1} of the same size as p. It has been shown in [START_REF] Mullen | A polynomial representation for logarithms in GF(q)[END_REF] that the polynomial

f (x) = -1 + p-2 k=1 (g -k -1) -1 x k mod p
is the unique interpolation polynomial of the discrete logarithm modulo p for S = {1, . . . , p-1}. Noting that any function over F p can be approximated at p -1 points by a polynomial of 2.5. Polynomial Approximation of the Discrete Logarithm degree at most p -2, this polynomial is actually of the largest possible degree and is dense (namely it contains p -1 monomials). The two following results (see [START_REF] Coppersmith | On Polynomial Approximation of the Discrete Logarithm and the Diffie-Hellman Mapping[END_REF]) show that a low degree and low weight univariate polynomial cannot interpolate the discrete logarithm for sufficiently large sets S. These results do not guarantee the hardness of the discrete logarithm problem but they can be considered as a good indication that this problem is indeed a computationally hard problem.

Theorem 2.5.1. Let f (X) ∈ Z[X] be a polynomial of degree n = deg(f ) ≤ p -2 and of weight t = w(f ) such that ind x = f (x) mod p, x ∈ S, for a set S ⊆ {1, . . . , p -1} of cardinality |S| = p -1 -s. Then deg(f ) ≥ p -2 -2s, w(f ) ≥ (p -1)/(2s + 1) -1.
Proof. Let R be the set of x ∈ {1, . . . , p -1} for which both ind x = f (x) mod p and ind gx = f (gx) mod p.

We have

|R| ≥ p -1 -2(p -1 -|S|) = p -1 -2s. Indeed for x ∈ {1, . . . , p -1}, x / ∈ R if
= 1 + ind x if x = g p-2 mod p. Hence f (gx) = 1 + f (x) mod p, for x ∈ R with x = g p-2 mod p. Therefore the polynomial h(X) = f (gX) -f (X) -1 has at least |R| -1 zeros modulo p and is not identical to zero modulo p (since h(0) = -1). Thus n ≥ deg(h) ≥ |R| -1. Also if f contains t monomials, then h contains at most t + 1 monomials. Applying Lemma 2.2.1, we see that p -1 -(|R| -1) ≥ (p -1)/(t + 1
) and the desired result follows.

In particular, if s = o(p), then deg(f ), w(f ) ∼ p. Theorem 2.5.1 is non trivial if the set S is dense enough (|S| > p/2). The next result is applicable to quite sparse sets S beginning with |S| > (2p)

1/2 . Theorem 2.5.2. Let f (X) ∈ Z[X] be a polynomial of degree n = deg(f ) ≤ p -2 such that ind x = f (x) mod p, x ∈ S, for a set S ⊆ {1, . . . , p -1}. Then deg(f ) ≥ |S|(|S| -1) 2(p -2) .
Proof. Let us consider the set

D = {a = yx -1 mod p, 2 ≤ a ≤ p -1, x, y ∈ S}.
Then |D| ≤ p -2. There is a ∈ D such that there are at least |S|(|S|-1)

|D| representations a = yx -1 mod p, x, y ∈ S; Select this a and let R be the set of x ∈ {1, . . . , p -1} for which both ind x = f (x) mod p and ind ax = f (ax) mod p.

Chapter 2. Preliminaries

Thus |R| ≥ |S|(|S|-1)
2(p-2) . Indeed for each representation a = yx -1 mod p, we get a pair x and y = ax mod p of elements of S. We also have ind ax = ind x + ind a or ind ax = ind x + ind ap + 1. Hence either

f (ax) = ind ax = ind x + ind a = f (x) + ind a mod p or f (ax) = ind ax = ind x + ind a -p + 1 = f (x) + ind a + 1 mod p mod p for x ∈ R. Therefore at least one of the polynomials h 1 (X) = f (aX) -f (X) -ind a and h 2 (X) = f (aX) -f (X) -ind a -1 has at least |R|/2 zeros modulo p.
Because of our choice of D neither of these polynomials is identical to zero modulo p. Indeed,

h 1 (0) = -ind a -1 = 0 mod p since a = 1, and h 2 (0) = -ind a = 0 mod p since 0 ≤ ind a ≤ p -2.
Thus n ≥ |R|/2 and the desired result follows.

The polynomial interpolation is a question which is well studied in general for cryptographic hard functions. For instance, lower bounds on the degree or weight of polynomials interpolating the discrete logarithm problem imply some lower bounds on the "sequential arithmetic complexity of the discrete logarithm in the computational tree model and in the random access machine model over real numbers" and lower bounds on the degree or weight of polynomials interpolating the Computational Diffie-Hellman assumption or the Decision Diffie-Hellman assumption have been obtained as well (see [MS01; Win01; KW04; Shp03] and references therein).

Chapter 3.

Polynomial Interpolation of the Naor-Reingold Pseudo-Random Functions

Many efficient public key cryptographic protocols are constructed using some assumptions which are believed to be hard, for instance the Computational Diffie-Hellman assumption or the Decision Diffie-Hellman assumption. In 1997, based on the Decision Diffie-Hellman assumption, Naor and Reingold [NR97; NR04] proposed an efficient pseudo-random function family. Since proving that the Decision Diffie-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 [START_REF] Ling | On the Multidimensional Distribution of the Naor-Reingold Pseudo-Random Function[END_REF][START_REF] Shparlinski | On the Naor-Reingold Pseudo-Random Function from Elliptic Curves[END_REF] and references therein), linear complexity (see [CGS10; GGI11; Shp00a; SS01]) and non-linear complexity (see [START_REF] Banks | Nonlinear Complexity of the Naor-Reingold Pseudo-random Function[END_REF]). These results are incomparable but they all support the assumption of the pseudo-randomness of the Naor-Reingold function. In order to break the security of the Naor-Reingold function, it would be sufficient 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 (g a x 1 , . . . , g a x k ) = g a x k+1
, for all a = (a 1 , . . . , a n ) ∈ S for a large subset S ⊆ (F * ) n , and for some known values x 1 , . . . ,

x k+1 ∈ {0, • • • , 2 n -1}) or (f (g a x , g a x+t 1 , . . . , g a x+t k-1
) = g a x+t k for many integers x ∈ {0, 1, . . . , 2 n -1}, and for some known values t 1 , . . . , t k and for some known secret key a), where for x ∈ {0, 1, . . . , 2 n -1} a x is defined in the next section. 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. We prove that a 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. This Chapter is organized as follows: we first recall the Naor-Reingold pseudo-random function and some known results that we need in the rest of the Chapter. Then we study the polynomial interpolation of the Naor-Reingold function defined over a finite field with fixed secret key and variable secret key. We conclude this Chapter by the polynomial interpolation of the Naor-Reingold function defined over an elliptic curve with fixed secret key and variable secret key.

Naor-Reingold pseudo-random function

In cryptography, a pseudo-random function family is a collection of functions (that can be evaluated efficiently using a secret-key) with the property that an adversary cannot efficiently observe any significant difference 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 {F n : K n × D n → R n } 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 : D n → R n defined by picking uniformly at random a secret-key

k ∈ K n such that F (m) = F n (k, m) for any m ∈ D n ;
• or an oracle simulating a truly random function F : D n → R n (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 difference 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 {F n :

K n × D n → R n } n∈N
is a pseudo-random function family if and only if no adversary with advantage asymptotically larger than the inverse of a polynomial exists.

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 = (a 1 , . . . , a n ) ∈ (Z * ) n and the Naor-Reingold function is defined as:

f a : {0, 1} n -→ G (x 1 , . . . , x n ) -→ f a (x 1 , . . . , x n ) = g n i=1 a x i i mod
The evaluation of f a is thus efficient1 since it consists only in n modular multiplications in Z and one modular exponentiation in G. To lighten the notation, given an n-dimensional vector a = (a 1 , . . . , a n ) ∈ (Z * ) n and a variable x that will denote indifferently an n-bit string (x 1 , . . . , x n ) ∈ {0, 1} n or an integer x ∈ {0, 1, . . . , 2 n -1} (which implicitly defines (x 1 , . . . , x n ) ∈ {0, 1} n the bit representation of x with extra leading zeros if necessary), we denote a x the element in Z defined by a

x = a x 1 1 • • • a xn n mod .
With this notation, the Naor-Reingold function is simply defined by f a (x) = g a x . Two interesting candidates for G are a subgroup of the multiplicative group of a finite field and a subgroup of the points of an elliptic curve defined over a finite field. In the setting of an elliptic curve E defined over F p for p > 3, we also define the function fa

(x) = [a x ]P ∈ E ⊂ F 2
p , for a secret key a = (a 1 , . . . , a n ) ∈ (F * ) n where again x will denote indifferently an n-bit string (x 1 , . . . , x n ) ∈ {0, 1} n or an integer x ∈ {0, 1, . . . , 2 n -1}. Because of the algebraic structure of E, this function is not pseudo-random and the Naor-Reingold pseudo-random function over E(F p ) is thus defined as, f a (x) = X( fa (x)), where X(P ) denotes the abscissa of P ∈ E.

Auxiliary results

In the forthcoming sections, we also need the following lemmas from [START_REF]Non-linear Complexity of the Naor-Reingold Pseudo-random Function[END_REF] and [START_REF] Gómez | On the linear complexity of the Naor-Reingold sequence[END_REF] about the distribution of products a x in F * to obtain concrete lower bounds on the weight and degree of polynomials interpolating the Naor-Reingold pseudo-random function with fixed secret key.

Lemma 3.2.1 ([WS99]

). Let m ≥ 1 be an integer. For any ∆ > 0 and for all but at most 2 -m ∆ -1 ( -1) m+2 vectors a = (a 1 , . . . , a m ) ∈ (F * ) m , the products a x for x ∈ {0, 1} m take at least -1 -∆ values in F * . Lemma 3.2.2 ([GGI11]). Let n ≥ j > 0 be two integers. For all but at most

(3 j -1)( -1) n-1 /2 vectors a = (a 1 , . . . , a n ) ∈ (F * ) n the products a x for x ∈ {0, 1} n take at least 2 j values in F * .

Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Finite Fields

In this section, we study the polynomial representation of the Naor-Reingold pseudo-random function over finite fields. From the known lower bounds on the polynomial interpolation on the discrete logarithm and the Diffie-Hellman Problem in the groups we considered (e.g. [CS00; KW06; LW02; LW03a; MW08; KW04; Shp03] and references therein) and the known result on the non-linear complexity of the Naor-Reingold pseudo-random function (see [START_REF] Banks | Nonlinear Complexity of the Naor-Reingold Pseudo-random Function[END_REF]), we prove that a low weight or degree k-variate polynomial cannot reveal information on the functions values.

Polynomial Interpolation with variable secret key

In this section, q is a prime power, n is an integer and g ∈ F * q is an element of prime order (with | q -1). We prove results on the multivariate polynomial approximation of the Generalized Diffie-Hellman and the Naor-Reingold functions over a finite field. We consider polynomials that approximate values of these functions for fixed values in {0, • • • , 2 n -1} and a large set of keys. First, we consider an approximation by a polynomial with k variables, with k ≤ n.

Theorem 3.3.1. Let 1 ≤ k ≤ n be an integer. Let S ⊆ (F * ) n , with |S| = ( -1) n -s with |S| > k( -1) n-1 . Let x 1 , . . . , x k+1 ∈ {1, • • • , 2 n -1} be pairwise distinct and let f ∈ F q [X 1 , . . . , X k ], be a polynomial satisfying: f g a x 1 , . . . , g a x k = g a x k+1
, for all a = (a 1 , . . . , a n ) ∈ S.

(3.1)

If the elements x i , i ∈ {1, . . . , k} seen as vectors over F n 2 are linearly independent over F 2 , then:

deg(f ) ≥ -1 2 - s ( -1) n-1 and if deg X i (f ) ≤ -1
2 , for all i ∈ {1, . . . , k}, we have

w(f ) ≥ k/2 2 1/2 ( k -( -1) k + 2s/( -1) n-k ) 1/2 .
3.3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Finite Fields 33

In particular, for s = o( n ), we have deg(f ) = Ω( ) and if deg X i (f ) ≤ -1 2 , for all i ∈ {1, . . . , k}, we have w(f ) = Ω( k/2 ).

Proof. For any i ∈ {1, . . . , k + 1}, we denote x i = x i 1 . . . x i n its binary representation and put xi = x i 1 . . . x i k 0 . . . 0 which is obtained from x i by considering the k first positions of its binary representation and replacing the nk last positions by 0. We suppose without loss of generality that the elements xi , i ∈ {1, . . . , k} seen as vectors over F n 2 are linearly independent over F 2 .

Since |S| > k( -1) n-1 , we have w(f ) ≥ 2 by the following claim:

Claim 3.3.2. If w(f ) = 1 then (3.1) holds for at most k( -1) n-1 keys a ∈ (F * ) n . Proof. If w(f ) = 1, then f is a monomial and there exists (α 1 , . . . , α k ) ∈ {0, . . . , -1} k such that α 1 a x 1 + • • • + α k a x k = a x k+1 mod (where f is the monomial f (X 1 , . . . , X k ) = X α 1 1 . . . X α k k )
. We prove by induction on k that the number of a ∈ (F * ) n such that

α 1 a x 1 + • • • + α k a x k = a x k+1 does not exceed k( -1) n-1 .
1. For k = 0, the equation a x k+1 = 0 has no solution and the statement is clearly true.

2. Otherwise, because x k+1 = x k , there exists j such that the j-th component of x k+1 is different from the j-th component of x k . Then the above equation can be written in the form A = Ba j where A and B do not depend on a j . If B = 0, then for any vector

(a 1 , • • • , a j-1 , a j+1 , • • • , a n ) ∈ (F * ) n-1
, the value of a j is defined uniquely. If B = 0, then A = 0 and by induction, the number of (a

1 , • • • , a j-1 , a j+1 , • • • , a n ) ∈ (F * ) n-1 does not exceed (k -1)( -1) n-2 . Therefore, the number of solutions does not exceed (k -1)( -1) n-1 + ( -1) n-1 = k( -1) n-1 ,

and the result follows.

There is some t ∈ {1, . . . , n} such that x k+1 t = 1 and let T = {i : x i t = 1} ⊆ {1, . . . , k} that we denote T = {i 1 , . . . , i v }, with i j < i j+1 for j ∈ {1, . . . , v -1}. Let

W = a ∈ (F * ) n : a = (
T = {(a 1 , . . . , a k ) ∈ (F * ) k : a = (a 1 , . . . , a k , b k+1 , . . . , b n ) ∈ W } satisfies |T | ≥ ( -1) k -2s/( -1) n-k . For all a 0 = (a 1 , . . . , a k ) ∈ T , putting a = (a 1 , . . . , a k , b k+1 , . . . , b n ), we have:        f g a x 1 , . . . , g a x k = g a x k+1 f g a x 1 , . . . , g a x i 1 -1 , g 2a x i 1 , g a x i 1 +1 , . . . , g a x iv -1 , g 2a x iv , g a x iv +1 , . . . , g a x n = g 2a x k+1
Since the elements xi , i ∈ {1, . . . , k} seen as vectors over F n 2 are linearly independent over F 2 , one can verify that the set

g a x 1 , . . . , g a x k ∈ (F * q ) k : a = (a 0 , b k+1 , . . . , b n ) ∈ W, and a 0 ∈ T
is of the same cardinality as T . Hence the polynomial

F (X 1 , . . . , X k ) = f (X 1 , . . . , X 2 i 1 , . . . , . . . , X 2 iv , . . . , X k ) -f 2 (X 1 , . . . , X k ) has at least |T | ≥ ( -1) k -2s/( -1) n-k zeros. Since w(f ) ≥ 2, one can see that F is a nonzero polynomial and deg F ≤ 2 deg f . By Lemma 2.2.2, we obtain: deg(f ) ≥ -1 2 - s ( -1) n-1 . Furthermore if deg X i (f ) ≤ -1
2 , for all i ∈ {1, . . . , n}, and since w(F ) ≤ 2w(f ) 2 , then by applying Lemma 2.2.3 we have:

w(f ) ≥ k/2 2 1/2 ( k -( -1) k + 2s/( -1) n-k ) 1/2 .
Now we consider an approximation by a polynomial with k variables and k > n with some technical conditions on the input values

x i ∈ {0, • • • , 2 n -1} for i ∈ {1, . . . , k}. Theorem 3.3.3. Let k > n be some integer. Let S ⊆ (F * ) n , with |S| = ( -1) n -s. Let x 1 , . . . , x k+1 ∈ {0, • • • , 2 n -1} be pairwise distinct such that x 1 = 2 n-1 = (1, 0, . . . , 0), x k+1 1 = 1 and x i 1 = 0 for i ∈ {2, . . . , k} and let f ∈ F q [X 1 , . . . , X k ],
with k > n be a polynomial satisfying:

f g a x 1 , . . . , g a x k = g a x k+1
, for all a = (a 1 , . . . , a n ) ∈ S.

We have

deg(f ) ≥ -1 2 - s ( -1) n-1 .
Proof. Let W be the set of vectors a ∈ (F * ) n such that a = (a 1 , . . . , a n ) ∈ S, (a 1 +1, . . . , a n ) ∈ S and a = (1, a 2 , . . . , a n ) satisfies a x k+1 = α mod for all α ∈ {1, . . . , d}, where d denotes the degree of f . Claim 3.3.4. We have

|W | ≥ ( -1) n -2s -deg(f )( -1) n-1 .
Proof. Let α ∈ {1, . . . , d}, the number of a ∈ (F * ) n such that a x k+1 = α mod does not exceed ( -1) n-1 .

Indeed, since x k = x 1 , there exists j ∈ {2, . . . , n} such that x k+1 j = 1, then for any vector (a 1 , . . . ,

a j-1 , a j+1 , • • • , a n ) ∈ (F * ) n-1
, the value of a j is defined uniquely by this equation. Since the number of vectors a = (a 1 , . . . , a n ) ∈ S such that (a 1 + 1, . . . , a n ) / ∈ S does not exceed s, the result follows.

By the pigeonhole principle, there exists

b = (1, b 2 , . . . , b n ) ∈ (F * ) n such that the set T = {a 1 ∈ F : a = (a 1 , b 2 , . . . , b n ) ∈ W } satisfies |T | ≥ -1 -deg(f ) -
       f g a 1 , g b x 2 . . . , g b x k = g a x k+1 f g a 1 +1 , g b x 2 , . . . , g b x k = g (a 1 +1,b 2 ,...,bn) x k+1 = g b x k+1 .g a x k+1
We have for all

a 1 ∈ T f g.g a 1 , g b x 2 , . . . , g b x k -g b x k+1 f g a 1 , g b x 2 . . . , g b x k = 0 (3.2)
and the polynomial

F (X) = f gX, g b x 2 , . . . , g b x k -g b x k+1 f X, g b x 2 . . . , g b x k has at least -1 -deg(f ) - 2s ( -1) n-1 zeros. The polynomial f (X, g b x 2 , . . . , g b x k
) is a nonzero polynomial by the first equation of the previous system and has degree smaller than deg(f ). Let d 0 its degree, then b x k+1 = d 0 mod by construction of W and it follows that the leading monomial of F is nonzero which implies that the polynomial F is nonzero. We also have deg(F ) ≤ deg(f ) and hence, by Lemma 2.2.2, we obtain:

deg(f ) ≥ -1 -deg(f ) - 2s ( -1) n-1 ,
and the result follows.

Theorem 3.3.3 can be applied to give lower bounds on the degree of interpolating polynomials for several generalized Diffie-Hellman problems (with k > n variables) from [START_REF] Bresson | Provably secure authenticated group Diffie-Hellman key exchange[END_REF].

Since the weight of a polynomial is a more discerning complexity estimate, we now prove a lower bound on the weight of an approximation by a polynomial with k variables and k > n (and without any condition on the input values

x i ∈ {0, • • • , 2 n -1} for i ∈ {1, . .

. , k}).

Theorem 3.3.5. Let k > n be some integer. Let

S ⊆ (F * ) n , with |S| = ( -1) n -s. Let x 1 , . . . , x k+1 ∈ {1, • • • , 2 n -1} be pairwise distinct and let f ∈ F q [X 1 , . . . , X k ] be a polynomial satisfying: f g a x 1 , . . . , g a x k = g a x k+1
, for all a = (a 1 , . . . , a n ) ∈ S,

for some different values x 1 , . . . , x k+1 ∈ {1, • • • , 2 n -1}. Then w(f ) ≥ -3 - s ( -1) n-1 2 + 2k + s ( -1) n-1 1/2 . Proof. Let I = {i ∈ {1, . . . , k} : x i n = 1} that we denote I = {i 1 , . . . , i v } with i 1 < i 2 < • • • < i v . Let A = {α i = (α 1 i , . . . , α v i ) ∈ {0, . . . , deg(f )} v }
be a set of cardinality at most w(f ) which will be given explicitly later in the proof and W A be the set of vectors a ∈ (F * ) n such that:

1. a = (a 1 , . . . , a n ) ∈ S 36 Chapter 3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Functions 2. a satisfies α 1 i a x i 1 -1 + • • • + α v i a x iv -1 = a x k+1 -1 for all α i ∈ A Claim 3.3.6. We have |W A | ≥ ( -1) n -T 0 , where T 0 = s + w(f )k( -1) n-1 .
Proof. For a fixed tuple α i ∈ A, by proceeding exactly as in the proof of Claim 1 one can prove by induction in v that the number of a ∈ (F * ) n such that α 1 i a

x i 1 -1 + • • • + α v i a x iv -1 = a x k+1 -1 does not exceed v( -1) n-1 . Since the cardinality of A is at most w(f ) and v ≤ k, we thus have |W A | ≥ |S| -kw(f )( -1) n-1 .

There exists by the pigeonhole principle

b = (b 1 , . . . , b n-1 , 1) ∈ (F * ) n such that T = {a n ∈ F : a = (b 1 , . . . , b n-1 , a n ) ∈ W A } satisfies |T | ≥ -1 - T 0 ( -1) n-1 .
Then for all a n ∈ T , we have:

f g b x 1 , . . . , g b x i 1 -1 , g b x i 1 an , g b x i 1 +1 , . . . . . . , g b x iv -1 , g b x iv -1 an , g b x iv +1 , . . . , g b x k = g b x k+1 -1 an . Let H(X) = f g b x 1 , . . . , g b x i 1 -1 , X b x i 1 -1 , g b x i 1 +1 , . . . . . . , g b x iv -1 , X b x iv -1 , g b x iv +1 , . . . , g b x k -X b x k+1 -1
and K(X) the polynomial obtained from H(X) by reducing the exponents of every monomial modulo . If we choose A to be the set of vectors obtained from the multivariate polynomial f by considering the monomials with variables X i 1 , . . . , X iv from each monomial of f , then A is of cardinality at most w(f ) and does not depend on b. One can see that K(X) is a nonzero polynomial by the choice of b and has degree less than with at least |T | zeros. Hence by Lemma 2.2.3, we obtain:

w(f ) + 1 ≥ w(K) ≥ 1 + T 0 ( -1) n-1
, and (w(f ) + 1) 2( -1) n-1 + s + w(f )k( -1) n-1 ≥ ( -1) n . We thus have:

w(f ) 2 2( -1) n-1 + s + 2k( -1) n-1 ≥ ( -1) n -2( -1) n-1 -s,
and the result follows.

Theorem 3.3.5 gives a lower bound on the weight of explicit polynomials approximating the Naor-Reingold pseudo-random function and it immediately gives a lower bound on the weight of explicit polynomials approximating the n-partite Diffie-Hellman problem by some well chosen inputs:

Corollary 3.3.7. Let S ⊆ (F * ) n , with |S| = ( -1) n -s. Let f ∈ F q [X 1 , . . . , X n ] be a polynomial satisfying f (g a 1 , . . . , g an ) = g a 1 .
..an for all a = (a 1 , . . . , a n ) ∈ S. We have

w(f ) ≥ -3 - s ( -1) n-1 2 + 2n + s ( -1) n-1 1/2 .
3.3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Finite Fields 37

The next theorem extends the previous approach and gives a lower bound on the weight of implicit polynomials approximating the generalized Diffie-Hellman problem.

Theorem 3.3.8. Let S ⊆ (F * ) n , with |S| = ( -1) n -s. Let f ∈ F q [X 1 , . . . , X n+1 ] be a polynomial satisfying: f (g a 1 , . . . , g an , g a 1 ...an ) = 0, for all a = (a 1 , . . . , a n ) ∈ S, then w(f ) ≥ ( -1) n-1 2( -1) n-1 + s 1/2 . Proof. Let (α, β) ∈ {0, . . . , deg(f )} 2 } with (α, β) = (0, 0). Let A = {(α , β ) ∈ {0, . . . , deg(f )} 2 } be a set of cardinality at most w(f ) with (α, β) /
∈ A and let W A be the set of vectors a ∈ (F * ) n such that:

1. a = (a 1 , . . . , a n ) ∈ S 2. a satisfies α + β(a 2 . . . a n ) = α + β (a 2 . . . a n ) mod for all (α , β ) ∈ A Claim 3.3.9. We have |W A | ≥ ( -1) n -s -w(f )( -1) n-1 . Proof. Given (α , β ) ∈ A, the number of a ∈ (F * ) n such that α + β(a 2 . . . a n ) = α + β (a 2 . . . a n ) mod does not exceed ( -1) n-1 . Indeed, we have α -α + (β -β )(a 2 . . . a n ) = 0 mod ,
and we can easily see that ββ = 0 mod (since otherwise, we have αα = 0 mod ). Therefore, for any vector (a 1 , a 3 , • • • , a n ) ∈ (F * ) n-1 , the value of a 2 is defined uniquely.

Since the total number of couples (α , β ) does not exceed w(f ), the number of a ∈ S such that a / ∈ W A does not exceed w(f )( -1) n-1 .

There exists by the pigeonhole principle b

= (b 2 , . . . , b n ) ∈ (F * ) n-1 such that T = {a 1 ∈ F : a = (a 1 , b) ∈ W A } satisfies |T | ≥ -1 -w(f ) - s ( -1) n-1 .
Then for all a 1 ∈ T , we have:

f (g a 1 , g b 2 , . . . g bn , g a 1 b 2 ...bn ) = 0.
Let H(X) = f (X, g b 2 , . . . , g bn , X b 2 ...bn ) and K(X) the polynomial obtained from H(X) by reducing the exponents of every monomial modulo . If we choose A independent of b and of cardinality at most w(f ), as in the proof of Theorem 3.3.5 (but this time with variables X 1 and X n+1 ) , then K(X) is not a zero polynomial by the choice of b and has degree less than with at least |T | zeros. Hence by Lemma 2.2.3, we obtain:

w(f ) ≥ w(K) ≥ 1 + w(f ) + s ( -1) n-1
, and the result follows.

Polynomial Interpolation with fixed secret key

In this section, p is an odd prime number, n is an integer and g ∈ F * p is an element of prime order (with | p -1). We prove results on the univariate and multivariate polynomial interpolation of the Naor-Reingold pseudo-random function over finite fields. We consider polynomials that interpolates values of the Naor-Reingold pseudo-random function for a fixed secret key a ∈ (F * ) n . The values considered are evaluation of the function at integers x ∈ {0, • • • , 2 n -1} and translates of these values by some fixed constants

t 1 , t 2 , • • • , t k ∈ N.
This setting is interesting for applications in cryptography. Note that if one value x + t i is larger than 2 n for some i ∈ {1, . . . , k} then, the Naor-Reingold function is not defined at x + t i . In the following, we consider simple sets where all translates belong to the Naor-Reingold function domain but our method can be adapted to other settings.

First, we consider multivariate polynomial interpolation over large sets of values.

Theorem 3.3.10. Let t ≥ 1 be an integer. Let t 1 , t 2 , • • • , t k be fixed distinct integers such that t 1 , t 2 , • • • , t k < 2 t and let A ⊆ {0, • • • , 2 n -1}. For some a ∈ (F * ) n , let F a (X 1 , . . . , X k ) ∈ F p [X 1 , • • • , X k ] such that F a (f a (x), f a (x + t 1 ), • • • , f a (x + t k-1 )) = f a (x + t k ) (3.3)
for all x ∈ A. For all but at most 2k( -1) n-1 vectors a ∈ (F * ) n , we have

         deg(F a ) + k k ≥ 2∆ + 1 -1 w(F a ) ≥ 2∆ + 1 -1 where ∆ = -1 -S for the set S = {a 2 t x ∈ F * : 2 t x ∈ A},
It is worth noting that the conclusion of Theorem 3.3.10 cannot hold for all vectors a ∈ (F * ) n . For instance, if we consider a secret key a = (a 1 , . . . , a n ) ∈ (F * ) n such that a n-1 = a n and the simple case k = 1 and t 1 = 1, we have f a (x + t 1 ) = f a (x) for all integer x in the set A = {x ∈ {0, • • • , 2 n -1}, x ≡ 1 mod 4}, (since x = (x 1 , x 2 , . . . , x n-2 , 0, 1) and x + t 1 = (x 1 , x 2 , . . . , x n-2 , 1, 0)). The polynomial F a (X 1 ) = X 1 of degree 1 and weight 1 therefore satisfies (3.3) for all x ∈ A where the set A is very large since A = 2 n /4. However, Theorem 3.3.10 ensures that the lower bounds on the degree and the weight of F hold with probability 1 -2k/( -1) when the secret key a is picked uniformly at random (and hence with overwhelming probability for k polynomial in the security parameter). In Theorem 3.3.10 statement, it is also necessary to consider the cardinality of a subset of {a x ∈ F * , x ∈ A} and not the cardinality of A itself since it is possible that for some secret key a, the latter is "large" while the former is "small". For instance, for a secret key a = (a, . . . , a) ∈ (F * ) n (where all components are equal to some constant value a ∈ F * ), we have

f a (x) = g a x = g a hw(x)
where hw(x) denotes x's Hamming weight (i.e., its number of non-zero coordinates). In this case, even if the set A is very large, {a x ∈ F * , x ∈ A} is of cardinality at most n and one can construct a small degree multivariate polynomial that interpolates the values of the Naor-Reingold pseudo-random function.

Proof. Since t 1 , t 2 , • • • , t k < 2 t ,
F a (g u , g ua t 1 , • • • , g ua t k-1 ) = g ua t k , for all u ∈ S. Let R = {u ∈ S|u(a t k ) -1 ∈ S}.
We put ∆ = -1 -S and, by the union bound, we have R ≥ -1 -2∆ and Claim 3.3.11.

F a (g u(a t k ) -1 , • • • , g ua t k-1 (a t k ) -1 ) = g u , for all u ∈ R. Let H a (X) = F a (X (a t k ) -1 , • • • , X a t k-1 (a t k ) -1
) -X ∈ F p [X] and K a (X) the polynomial obtained from H a (X) by considering the degree of monomials of H a (X) modulo .

Claim. The polynomial K a (X) is not a zero polynomial for all but at most 2k( -

1) n-1 vectors a ∈ (F * ) n . Proof. Indeed if K a (X) is a zero polynomial, then • either F a is a monomial of the form X α 1 1 • • • X α k k , with (α 1 , • • • , α k ) = (0, • • • , 0)
• or F a would be a sum of at least two monomials

X α 1 1 • • • X α k k and X β 1 1 • • • X β k k and there would exist (α 1 , • • • , α k ) = (β 1 , • • • , β k ) such that α 1 (a t k ) -1 + • • • + α k a t k-1 (a t k ) -1 = β 1 (a t k ) -1 + • • • + β k a t k-1 (a t k ) -1 in F . If F a is of the form X α 1 1 • • • X α k k , then from (3.3), it will follows that α 1 a x + • • • + α k a x+t k-1 = a x+t k in F , for all x ∈ A.
(3.4) Let x such that (3.4) is satisfied. Then we can easily prove for all n ≥ 1 by induction in k that the number of a ∈ (F * ) n solutions of (3.4) does not exceed k( -1) n-1 .

1. For k = 0, the equation a x+t k = 0 has no solution and the statement is clearly true.

2. Otherwise, let j = max({i ∈ {1 . . . , k}|α i = 0}). Because x + t k = x + t j , there exists

i such that i-th component of x + t k is different from the i-th component of x + t j .
Then the above equation can be written in the form T 1 = T 2 a i where T 1 and T 2 do not depend on a i . If T 2 = 0, then for any vector (a

1 , • • • , a i-1 , a i+1 , • • • , a n ) ∈ (F * ) n-1 ,
the value of a i is defined uniquely. If T 2 = 0, then by induction, the number of (a

1 , • • • , a i-1 , a i+1 , • • • , a n ) ∈ (F * ) n-1 does not exceed (k -1)( -1) n-1 .
Therefore, the number of solutions does not exceed (k -1)( -

1) n-1 + ( -1) n-1 = k( -1) n-1
, and the result follows.

In the second case, if there exists (α

1 , • • • , α k ) = (β 1 , • • • , β k ) such that α 1 (a t k ) -1 + • • • + α k a t k-1 (a t k ) -1 = β 1 (a t k ) -1 + • • • + β k a t k-1 (a t k ) -1 in F then we have (α 1 -β 1 )a 0 + • • • + (α k -β k )a t k-1 = 0 in F .
Then by proceeding as previously by induction on k, for all n, one can see that the number of solutions a ∈ (F * ) n does not exceed (k -1)( -1) n-1 .

For a ∈ (F * ) n such that K a (X) is not a zero polynomial, we have by Lemma 2.2.1, that w(K a (X)) ≥ -( -1-2∆) , since deg(K a (X)) ≤ -1 and K a (X) has at least -1 -2∆ roots of the g u . Therefore, by Lemma 2.2.1, we have

         deg(F a ) + k k ≥ 2∆ + 1 w(F a ) ≥ 2∆ + 1 -1
for all but at most 2k( -1) n-1 vectors a ∈ (F * ) n and the result follows.

Remark 3.3.12. Theorem 3.3.10 is non-trivial only when S ≥ (3 -2)/4. Since S ≤ 2 n-t , Theorem 3.3.10 only applies to settings where the message length n is greater than the sum of the bit-length of the underlying group order and t. The cardinality of the set S depends on A and on the secret key a = (a 1 , . . . , a n ) ∈ (F * ) n . In the following lemma for certain condition on A and on n, we show that S is close to for almost all secret key a. This allows us to obtain Corollary 3.3.14 and for the forthcoming theorems in this Chapter to obtain non trivial lower bounds.

Lemma 3.3.13. Let γ > δ > 0 such that n ≥ (1 + γ) log( -1). Let t = min (1, (γ -δ)/2) log( -1) -1 and let A ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A. Putting Γ = ( -1)2 -t , we obtain: S ≥ -1 -Γ, for all but at most ( -1) n-δ vectors a ∈ (F * ) n .
Proof. We denote again S = {a 2 t x ∈ F * : 2 t x ∈ A}.

Putting Γ = ( -1)2 -t and applying Lemma 3.2.1, we have S ≥ -1 -Γ for all but at most 2 t-n Γ -1 ( -1) n+2 ≤ ( -1) n-δ vectors a ∈ (F * ) n .

We apply Lemma 3.3.13 to Theorem 3.3.10 to obtain the following corollary:

Corollary 3.3.14. Let γ > δ > 0 such that n ≥ (1+γ) log( -1). Let t = min (1, (γ -δ)/2) log( - 1) -1 and t 1 , t 2 , • • • , t k be fixed distinct integers such that t 1 , t 2 , • • • , t k < 2 t and let A ⊆ {0, • • • , 2 n -1}. For some a ∈ (F * ) n , let F a (X 1 , . . . , X k ) ∈ F p [X 1 , • • • , X k ] such that Relation (3.3) holds for all x ∈ A. If {2 t x : x = 0, . . . , 2 n-t -1} ⊆ A, we have        deg(F a ) + k k ≥ 1 8 ( -1) min(1,(γ-δ)/2) w(F a ) ≥ 1 8 ( -1) min(1,(γ-δ)/2) -1
for all but at most 2k( -

1) n-1 + ( -1) n-δ vectors a ∈ (F * ) n .
The proof is straightforward since, with the previous notation, we have in this case ∆ < Γ. Likewise Lemma 3.3.13 can be applied to the next theorems of this paper to obtain non-trivial lower bounds for almost all vectors a ∈ (F * ) n .

For the cases where the cardinality of the set S is smaller than (3 -2)/4, Theorem 3.3.10 does not give a non-trivial lower bound on F 's degree. In the next theorem, we obtain such a lower bound for much smaller sets

A ⊆ {0, • • • , 2 n -1}. For some a ∈ (F * ) n , let F a (X) ∈ F p [X] such that F a (f a (x)) = f a (x + t) (3.5)
for all x ∈ A. For all but at most 2( -1) n-1 vectors a ∈ (F * ) n , we have

deg(F a ) ≥ S( S -1) -1 .
where S = {a 2 t x ∈ F * : 2 t x ∈ A}.

Proof. As in the previous proof, we have

F a (g u ) = g ua t for all u ∈ S.
Consider

D = {1 ≤ b ≤ -1 : b ≡ y -x mod , x, y ∈ S}.
There exists b ∈ D such that there are at least

S( S -1) D ≥ S( S -1) -1 representations b ≡ y -x mod , with x, y ∈ S.
We choose this b and put

R = {x ∈ S : b + x ≡ y mod , y ∈ S}.
Then we have

R ≥ S( S -1) -1 .
For u ∈ R, (since g x = g x+ , for all x), we have

F a (g u+b ) = g (u+b)a t = g ua t × g ba t = F a (g u ) × g ba t Let H a (X) = F a (g b X) -g ba t F a (X)
. Then H a (X) has at least R zeros. As in the previous proof, H a (X) = 0 for all but at most 2( -

1) n-1 vectors a ∈ (F * ) n and deg(H a ) ≤ deg(F a ), we have deg(F a ) ≥ S( S -1) -1 .
for all but at most 2( -1) n-1 vectors a ∈ (F * ) n .

In the following lemma, we show that there exists numerous sets A and corresponding

≤ s ≤ log(3 -2) -2 -(1/2 + δ) log( -1) . Let A ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A. Putting γ = 1 -log(3)(1/2 + δ) we obtain: (3 -2)/4 ≥ S ≥ ( -1) (1/2+δ)
for all but at most 3/2( -1) n-γ vectors a ∈ (F * ) n .

Proof. We denote again S = {a 2 t x ∈ F * : 2 t x ∈ A}.

Putting j = (1/2 + δ) log( -1) and applying Lemma 3.2.2, we obtain readily S ≥ ( -1) (1/2+δ) for all but at most (3 j -1)( -

1) n-1 ≤ 3/2( -1) n-γ vectors a ∈ (F * ) n . Since S ≤ 2 j+s ≤ (3 -2)/4
, we obtain the desired result.

For such sets A and S and parameters n, t, s given in Lemma 3.3.16, we have (using the notation of Theorem 3.3.15), that the degree of polynomial F a satisfying (3.5) verifies deg(F a ) ≥ c • 2δ for all but at most 2( -1) n-1 + 3/2( -1) n-γ vectors a ∈ (F * ) n (where c is an absolute constant close to 1). Remark 3.3.17. This proof technique cannot be used to obtain a lower bound on the weight of a univariate polynomial F or on the degree of a multivariate polynomial F for k ≥ 2 and it remains an open problem to improve Theorem 3.3.10 for smaller sets S with #S ≤ (3 -2)/4 in these settings. Elliptic Curves In this section, p is an odd prime number, n is an integer, E is an elliptic curve over F p and P is a point of the curve E with prime order (with | #E(F p )). We prove results on the univariate polynomial interpolation of the Naor-Reingold pseudo-random function from elliptic curves defined by f a (x) = X([a x ]P ) for a secret key a ∈ (F * ) n and an integer x ∈ {0, 1, . . . , 2 n -1} (where X(Q) denotes the abscissa of a point Q ∈ E(F p )). First, we consider interpolation over large sets of values.

Polynomial Interpolation of the

Theorem 3.4.1. Let E : y 2 = x 3 + γx + δ be an elliptic curve over F p with γδ = 0. Let t ≥ 1 be a fixed integer and let

A ⊆ {0, • • • , 2 n -1}. For some a ∈ (F * ) n , let F a (X) ∈ F p [X] such that F a (f a (x)) = f a (x + t) (3.6)
for all x ∈ A. For all but at most 2( -1) n-1 vectors a ∈ (F * ) n , we have

deg(F a ) ≥ 2 S -( -1) 14 .
where S = {a 2 t x ∈ F * : 2 t x ∈ A}.

3.4. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Elliptic Curves 43

Proof. We have F a (x u ) = x ua t for all u ∈ S, where x t = X([t]P ), for all t ∈ F . We consider the R = {u ∈ S : 2u ∈ S} with R ≥ -1 -2∆. For all u ∈ R, 2u ∈ S and [2u]P = O and F a (x 2u ) = x 2ua t is well-defined in F p and x ua t is thus not a root of ψ 2 . Therefore, we have:

F a (x 2u ) = x 2ua t = θ 2 (x ua t )/ψ 2 2 (x ua t ) = θ 2 (F a (x u ))/ψ 2 2 (F a (x u )), for all u ∈ R.
We thus get

F a θ 2 (x u ) ψ 2 2 (x u ) = θ 2 (F a (x u )) ψ 2 2 (F a (x u
)) for all u ∈ R. Finally, we consider the polynomial:

H a (X) = ψ 2d 2 (X)ψ 2 2 (F a (X)) F a θ 2 (X) ψ 2 2 (X) - θ 2 (F a (X)) ψ 2 2 (F a (X))
,

where d = deg(F a ).
The polynomial H a (X) has at least R/2 zeros. If a t = ±1, we will have F a (X) = X and by Lemma 2.3.1, it will imply that there exists α ∈ F p such that ψ 2 2 (F a (α)) = 0 and ψ 2 2 (α) = 0. Hence, we have H a (α) = -θ 2 (F a (α))ψ 2d 2 (α) = 0, since θ 2 (X) and ψ 2 2 (X) have no common zeros. Therefore, H a (X) is a non-zero polynomial and deg(H a ) ≤ 7d. Then we get that 7d ≥ R/2 and then d ≥ -1-2∆

14

. Since a t = ±1 for all but at most 2( -1) n-1 vectors a ∈ (F * ) n , the result follows.

Theorem 3.4.1 is only non-trivial if S ≥ ( + 13)/2. Again, the cardinality of the set S depends on A and on the secret key a = (a 1 , . . . , a n ) ∈ (F * ) n , but using again Lemma 3.3.13, we can easily obtain (as in Corollary 3.3.14) non-trivial lower bounds for specific sets A and parameter n.

In the following theorem, we obtain a lower bound for smaller sets S.

Theorem 3.4.2. Let t ≥ 1 be a fixed integer,

A ⊆ {0, • • • , 2 n -1}, 0 < < 1 and S = {a 2 t x ∈ F * : 2 t x ∈ A} with S ≥ 2( -1) log( ) . For some a ∈ (F * ) n , let F a (X) ∈ F p [X] such that F a (f a (x)) = f a (x + t) (3.7)
for all x ∈ A. For all but at most 2( -1) n-1 vectors a ∈ (F * ) n , we have

deg(F a ) ≥ S 4 log( ) × 2 .
Proof. We have F a (x u ) = x ua t for all u ∈ S where, as above, we denote x t = X([t]P ), for all t ∈ F . Let K be an integer and let us consider the sets

S i = {1 ≤ b ≤ -1 : 2 i m ≡ b mod , m ∈ S}, for 0 ≤ i ≤ K, and R i,j = S i ∩ S j for 0 ≤ i < j ≤ K. We have (K + 1) S - 0≤i<j≤K R i,j ≤ K i=0 S i ≤ -1.
44 Chapter 3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Functions Therefore, there is a pair 0 ≤ i < j ≤ K such that R 0,j-i = R i,j ≥ 2((K + 1) S -( -1))

K(K + 1) .

For u ∈ R 0,j-i , there exists a unique m ∈ S such that 2 j-i m ≡ u mod , with u ∈ S and the corresponding m's are distinct for two different u's. Since x k = x k+l for all k, then we have

F a (x 2 j-i m ) = x 2 j-i ma t for at least R 0,j-i different m ∈ S.
For each such m, we have

F a θ 2 j-i (xm) ψ 2 2 j-i (xm) = x 2 j-i ma t = θ 2 j-i (x ma t )/ψ 2 2 j-i (x ma t ) = θ 2 j-i (F a (x m ))/ψ 2 2 j-i (F a (x m )),
since m ∈ S. Finally, we consider the polynomial

H a (X) = ψ 2d 2 j-i (X)ψ 2 2 j-i (F a (X)) F a θ 2 j-i (X) ψ 2 2 j-i (X) - θ 2 j-i (F a (X)) ψ 2 2 j-i (F a (X))
,

where d = deg(F a ).
The polynomial H a (X) has at least R 0,j-i zeros. Since d ≥ 2 and 2 j-i and p are coprime, then by Lemma 2.3.2, there exists α ∈ F p such that ψ 2 2 j-i (F a (α)) = 0 and ψ 2 2 j-i (α) = 0. Hence, we have

H a (α) = -θ 2 j-i (F a (α))ψ 2d 2 j-i (α) = 0, since θ 2 j-i (X) and ψ 2 2 j-i (X) have no common zeros.
Therefore H a (X) is a non-zero polynomial and deg(H a ) ≤ d(2(2 j-i ) 2 -1) and we get

d ≥ R 0,j-i 2(2 2(j-i)+1 -1) ≥ (K + 1) S -( -1)
K(K + 1)(2 2(j-i)+1 -1) .

Since ji ≤ K, then we have

d ≥ (K + 1) S -( -1) K(K + 1)(2 2K+1 -1) ≥ 1 2 2K+1 -1 S K - -1 K(K + 1) ≥ S K(2 2K+1 -1) 1 - -1 S(K + 1)
.

Letting K = log( ) , for any 0 < < 1, we have

d ≥ S 2 log( ) × 2 1 - -1 S log( ) ≥ S 4 log( ) × 2 .
Theorem 3.4.2 also applies to numerous sets A and S for which Theorem 3.4.1 does not apply. For instance, we can consider parameters n, t, s given in Lemma 3.3.16 such that 2 n-t-s ≥ 2( -1) log( ) .

3.4. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Elliptic Curves 45

Bivariate Interpolation of the Naor-Reingold Pseudo-Random Function over

Elliptic Curves It seems rather difficult to obtain an analogue of Theorem 3.3.10 in the case of elliptic curves. In this section, we use the methods from [START_REF] Lange | Interpolation of the Elliptic Curve Diffie-Hellman Mapping[END_REF] and we prove results on bivariate interpolation of the Naor-Reingold pseudo-random function from elliptic curves (but in a slightly different setting). We use the notation from the previous section and, as before, we consider first interpolation over large sets of values.

Theorem 3.4.3. Let A 1 , A 2 ⊆ {0, • • • , 2 n -1} and t ≥ 1 be an integer. For some a ∈ (F * ) n , let F a (X, Y ) ∈ F p [X, Y ] such that F a (f a (x), f a (x )) = f a (x + x ) (3.8) for all (x, x ) ∈ A 1 × A 2 . We have deg(F a ) ≥ min ( -1)/∆ -2; ( S 2 -1) 1/3 -2 .
where ∆ = -1 -S 1 for the set

S 1 = {a x : x ∈ A 1 , x < 2 t } and where S 2 = {a 2 t x ∈ F * : 2 t x ∈ A 2 }.
Proof. We may suppose S 2 ≥ 10 since otherwise the result is trivial. We denote

d = min ( -1)/∆ -2; ( S 2 -1) 1/3 -2 . We have F a (x u , x u ) = x uu , for all u ∈ S 1 and u ∈ S 2 . Let R be the set of u ∈ S 1 such that ia mod ∈ S 1 , ∀i ∈ {1, • • • , d + 1}.
The cardinality of R is at least -1 -∆(d + 1). Let u ∈ R, then we have

F a (x (i+1)u , x v j ) = x (i+1)uv j , for all 0 ≤ i, j ≤ d, where v 0 , • • • , v d are any distinct elements of S 2 . Let us suppose that deg X (F a ), deg Y (F a ) ≤ d namely F a (X, Y ) = d i,j=0 c i,j X i Y j , then we have for 0 ≤ k, ≤ d, x (k+1)uv = d i,j=0 c i,j x i (k+1)u x j v .
Then F a 's coefficients are determined by the following matrix equation:

C =    c 0,0 . . . c 0,d . . . . . . c d,0 . . . c d,d    =     x 0 u . . . x d u . . . . . . x 0 (d+1)u . . . x d (d+1)u     -1    x uv 0 . . . x uv d . . . . . . x (d+1)uv 0 . . . x (d+1)uv d       x 0 v 0 . . . x 0 v d . . . . . . x d v 0 . . . x d v d    46
, • • • , d ω ∈ F p , d ω = 0, such that ω k=1 d k x kub = 0, b ∈ S 2 .
As at most two points with first coordinate equal to 0 exist on the elliptic curve and S 2 ≥ 3, we get ω ≥ 2. Since x kub = θ k (x ub )/ψ 2 k (x ub ), the polynomial

H(X) = ω k=1 d k θ k (X) ω j=1,j =k ψ 2 j (X)
has at least S 2 /2 zeros and degree at most

1 + ω k=1 (k 2 -1) = (2ω 3 + 3ω 2 -5ω + 6)/6 ≤ ω 3 /2 ≤ (d + 1) 3 /2.
Since p ω, then points of order ω on E exist over F p . Let α ∈ F p be the first coordinate of a point of order ω. Then we have ψ 2 ω (α) = 0 and

H(α) = d ω θ ω (α) ω-1 j=1 ψ 2 j (α) = 0. The polynomial H(X)
-t ≥ (1 + δ) log( -1) + 2. Let A 1 , A 2 ⊆ {0, • • • , 2 n -1} be two sets such that {0, . . . , 2 t -1} ⊆ A 1 and {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A 2 . Let S 1 = {a x : x ∈ A 1 , x < 2 t } and S 2 = {a 2 t x ∈ F * : 2 t x ∈ A 2 }, we have S 1 ≥ -1 -( -1)2 -m and S 2 ≥ ( -1)/2 + 1,
for all but at most 2( -1) n-δ vectors a ∈ (F * ) n .

Proof. Let ∆ = ( -1)2 -m . Applying Lemma 3.2.1, we have

S 1 ≥ -1 -∆ for all but at most 2 -t ∆ -1 ( -1) t+2 ( -1) n-t ≤ ( -1) n-δ vectors a ∈ (F * ) n . Likewise, applying Lemma 3.2.1 with ∆ = ( -1)/2 -1 , we have S 2 ≥ ( -1)/2 + 1 for all but at most 2 t-n ∆ -1 ( -1) n-t+2 ( -1) t ≤ ( -1) n-δ vectors a ∈ (F * ) n .
We apply Lemma 3.4.4 to Theorem 3.4.3 to obtain the following corollary: Corollary 3.4.5. Let m ≥ 1 be an integer and δ > 0 such that t ≥ (1 + δ) log( -1) + m + 1

and n -t ≥ (1 + δ) log( -1) + 2. Let A 1 ⊆ {0, • • • , 2 n -1} such that {0, . . . , 2 t -1} ⊆ A 1 and A 2 ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A 2 . For some a ∈ (F * ) n , let F a (X, Y ) ∈ F p [X, Y ] such that F a (f a (x), f a (x )) = f a (x + x ) (3.9)
3.4. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Elliptic Curves 47

for all (x, x ) ∈ A 1 × A 2 . We have deg(F a ) ≥ min 2 m -2; (( -1)/2) 1/3 -2 ,
for all but at most 2( -1) n-δ vectors a ∈ (F * ) n .

The proof is straightforward since, with the of notation of Theorem 3.4.3, we have in this case ∆ ≤ ( -1)2 -m and S 2 -1 ≥ ( -1)/2.

To conclude this section, we obtain a simple result for smaller sets S 1 .

Theorem 3.4.6. Let A 1 , A 2 ⊆ {0, • • • , 2 n -1} and t ≥ 1 be an integer. For some a ∈ (F * ) n , let F a (X, Y ) ∈ F p [X, Y ] such that F a (f a (x), f a (x )) = f a (x + x ) (3.10) for all (x, x ) ∈ A 1 × A 2 . We have deg(F a ) ≥ S 1 8 .
where

S 1 = {a x : x ∈ A 1 , x < 2 t } and S 2 = {a 2 t x ∈ F * : 2 t x ∈ A 2 } if there exists v ∈ S 2 such that 2v ∈ S 2 .
Proof. We have

F a (x u , x v ) = x uv and F a (x u , x 2v ) = x 2uv for all u ∈ S 1 .
Hence

F a x u , θ 2 (x v ) ψ 2 2 (x v ) = θ 2 (x uv ) ψ 2 2 (x uv ) = θ 2 (F a (x u , x v )) ψ 2 2 (F a (x u , x v )) for all u ∈ S 1 .
Finally, we consider the polynomial

U (X) = ψ 2 2 (F a (X, x v )) F a (X, θ 2 (x v ) ψ 2 2 (x v ) ) - θ 2 (F a (X, x v )) ψ 2 2 (F a (X, x v )) .
We have deg(U ) ≤ 4 deg(F a ). Let γ be a root of ψ 2 2 (X) and β such that F a (β,

x v ) = γ. Then U (β) = -θ 2 (F a (β, x v )) = 0,
and U is non-zero polynomial. Since U has at least S 1 /2 zeros, it follows that 4 deg(F a ) ≥

S 1 /2 i.e. deg(F a ) ≥ S 1 8 .
The condition on S 2 in the statement of Theorem 3.4.6 is achieved trivially when S 2 > -1 2 . It is worth mentioning that Theorem 3.4.6 also applies to many other sets. In the following lemma, we show that there exists numerous sets A 1 , A 2 and corresponding S 1 , S 2 such that Let t and n be integers such that t = (1/2 + δ 1 ) log( -1) + s for some integer s such that

S 1 ∈ [ √ + 1, ( -
0 ≤ s ≤ log( -1) -1 -(1/2 + δ 1 ) log( -1) and n -t ≥ (1 + δ 2 ) log( -1) + 2. Let A 1 ⊆ {0, • • • , 2 n -1} such that {0, . . . , 2 t -1}} ⊆ A 1 and A 2 ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A 2 . Putting γ = 1 -log(3)(1/2 + δ 1 )
we obtain:

( -1)/2 ≥ S 1 ≥ ( -1) (1/2+δ 1 ) and S 2 ≥ ( -1)/2 + 1,
for all but at most 3/2( -1) n-γ + ( -1) n-δ 2 vectors a ∈ (F * ) n . We then apply Lemma 3.4.7 to Theorem 3.4.6 to obtain the following corollary:

Corollary 3.4.8. Let 1 log(3) -1 2 > δ 1 > 0, δ 2 > 0 and γ = 1 -log(3)(1/2 + δ 1 )
. Let t and n be integers such that t = (1/2 + δ 1 ) log( -1) + s for some integer s such that

0 ≤ s ≤ log( -1) -1 -(1/2 + δ 1 ) log( -1) and n -t ≥ (1 + δ 2 ) log( -1) + 2. Let A 1 ⊆ {0, • • • , 2 n -1} such that {0, . . . , 2 t -1}} ⊆ A 1 and A 2 ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A 2 . For some a ∈ (F * ) n , let F a (X, Y ) ∈ F p [X, Y ] such that F a (f a (x), f a (x )) = f a (x + x ) (3.11) for all (x, x ) ∈ A 1 × A 2 . We have deg(F a ) ≥ ( -1) (1/2+δ 1 ) /8,
for all but at most 3/2( -

1) n-γ + ( -1) n-δ 2 vectors a ∈ (F * ) n .
The proof is straightforward since, with the notation of Theorem 3.4.6, we have in this case S 1 ≥ ( -1) (1/2+δ 1 ) and there exists v ∈ S 2 such that 2v ∈ S 2 since S 2 > ( -1)/2

Polynomial Interpolation with variable secret key

In this section, p is an odd prime number and we prove results on the approximation by a polynomial with k ≥ 1 variables of the Naor-Reingold pseudo-random function from elliptic curves. For a positive integer t, we denote X(tP ) by x t .

Theorem 3.4.9. Let n be an integer, S ⊆ (F * ) n , with |S| = ( -1) ns. Let f ∈ F p [X 1 , . . . , X k ], be a polynomial satisfying:

f (x a x 1 , . . . , x a x k ) = x a x k+1 , for all a = (a 1 , . . . , a n ) ∈ S, for some values x 1 , . . . , x n ∈ {0, • • • , 2 n -1} such that x 1 1 = 1, x k+1 1 = 1 and x i 1 = 0 for i ∈ {2, . . . , k}. Then deg(f ) ≥ -1 14 - s 7( -1) n-1 . Proof. Let W = {a ∈ (F * ) n : a = (a 1 , . . . , a n ) ∈ S and (2a 1 , . . . , a n ) ∈ S}, then |W | ≥ ( -1) n -2s. Then there exists b = (b 2 , . . . , b n ) ∈ (F * l ) n-1 such that the set T = {a 1 ∈ (F * l ) : a = (a 1 , b 2 , . . . , b n ) ∈ W } satisfies |T | ≥ ( -1) -2s/( -1) n-1 . Thus for all a 1 ∈ T , putting a = (a 1 , b 2 , . . . , b n ), we have: f (x a x 1 , . . . , x b x k ) = x a x k+1 f (x 2a x 1 , . . . , x b x k ) = x 2a x k+1
3.4. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Elliptic Curves 49

Hence for all a 1 ∈ T , we have:

f θ 2 (x a 1 b x 1 ) ψ 2 2 (x a 1 b x 1 ) , . . . , x b x k = θ 2 (f ((x a 1 b x 1 , . . . , x b x k ))) ψ 2 2 (f ((x a 1 b x 1 , . . . , x b x k )))
We consider the polynomial:

H(X) = ψ 2d 2 (X)f θ 2 (X) ψ 2 2 (X) , . . . , x b x k ψ 2 2 (f (X, . . . , x b x k )) -ψ 2d 2 (X)θ 2 (f (X, . . . , x b x k ))
where

d = deg X 1 f . Let γ be a root of ψ 2 2 (X),then H(γ) = cθ d 2 (γ) = 0, for some coefficient c ∈ F * p .
Thus H is a nonzero polynomial and we have deg H ≤ 7d ≤ 7 deg f . Since H has at least |T |/2 ≥ ( -1)/2s/( -1) n-1 ) zeros, we obtain:

deg(f ) ≥ -1 14 - s 7( -1) n-1 .
Chapter 4.

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

In 2005, Dodis and Yampolskiy [START_REF] Dodis | A Verifiable Random Function with Short Proofs and Keys[END_REF] proposed an efficient 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:

V x : {1, . . . , d} -→ G m -→ V x (m) = g 1 x+m if x + m = 0 mod t and 1 G otherwise.
The Dodis-Yampolskiy pseudo-random function family has found numerous applications in cryptography (e.g., for compact e-cash [START_REF] Camenisch | Compact E-Cash[END_REF] or anonymous authentication [START_REF] Camenisch | How to win the clonewars: Efficient periodic n-times anonymous authentication[END_REF]). Dodis and Yampolskiy showed that their construction has some very attractive security properties, provided that some assumption about the hardness of breaking the so-called

Decision Diffie-Hellman Inversion problem holds in G [DY05]

. This assumption is nonstandard and Cheon [START_REF] Hee | Discrete Logarithm Problems with Auxiliary Inputs[END_REF] proved that it is stronger than the classical discrete logarithm assumption in G. In this Chapter, we study the distribution of the Dodis-Yampolskiy pseudo-random function over finite fields and over elliptic curves and prove lower bounds on the degree of polynomials which interpolate these functions. The first section deals with the distribution of the Dodis-Yampolskiy pseudo-random function over finite fields and over elliptic curves. In the second section, we prove lower bounds on the degree of polynomials interpolating this pseudo-random function over finite fields and we conclude the chapter by proving lower bounds on the degree of polynomials interpolating this pseudo-random function over an elliptic curve.

Contents

-51 -

Distribution of the Dodis-Yampolskiy Pseudo-Random Functions

For a sequence of N points Γ = (γ 0,n , . . . , γ s-1,n ) n∈{1,...,N } in the s-dimensional unit cube, we define its discrepancy by D Γ :

D Γ = sup B⊆[0,1) s T Γ (B) N -|B| ,
where T Γ (B) denotes the number of points of the sequence Γ in a box B (i.e. a polyhedron

[α 0 , β 0 ) × • • • × [α s-1 , β s-1
) ⊆ [0, 1) s ) of volume |B| and the supremum is taken over all such boxes. For an integer vector a = (a 0 , . . . , a s-1 ) ∈ Z s , we define |a| = max ν∈{0,...,s-1} |a ν | and r(a) = s-1 ν=0 max{|a ν |, 1}. A critical issue with a pseudo-random sequence Γ in the s-dimensional unit cube is that it may not be perfectly equidistributed namely spread in a given volume of the s-dimensional unit cube (as it is the case in quasi-Monte Carlo methods ). Sequences in [0, 1) s with low discrepancy will spread over [0, 1) s as uniformly as possible, reducing gaps and clustering of points. In order to show that a sequence Γ is uniformly distributed, we need to show that its discrepancy D Γ is very small (i.e. tends to 0). The following lemma is our main tool for finding non-trivial upper bound for the discrepancy. It is a slightly weaker form of the Koksma-Szüsz inequality [DT97, Theorem 1.21]. The implied constant in the symbol " " depends on the integer s. Lemma 4.1.1. For any integer L > 1 and any sequence Γ of N points, we have

D Γ 1 L + 1 N 0<|a|<L 1 r(a) N n=1 e s-1 ν=0 a ν γ ν,n ,
where the sum is taken over all integer vectors a ∈ Z s with 0 < |a| < L.

We also need the well-known orthogonality relation:

Distribution of the Dodis-Yampolskiy Pseudo-Random Function over Finite Fields

Let q = p r be a prime power for some integer r > 1, let g ∈ F * q be an element of prime order t. For x ∈ Z t and d ≤ t, we denote by D x (d) the discrepancy of the points (

V x,1 (n)/p, . . . , V x,r (n)/p) for 1 ≤ n ≤ d, where V x (n) = g 1 x+n ∈ F p r and V x (n) = V x,1 (n)β 1 + • • • + V x,r (n)β r ,
D x (d) ≤ t 1-α k,l q β k,l +o(1) d , where α k,l = 1 2(2k+l) -1 4kl and β k,l = 1 4(2k+l) .
Proof. From Lemma 4.1.1, we derive

D x (d) 1 p + 1 d 0<|a|<p 1 r(a) d n=1 e p   r j=1 a j V x,j (n)   ,
where a = (a 1 , . . . , a r ). Set

S d (a) = d n=1 e p ( r j=1 a j V x,j (n)).
Let {δ 1 , . . . , δ r } be the dual basis of the given ordered basis {β 1 , . . . , β r }. For j ∈ {1, . . . , r} and n ∈ {1, . . . , d}, we have V x,j (n) = Tr(δ j V x (n)), where Tr denotes the trace of F p r over

F p (namely Tr(x) = x + x p + • • • + x p r-1
). Therefore,

S d (a) = d n=1 e p   Tr   r j=1 a j δ j V x (n)     = d n=1 e p (Tr(α a V x (n)))
where α a = r j=1 a j δ j ∈ F p r . Let χ be defined by χ(z) = e p (Tr(z)). Then χ is a non trivial additive character on F p r . Since there exists j ∈ {1, . . . , r} such that a j = 0, then α a = 0. We have:

S d (a) = d n=1 χ(α a V x (n)) with α a = 0.
We have

S d (a) = x+d n=x+1 n∈Z * t χ(α a g 1/n ) = 1 t n∈Z * t χ(α a g 1/n ) × t-1 c=0 x+d v=x+1 v∈Z * t e t (c(n -v)) = 1 t t-1 c=0   n∈Z * t χ α a g 1/n e t (cn)   × x+d v=x+1 v∈Z * t e t (-cv).
By applying Proposition 2.4.1 and (4.2), we obtain 1) .

S d (a) ≤ 1 t t-1 c=0 x+d v=x+1 v∈Z * t e t (-cv) × t 1-α k, q β k, +o(1) ≤ t 1-α k, q β k, +o (
4.1. Distribution of the Dodis-Yampolskiy Pseudo-Random Functions

55

By applying this bound to D x (d), we have

D x (d) 1 p + t 1-α k,l q β k, +o(1) d 0<|a|<p 1 r(a) 1 p + t 1-α k, q β k, +o(1) d log r p ≤ t 1-α k, q β k, +o(1) d
With the choice k = 4, l = 8, t = q 1+o(1) and d = t 127 128 + , we obtain 1) .

D x (d) ≤ p r(-+o(1)) = q -+o(

Distribution of the Dodis-Yampolskiy Pseudo-Random Function over Elliptic Curves

Let E : y 2 = x 3 + Ax + B, be an elliptic curve over F p . For P ∈ E(F p ) of prime order t, for

x ∈ Z t , and for 1 ≤ d ≤ t we denote by D x (d) the discrepancy of the points (X(V x (n))/p) for n ∈ {1, . . . , d} where V x (n) = 1 x+n P ∈ E(F p ). We obtain the following theorem. Theorem 4.1.3. For any x ∈ Z t , any integers k ≥ 2, l ≥ 1 and 1 ≤ d ≤ t, we have:

D x (d) ≤ t 1-α k, p β k, +o(1) d ,
where

α k, = 1 2(4k+ ) -1 4k and β k, = 1 4(4k+ )
.

Proof. From Lemma 4.1.1, we derive

D x (d) 1 p + 1 d 0<|a|<p 1 |a| d n=1 e p (aX(W x (n))) ,
where a is an integer. Set

S d (a) ≤ 1 t t-1 c=0 x+d v=x+1 v∈Z * t e t (-cv) × t 1-α k, p β k, +o (1)
≤ t 1-α k, p β k, +o (1) 56 Chapter 4. Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function

By applying this bound to D x (d), we have

D x (d) 1 p + t 1-α k, p β k, +o(1) × 1 d 0<|a|<p 1 |a| 1 p + t 1-α k, p β k,l +o(1) × 1 d log p ≤ t 1-α k, p β k, +o (

Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function over Finite Fields

Let g ∈ F * p r for some integer r > 1, be an element of prime order t | p r -1. In this section, we prove a lower bound on the degree of univariate polynomial interpolation of the Dodis-Yampolskiy pseudo-random function over finite fields. We consider polynomials that interpolate values of the Dodis-Yampolskiy pseudo-random function for a fixed secret key

x ∈ F * t .
The values considered are evaluation of the function at integers n ∈ {1, . . . , d} for some integer 1 ≤ d ≤ t and translates of these values by some fixed constants λ ∈ N. This setting is interesting for applications in cryptography [START_REF] Camenisch | Compact E-Cash[END_REF][START_REF] Camenisch | How to win the clonewars: Efficient periodic n-times anonymous authentication[END_REF]. Note that if one value n is larger than d then, the Dodis-Yampolskiy function is not necessarily defined at n + λ. In the following, we consider simple sets where all translates belong to the function domain but our method can be adapted to other settings. Theorem 4.2.1. Let λ be a fixed integer and let A ⊆ {1, . . . , d}. For some x ∈ F * t , let F (X) ∈ F p [X] be such that F (g

1 x+n ) = g 1 x+n+λ for all n ∈ A. We have deg(F ) ≥ t -2s 4 and w(F ) ≥ t 4s 1/2
where A = ts.

Proof. Let R = {(n+x) mod t : n ∈ A}. Then R ⊆ F t and R = t-s. We have F (g

1 n ) = g 1 n+λ for all n ∈ R. Noticing that 1 n+λ = 1 λ (1 -1 λ n +1 ), we obtain F (g u λ ) = g 1 λ (1-1 u+1 ) for all u = λ n , n ∈ R. Let R 0 = {u = λ n : n ∈ R \ {0}} and T = {u ∈ R 0 : 2u + 1 ∈ R 0 }. Since R 0 = t -s, we have T ≥ t -2s. Then F g 2u+1 λ = g 1 λ (1-1 2u+2 ) = g 1 λ ( 1 2 + 1 2 (1-1 u+1 )) = g 1 2λ × g 1 2λ (1-1 u+1 )
for all u ∈ T . We thus have

F 2 g 2u+1 λ = g 1 λ × g 1 λ (1-1 u+1 ) = g 1 λ × F (g u λ )
, for all u ∈ T .

Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function over

(X) = F 2 (g 1 λ X 2 ) -g 1 λ F (X)

Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function over Elliptic Curves

In this section, p is an odd prime number, E is an elliptic curve defined over F p and P is a point of the curve E(F p ) with prime order t. We prove lower bounds on the degree of polynomial interpolation of the Dodis-Yampolskiy pseudo-random function over elliptic curves defined by V x (n) = X

(P ) = 0. For some x ∈ F * t , let F (X) ∈ F p [X] be such that ψ 2 2 (F (X(P ))) = 0 and F (V x (n)) = V x (n + 1) for all n ∈ S. We have deg(F ) ≥ t -2s 176 . Proof. Let R = {(n + x) mod t : n ∈ S} ⊆ F t . We have R = t -s. Let us denote x k = X([k]P ) and R 0 = { 1 n : n ∈ R}, then we have F (x u ) = x 1-1 1+u
for all u ∈ R 0 . We consider the set T = {u ∈ R 0 : 2u + 1 ∈ R 0 }, then T ≥ t -2s. For all u ∈ T , we have:

F (x 2u+1 ) = x 1-1 2(u+1) = x 1/2+1/2(1-1/(u+1)) and F (x u ) = x 1-1/(u+1) (4.3)
Using division polynomials (see Section 2.3.2), we can write:

x 1+1-1 (u+1) = θ 2 (F (x 2u+1 )) ψ 2 2 (F (x 2u+1 )) (4.4)
Using the elliptic curve addition law, we have

x 1+α = a(x α ) -2y 1 y α (x α -x 1 ) 2 where a(X) = x 1 X 2 + (x 2 1 + A)X + Ax 1 + 2B,
and for any polynomial G of degree m ≥ 1, we have

G(x 1+α ) = u(x α ) -y α v(x α ) (x α -x 1 ) 2m and lc(u) = G(x 1 )
with uniquely determined polynomials u(X) and v(X) with deg(u) ≤ 2m (deg(u) = 2m if G(x 1 ) = 0) and deg(v) ≤ 2m -2 and where lc(u) is the leading coefficient of the polynomial u(X). Since F (x u ) = x 1-1 u+1

, we can rewrite (4.4) as:

a(F (x u )) -y 1 y 1-1 u+1 (F (x u ) -x 1 ) 2 = θ 2 (F (x 2u+1 )) ψ 2 2 (F (x 2u+1 )) .
Chapter 4. Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function

Since the point (x 1-1 u+1 , y 1-1 u+1 ) ∈ E(F p ) and F (x u ) = x 1-1 u+1 , the polynomial y 2 1 (F (x u ) 3 + A • F (x u ) + B)ψ 4 2 (F (x 2u+1 )) is equal to the polynomial [(F (x u ) -x 1 ) 2 θ 2 (F (x 2u+1 )) - a(F (x u ))ψ 2 2 (F (x 2u+1
))] 2 . We thus obtain

y 2 1 (F (x u ) 3 + A • F (x u ) + B) × p 1 (x 2u ) -y 2u p 2 (x 2u ) (x 2u -x 1 ) 12d 0 = Q(x u , x 2u , y 2u ),
where d 0 = deg(F ) and Q(x u , x 2u , y 2u ) denotes a polynomial of the form

(F (x u ) -x 1 ) 2 p 3 (x 2u ) -y 2u p 4 (x 2u ) (x 2u -x 1 ) 8d 0 -a(F (x u )) p 5 (x 2u ) -y 2u p 6 (x 2u ) (x 2u -x 1 ) 6d 0 2 such that deg(p 1 ) ≤ 6d 0 , deg(p 2 ) ≤ 6d 0 -2, deg(p 3 ) ≤ 4d 0 , deg(p 4 ) ≤ 4d 0 -2, deg(p 5
) ≤ 3d 0 and deg(p 6 ) ≤ 3d 0 -2. We obtain:

y 2 1 (F (x u ) 3 + AF (x u ) + B)(x 2u -x 1 ) 4d 0 (p 1 (x 2u ) -y 2u p 2 (x 2u )) = P (x u , x 2u , y 2u ),
where

P (x u , x 2u , y 2u ) = [(F (x u ) -x 1 ) 2 p 3 (x 2u ) -a(F (x u ))(x 2u -x 1 ) 2d 0 p 5 (x 2u ) -y 2u ((F (x u ) -x 1 ) 2 p 4 (x 2u ) -a(F (x u ))(x 2u -x 1 ) 2d 0 p 6 (x 2u ))] 2 .
We then proceed as previously by trying to eliminate y 2u . We obtain an expression in function of x u and x 2u and we replace x 2u by θ 2 (xu) ψ 2 2 (xu) . We finally obtain a rational function in x u of the form:

Q(x u ) ψ 40d 0 2 (x u ) = 0, where Q(X) ∈ F p [X] and deg(Q) ≤ 88d 0 .
Claim 4.3.2. We have

Q(X) = 0 if ψ 2 2 (F (x 1
)) = 0 and x 1 = 0

Proof. We have deg(P 5 ) = 3d 0 iff ψ 2 2 (F (x 1 )) = 0. If deg(P 5 ) = 3d 0 , One can then verify that the leading coefficient of Q is the leading coefficient of the numerator of the rational function obtained from [(F (x u )x 1 ) 2 p 3 (x 2u )a(F (x u ))(x 2ux 1 ) 2d 0 p 5 (x 2u )] 4 after replacing x 2u by

θ 2 (xu) ψ 2 2 (xu) . Therefore, if deg(P 5 ) = 3d 0 , then the leading coefficient of Q is (f 2 × x 1 × ψ 2 2 (F (x 1 ))) 4 which is non zero if x 1 = 0 since deg(P 5 ) = 3d 0 iff ψ 2 2 (F (x 1 )) = 0, where f is the leading coefficient of F . Then if ψ 2 2 (F (x 1 )) = 0 and x 1 = 0, Q(X) is a non-zero polynomial.
If ψ 2 2 (F (x 1 )) = 0 and x 1 = 0, Q(X) is a non-zero polynomial with at least T /2 different zeros. We thus have 88d 0 ≥ (t -2s)/2 and the claimed result.

The condition X(P ) = 0 in the statement of Theorem 4.3.1 holds obviously for almost all point P . The lower bound then holds if the group order E(F p ) is odd since in this case, the technical condition ψ 2 2 (F (X(P ))) = 0 is always satisfied. However, we obtain a weaker lower bound for the polynomial degree which holds for every curve E.

Polynomial

x ∈ F * t , let F (X) ∈ F p [X] such that F (V x (n)) = V x (n + 1) for all x ∈ A. We have deg(F ) ≥ (t -3s) 1/2 /6. Proof. Let R = {(n + x) mod t : n ∈ A}. Then R ⊆ F t and R = t -s. The equation F (V x (n)) = V x (n + 1) then becomes: F X 1 n P = X 1 n + 1 P , for all n ∈ R. Denoting x k = X([k]P ) = X([k mod t]P ) and considering the set T = {n ∈ R : n/2, n + 1 ∈ R}, we have F x 2 n = F x 1 n/2 = x 1 n/2+1 = x 2 n+2 = θ 2 (x 1 n+2 ) ψ 2 2 (x 1 n+2 ) = θ 2 (F (x 1 n+1
))

ψ 2 2 (F (x 1 n+1 )) = θ 2 (F (F (x 1 n ))) ψ 2 2 (F (F (x 1 n ))
) , hence we have

F   θ 2 (x 1 n ) ψ 2 2 (x 1 n )   = θ 2 (F (F (x 1 n ))) ψ 2 2 (F (F (x 1 n )))
, for all n ∈ T.

Finally, we consider the polynomial

H(X) = ψ 2d 0 2 (X)ψ 2 2 (F (F (X))) F θ 2 (X) ψ 2 2 (X) - θ 2 (F (F (X))) ψ 2 2 (F (F (X))
) .

The polynomial H(X) has at least T /2 zeros. We have F (F (X)) = X and by Lemma 2.3.2, it will imply that there exists α ∈ F p such that ψ 2 2 (F (F (α))) = 0 and ψ 2 2 (α) = 0. Hence, we have H(α) = -θ 2 (F (F (α)))ψ 2d 0 2 (α) = 0, since θ 2 (X) and ψ 2 2 (X) have no common zeros. Therefore, H(X) is a non-zero polynomial and deg(H) ≤ 9d 2 0 . Then we get that 9d 2 0 ≥ R/2 and the result follows.

Part II.

Lattice-Based Cryptanalysis of Pseudo-Random Generators and Signatures

Coppersmith's methods

In this section, we give two short descriptions of Coppersmith's methods for solving a multivariate modular polynomial system of equations modulo an integer N . We refer the reader to [START_REF] Jochemsz | A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants[END_REF] for details and proofs. We want this root to be small in the sense that each of its components is bounded by a known value X i . We also need to bound the sizes of X i allowing to recover the desired root in polynomial time.

First method

Polynomials collection.

In a first step, one generates a collection P of polynomials { f1 , . . . , fr } linearly independent having (x 1 , . . . , x n ) as a root modulo N . Usually, multiples and powers of products of f i , i = 1, . . . , s are chosen , namely f = y

α 1, 1 • • • y α n, n f k 1, 1 • • • f k s, s
for some integers α 1, , . . . , α n, , k 1, , k s, . Such polynomials satisfy the relation f (x 1 , . . . , x n ) ≡ 0 mod N s i=1 k i, , i.e., there exists an integer c i such that fi (x 1 , . . . , x n ) = c i N s j=1 k j, .

Matrix construction.

We denote as M the set of monomials appearing in collection of polynomials P. Then each polynomial fi can be expressed as a vector with respect to a chosen order on M . We hence construct a matrix M as follows and we define as L the lattice generated by its rows:

M =                1 X -1 1 . . . X -a 1 1 . . . X -an n 0 f1 . . . fr ↓ ↓ ↓ N s i=1 k i,1 . . . N s i=1 k i,r                1 y 1 . . . y a 1 1 . . .

y an n

On that figure, every row of the upper part is related to one monomial of M (we assume in the figure that M contains 1, y 1 , and y a 1 1 . . . y an n among other monomials). The left-hand side contains the bounds on these monomials (e.g., the coefficient X -1 1 X -2 2 is put in the row related to the monomial y 1 y 2 2 ). The right-hand side is formed by all vectors coming from P.

A short vector in a sublattice.

Let us now consider the row vector

r 0 = (1, x 1 , . . . , x a 1 1 . . . x an n , -c 1 , . . . , -c r ) .

Coppersmith's methods

65

By multiplying this vector by the matrix M, one obtains:

s 0 = 1, x 1 X 1 , . . . , x 1 X 1 a 1 • • • x n X n an , 0, . . . , 0 .
s 0 ∈ L is sufficient to recover the root we are searching for and its norm is very small since s 0 2 √ M . Thus, the recovery of a small vector in L, will likely lead to the recovery of the desired root (x 1 , . . . , x n ). To this end, we first restrict ourselves in a more appropriated subspace. Indeed, noticing that the last coefficients of s 0 are all null, we know that this vector belongs to a sublattice L whose last coordinates are composed by zero coefficients. By doing elementary operations on the rows of M, one can construct that sublattice and its determinant is the same as the one of L.

Method conclusion.

To finally compute all the small solutions (x 1 , . . . , x n ) of the original modular polynomial system, we require n independent polynomials having as root (x 1 , . . . , x n ) over the integers. To this end, we combine the two following lemmas, where Lemma 5.1.1 is due to Coppersmith see [START_REF] Coppersmith | Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known[END_REF] and Lemma 5.1.2 is due to Jutla see [START_REF] Charanjit | On Finding Small Solutions of Modular Multivariate Polynomial Equations[END_REF].

b i 2 -i-1 4 det(L) b ω-i max 1 i
.

In order to obtain n polynomials over the integers having as root (x 1 , . . . , x n ) , one computes an LLL-reduced basis of the lattice L and computes the Gram-Schmidt's orthogonalized basis (b 1 , . . . , b t ) of the LLL output basis (b 1 , . . . , b t ), with t = M . s 0 belongs to L and if its norm is smaller than those of b i for i ∈ {tn + 1, . . . , t}, then s 0 is orthogonal to b i for i ∈ {tn + 1, . . . , t} by Lemma 5.1.1. Extracting the coefficients appearing in b i for i ∈ {tn + 1, . . . , t}, one can construct n polynomial p 1 , . . . , p n defined over Z such that {p 1 (x 1 , . . . , x n ) = 0, . . . , p n (x 1 , . . . , x n ) = 0}. Under the (heuristic) assumption that all created polynomials define an algebraic variety of dimension 0, the previous system can be solved (e.g., using elimination techniques such as resultant computation or Gröebner basis) and the desired root recovered in polynomial time.

By Lemma 5.1.2, putting t = M the condition on the bounds X i that make this method work is:

s 0 √ t 2 -t-n 4 det(L) b n-1 max 1 t-n+1
, which can be rewritten as:

1 t -t-n+1 2 2 -(t-n)(t-n+1) 4 b 1-n max det(L),
in the next Chapter, for large dimensions lattices we let b n-1 max and t

-t-n+1 2 2 -(t-n)(t-n+1) 4
contribute to an error term (see [M R10] for details) to obtain the simplified condition:

1 < det(L)
The condition on the bounds X i that make this method work is then given by the following (simplified) inequation :

y k 1 1 ...y kn n ∈M X k 1 1 • • • X kn n < N r =1 s i=1 k i, .
(5.1)

For such techniques, the most complicated part is the choice of the collection of polynomials, what could be a really intricate task when working with multiple polynomials.

Remark 5.1.3. In practice, for small dimensions lattices, the experimental bounds on X i could be worse than the expected one due to the fact that we cannot give useful estimates for the value b max in general.

Second method

i (x 1 , . . . , x n ) ≡ 0 mod N .
Our goal is to recover the desired root (x 1 , . . . , x n ). This problem is generally intractable but becomes solvable (under some conditions) in polynomial time log(p) O (1) (for constant n and constant total degree of the input polynomials) if the root (x 1 , . . . , x n ) is upper-bounded by some values (X 1 , . . . , X n ) that depends on N and the degree of the polynomials f 1 , . . . , f s .

Polynomials collection.

In a first step, one generates a larger collection P of polynomials { f1 , . . . , fr } linearly independent having (x 1 , . . . , x n ) as a root modulo N m , for some positive integer m. Usually, the technique consists in taking product of powers of the modulus N , the polynomials f i for i ∈ {1, . . . , s} and some well-chosen monomials, such as

f = p m- s j=1 k j, y α 1, 1 • • • y α n, n f k 1, 1 • • • f k s, s
for some positive integers α 1, , . . . , α n, , k 1, , k s, . Such polynomials satisfy the relation f (x 1 , . . . , x n ) ≡ 0 mod p m .

Lattice construction.

In a second step, one denotes as M the set of monomials appearing in collection of polynomials P, and one writes the polynomials fi (y 1 X 1 , . . . , y n X n ) for i ∈ {1, . . . , r} as a vector b i ∈ (Z) ω , where ω = M . One then constructs a lattice L generated by the vectors b 1 , . . . , b r and computes its reduced basis using the LLL algorithm [START_REF] Arjen | Factoring polynomials with rational coefficients[END_REF].

Lemma 5.1.4. Let L be a lattice of dimension ω. In polynomial time, the LLL algorithm given as input of basis of L outputs a reduced basis of L formed by vectors v i , 1 i ω that satisfy:

v 1 v 2 • • • v 2 2 ω(ω-1) 4(ω+1-i) det(L) 1 ω+1-i .
5.2. Analytic Combinatorics 67

Generating new polynomials.

In a third step of the method, one combines Lemma 5.1.5 below (from [START_REF] Howgrave-Graham | Finding Small Roots of Univariate Modular Equations Revisited[END_REF]) and Lemma 5.1.4 to obtain n multivariate polynomials g 1 (y 1 , . . . , y n ), . . . , g n (y 1 , . . . , y n ) having (x 1 , . . . , x n ) as a root over the integers.

Lemma 5.1.5. (Howgrave-Graham Let h(y 1 , . . . , y n ) be a polynomial over Z having at most ω monomials. Suppose that:

1. h(x 1 , . . . , x n ) = 0 mod W for some |x 1 | < X 1 , . . . , |x n | < X n and, 2. h(X 1 y 1 , . . . , X n y n ) W √
ω . Then h(x 1 , . . . , x n ) = 0 holds over the integers.

The LLL algorithm run on the lattice L to obtain n reduced vectors v i , i ∈ {1, . . . , n} that we see as some polynomials hi (y 1 X 1 , . . . , y n X n ), i ∈ {1, . . . , n}. One can see that for i ∈ {1, . . . , n}, hi (x 1 , . . . , x n ) = 0 mod p m , since hi is a linear combination of f1 , . . . , fr . Then if the following condition holds: 2 r(r-1)

4(r+1-n) det(L) 1 r+1-n < p m √ ω ,
by Lemmas 5.1.4 and 5.1.5, hi (x 1 , . . . , x n ) = 0, i ∈ {1, . . . , n} holds over the integers and we then obtain n polynomials having (x 1 , . . . , x n ) as a root over the integers.

Condition.

In our attacks, the number of polynomials in the first step is equal to the number of monomials that appears in the collection, so r = ω = M . In the analysis, we let (as usual in this setting) terms that do not depend on N contribute to an error term ε, and the simplified condition becomes: det(L) < N m(ω+1-n) .

Under the (heuristic) assumption that all created polynomials in the third step define an algebraic variety of dimension 0, the previous system can be solved (e.g., using elimination techniques such as resultant computation or Gröbner basis) and the desired root recovered in polynomial time1 log(p) O (1) (for constant n and constant total degree of the input polynomials). We assume that these polynomials define an algebraic variety of dimension 0 and we justify the validity of our attacks by computer experiments.

Analytic Combinatorics

We now recall the analytic combinatorics results (see [START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Benhamouda | Easing Coppersmith Methods Using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness[END_REF] for more details) that we need in the next two Chapters.

Introduction

To make things clear, we will explain the method with one multivariate modular polynomial. As explained in the former section, Coppersmith's method requires polynomials which are usually constructed as f k = y k 1 1 . . . y kn n f k (with f being a polynomial of degree e in the variables y 1 , . . . , y n ). In the following, we thus consider a set of polynomials looking like

P = {f k = y k 1 1 . . . y kn n f k mod N k | 1 k < t and deg(f k ) = k 1 + • • • + k n + k e < te} ,
where the notation modN k is only here to recall that the considered solution verifies f k ≡ 0 mod N k (to make things clearer). We suppose that f is not just a monomial (i.e., is the sum of at least two distinct monomials) and therefore each k corresponds to a distinct polynomial f k .

The set of monomials appearing in the collection P will usually look like

M = {y k = y k 1 1 . . . y kn n | 0 deg(y k ) = k 1 + • • • + k n < te} .
By construction, since (x 1 , . . . , x n ) is a modular root of the polynomials f k , there exists an integer c k such that f k (x 1 , . . . , x n ) = c k N k (see Section 5.1). Furthermore, this root is small in the sense that each of its components is bounded by a known value, namely |x 1 | < X 1 , . . . , |x n | < X n . These considerations imply that for the final condition in Coppersmith's method (see Equation (5.1)), one needs to compute the values

ψ = f k ∈P k and ∀i ∈ {1, . . . , n}, α i = y k ∈M k i .
These values correspond to the exponent of N and X i (for i ∈ {1, . . . , n}) in Equation (5.1) respectively.

For the sake of readability for the reader unfamiliar with analytic combinatorics, we first show how to compute the number of polynomials in P or M of a certain degree and then how to compute these sums ψ and α i but only for polynomials in P or M of a certain degree. These computations are of no direct use for Coppersmith's method but are a warm-up for the really interesting computation, namely these sums ψ and a i for polynomials in P or M up to a certain degree.

Combinatorial Classes, Sizes, and Parameters

A combinatorial class is a finite or countable set on which a size function is defined, satisfying the following conditions: (i) the size of an element is a non-negative integer and (ii) the number of elements of any given size is finite. Polynomials of a "certain" form and up to a "certain" degree can be considered as a combinatorial class, using a size function usually related to the degree of the polynomial.

In the following, we can consider the set P as a combinatorial class, with the size function S P defined as

S P (f k ) = deg(f k ) = k 1 + • • • + k n + k e.
In order to compute the sum of the k as explained in Section 5.2.1, we define another function χ P , called a parameter function, such that χ P (f k ) = k . This function will enable us, instead of counting "1" for each polynomial, to count "k " for each polynomial, which is exactly what we need (see Section 5.2.4 for the details).

As for the monomials, we will also consider the set M as a combinatorial class, with the size function S M defined as S M (y k ) = k 1 + • • • + k n . In the case the bounds on the variables are equal (X 1 = • • • = X n = X), the parameter function corresponding to the exponent α 1 of X 1 in the final condition in Coppersmith's method will be set as χ

M (y k ) = k 1 + • • • + k n .
Otherwise, one will be able to define other parameter functions in case the bounds are not equal .

Counting the Elements: Generating Functions

The counting sequence of a combinatorial class A with size function S is the sequence of integers (A p ) p 0 where A p = |{a ∈ A p | S(a) = p}| is the number of objects in class A that have size p. For instance, if we consider the set M defined in 5.2.1, we have the equality M 1 = n since there are n monomials in n variables of degree 1.

Definition 5.2.1. The ordinary generating function (OGF) of a combinatorial class A

is the generating function of the numbers A p , for p 0, i.e., the formal2 power series

A(z) = +∞ p=0 A p z p . For instance, if we consider the set M (1) = {y k 1 1 | 1 k 1 <

t} of the monomials with one variable, then one gets M

(1) p = 1 for all p ∈ N, implying that M (1) (z) = +∞ p=0 z p = 1 1-z . In the former example, we constructed the OGF A(z) from the sequence of numbers A p of objects that have size p. Of course, what we are really interested in is to do it the other way around. We now describe an easy way to construct the OGF, and we will deduce from this function and classical analytic tools the value of A p for every integer p. We assume the existence of an "atomic" class, comprising a single element of size 1, here a variable, usually denoted as Z. We also need a "neutral" class, comprising a single element of size 0, here 1, usually denoted as ε. Their OGF are Z(z) = z and E(z) = 1. We show in Table 5.1 the possible admissible constructions that we will need here, as well as the corresponding generating functions.

Z(z) = z Neutral class ε E(z) = 1 Disjoint union A = B + C (when B ∩ C = ∅) A(z) = B(z) + C(z) Complement A = B \ C (when C ⊆ B) A(z) = B(z) -C(z) Cartesian product A = B × C A(z) = B(z) • C(z) Cartesian exponentiation A = B k = B × • • • × B A(z) = B(z) k Sequence A = Seq(B) = ε + B + B 2 + . . . A(z) = 1 1-B(z)
One then recovers the formula M (1) (z) = 1 1-z from Z(z) = z and the construction Seq(Z) to describe M (1) . Similarly, if we now consider the set (1) . Finally, since 1 (1-z) 2 = +∞ p=1 pz p-1 , one gets, for all p 1, (M 2 ) p = p + 1, which is exactly the number of monomials with two variables of size p.

M (2) = {y k = y k 1 1 y k 2 2 | 0 k 1 +k 2 <

t} of the monomials with two variables, with the size function S(y

k ) = k 1 + k 2 , then one gets M (2) (z) = M (1) (z) • M (1) (z) = 1 (1-z) 2 from M (2) = M (1) × M
When the class contains elements of different sizes (such as variables of degree 1 and polynomials of degree e), the variables are represented by the atomic element Z and the polynomials by the element Z e , in order to take into account the degree of the polynomial f . If we consider for instance the set P (1,2)

= {f k = y k 1 1 f k | 1 k < t and deg(f k ) = k 1 + 2k < 2t},
with f a polynomial of degree 2, this set is isomorphic to Seq(Z) × Z 2 Seq(Z 2 ), since deg(f ) = 2. This leads to an OGF equals to

1 1 -z z 2 1 -z 2 = +∞ q=0 qz q +∞ r=1 rz 2r = +∞ p=0 p/2 r=1 (p -2r)rz p , which gives P (1,2) p = p/2
r=1 (p -2r)r, which is exactly the number of polynomials of degree p contained in the class.

Counting the Parameters of the Elements: Bivariate Generating Functions

As seen in the former section, when one considers a combinatorial class A of polynomials and computes the corresponding OGF A(z), classical analytic tools enable to recover A p as the coefficient of z p in the OGF. As explained in the introduction of this section, however, Coppersmith's method requires a computation a bit more tricky, which involves an additional parameter. For the sake of simplicity, we describe this technique on an example. For instance, consider our monomial set example M (2) , but now assume that X 1 = X 2 . Our goal is to compute k 1 , where the sum is taken over all the monomials in M (2) of size p. We set a parameter function3 χ(y k ) = k 1 and we do not compute M

(2) p (for p 1) anymore, but rather

χ p (M (2) ) = y k ∈M (2) |S(y k )=p χ(y k ) = y k ∈M (2) |S(y k )=p k 1
where, informally speaking, instead of counting for 1, every monomial counts for the value of its parameter (here the degree k 1 in y 1 ).

The value χ p (M (2) ) cannot be obtained by the construction of M (2) as Seq(Z) × Seq(Z) that we used in the former section, since the two atomic elements Z do not play the same role (the first one is linked with the parameter, whereas the second one is not). The classical solution is simply to "mark" the atomic element useful for the parameter, with a new variable u: With this new parameter function, M (2) is seen as Seq(uZ) × Seq(Z), defining the bivariate ordinary generating function (BGF) 4

M 2 (z, u) = 1 1-uz 1
1-z . We remark that when we set u = 1, we get the original non-parameterized OGF. Informally speaking, the BGF of a combinatorial class A with respect to a size function S and a parameter function χ is obtained from the corresponding OGF by replacing each z by u k z where k is the value of the parameter taken on the atomic element Z. We then obtain χ p (A) via the following result:

Theorem 5.2.2. Assume A is a combinatorial class with size function S and parameter function χ, and assume A(z, u) is the bivariate ordinary generating function for A corresponding to this parameter (constructed as explained above). Then, if we define

χ p (A) = a∈A|S(a)=p χ(a)
the ordinary generating function of the sequence (χ p (A)) p 0 is equal to the value (∂A(z, u)/∂u) u=1 , meaning that we have the equality

∂A(z, u) ∂u u=1 = +∞ p=0 χ p (A)z p def = χ(A)(z) .
Coming back to our example, one then gets

χ(M (2) )(z) = +∞ p=0 χ p (M (2) )z p = ∂M (2) (z, u) ∂u u=1 = z (1 -z) 3 = +∞ p=1 p(p -1) 2 z p-1 .
meaning that χ p (M (2) ) = p(p + 1)/2 (remind that it is an equality on formal series). Finally, the sum of the degrees k 1 of the elements of size p is p(p + 1)/2, which can be checked by enumerating them:

y p 2 , y 1 y p-1 2 , y 2 1 y p-2 2 , . . . , y p-1 1 y 2 , y p 1 .
It is easy to see that the result is exactly the same for X 2 , without any additional computation, by symmetry.

Counting the Parameters of the Elements up to a Certain Size

We described in the former section a technique to compute the sum of the (partial) degrees of elements of size p, but how about computing the same sum for elements of size up to p? Using the notations of the former section, we want to compute

χ p (A) = a∈A|S(a) p χ p (a) .
The naive way is to sum up the values χ i (A) for all i between 0 and p:

χ p (A) = p i=0 a∈A|S(a)=i χ i (a) ,
but an easier way to do so is to artificially force all elements a of size less than or equal to p to be of size exactly p by adding enough times a dummy element y 0 such that χ(y 0 ) = 0.

In our context of polynomials, the aim of the dummy variable y 0 is to homogenize the polynomial. If we consider again the set M (2) of monomials of two variables y 1 and y 2 , with size function equal to S(y k ) = k 1 + k 2 and parameter function equal to χ(y k ) = k 1 , and if we are interested in the sum of the degrees k 1 of the elements in this set of size up to p, we now describe this set as Seq(uZ) × Seq(Z) × Seq(Z), the last part being the class of monomials Chapter 5. Preliminaries in the unique variable y 0 . This variable is not marked, since its degree is not counted. One obtains the new bivariate generating function

M (2) (z, u) = 1 1-uz 1 (1-z) 2 and χ (M (2) )(z) = +∞ p=0 χ p (M (2) )z p = ∂M (2) (z, u) ∂u u=1 = z (1 -z) 4 = +∞ p=2 p(p -1)(p -2) 6 z p-2 ,
meaning that χ p (M (2) ) = p(p + 1)(p + 2)/6 (remind that it is an equality on formal series). Finally, the sum of the degrees k 1 of the elements of size up to p (i.e., the exponent of X 1 in Coppersmith's method) is p(p + 1)(p + 2)/2, which can be checked by the computation

p i=0 i(i + 1) 2 = p(p + 1)(p + 2) 6 .
Again, it is easy to see that the result is exactly the same for X 2 , without any additional computation.

Asymptotic Values: Transfer Theorem

Finding the OGF or BGF of the combinatorial classes is usually an easy task, but finding the exact value of the coefficients can be quite painful. Coppersmith's method is usually used in an asymptotic way. Singularity analysis enables us to find the asymptotic value of the coefficients in an simple way, using the technique described in [START_REF] Flajolet | Analytic Combinatorics[END_REF], Corollary V I.1 (sim-transfer), page 392. Adapted to our context, their transfer theorem can be stated as follows:

Theorem 5.2.3 (Transfer Theorem). Assume A is a combinatorial class with an ordinary generating function F regular enough such that there exists a value c verifying

F (z) ∼ z→1 c (1 -z) α
for a non-negative integer α. Then the asymptotic value of the coefficient F n is

F n ∼ n→∞ cn α-1 (α -1)! .

Some useful applications of the technique

We now describe how to use the generic tools recalled in the former section to count the exponents of the bounds X 1 , . . . , X n and of the modulo N .

Counting the Bounds for the Monomials (Useful Examples)

First Example.

In this example, we consider

M = {y 1 i 1 • • • y n in | 1 i 1 + • • • + i n < t}
with the bounds |y j | < X j for 1 j n. In order to obtain the exponent for the bound X j , we consider M as a combinatorial class, with the size function S(y

1 i 1 . . . y n in ) = i 1 + • • • + i n and the parameter function χ X j (y 1 i 1 . . . y n in ) = i j . We then describe M as n k=1 k =j Seq(Z) y k × Seq(uZ) y j × Seq(Z) y 0 \ε
(the last Seq(Z) being for the dummy value y 0 ), which leads to the OGF

F (z, u) = 1 1 -z n 1 1 -uz -1 .
The next step is to compute the partial derivative in u at u = 1:

∂F (z, u) ∂u u=1 = 1 1 -z n z 1 -uz 2 u=1 = z (1 -z) n+2
and take the equivalent value when z → 1:

∂F (z, u) ∂u u=1 ∼ z→1 1 (1 -z) n+2 ,
which finally leads, using Theorem 5.2.3, to χ X j ,<t (M ) ∼ (t-1) n+1 (n+1)! ∼ t n+1 (n+1)! . This set of monomials used in Coppersmith's method (first method) thus leads to the

bound n i=1 X t n+1 (n+1)! i .

Concrete bounds.

For n = 2, we give in the table below the exponent for the bound X j for smaller t by computing the Taylor series at 0 of the function ∂F (z,u) ∂u u=1

. One can verify that each value in the table equals t-1 j=1 j(j+1) 2 which is the exponent for the bound X j by direct computations. In the case where

X 1 = • • • = X n = X, the bound becomes X nt n+1
(n+1)! . In this same case, one could consider M as a combinatorial class, with the size function S(y

1 i 1 . . . y n in ) = i 1 +• • •+i n and the parameter function χ X j (y 1 i 1 . . . y n in ) = i 1 + • • • + i n (
since the bound X is the same for all variables) and then obtain the same bound.

Second Example.

In this example, we consider

M = {y 1 i 1 . . . y n in | (i 1 = 0 or 0 i 2 e) and 1 i 1 + • • • + i n < t}
with the bounds |y i | < X for 1 i n. We use the size function S(y

1 i 1 . . . y n in ) = i 1 +• • •+i n and the parameter function χ(y 1 i 1 . . . y n in ) = i 1 + • • • + i n .
Chapter 5. Preliminaries

The first step is to split M into disjoint subsets. In our case, the three disjoint subsets correspond to (i 1 = 0 and 0 i 2 e), (i 1 = 0 and 0 i 2 e) and (i 1 = 0 and e + 1 i 2 ). Taking into account the dummy value y 0 , we describe them as

(ε + Z + • • • + Z e ) × n-2 i=1 Seq(uZ) × Seq(Z)
for the first one and

(uZ) × Seq(uZ) × (ε + Z + • • • + Z e ) × n-2 i=1 Seq(uZ) × Seq(Z)
for the second one and

(uZ) e+1 × Seq(uZ) × n-2 i=1 Seq(uZ) × Seq(Z)
for the third one. This leads to the OGF

F (z, u) = 1 + uz 1 -uz (1 + z + • • • + z e ) + (uz) e+1 1 -uz 1 1 -uz n-2 1 1 -z = 1 + z + • • • + z e + (uz) e+1 (1 -uz) n-1 1 1 -z ,
which gives, after computations,

∂F (z, u) ∂u u=1 = (e + 1)(1 -uz)u e z e+1 + (n -1)z(1 + z + • • • + z e + (uz) e+1 ) (1 -uz) n 1 1 -z u=1 ,
and take the equivalent value when z → 1:

∂F (z, u) ∂u u=1 ∼ z→1 (e + 2)(n -1) (1 -z) n+1 ,
which finally leads, using Theorem 5.2.3, to χ <t (M )

∼ (e+2)(n-1)t n n!
. This set of monomials used in Coppersmith's method (first method) thus leads to the bound X (e+2)(n-1)t n n!

Counting the Bounds for the Polynomials

First Example.

We now consider the set

P = {f k = y k 1 1 . . . y kn n f k mod N k | 1 k < t and deg(f k ) = k 1 + • • • + k n + k e < te}
with the bounds X 1 = • • • = X n = X for the variables. In order to obtain the exponent for the modulus N , we consider the size function S(y

1 k 1 . . . y n kn f k ) = k 1 + • • • + k n + k and the parameter function χ N (y 1 k 1 . . . y n kn f k ) = k .
For the sake of simplicity, we can consider 0 k < t since the parameter function is equal to 0 on the elements f k such that k = 0. We describe P as n i=1 Seq(Z)×Seq(uZ e )×Seq(Z) (the last one being for the dummy value y 0 ), since only f needs a marker and its degree is e. This leads to the OGF

F (z, u) = 1 1 -z n+1 1 1 -uz e .
The next step is to compute the partial derivative in u at u = 1:

∂F (z, u) ∂u u=1 = z e (1 -uz e ) 2 1 1 -z n+1 u=1 = z e (1 -z e ) 2 1 1 -z n+1
and take the equivalent value when z → 1, using the formula 1z e ∼ e(1z):

∂F (z, u) ∂u u=1 ∼ z→1 1 e 2 (1 -z) n+3 ,
which finally leads, using Theorem 5.2.3, to χ N, < te (P) ∼ (te) n+2 e 2 (n+2)! .

Second Example.

Let f 1 (y 1 , . . . , y n ), . . . , f s (y 1 , . . . , y n ) be multivariate polynomials defined over Z of degree e 1 , . . . , e s respectively, we now consider the set

P = { f = y α 1, 1 . . . y α n, n f k 1, 1 • • • f k s, s mod N s j=1 k j, | 1 s j=1 k j, and deg( f ) = n j=1 α j, + s j=1 e j k j, < te}
where e = max(e 1 , . . . , e s ). In order to obtain the exponent for the modulus N at the end of Coppersmith's method, we consider the size function S( f ) = n j=1 α j, + s j=1 e j k j, and the parameter function χ f j ( f ) = k j, , for j ∈ {1, . . . , s}.

For the sake of simplicity, we can consider 0 s j=1 k j, . Since the degree of each f j is e j , we describe P as n k=1 Seq(Z)

y k × s k=1 k =j Seq(Z e k ) f k × Seq(uZ e j ) f j × Seq(Z) dummy var.
which leads to the following generating function

F j (u, z) = 1 1 -z n s k=0 k =j 1 1 -z e k 1 1 -uz e j 1 1 -z .
The next step is to compute the partial derivative in u at u = 1:

∂F j ∂u (u, z) u=1 = 1 1 -z n+1 × s k=0 k =j 1 1 -z e k × z e j (1 -z e j ) 2 .

Chapter 5. Preliminaries

We take the equivalent when z → 1, using the formula 1z m ∼ m(1z):

∂F j ∂u (u, z) u=1 ∼ z→1 1 e j ( s k=1 e k )(1 -z) n+s+2
, which finally leads, using Theorem 5.2.3, to

χ f j ,<te (P) ∼ (te) n+s+1 e j ( s k=1 e k )(n + s + 1)! .
This set of polynomials used in Coppersmith's method thus leads to the bound

N (te) n+s+1 (n+s+1)! s k=1 e k s j=1 1 e j .
Chapter 6.

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

In this Chapter, we analyze the security of the Elliptic Curve Linear Congruential Generator (EC-LCG) and of the Elliptic Curve Power Generator (EC-PG). We use the Coppersmith's methods to show that these generators are insecure if sufficiently many bits are output at each iteration. Gutierrez and Ibeas showed that the EC-LCG is insecure given a certain amount of most significant bits of some consecutive values of the sequence. Using the Coppersmith's methods, we are able to improve the security bounds of this generator in their setting and in other settings. We also show that the EC-PG is insecure if sufficiently many bits are output at each iteration using the same techniques. The Chapter is organized as follows, in the first section we present the Linear Congruential Generator and Power Generator on Elliptic Curves. In the second and third sections, we infer the EC-LCG when the composer is known or unknown and we conclude the Chapter by inferring the EC-PG.

Linear Congruential Generator and Power Generator on Elliptic Curves

In cryptography, a pseudo-random number generator is a deterministic algorithm which takes as input a short random seed and output and output a long pseudo-random sequence. Random numbers have found a number of applications in the literature. For instance they are useful for privacy, randomized algorithms and key generation. In 1994, S.

Hallgren see [S H94] proposed a pseudo-random numbers generator based on a subgroup of points of an elliptic curve defined over a prime finite field. This generator is known as the Linear Congruential Generator on Elliptic Curves (EC-LCG). If E is an elliptic curve defined over a prime finite field F p , for a given point G ∈ E(F p ), the Linear Congruential Generator on Elliptic Curves, EC-LCG is a sequence (U n ) of pseudo-random numbers defined by the relation:

U n = U n-1 ⊕ G = nG ⊕ U 0 , n ∈ N
where U 0 ∈ E(F p ) is the initial value or seed. We refer to G as the composer of the generator. For a positive integer e > 1 and a point G ∈ E(F p ) of order with gcd(e; ) = 1, the Elliptic curve power generator, EC-PG is a sequence (V n ) of pseudo-random numbers defined by the relation:

V n = eV n-1 = e n G n ∈ N where V 0 ∈ E(F p )
is the initial value or seed. The EC-LCG and the EC-PG provide a very attractive alternative to linear and non-linear congruential generators and they have been extensively studied in the literature, see [Shp08; HS05; GL01; GBS99; MS02; PJ02; Shp09b] and the references therein. In Cryptography, we want to use the output of the generator as a stream cipher. One can notice that if two consecutive values U n , U n+1 of the generator are revealed, it is easy to find U 0 and G. So, we output only the most significant bits of each coordinate of U n , n = 0, 1, . . . in the hope that this makes the resulting output sequence difficult to predict. Likewise we output only the most significant bits of each coordinate of V n , n = 0, 1, . . . . We show that the EC-LCG and the EC-PG are insecure if sufficiently many bits are output at each stage. Therefore a secure use of these generators requires to output much fewer bits at each iteration and the efficiency of the schemes is thus degraded. Our attacks used the well-known Coppersmith's methods for finding small roots on polynomial equations. These methods have been used to infer many pseudorandom generators and to cryptanalyze many schemes in Cryptography (see [START_REF] Benhamouda | Easing Coppersmith Methods Using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness[END_REF][START_REF] Bauer | Inferring Sequences Produced by Nonlinear Pseudorandom Number Generators Using Coppersmith's Methods[END_REF] and the references therein). Throughout this chapter, ∆ < p δ , with 0 < δ < 1, corresponds to the situation where a proportion of at most δ of the least significant bits of the output sequence remain hidden.

Predicting EC-LCG Sequences for Known Composer

In the cryptographic setting, the initial value U 0 = (x 0 , y 0 ) and the constants G, a and b are supposed to be the secret key. In the following we infer the EC-LCG in the case where the composer G is known and the curve is kept secret. We consider two cases: the case where the most significant bits of consecutive values U n of the sequence is output and the case where the most significant bits of the abscissa of consecutive multiple values U kn (for some fixed integer k) of the sequence is output. In the first case, we show that the generator is insecure Chapter 6. Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves

Condition. If we denote by

ν 1 = χ <2t,∆ (M), ν 2 = χ <2t,X (M), ν 3 = χ <2t,Y (M) and ε = χ <2t (P), the condition for Coppersmith's method is p ε > ∆ ν 1 X ν 2 Y ν 3 , ie ∆ < p ε ν 1 +3ν 2 +2ν 3 , where: ε ν 1 + 3ν 2 + 2ν 3 ∼ χ <2t (P) χ <2t,∆ (M) + 3χ <2t,X (M) + 2χ <2t,Y (M) ∼ 1 5 ,
this leads to the expecting bound: ∆ < p 1 5 .

Complexity of the attack. The dimensions of the matrix used in Coppersmith's methods depend on the cardinalities of the set of polynomials and monomials. To compute the cardinalities of the sets P and M, we make used of the parameters functions χ(z

j 1 1 . . . z j 4 4 f i 1 1 g i 2 1 ) = 1 and χ(z i 1 1 . . . z i 4 4 u i 5 v i 6 ) = 1.
This leads to the generating functions:

F 1 (z) = 1 1 -z 5 × 1 1 -z 2 × 1 1 -z -1
and

F 2 (z) = 1 1 -z 5 × 1 1 -z 2 × 1 1 -z ,
for P and M respectively. Asymptotic bounds. We have:

F 1 (z), F 2 (z) ∼ z→1 1 2(1 -z) 7 ,
which leads when t goes to infinity to the asymptotic bound: This bound improves the known bound ∆ < p 1/6 . Next we further improve the previous bound and we show that the generator is insecure if at least a proportion of 8/11 of the most significant bits of an infinite consecutive values U i of the sequence is output.

1 2 × (2t
Experimental Results. We have implemented the attack in Sage 7.6 on an elliptic curve over F p for a 256-bit prime p on a MacBook Air laptop computer (2,2 GHz Intel Core i7, 4 Gb RAM 1600 MHz DDR3, Mac OSX 10.10.5). Our theoretical bound is δ theo = 1 5 (δ < p δ ) and we denote the experimental bound by δ exp . We consider the family of polynomials P t with t = 2 which corresponds to a lattice of dimension 89 and we could not increase the value of t (which allows us to obtain a better theoretical bound) because of the large dimension of the corresponding lattice. After the computations of the LLL reduced basis and Gram-Schmidt orthogonalized basis which takes a few seconds, we obtain:

• a polynomial system over the integers of dimension 0 if δ exp < 0.08 and we can then recover the seed U 0 • a polynomial system over the integers of dimension 1 if δ exp 0.1. After the computation of the Gröbner basis, we add the two polynomials uz 3 1 + z 2 1 z 2z 2 3 and vz 1 z 4 + z 2 z 3 to the polynomials obtained with the computation of the Gröbner basis and we are able from the new system to obtain the seed U 0 . Theorem 6.2.2. (more consecutive outputs) Given ∆-approximations W 0 , W 1 ,. . . ,W n (for some integer n > 1) to n + 1 consecutive affine values U 0 , U 1 ,. . . ,U n produced by the EC-LCG, and given the value of the composer G = (x G , y G ). Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 in polynomial time in log p as soon as ∆ < p 3n 11n+4

Proof. Let us assume, for instance that the adversary has access to n+1 ∆-approximations W 0 , W 1 ,. . . ,W n of U 0 , U 1 ,. . . ,U n produced by the EC-LCG. Then using the equalities x j = α j + e j and y j = β j + f j , for j = 0, . . . , n, where |e j |, |f j | < ∆ and W j = (α j , β j ) and U j = (x j , y j ) leads to the following polynomial system:

                   f 1 (e 0 , e 1 , f 0 ) = 0 mod p g 1 (e 0 , e 1 , f 0 , f 1 ) = 0 mod p . . . f n (e n-1 , e n , f n-1 ) = 0 mod p g n (e n-1 , e n , f n-1 , f n ) = 0 mod p . Where for i = 1, . . . , n, f i (z i-1 , z i , z n+i ) = A 1 z i-1 + A 2 z i + A 3 z n+i + A 4 z 2 i-1 + A 5 z i-1 z i + z 3 i-1 + z 2 i-1 z i -z 2 n+i + A 6 and g i (z i-1 , z i , z n+i , z n+i+1 ) = B 1 z i-1 + B 2 z i + B 3 z n+i + B 4 z n+i+1 + z i-1 z n+i+1 + z i z n+i + B 5
are polynomials whose coefficients A i and B i are functions of x G , and the approximations values

α k , β k , (k = i -1, i). If we fix u i = z 3 i-1 + z 2 i-1 z i -z 2 n+i and v i = z i-1 z n+i+1 + z i z n+i , then the polynomial f i becomes f i (z i-1 , z i , z n+i , u i ) = A 1 z i-1 + A 2 z i + A 3 z n+i + A 4 z 2 i-1 + A 5 z i-1 z i + u i + A 6 and g i becomes g i (z i-1 , z i , z n+i , z n+i+1 , v i ) = B 1 z i-1 + B 2 z i + B 3 z n+i + B 4 z n+i+1 + v i + B 5 .
The adversary is then looking for the solutions of the modular multivariate polynomial system:

                   f 1 (z 0 , z 1 , z n+1 , u 1 ) = 0 mod p g 1 (z 0 , z 1 , z n+1 , z n+2 , v 1 ) = 0 mod p . . . f n (z n-1 , z n , z 2n , u n ) = 0 mod p g n (z n-1 , z n , z 2n , z 2n+1 , v n ) = 0 mod p . With |z j | < ∆, j = 0, . . . , 2n + 1, |u i | < X = ∆ 3 and |v i | < Y = ∆ 2 , i = 1, . . . , n.
We consider the following collection of polynomials:

P = fj 0 ,...,j 2n+1 ,i 1 ,...,in,l 1 ,...,ln = z j 0 0 . . . z j 2n+1 2n+1 f i 1 1 . . . f in n g l 1 1 . . . g ln n mod p i 1 +l 1 •••+in+ln s.t. i 1 + l 1 + • • • + i n + l n > 0 and j 0 + • • • + j 2n+1 + 2(i 1 + • • • + i n ) + l 1 + • • • + l n < 2t
. Chapter 6. Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves

To prevent the attacks of [START_REF] Gutierrez | Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits[END_REF] and the previous attacks on the EC-LCG, one could output only the most significant bits of the abscissa of consecutive multiple values U kn (for some fixed integer k) of the sequence. We consider this setting here and use summation polynomials to infer the EC-LCG. These polynomials were used to solve elliptic curve discrete logarithm problem and we use it below to infer the EC-LCG when the attacks of [START_REF] Gutierrez | Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits[END_REF] and the previous attacks on the EC-LCG cannot work. In the first time, we show that the generator is insecure if at least a proportion of 7/8 of the most significant bits of two values X(U 0 ) and X(U k ) is output, X(P ) denoting the abscissa of the point P . Theorem 6.2.3. (two outputs) Given ∆-approximations w 0 , w k to two values X(U 0 ), X(U k ) produced by the EC-LCG. Under the heuristic assumption that all created polynomials we get by applying Coppersmith's methods with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 in polynomial time in log p as soon as ∆ < p 1/8 . Proof. We set U 0 = (x 0 , y 0 ), U k = (x k , y k ) and G = (x G , y G ). We then have the equalities:

x i = w i + e i where |e i | < ∆, i = 0, k. We have U 0 ⊕ (-U k ) = -kG, thus U 0 ⊕ (-U k ) ⊕ kG = O. Hence: f 3 (x 0 , x k , X(kG)) = 0,
where f 3 is the polynomial defined in section 2.3.3. Using the equalities x i = w i + e i , i = 0, k we obtain the polynomial equation:

f (e 0 , e k ) = 0,
where f (y 1 , y 2 ) = f 3 (w 0 + y 1 , w 0 + y 2 , X(kG)) is a polynomial of degree 4. We consider monomials with respect to a monomial ordering such that LM (f ) = y 2 1 y 2 2 . We consider the following collection of polynomials:

P = { fj 1 ,j 2 ,i = y j 1
1 y j 2 2 f i mod p i : i > 0 and j 1 + j 2 + 4i < 4t and (j 1 < 2 ∨ j 2 < 2)} , One can check that the polynomials fj 1 ,j 2 ,i are linearly independent since LM (f ) = y j 1 1 y j 2 2 for each fj 1 ,j 2 ,i from P. The list of monomials appearing within this collection can be described as:

M = z j 1 1 z j 2 2 mod ∆ j 1 +j 2 : j 1 + j 2 < 4t ,
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj 1 ,j 2 ,i ) = j 1 + j 2 + 4i and the parameter function χ( fj 1 ,j 2 ,i ) = i.

Since the degree of each variable z i is 1 and the degree of f is 4, we can described P as:

Seq(uZ 4 ) × (ε + Z)(Seq(Z) + Z 2 Seq(Z)) × Seq(Z),
where the last one is for the dumming value y 0 . This leads to the generating function:

F (z, u) = (1 + z)(1 + z 2 ) (1 -z) 2 × 1 1 -uz 4 .

Predicting EC-LCG Sequences for Known Composer

87

We have ∂F ∂u (u, z) 4 , since 4t ∼ 4t -1, this leads to:

u=1 = z 4 (1 + z)(1 + z 2 ) (1 -z) 2 (1 -z 4 ) 2 as z → 1 , 1 -z 4 ∼ 4(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 1 4(1 -z)
χ <4t (P) ∼ 1 4 × (4t) 3 3!
Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(y j 1 1 y j 2 2 ) = j 1 + j 2 and the parameter function χ(y j 1 1 y j 2 2 ) = j 1 + j 2 . Since the degree of each z i is 1, we can then described M as:

2 i=1 Seq(uZ) × Seq(Z),
where the last one is for the dumming value y 0 . Which leads to the generating function:

F (z, u) = 1 1 -uz 2 × 1 1 -z .
We have ∂F ∂u (u, z)

u=1 = 2z (1 -z) 4 , as z → 1 , 1 -z n ∼ n(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 2 (1 -z) 4 , since 4t ∼ 4t -1, this leads to: χ <4t (M) ∼ 2(3t) 3 3!
Condition. If we denote by ν = χ <4t (P), and ε = χ <4t (M), the condition for Coppersmith's method is p ν > ∆ ε , ie ∆ < p ν ε , where: Experimental Results. We have implemented the attack in Sage 7.6 on an elliptic curve over F p for a 256-bit prime p on a MacBook Air laptop computer (2,2 GHz Intel Core i7, 4 Gb RAM 1600 MHz DDR3, Mac OSX 10.10.5). Our theoretical bound is δ theo = 1 8 (δ < p δ ) and we denote the experimental bound by δ exp . We consider the family of polynomials P t with t = 2 which corresponds to a lattice of dimension 40. After the computations of the LLL reduced basis and Gram-Schmidt orthogonalized basis which takes a few seconds, we obtain a polynomial system over the integers of dimension 0 if δ exp < 0.085 and we can then recover the seed U 0 .

ν ε ∼ χ <4t (P) χ <4t (M) ∼ 1
We further improve the previous bound and we show that the EC-LCG is insecure if at least a proportion of 3/4 of the most significant bits of an infinite consecutive multiple values U kn of the sequence is output. Theorem 6.2.4. (more outputs) Given ∆-approximations w 0 , w k ,. . . ,w kn to n + 1 values X(U 0 ), X(U k ),. . . ,X(U kn ) produced by the EC-LCG. Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 in polynomial time in log p as soon as ∆ < p n 4(n+1) .

Proof. We set U kt = (x kt , y kt ), for t = 0, . . . , n and G = (x G , y G ). We then have the equalities:

x i = w i + e i where |e i | < ∆, i = 0, k, . . . , nk. We have U kt -U k(t+1) = -kG, for t = 0, . . . , n -1. Thus U kt -U k(t+1) + kG = O. Hence: f 3 (x tk , x k(t+1) , X(kG)) = 0,
where f 3 is like in the previous proof the polynomial defined in section 2.3.3. Using the equalities x i = w i + e i , i = 0, k, . . . , kn we obtain the polynomial system: f j (e (j-1)k , e jk ) = 0, j = 1, . . . , n where f j (y j-1 , y j ) = f 3 (w (j-1)k + y j-1 , w jk + y j , X(kG)) is a polynomial of degree 4. We consider monomials with respect to a monomial ordering such that LM (f k ) = y 2 j-1 y 2 j . We consider the following collection of polynomials:

P = { fj 0 ,...,jn,i k = y j 0 0 . . . y jn n f i k k mod p i k : k = 1, . . . , n; (j k-1 < 2 ∨ j k < 2) (i k > 0) and (j 0 + • • • + j n + 4i k ) < 4t} ,
One can check that the polynomials fj 0 ,...,jn,i k are linearly independent. The list of monomials appearing within this collection can be described as:

M = z j 0 0 . . . z jn n mod ∆ j 0 +•••+jn : j 0 + • • • + j n < 4t ,
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj 0 ,...,jn,i k ) = j 0 +• • •+j n +4i k and the parameter function χ( fj 0 ,...,jn,i k ) = i k .

Since the degree of each variable z i is 1 and the degree of f is 4, we can described P as:

n k=1 Seq(uZ 4 ) × (ε + Z)(Seq(Z) + Z 2 Seq(Z)) × n j=0,j =k-1,k
Seq(Z) × Seq(Z),

Predicting EC-LCG Sequences for Known Composer

89

where the last one is for the dumming value z 0 . This leads to the generating function:

F (z, u) = n k=1 (1 + z)(1 + z 2 ) (1 -z) n+1 × 1 1 -uz 4 . We have ∂F ∂u (u, z) u=1 = nz 4 (1 + z)(1 + z 2 ) (1 -z) n+1 (1 -z 4 ) 2 as z → 1 , 1 -z 4 ∼ 4(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 n 4(1 -z) n+3 ,
since 4t ∼ 4t -1, this leads to:

χ <4t (P) ∼ n 4 × (4t) n+2 (n + 2)!
Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(y j 1 1 y j 2 2 ) = j 0 + • • • + j n and the parameter function χ(y j 0 0 . . . y jn n ) = j 0 + • • • + j n . Since the degree of each z i is 1, we can then described M as:

n i=0 Seq(uZ) × Seq(Z),
where the last one is for the dumming value z 0 . Which leads to the generating function:

F (z, u) = 1 1 -uz n+1 × 1 1 -z .
We have ∂F ∂u (u, z)

u=1 = 2z (1 -z) n+3 , as z → 1 , 1 -z n ∼ n(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 n + 1 (1 -z) n+3 , since 4t ∼ 4t -1, this leads to: χ <4t (M) ∼ (n + 1)(4t) n+2 (n + 2)!
Condition. If we denote by ν = χ <4t (P), and ε = χ <4t (M), the condition for Coppersmith's method is p ν > ∆ ε , ie ∆ < p ν ε , where:

ν ε ∼ χ <4t (P) χ <4t (M) ∼ n 4(n + 1)
, this leads to the expecting bound:

∆ < p n 4(n+1) → n→∞ ∆ < p 1 4 .

90

Chapter 6. Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves

Predicting EC-LCG Sequences for Unknown Composer

In this section, we infer the EC-LCG in the case where the composer G is unknown and the curve is kept secret. In the following, We show that the generator is insecure if at least a proportion of 23/24 of the most significant bits of three consecutive values U 0 and U 1 and U 2 of the sequence is output.

Theorem 6.3.1. (three consecutive outputs) Given ∆-approximations W 0 , W 1 , W 2 to three consecutive affine values U 0 , U 1 , U 2 produced by the EC-LCG. Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 and the composer G in polynomial time in log p as soon as ∆ < p 1/24 .

Proof. We set U 0 = (x 0 , y 0 ), U 1 = (x 1 , y 1 ), U 2 = (x 2 , y 2 ), W 0 = (α 0 , β 0 ), W 1 = (α 1 , β 1 ) and W 2 = (α 2 , β 2 ). We then have the equalities:

x i = α i + e i , y j = β j + f j , where |e i |, |f i | < ∆, i = 0, 1, 2. (6.1)
We also have:

       y 2 0 = x 3 0 + ax 0 + b y 2 1 = x 3 1 + ax 1 + b y 2 2 = x 3 2 + ax 2 + b .
Eliminating the curve parameters a, b and assuming that U 2 = ±U 1 (that is, x 2 = x 1 ), we obtain the following equation:

y 2 2 (x 0 -x 1 ) + x 3 2 (x 1 -x 0 ) + x 3 0 (x 2 -x 1 ) + y 2 0 (x 1 -x 2 ) + x 3 1 (x 0 -x 2 ) + y 2 1 (x 2 -x 0 ) = 0
Using the equalities 6.1, leads to the equation: f (e 0 , e 1 , e 2 , f 0 , f 1 , f 2 ) = 0 mod p where f is a polynomial of degree 4 whose coefficients are functions of α 0 , α 1 , α 2 , β 0 , β 2 , and

β 2 .

Description of the attack

The adversary is therefore looking for the solutions smaller than ∆ of the following modular multivariate polynomial equation:

f (z 1 , . . . , z 6 ) = 0 mod p
The attack consists in applying Coppersmith's methods as in the former subsection. We consider monomials with respect to a monomial ordering such that LM (f ) = z 3 1 z 2 . From now on, we use the following collection of polynomials:

P = { fj 1 ,...,j 6 ,i = z j 1 1 . . . z j 6 6 f i mod p i : i > 0 and j 1 + • • • + j 6 + 4i < 4t and (0 j 1 < 3 ∨ j 2 = 0)} ,
One can check that the polynomials fj 1 ,...,j 6 ,i are linearly independent since LM (f ) = z j 1 1 . . . z j 6 6 for each fj 1 ,...,j 6 ,i from P. The list of monomials appearing within this collection can be described as:

M = z j 1 1 . . . z j 6 6 mod ∆ j 1 +•••+j 6 : j 1 + • • • + j 6 < 4t .
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj 1 ,...,j 6 ,i ) = j 1 + • • • + j 6 + 4i and the parameter function χ( fj 1 ,...,j 6 ,i ) = i. Since the degree of each variable z i is 1 and the degree of f is 4, we can described P as:

4 i=1 Seq(Z) × Seq(uZ 4 ) ×   (ε + Z + Z 2 z 1 )(ε + ZSeq(Z) z 2 ) + Z 3 Seq(Z) z 1    × Seq(Z),
where the last one is for the dummy value z 0 . This leads to the generating function:

F (z, u) = 1 1 -z 5 × 1 1 -uz 4 × (1 + z + z 2 )(1 + z/(1 -z)) + z 3 1 -z .
We have ∂F ∂u (u, z)

u=1 = 1 + z + z 2 + z 3 (1 -z) 6 × z 4 (1 -z 4 ) 2 as z → 1 , 1 -z 4 ∼ 4(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 1 4(1 -z) 8 , since 4t ∼ 4t -1, this leads to: χ <4t (P) ∼ 1 4 × (4t) 7 7!
Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j 1 1 . . . z j 6 6 ) = j 1 + • • • + j 6 and the parameter function χ(z j 1 1 . . . z j 6 6 ) = j 1 + • • • + j 6 . Since the degree of each z i is 1, we can then described M as:

6 i=1 Seq(uZ) × Seq(Z),
where the last one is for the dummy value z 0 . Which leads to the generating function:

F (z, u) = 1 1 -uz 6 × 1 1 -z .
We have ∂F ∂u (u, z) . This bound improves the known bound ∆ < p 1/46 .

u=1 = 6z (1 -z) 8 , as z → 1 , 1 -z n ∼ n(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 6 (1 -z) 8 , since 4t ∼ 4t -1,

Complexity of the attack

To compute the cardinalities of the sets P and M, we make used of the parameters functions χ( fj 1 ,...,j 6 ,i ) = 1 and χ(z j 1 1 . . . z j 6 6 ) = 1. This leads to the generating functions:

F 1 (z) = 1 1 -z 5 × z 4 1 -z 4 × 1 + z + z 2 + z 3 1 -z and F 2 (z) = 1 (1 -z) 7 ,
for P and M respectively. Asymptotic bounds. We have: Next, we further improve the previous bound and we show that the generator is insecure if at least a proportion of 7/8 of the most significant bits of an infinite consecutive values U i of the sequence is output.

F 1 (z), F 2 (z) ∼ z→1 1 (1 -z)

Theorem 6.3.2. (more consecutive outputs)

Given ∆-approximations W 0 , W 1 ,. . . ,W n+1 (for some integer n > 1) to n + 2 consecutive affine values U 0 , U 1 ,. . . ,U n+1 produced by the EC-LCG. Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 and the composer G in polynomial time in log p as soon as ∆ < p n/4(2n+4) .

Proof. Let us assume, for instance that the adversary has access to n + 1 ∆-approximations W 0 , W 1 ,. . . ,W n+1 of U 0 , U 1 ,. . . ,U n+1 produced by the EC-LCG. Then using the equalities x j = α j + e j and y j = β j + f j , for j = 0, . . . , n, where |e j |, |f j | < ∆ and W j = (α j , β j ) and U j = (x j , y j ) and the fact that y 2 j = x 3 j + ax j + b, j = 0, . . . , n + 1 and eliminating the curve parameters from three consecutive points U j , U j+1 , U j+2 ,j = 0, . . . , n -1 leads to the following polynomial system:

         f 1 (e 0 , e 1 , e 2 , f 0 , f 1 , f 2 ) = 0 mod p . . .
f n (e n-1 , e n , e n+1 , f n-1 , f n , f n+1 ) = 0 mod p . Where f j are polynomials of degrees 4 and LM (f i ) = z 3 i-1 z i . The adversary is then looking for the solutions of the modular multivariate polynomial system:

         f 1 (z 0 , z 1 , z 2 , z n+2 , z n+3 , z n+4 ) = 0 mod p . . . f n (z n-1 , z n , z n+1 , z 2n+1 , z 2n+2 , z 2n+3 ) = 0 mod p .
We consider the following collection of polynomials:

P =      fj 0 ,...,j 2n+3 ,α i = z j 0 0 . . . z j 2n+3 2n+3 f α i i mod p α i s.t. i = 1, . . . , n; (j i-1 < 3 ∨ j i = 0) (α i > 0) and (j 0 + • • • + j 2n+3 + 4α i ) < 4t      .
The list of monomials appearing within this collection can be described as:

M = z j 0 0 . . . z j 2n+3 2n+3 mod ∆ j 0 +•••+j 2n+3 : j 0 + • • • + j 2n+3 < 4t ,
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj 0 ,...,j 2n+3 ,α i ) = j 0 + • • • + j 2n+3 + 4α i and the parameter function χ( fj 0 ,...,j 2n+3 ,α i ) = α i . We can described P as:

n i=1 2n+3 j=0 j / ∈{i-1,i} Seq(Z) × Seq(uZ 4 ) × (ε + Z + Z 2 )(ε + ZSeq(Z)) + Z 3 Seq(Z) × ε × Seq(Z),
where the last one is for the dummy variable. This leads to the generating function:

F (z, u) = 1 (1 -z) 2n+3 × 1 1 -uz 4 × n (1 + z + z 2 )(1 + z/(1 -z)) + z 3 1 -z .
We have 2n+3 ) = j 0 + • • • + j 2n+3 and the parameter function χ(z j 0 0 . . . z

∂F ∂u (u, z) u=1 ∼ z→1 n 4(1 -z) 2n+6 , since 4t ∼ 4t -1,
j 2n+3 2n+3 ) = j 0 + • • • + j 2n+3 .
We can described M as:

2n+4 i=1 Seq(uZ) × Seq(Z),
where the last one is for the dummy variable. This leads to the generating function:

F (z, u) = 1 1 -uz 2n+4 × 1 1 -z .
We get

∂F ∂u (u, z) u=1 ∼ z→1 2n + 4 (1 -z) 2n+6 , since 4t ∼ 4t -1, this leads to: χ <4t (M) ∼ (2n + 4) × (4t) 2n+5 (2n + 5)!
Condition. If we denote by ν = χ <4t (P), and ε = χ <4t (M), the condition for Coppersmith's method is p ν > ∆ ε , ie ∆ < p ν ε , where:

ν ε ∼ χ <4t (P) χ <4t (M) ∼ n 4(2n + 4) ,
This leads to the expecting bound:

∆ < p n 4(2n+4) → n→∞ ∆ < p 1/8 .

Predicting the Elliptic curve power generator

We infer the EC-PG in the case where the constants a, b and e are known. We show that this generator is insecure if at least a proportion of 1 -1 2e 2 of the most significant bits of two consecutive values X(V 0 ) and X(V 1 ) is output. Theorem 6.4.1. (two consecutive outputs) Given ∆-approximations w 0 , w 1 to two consecutive values X(V 0 ), X(V 0 ) produced by the EC-PG and under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed V 0 in heuristic polynomial time in log p as soon as ∆ < p Proof. We put V 0 = (x 0 , y 0 ), V 1 = (x 1 , y 1 ). We have x 1 = θe(x 0 ) ψ 2 e (x 0 ) (where the polynomials θ e (X) and ψ 2 e (X) are defined in section 2.3.2) since V 1 = eV 0 . Using the equalities x 0 = w 0 +α 0 and x 1 = w 1 + α 1 with α i < ∆, we have f (α 1 , α 0 ) = 0, where f (y 1 , y 2 ) = (y 1 + w 1 )ψ 2 e (y 2 + w 0 )θ e (y 2 + w 0 ) s a polynomial of degree e 2 . We are looking for small modular modulo p.

We consider monomials with respect to a monomial ordering such that the leading monomial of f is LM (f ) = y 1 y e 2 -1

2

. We consider the following collection of polynomials (parameterized by some integer t ∈ N): P = f j 1 ,j 2 ,i = y j 1 1 y j 2 2 f i mod p i : i > 0 and j 1 + j 2 + e 2 i < e 2 t and (j 1 = 0 ∨ 0 j 2 e 2 -2) .

One can check that the polynomials f j 1 ,j 2 ,i are linearly independent since LM ( f j 1 ,j 2 ,i ) = y j 1 1 y j 2 2 for each f j 1 ,j 2 ,i . The list of monomials appearing within this collection can be described as:

M = y j 1 1 y j 2 2 mod ∆ j 1 +j 2 : j 1 + j 2 < e 2 t .
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj 1 ,j 2 ,i ) = j 1 + j 2 + e 2 i and the parameter function χ( fj 1 ,j 2 ,i ) = i.

Since the degree of each variable z i is 1 and the degree of f is e 2 , we can described P as:

Seq(uZ e 2 ) ×   (ε + Z + • • • + Z e 2 -2 y 2 )(ε + ZSeq(Z) y 1
) + Z e 2 -1 Seq(Z)

y 2    × Seq(Z),
where the last one is for the dumming value y 0 . This leads to the generating function:

F (z, u) = 1 1 -z 2 × 1 1 -uz e 2 × 1 + z + • • • + z e 2 -1 .
We have

∂F ∂u (u, z) u=1 = z e 2 (1 + z + • • • + +z e 2 -1 ) (1 -z) 2 (1 -z e 2 ) 2
as z → 1 , 1z e 2 ∼ e 2 (1z) leads to: 4 , since e 2 t ∼ e 2 t -1, this leads to:

∂F ∂u (u, z) u=1 ∼ z→1 1 e 2 (1 -z)
χ <e 2 t (P) ∼ 1 e 2 ×
(e 2 t) 3 3! Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j 1 1 . . . z j 6 6 ) = j 1 + • • • + j 6 and the parameter function χ(y j 1 1 y j 2 2 ) = j 1 + j 2 . Since the degree of each z i is 1, we can then described M as:

2 i=1 Seq(uZ) × Seq(Z),
where the last one is for the dumming value y 0 . Which leads to the generating function: (for some integer n > 1)

F (z, u) = 1 1 -uz 2 × 1 1 -z .
to n + 1 consecutive values X(V 0 ), X(V 1 ),. . . , X(V 1 )
produced by the EC-PG and under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed V 0 in heuristic polynomial time in log p as soon as ∆ < p n (n+1)e 2 Proof. We put V i = (x i , y i ), i = 0, . . . , n. We have x j+1 = θe(x j ) ψ 2 e (x j ) since V j+1 = eV j for j = 0, . . . , n -1. Using the equalities x i = w i + α i , i = 0, . . . , n with α i < ∆, we have f j (α j , α j-1 ) = 0, for j = 1, . . . , n where f j (y j-1 , y j ) = (y j-1 +w j )ψ 2 e (y j +w j-1 )-θ e (y j +w j-1 ). We are then looking for small modular modulo p. We use the Coppersmith's methods to recover the desired solution in polynomial time. The monomials are ordered with respect to a monomial ordering such that the leading monomial of each f j is y j-1 y e 2 -1 j . f j is a polynomial of degree e 2 . We consider the following collection of polynomials (parameterized by some integer t ∈ N):

P = f j 1 ,...,jn,i k = y j 1 1 . . . y jn n f i k k mod p i k : i k > 0, k ∈ {1, . . . , n}, and j 1 + • • • + j n + e 2 i k < e 2 t and (j k-1 = 0 ∨ 0 j k e 2 -2) .
One can check that the polynomials f j 1 ,...,jn,i k are linearly independent since LM ( f j 1 ,...,jn,i k ) = y j 1 1 . . . y jn n for each f j 1 ,...,jn,i k . The list of monomials appearing within this collection can be described as:

M = y j 0 0 . . . y jn n mod ∆ j 0 +•••+jn : j 0 + • • • + j n < e 2 t .
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj 1 ,...,jn,i k ) = j 1 + • • • + j 2 + e 2 i k and the parameter function χ( fj 1 ,...,jn,i k ) = i k . Since the degree of each variable z i is 1 and the degree of f k is e 2 , we can described P as:

n k=1 Seq(uZ e 2 ) ×   (ε + Z + • • • + Z e 2 -2 y k )(ε + ZSeq(Z) y k-1
) + Z e 2 -1 Seq(Z)

y k    × n j=0 j / ∈{k-1,k} Seq(Z) × Seq(Z),
where the last one is for the dumming value z 0 . This leads to the generating function:

F (z, u) = n k=1 1 1 -z n+1 × 1 + z + • • • + z e 2 -1 1 -uz e 2 .
We have n+3 , since e 2 t ∼ e 2 t -1, this leads to:

∂F ∂u (u, z) u=1 = nz e 2 (1 + z + • • • + +z e 2 -1 ) (1 -z) n+1 (1 -z e 2 ) 2 as z → 1 , 1 -z e 2 ∼ e 2 (1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 n e 2 (1 -z)
χ <e 2 t (P) ∼ n e 2 × (e 2 t) n+2 (n + 2)!
Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j 1 1 . . . z j 6 6 ) = j 1 + • • • + j 6 and the parameter function χ(y j 0 0 . . . y j 2 n ) = j 1 + • • • + j n . Since the degree of each y i is 1, we can then described M as:

n i=0 Seq(uZ) × Seq(Z),
where the last one is for the dumming value z 0 . Which leads to the generating function: Chapter 7.

F (z, u) = 1 1 -uz (n+1) × 1 1 -z . We have ∂F ∂u (u, z) u=1 = (n + 1)z (1 -z) n+3 , which leads to: ∂F ∂u (u, z) u=1 ∼ z→1 n + 1 (1 -z) ( n + 3) , since e 2 t ∼

Lattice Attacks on Pairing-Based Signatures

The present Chapter deals with lattice attacks on some well-known Pairing-Based signatures. Practical implementations of cryptosystems often suffer from critical information leakage through side-channels (such as their power consumption or their electromagnetic emanations). 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). 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 Chapter is organized as follows: we start by recalling the Sakai-Kasahara, Boneh-Boyen and Gentry's Pairing-Based Signatures Schemes. We then present the attack on Gentry's signatures. Next, we present the attack on Boneh-Boyen's signatures and we conclude by the attack on Sakai-Kasahara's signature.

Contents

-99 -• Signature generation. Given a message m ∈ {0, 1} * , the user computes its hash value H(m), and picks uniformly at random r ∈ Z p . It computes the signing exponent σ = (y + r)/(x + H(m)) mod p and the group element s = g σ . The signature is the pair (r, s) ∈ Z p × G.

• Signature verification. Given (r, s) ∈ Z p × G, a verifier accepts it as a signature on m ∈ {0, 1} * if and only if the following equality holds: e(s, h 1 g H(m) )

?

= e (g, h 2 g r )

Description of the Attack

In this section, we use Coppersmith's methods to attack Gentry's signatures when the attacker learns some blocks of consecutive bits of the signing exponents.

Let n 1 be some integer. We suppose that the attacker is given (n + 2) message/signature pairs (m i , (r i , s i )) i∈{0,...,n+1} as described above (where n does not depend on the security parameter λ). To simplify the notation in the following, instead of the hash values H(m i ), we assume that the m i belongs to Z p (for i ∈ {0, . . . , n + 1}).

We assume that the attacker knows some blocks of consecutive bits of the corresponding signing exponents σ i for i ∈ {0, . . . , n + 1} and its goal is to recover the secret keys x and y. From the knowledge of two different signing exponents σ i and σ j for integers i, j ∈ {0, . . . , n + 1} with i = j, the attacker can actually recover the secrets x and y. Its goal is therefore to recover the hidden bits of two σ i 's in order to obtain x and y.

We have σ i = (y + r i )/(x + m i ) mod p for i ∈ {0, . . . , n + 1} which can be rewritten as:

σ i (x + m i ) -y -r i = 0 mod p, i ∈ {0, . . . , n + 1}.
We consider a chosen-message attack where the attacker uses an arbitrary unique message m for all signatures (i.e. m i = m for all i ∈ {0, . . . , n + 1}). Eliminating x and y, in the previous equation, we obtain for a, b, i ∈ {0, . . . , n + 1} with 0 a < b < i n + 1:

(r a -r b )σ i + (r i -r a )σ b + (r b -r i )σ a = 0 mod p (7.1)
Putting σ i = N j=1 x i,j 2 k i,j + γ i , i ∈ {0, . . . , n + 1}, where γ i is known to the attacker and x i,j , j ∈ {1, . . . , N } are unknown and |x i,j | < 2 µ i,j for some integer µ i,j and with the choice a = 0, b = 1, we obtain a polynomial f i (z 0,1 , . . . , z 0,N , . . . , z n+1,1 , . . . , z n+1,N ) having as root X 0 = (x 0,1 , . . . , x 0,N , . . . , x n+1,1 , . . . , x n+1,N ) modulo p with:

f i = z i,N + N -1 j=1 a i,j z i,j + N j=1 b i,j z 1,j + N j=1 c i,j z 0,j + γ i (r 0 -r 1 ) + d i mod p (7.2) for i ∈ {2, . . . , n + 1}, where          a i,j = 2 k i,j /2 k i,N mod p b i,j = 2 k 1,j (r i -r 0 )/((r 0 -r 1 )2 k i,N ) mod p c i,j = 2 k 0,j (r 1 -r i )/((r 0 -r 1 )2 k i,N ) mod p d i = (γ i (r 0 -r 1 ) + γ 1 (r i -r 0 ) + γ 0 (r 1 -r i ))/((r 0 -r 1 )2 k i,N ) mod p
Chapter 7. Lattice Attacks on Pairing-Based Signatures for i ∈ {2, . . . , n + 1} and j ∈ {1, . . . , N }.

We consider the following collection of polynomials (parameterized by some integer m ∈ N that does not depend on the security parameter λ): P m = f i 0,1 ,...,i n+1,1 ,i 0,2 ,...,i n+1,2 ,...,i 0,N ,...,i n+1,N , for all vectors of integers (i 0,1 , . . . , i n+1,1 , i 0,2 , . . . , i n+1,2 , . . . , i 0,N , . . . , i n+1,N ) verifying

0 i 0,1 + • • • + i n+1,1 + • • • + i 0,N , . . . , i n+1,N m
and where the polynomial f i 0,1 ,...,i n+1,1 ,i 0,2 ,...,i n+1,2 ,...,i 0,N ,...,i n+1,N is defined by: ) . One can see that f i 0,1 ,...,i n+1,1 ,i 0,2 ,...,i n+1,2 ,...,i 0,N ,...,i n+1,N (X 0 ) = 0 mod p m for all such vector of integers.

z i 0,1 0,1 . . . z i n+1,1 n+1,1 . . . z i 0,N -1 0,N -1 . . . z i n+1,N -1 n+1,N -1 z i 0,N 0,N z i 1,N 1,N f i 2,N 2 . . . f i n+1,N n+1 p m-(i 2,N +•••+i n+1,N
If we use for instance the lexicographical monomial order (with z i,j < z i ,j if (j < j or (j = j and i < i )) on the set of monomials, we can define an order over the set of polynomials as:

f i 0,1 ,...,i n+1,1 ,i 0,2 ,...,i n+1,2 ,...,i 0,N ,...,i n+1,N < f i 0,1 ,...,i n+1,1 ,i 0,2 ,...,i n+1,2 ,...,i 0,N ,...,i n+1,N if z i 0,1 0,1 . . . z i n+1,1 n+1,1 . . . z i 0,N 0,N . . . z i n+1,N n+1,N < z i 0,1 0,1 . . . z i n+1,1 n+1,1 . . . z i 0,N 0,N . . . z i n+1,N n+1,N .
Using this order, we can write P m = { fi , i ∈ {1, . . . , ω}}, with f1 < f2 < • • • < fω where ω is the number of polynomials. Putting U = 2 max i,j µ i,j , we define the lattice L generated by b 1 , . . . , b ω , where for i ∈ {1, . . . , ω}, b i is the coefficient vector of the polynomial fi (U z 0,1 , . . . , U z n+1,1 , . . . , U z 0,N , . . . , U z n+1,N ).

One can easily verify that the basis matrix is lower triangular and the diagonal elements are N ) , where the integer a is equal to i

U a p m-(i 2,N +•••+i n+1,
0,1 + • • • + i n+1,1 + i 0,N + • • • + i n+1,N .
The number of variables is N (n + 2) and the success condition of Coppersmith's method is det(L) < p m(ω-N (n+2)) , where ω = i∈I 1 is the dimension of the lattice with

I = {i = (i 0,1 , . . . , i 0,N , . . . , i n+1,N )|0 i 0,1 + • • • + i n+1,N m}. We have det(L) = U η p mω p -µ with µ = i∈I i 2,N + • • • + i n+1,N and η = i∈I i 0,1 + • • • + i n+1,N .
If m is large, we can neglect the N (n + 2) term in Coppersmith success condition and the asymptotic condition becomes:

U η < p µ .
Using analytic combinatorics methods (see below for details), one can verify that when m tends to ∞, we have η

= N (n + 2)β(m, N, n) and µ = nβ(m, N, n), with β(m, N, n) = m N (n+2)+1 (N (n + 2) + 1)! + o(m N (n+2)+1 ).
Therefore, the attacker can recover x and y as long as the sizes of each unknown block in the signatures σ i for i ∈ {0, . . . , n + 1} satisfies:

U < p n (n+2)N → n→∞ p 1 N .

Lattice Attack On Gentry Signatures

105

We can thus heuristically recover (using large2 constant parameters n and m) the secret key (x, y) if the number of consecutive bits of each unknown block is smaller than log 2 (p) /N .

• In order to compute η, we consider M (the set of monomials appearing in the collection P m ) as a combinatorial class, with the size function S(z N and the parameter function

i 0,1 0,1 . . . z i n+1,1 n+1,1 . . . z i 0,N 0,N . . . z i n+1,N n+1,N ) = i 0,1 + • • • + i n+1,1 + • • • + i 0,N + • • • + i n+1,
χ(z i 0,1 0,1 . . . z i n+1,1 n+1,1 . . . z i 0,N 0,N . . . z i n+1,N n+1,N ) = i 0,1 + • • • + i n+1,1 + • • • + i 0,N + • • • + i n+1,N . We describe M as N (n+2) k=1 Seq(uZ) × Seq(Z)
the last Seq(Z) being for the dummy value. This then leads to the OGF

F (z, u) = 1 1 -uz N (n+2) 1 1 -z .
We get

∂F ∂u (u, z) u=1 ∼ z→1 N (n + 2) (1 -z) N (n+2)+2 ,
this leads to:

χ <m (M ) = η ∼ N (n + 2) × (m) N (n+2)+1 (N (n + 2) + 1)! .
• To compute µ, we consider M as a combinatorial class, with the size function S(z

i 0,1 0,1 . . . z i n+1,1 n+1,1 . . . z i 0,N 0,N . . . z i n+1,N n+1,N ) = i 0,1 + • • • + i n+1,1 + • • • + i 0,N + • • • + i n+1,N and the parameter function χ(z i 0,1 0,1 . . . z i n+1,1 n+1,1 . . . z i 0,N 0,N . . . z i n+1,N n+1,N ) = i 2,N + • • • + i n+1,N . We describe M as N (n+2)-n k=1 Seq(Z) × n k=1 Seq(uZ) × Seq(Z)
the last Seq(Z) being for the dummy value. This then leads to the OGF

F (z, u) = 1 1 -uz n 1 1 -z N (n+2)-n+1 . We get ∂F ∂u (u, z) u=1 ∼ z→1 n (1 -z) N (n+2)+2 ,
this leads to:

χ <m (M ) = µ ∼ n × (m)

Experimental Results

We have implemented the attack in Sage 7.6 on a MacBook Air laptop computer (2,2 GHz Intel Core i7, 4 Gb RAM 1600 MHz DDR3, Mac OSX 10.10.5). Table 7.1 lists the theoretical bound δ theo = n (n+2)N and an experimental bound δ exp for a 512-bit prime p (corresponding to a 256-bit security level) with (n + 2) signatures (for n ∈ {1, 3, 5}) and a few number of unknown blocks (N 2). We consider the family of polynomials P m with m = 4 and m = 2. We ran 2 7 experiments for all parameters and Table 7.1 gives the average running time (in seconds) of the LLL algorithm and the Gröbner basis computation.

We denote α the maximum number of least significant bits that the attacker knows in each signature σ j , for all j = 0 (for instance α = 0 means that it does not know any least significant bits of the signatures σ j , for all j ∈ {1, . . . , n + 1}). If we know at least δ exp log 2 (p) + α least significant bits of the signature σ 0 then the Gröbner basis always gives us a system of dimension 0 and we are able to find the N unknown block of sizes p δexp in each signature σ i for i ∈ {0, . . . , n + 1}. Otherwise, Gröbner basis computations gives us a system of dimension 1 and we are a priori unable to find the unknown blocks (though it is possible in some cases to obtain additional information). This system of dimension 1 occurs because the constructed system admits a large number of "small" solutions. We give an example of this in Appendix 7.3. However, If the condition mentioned above is satisfied, we obtain for N = 1 and n + 2 = 3, the success rates given in Table 7.2 (over 250 attacks performed for each parameter pair (m, δ exp )).

Concrete Attack Examples against Gentry signatures

In this section, we present two attack examples on Gentry signatures for a 256-bit prime p with 3 signatures (r 0 , σ 0 ), (r 1 , σ 1 ) and (r 2 , σ 2 ) and one T -bit unknown block in each signature, with T = 0.3 log 2 (p) . We recall that for i ∈ {0, 1, 2}, σ i = g s i where s i = (y + r i )/(x + m) mod p, x and y are the secret keys and p, m and r i , i ∈ {0, 1, 2} are public information. In this example, we took the following random values:

• p = 9b814891e89496e776bfeeebcac5c74130862914fe2b928d40c3a88323dcbaaf • m = 440f4a9df2936c4aad3856ed0ea5cf3d131ef658fc36c2fa56763373288d5519 • x = 57a7b0913f5202e31555ec9538ff90f38a5e6c53b359edfe1106c8ee9518029a • y = 259b67be7de53e0546860379bc31ab9bb30caf68c314a956a1719e18d4a24ae2 • r 0 = 75c471becf6a9d86aa5480985a95702617892ba84b7662d6bdf3a3c1931abf3b • r 1 = 675e28ffbf96b29365ebda463c3a0a4290a284f9fed9ddd0ccdada587c1f0152 • r 2 = 7961b0df3f0a286547f25da59a7c2a7c28764f4335a0aa2cd5a72ba2393a6cd3 • s 0 = 45f185a8ce35c2b95b3e1aef9fc516ec9e840c9a5b6b36c70532b10145790401 • s 1 = 8f63fe87fd0d67f6594ff44ba86a2755b2b6ad6a0b7ab4aafecae41fca50c713 • s 2 = 57de02b444bb7716c021d21162c3727ba904ae6e4d44aca2ad9f4406669e8744 and T = 0.3 log 2 (p) = 76.
In the first case, we suppose that we do not know any least significant bits of each signature and show that we are unable to find the unknown blocks since the Gröbner basis gives us a system of dimension 1.

In the second case, we suppose that we know T + 2 least significant bits of σ 0 but do not know any least significant bits of s 1 , and s 2 . We also suppose that we do not know T intermediate bits of s 0 and we show that in this case we are able to find the unknown blocks since the Gröbner basis gives us a system of dimension 0.

s 0 = 2 T • 45f185a8ce35c2b95b3e1aef9fc516ec9e840c9a5b6b3 + z 0 , s 1 = 2 T • 8f63fe87fd0d67f6594ff44ba86a2755b2b6ad6a0b7ab + z 1 , s 2 = 2 T • 57de02b444bb7716c021d21162c3727ba904ae6e4d44a + z 2 ,
where the T -bit numbers z 0 , z 1 and z 2 are the unknown blocks.

• We get the polynomial f (y 0 , y 1 , y 2 ) defined by:

y 2 + 86acc2de9d15dab4df6a8114243623f246376c1103c29ee97a0dd7490f87eb33 y 1 + 14d485b34b7ebc3297556dd7a68fa34eea4ebd03fa68f3a3c6b5d13a1454cf7b y 0 + 11f10fbe97565b062acfb71c6d98f596de6c1e236edaa9168d891d78d66e8c4a
having as root (z 0 , z 1 , z 2 ) modulo p.

• Constructing the lattice with m = 4, after the LLL reduction and the Gröbner basis computation, we obtain the system of polynomials

f 1 (y 0 , y 1 , y 2 ) = y 2 -y 0 -5dba86c930521258343 f 2 (y 0 , y 1 , y 2 ) = y 1 -y 0 + 21c0667cce17b283cee
having indeed (z 0 , z 1 , z 2 ) as root over the integers. However, the dimension of the system is 1 and then we are a priori unable to find the unknown blocks.

Second case

• We can write the signatures as:

s 0 = 36c70532b10145790401 + 2 79 • z 0 + 2 79+T • 8be30b519c6b8572b67c35df3 s 1 = 2 T • 8f63fe87fd0d67f6594ff44ba86a2755b2b6ad6a0b7ab + z 1 s 2 = 2 T • 57de02b444bb7716c021d21162c3727ba904ae6e4d44a + z 2
where the T -bit numbers z 0 , z 1 and z 2 are the unknown blocks.

• If one proceeds like in the attack, we obtain the polynomial f (y 0 , y 1 , y 2 ) defined by

y 2 + 86acc2de9d15dab4df6a8114243623f246376c1103c29ee97a0dd7490f87eb33 y 1 + 78836c7dbcc6bee53ea07b359a07fa111e09607336b452976acd0f0ec2a0c985 y 0 + 77b82eec348f27f19cb7a6c1cc895cf7261093b80d067ea4eb7b8da90e1ae306
having as root (z 0 , z 1 , z 2 ) modulo p.

• Constructing the lattice with m = 4, after the LLL reduction and the Gröbner basis computation, one obtains the system of polynomials

     f 1 (y 0 , y 1 , y 2 ) = y 2 -ca2ad9f4406669e8744 f 2 (y 0 , y 1 , y 2 ) = y 1 -4aafecae41fca50c713 f 3 (y 0 , y 1 , y 2 ) = y 0 -f8a2dd93d081934b6d6 having (z 0 , z 1 , z 2 )
as root over the integers. The dimension of the system is 0 and one finds readily the unknown blocks.

Boneh-Boyen Signatures

Two years before the proposal of Gentry's IBE, Boneh and Boyen proposed two IBE schemes in [START_REF] Boneh | Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles[END_REF] and described one signature scheme obtained using the Naor transformation in [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF]. Their scheme has comparable efficiency properties and also achieves existential unforgeability under chosen-message attacks in the standard security model.

With the same notation as above, Boneh-Boyen signature scheme is defined by the three following algorithms:

• Key generation. The user picks uniformly at random (x, y) ∈ Z 2 p , computes h 1 = g x and h 2 = g y and sets sk = (x, y) and pk = (h 1 , h 2 ) ∈ G 2 .

• Signature generation. Given a message m ∈ {0, 1} * , the user computes its hash value H(m), and picks uniformly at random r ∈ Z p . It computes the signing exponent s = 1/(x + H(m) + yr) mod p and the group element σ = g s . The signature is the pair (r, σ) ∈ Z p × G.

• Signature verification. Given (r, σ) ∈ Z p × G, a verifier accepts it as a signature on m ∈ {0, 1} * if and only if the following equality holds:

e(σ, h 1 • g H(m) • h r 2 )
? = e (g, g)

Description of the Attack

In this section, we use the Coppersmith's methods to attack Boneh-Boyen's signature. Let n 1 be some integer. We suppose that the attacker is given (n + 2) message/signature pairs (m i , (r i , s i )) i∈{0,...,n+1} as described above (where n does not depend on the security parameter λ). As above, to simplify the notation, we replace H(m i ) by m i ∈ Z p (for i ∈ {0, . . . , n + 1}). We assume that the attacker knows some blocks of consecutive bits of the corresponding signing exponents σ i = 1/(x + m + yr i ) mod p, for i ∈ {0, . . . , n}, where p, r i and m i are known to the attacker and x and y are kept secret. As for Gentry signatures, from the knowledge of two different signing exponents, the attacker can actually recover the secrets x and y and its goal is to recover the hidden bits of two σ i 's in order to recover x and y.

We have σ i = 1/(x + m i + yr i ) mod p for i ∈ {0, . . . , n + 1} and we have: Putting σ i = N j=1 x i,j 2 k i,j + γ i , i ∈ {0, . . . , n + 1}, where γ i is known to the attacker and x i,j , j ∈ {1, . . . , N } are unknown with |x i,j | < 2 µ i,j for some integer µ i,j and a = 0, Chapter 7. Lattice Attacks on Pairing-Based Signatures we obtain a polynomial f 0,b,i (z 0,1 , . . . , z 0,N , . . . , z n+1,1 , . . . , z n+1,N ) having as "small" root X 0 = (x 0,1 , . . . , x 0,N , . . . , x n+1,1 , . . . , x n+1,N ) modulo p, where : Using that order, we can order the set of polynomials from the smallest element to the greatest as follows: P = {p m1 , . . . , p mω 1 , f 0,1,2 , . . . , f 0,1,n+1 , f 0,2,3 , . . . , f 0,2,n+1 , . . . , f 0,n,n+1 } = { f1 , . . . , fω } where m1 < • • • < mω 1 , ω 1 is the cardinality of M 1 and ω is the cardinality of M. Putting U = 2 max i,j µ i,j , we define the lattice L generated by b 1 , . . . , b ω , where for each i ∈ {1, . . . , ω}, b i is the coefficient vector of the polynomial fi (U z 0,1 , . . . , U z 0,N , . . . , U z n+1,1 , . . . , U z n+1,N ).

x + m i + yr i - 1
σ i = 0
One can verify that the basis matrix is lower triangular. The number of variables is N (n + 2) and the success condition for the Coppersmith's method is: det(L) < p ω-N (n+2)+1 , with ω = M = N 2 (n + 1)(n + 2) 2 + (n + 2)N + 1.

We have det(L) = U 2N 2 (n+1)(n+2) 2 +(n+2)N p ω-n(n+1) 2 and the success condition becomes:

U < p n(n+1) 2 -N (n+2)+1
2N 2 (n+1)(n+2) 2 +(n+2)N . If n is large and since N is small, we can neglect -N (n + 2) + 1 which contribute to a small error term. So the attacker can recover x and y as long as the sizes of each unknown block in the signatures σ i , i ∈ {0, . . . , n + 1} satisfies:

U < p n(n+1) 2N 2 (n+1)(n+2)+2(n+2)N → n→∞ p 1 2N 2 .
We can thus heuristically recover the secret key if the number of consecutive bits of each unknown block is smaller than log 2 (p) /(2N 2 ).

Experimental results

Table 7.3 lists the theoretical bound δ theo = n(n+1)

2N 2 (n+1)(n+2)+2(n+2)N and an experimental bound δ exp for a 512-bit prime p with (n + 2) signatures for a few values of n ∈ {4, 6, 10} and one or two unknown blocks per signatures.

We ran 2 7 experiments for all parameters and in all cases (for the bound δ exp ), the assumption that the created polynomials define an algebraic variety of dimension 0 was verified. The constructed system was solved using Gröbner basis and the desired root recovered. Table 7.3 gives the average running time (in seconds) of the LLL algorithm and the Gröbner basis computation (using the same configuration as above).

Lattice Attack on Sakai-Kasahara Signatures

Sakai-Kasahara Signatures

In [START_REF] Sakai | ID based Cryptosystems with Pairing on Elliptic Curve[END_REF], Sakai and Kasahara presented the first pairing-based signature scheme in the exponent-inversion framework. Their scheme is very close to Boneh-Boyen signature schemes but produces shorter signatures (at the cost of relying on the random oracle heuristic [START_REF] Zhang | An Efficient Signature Scheme from Bilinear Pairings and Its Applications[END_REF]).

With the same notation as above, Sakai-Kasahara signature scheme is defined by the three following algorithms:

• Key generation. The user picks uniformly at random x ∈ Z p , computes h = g x and sets sk = x and pk = h ∈ G.

• Signature generation. Given a message m ∈ {0, 1} * , the user computes its hash value H(m). It computes the signing exponent s = 1/(x + H(m)) mod p and the group element σ = g s . The signature is the group element σ ∈ G.

• Signature verification. Given σ ∈ G, a verifier accepts it as a signature on m ∈ {0, 1} * if and only if the following equality holds: e(σ, h • g H(m) )

?

= e (g, g)

We present in the following an attack on this scheme when the attacker learns some blocks of consecutive bits of the signing exponents. This computational problem is related to the Modular Inversion Hidden Number Problem which was introduced in 2001 by Boneh, Halevi and Howgrave-Graham [START_REF] Boneh | The Modular Inversion Hidden Number Problem[END_REF]. In this problem, the attacker does not know exactly one Chapter 7. Lattice Attacks on Pairing-Based Signatures block of least significant bits of the signing exponents σ i while our attack considers the setting where the attacker does not know N 1 different blocks in each σ i (for any N ).

Description of the Attack

In this section, we use the Coppersmith's methods to attack Sakai-Kasahara signatures. Let n 1 be some integer. We suppose that the attacker is given (n + 1) message/signature pairs (m i , s i ) i∈{0,...,n} as described above (where n does not depend on the security parameter λ). Again, to simplify the notation, we replace H(m i ) by m i ∈ Z p (for i ∈ {0, . . . , n}). We assume that the attacker knows some blocks of consecutive bits of the corresponding signing exponents σ i = 1/(x + m i ) mod p for i ∈ {0, . . . , n} and its goal is to recover x. One can see that from the knowledge of a value σ i , the attacker can actually recover the hidden number x and it is thus sufficient to recover the hidden bits of a single σ i 's in order to recover x.

We have σ i = 1/(x + m i ) mod p for i ∈ {0, . . . , n} which can be rewritten as:

x + m i -1 σ i = 0 mod p, i ∈ {0, . . . , n}.

Eliminating x, we obtain:

(m im a )σ i σ a + σ iσ a = 0 mod p a, i ∈ {0, . . . , n}, 0 a < i n. (7.5) Putting, for i ∈ {0, . . . , n + 1}, σ i = N j=1 x i,j 2 k i,j + γ i , where γ i is known to the attacker and x i,j for j ∈ {1, . . . , N } are unknown with |x i,j | < 2 µ i,j for some integer µ i,j , we obtain a polynomial f a,i (z 0,1 , . . . , z 0,N , . . . , z n,1 , . . . , z n,N ) having as root X 0 = (x 0,1 , . . . , x 0,N , . . . , x n,1 , . . . , x n,N ) modulo p with:

f a,i = N j=1 N k=1
α a,i,j,k z i,j z a,k + N j=1 β a,i,j z i,j + N j=1 γ a,i,j x a,j + δ a,i mod p (7.6) for a, i ∈ {0, . . . , n}, a < i and with known coefficients, where α a,i,N,N = 1. The set of monomials appearing in the polynomials f a,i is: M = {1, z a,j z b,k , z i,j : i ∈ {0, . . . , n}; a, b ∈ {0, . . . , n}; a < b; j, k ∈ {1, . . . , N }} .

We consider the following set of polynomials: P = {p m, m ∈ M 1 } ∪ {f a,i : a, i ∈ {0, . . . , n}; a < i} , where M 1 = M \ M 2 with M 2 = {z a,N z i,N : a, i ∈ {0, . . . , n}; a < i}. One can see that for any polynomial f ∈ P, f (X 0 ) = 0 mod p. We can define an order on the set of monomials such that all the monomials in M 1 are smaller than any monomial in M 2 and for z a,N z i,N , z a ,N z i ,N ∈ M 2 , z a,N z i,N < z a ,N z i ,N if (a < a or (a = a and i < i )).

Using that order, we can order the set of polynomials from the smallest element to the greatest as follows: P = {p m1 , . . . , p mω 1 , f 0,1 , . . . , f 0,n , f 1,2 , . . . , f 1,n , . . . , f n-1,n } = { f1 , . . . , fω } where m1 < • • • < mω 1 , ω 1 is the cardinality of M 1 and ω is the cardinality of M. Putting U = 2 max i,j µ i,j , we define the lattice L generated by b 1 , . . . , b ω , where b i is the coefficient

2

. The success condition then becomes:

U < p n(n+1) 2 -N (n+1)+1 2N 2 n(n+1) 2 +(n+1)N .
If n is large and since N is small, we can neglect -N (n + 1) + 1 which contributes to a small error. The attacker can recover x and y as long as the sizes of each unknown block in the signatures σ i , i ∈ {0, . . . , n} satisfies:

U < p n(n+1) 2N 2 n(n+1))+2(n+1)N → n→∞ p 1 2N 2 .
We can heuristically recover the secret key of Sakai-Kasahara signatures if the number of consecutive bits of each unknown block is smaller than log 2 (p) /(2N 2 ).

Experimental results

Table 7.4 gives the theoretical bound δ theo = n(n+1) 2N 2 n(n+1))+2(n+1)N and an experimental bound δ exp for a 512-bit prime p with (n + 1) signatures for a few values of n ∈ {4, 6, 10} and one or two unknown blocks per signatures.

We ran 2 7 experiments for all parameters . As in the attack on Boneh-Boyen signatures, the assumption that the created polynomials define an algebraic variety of dimension 0 was verified (in all cases for the bound δ exp ) and the constructed system was solved using Gröbner basis and the desired root recovered. Table 7.4 gives the average running time (in seconds) of the LLL algorithm and the Gröbner basis computation (using the same configuration as above).

Chapter 8.

Conclusion and Open Questions

Conclusion

In this thesis:

• We proved lower bounds on the degree and weight of multivariate polynomial representations of the Naor-Reingold function over a finite field and over the group of points on an elliptic curve over a finite field for fixed secret keys and variable secret keys. For fixed secret keys, we showed that a low-weight or low-degree multivariate polynomial cannot reveal information on the functions values over finite fields and that a low-degree univariate and bivariate polynomial cannot reveal information on the functions values over elliptic curves. For variable secret keys, we showed that a low-weight or low-degree multivariate polynomial cannot reveal information on the functions values over finite fields and that a low-degree multivariate polynomial cannot reveal information on the functions values over elliptic curves in certain cases.

• We studied the distribution of the Dodis-Yampolskiy pseudo-random function values over finite fields and over elliptic curves. We showed that for almost all values of parameters, the Dodis-Yampolskiy pseudo-random function produces a uniformly distributed sequence. We also proved lower bounds on the degree of polynomials interpolating the values of these functions in these two settings of practical interest. We showed that a low-weight or low-degree univariate polynomial cannot reveal the secret key x when evaluated at V x (m) (for some integer m ∈ {1, . . . , d}) for all x over finite fields and that a low-degree univariate cannot reveal the secret key x when evaluated at V x (m) over elliptic curves.

• We analyzed the security of the elliptic curve linear congruential generator (EC-LCG) and of the elliptic curve power generator (EC-PG). In the case where the composer is known, we showed that the EC-LCG is insecure if at least a proportion of 8/11 of the most significant bits of an arbitrary large number of consecutive values U i of the sequence is output. We also tackled the case where the most significant bits of an arbitrary large number of non consecutive values (namely the most significant bits of the abscissa of values U ki for some fixed integer k) of the sequence is output and we showed that the EC-LCG is insecure if at least a proportion of 3/4 of the most significant bits is output. Furthermore, we consider the cryptographic setting where the composer is unknown and we showed that this generator is insecure if at least a proportion of 7/8

-115 -data. In [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF], Coron proposed notably to randomize the exponent and the projective coordinates of the base point. The first question is: Question 8.6. Can we extend our attacks in such setting (as it was done recently for ECDSA in [START_REF] Goudarzi | Lattice Attacks against Elliptic-Curve Signatures with Blinded Scalar Multiplication[END_REF])? Our attacks are heuristic and it would be very interesting to give proven version of our attacks (as it was done in [NS02; NS03] for ECDSA signatures). It is also interesting to study further the attack against Gentry signatures when the unknown blocks of consecutive bits overlap. Finally, it would be nice to improve our attacks on Boneh-Boyen and Sakai-Kasahara signatures and to show that one can recover the secret key if the number of consecutive bits of each unknown block is smaller than log 2 (p) /(cN ) for some constant c. Les implémentations pratiques de cryptosystèmes souffrent souvent de fuites critiques d'informations à travers des attaques par canaux cachés. Ceci peut être le cas lors du calcul de l'exponentiation afin de calculer la sortie de la fonction pseudo-aléatoire de Dodis-Yampolskiy et plus généralement le calcul des signatures dans certains schémas de signatures bien connus à base de couplage (signatures de Sakai-Kasahara, Boneh-Boyen et Gentry) basées sur le paradigme d'inversion. Nous présentons des algorithmes (heuristiques) en temps polynomial à base des réseaux qui retrouvent le secret de celui qui signe le message dans ces trois schémas de signatures lorsque plusieurs messages sont signés sous l'hypothèse que des blocs consécutifs de bits des exposants sont connus de l'adversaire.

Résumé

Mots Clés

fonctions pseudo-aléatoires, générateurs pseudoaléatoires, signature à base de couplage, discrépance, interpolation polynomiale, attaques à base de réseaux.

Abstract

Randomness is a key ingredient in cryptography. For instance, random numbers are used to generate keys, for encryption and to produce nonces. They are generated by pseudo-random generators and pseudorandom functions whose constructions are based on problems which are assumed to be difficult. In this thesis, we study some complexity measures of the Naor-Reingold and Dodis-Yampolskiy pseudorandom functions and study the security of some pseudo-random generators (the linear congruential generator and the power generator on elliptic curves) and some pairing-based signatures based on exponentinversion framework.

We show that the Dodis-Yampolskiy pseudo-random functions is uniformly distributed and that a lowdegree or low-weight multivariate polynomial cannot interpolate the Naor-Reingold and Dodis-Yampolskiy pseudo-random functions over finite fields and over elliptic curves. The contrary would be disastrous since it would break the security of these functions and of problems on which they are based. We also show that the linear congruential generator and the power generator on elliptic curves are insecure if too many bits are output at each iteration.

Practical implementations of cryptosystems often suffer from critical information leakage through sidechannels. This can be the case when computing the exponentiation 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, Boneh-Boyen signatures and Gentry signatures) based on the exponent-inversion framework. We present latticebased polynomial-time (heuristic) algorithms that recover the signer's secret in the pairing-based signatures when used to sign several messages under the assumption that blocks of consecutive bits of the exponents are known by the attacker.

Keywords

pseudo-random functions, pseudo-random generators, pairing-based signatures, discrepancy, polynomial interpolation, lattice attacks.

Figure 2 . 1 .

 21 Figure 2.1.: Adding two points on an elliptic curve over R

  [r]P = P ⊕ • • • ⊕ P r times (and [r]P = -([-r]P ) for r ≤ 0).

Contents 3. 1 .

 1 Naor-Reingold pseudo-random function . . . . . . . . . . . . . . . . . 31 3.2. Auxiliary results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.1. Polynomial Interpolation with variable secret key . . . . . . . . . . . . . 32 3.3.2. Polynomial Interpolation with fixed secret key . . . . . . . . . . . . . . 38 3.4. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . 42 3.4.1. Polynomial Interpolation with fixed secret key . . . . . . . . . . . . . . 42 3.4.2. Polynomial Interpolation with variable secret key . . . . . . . . . . . . . 48 3.1. Naor-Reingold pseudo-random function

2s(

  -1) n-1 . Then for all a 1 ∈ T , putting a = (a 1 , b 2 , . . . , b n ), we have: 3.3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Finite Fields 35

1 .

 1 Univariate Interpolation of the Naor-Reingold Pseudo-Random Function over

  is a non-zero polynomial and we have (d + 1) 3 /2 ≥ S 2 /2 in contradiction with the definition of d. This shows that C is not singular and in particular each row of C has at least one non-zero entry and we have deg(F a ) ≥ deg X (F a ) ≥ d.Theorem 3.4.3 is non-trivial only for S 1 ≥ ( -1)/2 and we can obtain (as in Corollary 3.3.14) non-trivial lower bounds on the degree of the interpolating polynomial for specific sets A 1 and A 2 and parameter t. Lemma 3.4.4. Let m ≥ 1 be an integer, δ > 0 and t be an integer such that t ≥ (1 + δ) log( -1) + m + 1 and n

  inequality [[IK04], Bound (8.6)] (which holds for any integers m and M with 1 ≤ M ≤ m):

1 ) × 1 d 1 2

 111 With the choice k = 4, = 16, t = p 1+o(1) and d = t 255 256 + , we obtain D x (d) p -+o(1) . Remark 4.1.4. If d = t -1, with t = p + , 0 < ≤ 1 2 , then S a (d) can be estimated easily, and we have D x (d) p -+o(1) .

Lemma 5 . 1 . 1 .Lemma 5 . 1 . 2 .

 511512 Let (b 1 , . . . , b ω ) be an LLL -reduced basis of a lattice L. If a lattice element s satisfies s b i for all i ∈ {k + 1, . . . , ω}, then s lies in the space spanned by b 1 , . . . , b k . Let A = (v 1 , . . . , v ω ) be a basis of a lattice L. If b max denotes the maximal length of the Gram-Schmidt orthogonalized basis (b 1 , . . . , b ω ) of A, namely b max = max i b i . For an LLL -reduced basis B = (b 1 , . . . , b ω ) of the lattice L , it holds that:

Contents 6. 1 .

 1 Linear Congruential Generator and Power Generator on Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.2. Predicting EC-LCG Sequences for Known Composer . . . . . . . . . 78 6.3. Predicting EC-LCG Sequences for Unknown Composer . . . . . . . 90 6.3.1. Complexity of the attack . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.4. Predicting the Elliptic curve power generator . . . . . . . . . . . . . 94 -77 -

108 Chapter 7 .

 7 Lattice Attacks on Pairing-Based Signatures 7.3.0.1. First case • We can write the signatures as:

  mod p, i ∈ {0, . . . , n + 1}.Eliminating x and y and assuming again that the attacker chooses a unique message m (namely m i = m, for all i ∈ {0, . . . , n + 1}), we obtain, for a, b, i ∈ {0, . . . , n + 1} with 0 a < b < i n + 1:(r br i )σ i σ b + (r ir a )σ i σ a + (r ar b )σ a σ b = 0 mod p. (7.3)

  i,j,k z i,j z b,k + i,j,k z i,j z 0,k + b,j,k z b,j z 0,k+ N j=1 α 0,b,i,j z i,j + N j=1 β 0,b,i,j z b,j + N j=1 γ 0,b,i,j z 0,j + δ 0,b,i mod p (7.4)for b, i ∈ {1, . . . , n + 1}, b < i and with known coefficients , where α b,i,N,N = 1. The set of monomials appearing in the polynomials f 0,b,i is:M = 1, z a,j z b,k , z i,j : i ∈ {0, . . . , n + 1} a, b ∈ {0, . . . , n + 1}; a < b j, k ∈ {0, . . . , N } .We consider the following set of polynomials:P = {p m, m ∈ M 1 } ∪ {f 0,b,i : b, i ∈ {1, . . . , n + 1}; b < i} , where M 1 = M \ M 2 with M 2 = {z b,N z i,N : b, i ∈ {1, . . . , n + 1}; b < i}.One can see that for any polynomial f ∈ P, f (X 0 ) = 0 mod p. We can define an order on the set of monomials such that all the monomials in M 1 are smaller than any monomial in M 2 and for z b,N z i,N , z b ,N z i ,N ∈ M 2 , z b,N z i,N < z b ,N z i ,N if (b < b or (b = b and i < i )).

  det(L) < p ω-N (n+1)+1 , with ω = M = N 2 n(n+1) 2 + (n + 1)N + 1 and det(L) = U 2N 2 n(n+1) 2 +(n+1)N p ω-n(n+1)

  r[b = b ] -1.Here a polynomial time adversary A is simply a non-uniform probabilistic polynomial-time oracle Turing machine. The adversary is polynomial in the input length bit and with a single bit output. It is not known if cryptographically secure pseudo-random generators exist. Proving that they exist is difficult since their existence implies P = N P , which is widely believed but a famously open problem. The existence of cryptographically secure pseudorandom generators is widely believed as well and they are necessary for many applications in cryptography. It is well-known by combining the results of [BM84; JL99] that:

	Theorem 1.1.1. Cryptographically secure pseudo-random generators exist if and only if
	one-way functions exist.

  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[START_REF] Goldreich | How to Construct Random Functions (Extended Abstract)[END_REF] and Goldreich and Levin[START_REF] Goldreich | A Hard-Core Predicate for all One-Way Functions[END_REF], the following result is known:

	Theorem 1.2.1. Pseudo-random functions exist if and only if one-way functions exist.

Contents 2.1. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2. Finite fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3. Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

	2.3.1. Definition and addition law . . . . . . . . . . . . . . . . . . . . . . . . . 19
	2.3.2. Division polynomials of elliptic curves . . . . . . . . . . . . . . . . . . . 20
	2.3.3. Summation polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
	2.4

. Exponential Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

	2.4.1. Finite Fields and Exponential Sums . . . . . . . . . . . . . . . . . . . . 23
	2.4.2. Elliptic Curves and Exponential Sums . . . . . . . . . . . . . . . . . . . 25
	2.5

. Polynomial Approximation of the Discrete Logarithm . . . . . . . . 26 -17 -

  If m is a power of p then E[m] is either isomorphic to (Z/mZ) or to {O}. Accordingly, the degree of ψ 2 m (X) is m 2 -1 if p | m and strictly less than m 2 -1 otherwise. By induction one can show that θ m

	that these points occur in pairs Q = (x, y) and -Q = (x, -y), which coincide only if 2Q = O, i.e, if x is a zero of ψ 2 2 (X). We recall that the group of m-torsion points E[m], for an elliptic curve E defined over a field of characteristic p, is isomorphic to (Z/mZ) 2 if p m and to a proper subgroup of (Z/mZ) 2 if p | m.

  we have a 2 t x+t i = a 2 t x a t i 3.3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Finite Fields 39 for all x ∈ A such that 2 t x ≤ 2 n -1 and i ∈ {1, • • • , k}. The relation (3.3) thus becomes

  Let t ≥ 1 be a fixed integer and let

	3.3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Finite Fields 41
	Theorem 3.3.15.
	S with #S ∈ [ applies for univariate interpolation (i.e. k = 1).	√ + 1, (3 -2)/4]. Theorem 3.3.15 only

  Chapter 3. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Functions The matrix C is non-singular if and only if the middle matrix on the right hand is non-singular. A subset {v 0 , • • • , v d } of S 2 with this property exists if and only if the vectors T k = (x kub ) b∈S 2 for k ∈ {1, • • • , d + 1} are linearly independent. If these vectors were linearly dependent, then there would exist an integer ω with 1 ≤ ω ≤ d + 1 and coefficients d 1

  where {β 1 , . . . , β r } is an ordered basis of F p r over F p .

	54	Chapter 4. Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function

Theorem 4.1.2. For any x ∈ Z t , any integers k ≥ 2, ≥ 1 and 1 ≤ d ≤ t, we have:

  . The polynomial H(X) is a non-zero polynomial and deg(H) ≤ 4 deg(F ). Since H(X) has at least T = t -2s zeros, we have 4 deg(F ) ≥ t -2s and then deg(F ) ≥ t-2s 4 . Moreover, if deg(H) ≤ t -1, since the zeros of H are the powers of g 1 λ , then we have by Lemma 2.2.1, w(H) ≥ t/(t -(t -2s)), and since w(H) ≤ 2(w(F )) 2 , it follows that w(F ) ≥ (t/4s) 1/2 .

	Remark 4.2.2. Theorem 4.2.1 is non-trivial only when A > t/2. It remains an open
	question to obtain non-trivial lowers bounds for smaller sets A.

  Interpolation of the Dodis-Yampolskiy Pseudo-Random Function over Elliptic Curves 59

Theorem 4.3.3. Let 1 ≤ d ≤ t be a fixed integer and let A ⊆ {1, . . . , d}, A = ts. For some

Table 5 .

 5

		1.: Combinatorics constructions and their OGF
		Construction	OGF
	Atomic class	Z

  this leads to: Chapter 6. Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves Condition. If we denote by ν = χ <4t (P), and ε = χ <4t (M), the condition for Coppersmith's method is p ν > ∆ ε , ie ∆ < p

	ν ε , where:
	ν ε	∼	χ <4t (P) χ <4t (M)	∼	1 24	,
	this leads to the expecting bound:		∆ < p	1 24
	χ <4t (M) ∼	6(3t) 7 7!

  We give in the table below the cardinalities of the sets P and M for smaller t.

	7 ,
	which leads when t goes to infinity to the asymptotic bound:
	(4t) 6 6!
	Concrete bounds. t number of polynomials 0 1 number of monomials 84 1716 12376 54264 177100 2 3 4 5 84 1716 12376 54264

  this leads to: Chapter 6. Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j 0 0 . . . z

	j 2n+3
	χ <4t (P) ∼	n 4	×	(4t) 2n+5 (2n + 5)!

  Chapter 6. Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves If we denote by ν = χ <e 2 t (P), and ε = χ <e 2 t (M), the condition for Coppersmith's method is p ν > ∆ ε , ie ∆ < p

	We have which leads to: since e 2 t ∼ e 2 t -1, this leads to:	∂F ∂u ∂F ∂u (u, z) (u, z) u=1 u=1 z→1 = (1 -z) 4 , 2z ∼ 2 (1 -z) 4 ,
		χ <e 2 t (M) ∼	2(e 2 t) 3 3!
	Condition. ν ε , where:
		ν ε	∼	χ <e 2 t (P) χ <e 2 t (M)	∼	1 2e 2 ,
	this leads to the expecting bound:
				∆ < p	1 2e 2 .

Theorem 6.4.2. (more consecutive outputs) Given ∆-approximations w 0 , w 1 ,. . . ,w n

  e 2 t -1, this leads to: Chapter 6. Inferring a Linear Congruential Generator and a Power Generator on Elliptic Curves Condition. If we denote by ν = χ <e 2 t (P), and ε = χ <e 2 t (M), the condition for Coppersmith's method is p ν > ∆ ε , ie ∆ < p

				ν ε , where:
	ν ε	∼	χ <e 2 t (P) χ <e 2 t (M)	∼	n (n + 1)e 2 ,
	this leads to the expecting bound:
	∆ < p	n (n+1)e 2	→ n→∞	∆ < p	1 e 2 .
	χ <e 2 t (M) ∼	(n + 1)(e 2 t) ( n + 2) (n + 2)!

Table 7 .

 7 1.: Lattice Attack on Gentry signatures. Average running time (in seconds) of the LLL algorithm and the Gröbner basis computation. In[START_REF] Galindo | Limits of a conjecture on a leakage-resilient cryptosystem[END_REF], Galindo and Vivek analyzed the security of an ElGamal-based public-key encryption scheme (with stateful decryption) proposed by Kiltz and Pietrzak[START_REF] Kiltz | Leakage Resilient ElGamal Encryption[END_REF] which was conjectured to resists lunch-time chosen ciphertext attacks in the so-called only computation leaks model. They disprove the conjecture by proposing an algorithm to solve a new computational problem, deemed Hidden Shares -Hidden Number Problem, which is less general but has some similarities with the problem investigated in this section.

	N (n+2)+1
	(N (n + 2) + 1)!	.

Table 7 .

 7 2.: Lattice Attack on Gentry signatures. Success rates (over 250 attacks performed for each parameter pair (m, δ exp )).

	7.3. Concrete Attack Examples against Gentry signatures	107
	δ exp = 0.3225 δ exp = 0.3250 δ exp = 0.3275 δ exp = 0.3300 δ exp = 0.3325 δ exp = 0.3350	m = 2 100 98.4 90.4 66.0 10.0 0	m = 3 100 98.4 92.8 65.2 15.2 0	m = 4 100 99.2 94.4 72.8 17.2 0

Table 7 .

 7 7.5. Lattice Attack on Sakai-Kasahara Signatures 3.: Lattice Attack on Boneh-Boyen signatures. Average running time (in seconds) of the LLL algorithm and the Gröbner basis computation.

	111

Table 7 .

 7 7.5. Lattice Attack on Sakai-Kasahara Signatures 4.: Lattice Attack on Sakai-Kasahara signatures. Average running time (in seconds) of the LLL algorithm and the Gröbner basis computation. vector of fi (U z 0,1 , . . . , U z 0,N , . . . , U z n,1 , . . . , U z n,N ) for i ∈ {1, . . . , ω},. One can easily verify that the basis matrix is lower triangular. The number of variables is N (n + 1) and the success condition for the Coppersmith's method is:

	113

  L'aléatoire est un ingrédient clé en cryptographie. Par exemple, les nombres aléatoires sont utilisés pour générer des clés, pour le chiffrement et pour produire des nonces. Ces nombres sont générés par des générateurs pseudo-aléatoires et des fonctions pseudoaléatoires dont les constructions sont basées sur des problèmes qui sont supposés difficiles. Dans cette thèse, nous étudions certaines mesures de complexité des fonctions pseudo-aléatoires de Naor-Reingold et Dodis-Yampolskiy et étudions la sécurité de certains générateurs pseudo-aléatoires (le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques) et de certaines signatures à base de couplage basées sur le paradigme d'inversion.Nous montrons que la fonction pseudo-aléatoire de Dodis-Yampolskiy est uniformément distribué et qu'un polynôme multivarié de petit dégré ou de petit poids ne peut pas interpoler les fonctions pseudoaléatoires de Naor-Reingold et de Dodis-Yampolskiy définies sur un corps fini ou une courbe elliptique. Le contraire serait désastreux car un tel polynôme casserait la sécurité de ces fonctions et des problèmes sur lesquels elles sont basées. Nous montrons aussi que le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques sont prédictibles si trop de bits sont sortis à chaque itération.

More efficient candidates of pseudo-random function families are known, but the Naor-Reingold function family is among the most efficient ones with strong security guarantees under a standard computational assumption.

It is well known that the computational complexity of Gröbner basis algorithm may be exponential or even doubly exponential. In our setting, the number of variables and the total degree of the input polynomials are fixed and the theoretical complexity is polynomial in the field size (and thus in the security parameter).

We stress that it is a "formal" series, i.e., with no need to worry about the convergence.

Note that it is possible to count the exponents of both X1 and X2 at once using two parameters, but it is usually easier to count them separately, which often boils down to the same computation. See concrete examples in Section 5.3.

In complex cases, the marker u can be put to some exponent k, for instance if the parameter considered has a value equal to k for the atomic element.

In order to reach this asymptotic bound, the constructed matrix is of huge dimension and the resulting polynomial system has a very large number of variables and the computation which is theoretically polynomial-time becomes in practice prohibitive.

Acknowledgments

Preliminaries

In this Chapter, we recall two short descriptions of Coppersmith's methods that we use in the next two Chapters. These methods have been introduced in 1996 by Don Coppersmith for polynomial of one or two variables see [START_REF] Coppersmith | Finding a Small Root of a Univariate Modular Equation[END_REF][START_REF] Coppersmith | Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known[END_REF]. Because of its importance in cryptanalysis, these methods have been reformulated [START_REF] Howgrave-Graham | Finding Small Roots of Univariate Modular Equations Revisited[END_REF] and extended for multivariate polynomials [START_REF] Jochemsz | A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants[END_REF]. They have been used in cryptography to attack many schemes (see [BD00; BM03; HM10] for RSA and its variants, [HM09; BVZ12] for pseudorandom generators).

We also recall the analytic combinatorics proposed by [START_REF] Flajolet | Analytic Combinatorics[END_REF] and used by [START_REF] Benhamouda | Easing Coppersmith Methods Using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness[END_REF] to ease the Coppersmith's methods and we conclude the Chapter by presenting some useful examples that enable to understand the analytic combinatorics.

if at least a proportion of 4/5 of the most significant bits of two consecutive values U 0 and U 1 of the sequence is output. In the second case, We show that the generator is insecure if at least a proportion of 7/8 of the most significant bits of two values X(U 0 ) and X(U k ) is output, X(P ) denoting the abscissa of the point P .

Theorem 6.2.1. (two consecutive outputs) Given ∆-approximations W 0 , W 1 to two consecutive affine value U 0 , U 1 produced by the EC-LCG, and given the value of the composer G = (x G , y G ). Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 in heuristic polynomial time in log p as soon as ∆ < p 1/5 .

Proof. We suppose U 0 / ∈ {-G, G}. Then, clearing denominators in 2.1, we can translate

into the following identities in the field F p :

where U 0 = (x 0 , y 0 ), U 1 = (x 1 , y 1 ) and

Set W 0 = (α 0 , β 0 ) and W 1 = (α 1 , β 1 ). Then using the equalities x j = α j + e j and y j = β j + f j , for j = 0, 1, where |e j |, |f j | < ∆ leads to the following polynomial system:

f (e 0 , e 1 , f 0 ) = 0 mod p g(e 0 , e 1 , f 0 , f 1 ) = 0 mod p .

where

are polynomials whose coefficients A i and B i are functions of x G , and the approximations values

Description of the attack

The adversary is therefore looking for the small solutions of the following modular multivariate polynomial system:

The attack consists in applying

Coppersmith's methods for multivariate polynomials with one modulo. From now, we use the following collection of polynomials (parameterized by some integer t ∈ N):

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

The list of monomials appearing within this collection can be described as:

If we use for instance the monomial order lex (with z i < u < v) on the set of monomials, then the leading monomial of f 1 is LM (f 1 ) = u and LM (g 1 ) = v. Then the polynomials in P are linearly independent since we have prohibited the multiplication by u and v.

Bounds for the polynomials modulo p. We consider the set P as a combinatorial class, with the size function S(z

The degree of each variable z i , u, v is 1, whereas the degree of f 1 is 2 and the degree of g 1 is 1. For the sake of simplicity, we can consider 0 i 1 + i 2 , since the parameter function equals 0 for elements z j 1 1 . . . z j 4 4 f i 1 1 g i 2 1 with i 1 + i 2 = 0. We can described P as:

where the last one is for the dummy value z 0 . This leads to the generating function:

Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function

, 2 and 1 respectively in the condition of the set, we can described M as:

where the last one is for the dummy value z 0 . Which leads to the generating function:

Predicting EC-LCG Sequences for Known Composer

81

We have ∂F ∂u (u, z)

Bounds for the monomials modulo X. We consider the set M as a combinatorial class, with the size function

As z 1 , z 2 , z 3 , z 4 , u, v "count for" 1, 1, 1, 1, 2 and 1 respectively in the condition of the set, we can described M as:

where the last one is for the dummy value z 0 . Which leads to the generating function:

This leads to:

Bounds for the monomials modulo Y . We consider again the set M as a combinatorial class, with the size function

As z 1 , z 2 , z 3 , z 4 , u, v "count for" 1, 1, 1, 1, 2 and 1 respectively in the condition of the set, we can described M as:

where the last one is for the dummy value z 0 . Which leads to the generating function:

This leads to:

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

The list of monomials appearing within this collection can be described as:

Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj 0 ,...,j 2n+1 ,i 1 ,...,in,l 1 ,...,ln

We can described P as:

where the last one is for the dummy variable. This leads to the generating function:

We have

Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j 0 0 . . . z

We can described M as:

where the last one is for the dummy value y 0 . Which leads to the generating function:

Bounds for the monomials modulo X. We consider the set M as a combinatorial class, with the size function

We can described M as:

where the last one is for the dummy value y 0 . Which leads to the generating function:

This leads to:

Bounds for the monomials modulo Y . We consider the set M as a combinatorial class, with the size function

We can described M as:

where the last one is for the dummy value y 0 . Which leads to the generating function:

This leads to:

, where:

this leads to the expecting bound:

Sakai-Kasahara, Boneh-Boyen and Gentry's Pairing-Based Signatures Schemes

An identity-based encryption (IBE) scheme is a public key encryption scheme in which a user public key is its identity which may be an arbitrary string such as an email address, a phone number or any other identifier and the user private key is generated by a trusted authority called the private-key generator. In their seminal paper proposing the first IBE scheme, Boneh and Franklin [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF] mentioned an interesting transform from an IBE scheme to a signature scheme (whose observation was attributed to Naor). The transformation is as follows: the private-key generator public key and secret key correspond to the public key and secret key of the signature scheme and the user private key generation correspond to signatures generation. The well-known short signature scheme proposed by Boneh, Lynn and Shacham [BLS01; BLS04] can be seen as an application of Naor transformation to Boneh and Franklin IBE [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF]. Pairings (or bilinear maps) are powerful mathematical constructs which have been used since 2000 to design numerous complex cryptographic protocols. There are three known pairing-based approaches to design identity-based encryption schemes [START_REF] Boyen | A tapestry of identity-based encryption: practical frameworks compared[END_REF]: full-domainhash [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF], commutative-blinding [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF] and exponent-Inversion [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF][START_REF] Boneh | Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles[END_REF][START_REF] Boneh | Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups[END_REF]. In this Chapter, we focus on the latter framework which gives rise to several short signature schemes thanks to Naor transformation. We consider several pairing-based signature schemes in the exponent-inversion framework. In [START_REF] Sakai | ID based Cryptosystems with Pairing on Elliptic Curve[END_REF], Sakai and Kasahara presented the first such scheme (whose security was analyzed in the random oracle model by Zhang, Safavi-Naini and Susilo in [START_REF] Zhang | An Efficient Signature Scheme from Bilinear Pairings and Its Applications[END_REF]). Boneh and Boyen [START_REF] Boneh | Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles[END_REF] then presented the first pairing-based signature whose security can be proven in the standard security model. In 2006, Gentry [START_REF] Gentry | Practical Identity-Based Encryption Without Random Oracles[END_REF] proposed yet another scheme using the exponent-inversion paradigm, with a tighter security proof than the earlier proposals. These schemes can be described in a general simplified form as follows. Let G and G T be two cyclic groups of the same prime order p and let g be a generator of G. We suppose that (G, G T ) are equipped with an efficiently computable bilinear map e : G × G → G T . Let H : {0, 1} * → Z q be a collision-resistant hash function. Let f, g ∈ Z p [X, Y, M, R] be two polynomials of degree at most one in X and Y . The key generation picks uniformly at random two integers (x, y) ∈ Z p as the signing secret key and outputs (g x , g y ) ∈ G 2 as the public-key. To sign a message m ∈ {0, 1} * , the signer picks uniformly at random r ∈ Z p , computes σ = g f (x,y,H(m),r)/g(x,y,H(m),r) and outputs the pair (σ, r) as the signature. The validity of a signature is checked by verifying whether the following equality holds: e(σ, g g(x,y,H(m),r) = e(g f (x,y,H(m),r) , g) where the elements g f (x,y,H(m),r) and g g(x,y,H(m),r) can be computed publicly from g x , g y , m and r. The three schemes use the following specific polynomials: 1 Sakai-Kasahara scheme actually does not use the secret key y and is deterministic.

102

Chapter 7. Lattice Attacks on Pairing-Based Signatures

We present lattice-based polynomial-time algorithms that recover the signer's secret (x, y) ∈ Z 2 p in these pairing-based signatures when used to sign a constant number of messages under the assumption that blocks of consecutive bits of the corresponding exponents f (x, y, H(m), r)/g(x, y, H(m), r) mod p are known by the attacker. We consider knownmessage attacks and chosen-message attacks (i.e. where the atacker is allowed to choose the message m). The method of this paper is heuristic and uses Coppersmith's lattice technique. Let denote the bit-length of p and N denote the number of unknown blocks of each signing exponent. In a nutshell, we show that one can recover the secret key if the number of consecutive bits of each unknown block is smaller than the following theoretical values:

provided that the number of signatures is sufficiently large (see the corresponding sections in the chapter for more precise bounds). It is interesting to note, that Gentry scheme which provides the best classical security (tight security reduction in the standard security model), is the weakest against our class of attacks.

More generally, our lattice-based algorithms can be seen as methods to solve variants of the modular inversion hidden number problem which was introduced by Boneh, Halevi and Howgrave-Graham in 2001 [START_REF] Boneh | The Modular Inversion Hidden Number Problem[END_REF]. This problem is to find a hidden number given several integers and partial bits of the corresponding modular inverse integers of the sums of the known integers and that unknown integer. It was used in [START_REF] Boneh | The Modular Inversion Hidden Number Problem[END_REF] to built a pseudo-random number generator and a message authentication code scheme. In [START_REF] Ling | On the modular inversion hidden number problem[END_REF], the authors mentioned that it is interesting to study a general problem of recovering of an unknown rational function. One can see our results as a first step towards solving this problem.

The efficiency of our (heuristic) attacks has been validated experimentally.

Lattice Attack On Gentry Signatures

Gentry Signatures

Gentry introduced in [START_REF] Gentry | Practical Identity-Based Encryption Without Random Oracles[END_REF] an IBE scheme without random oracles with short public parameters and tight security reduction in the standard security model. In this paragraph, we describe the signature scheme obtained by applying Naor transformation to Gentry's IBE. The resulting scheme achieves existential unforgeability under chosen-message attacks in the standard security model. Let G and G T be two cyclic groups of the same prime order p (where p > 2 2λ for a security parameter λ) and let g be a generator of G. We suppose that (G, G T ) are equipped with an efficient computable bilinear map e : G × G → G T . Let H : {0, 1} * → Z q be a collision-resistant hash function. Gentry signature scheme is defined by the three following algorithms:

• Key generation. The user picks uniformly at random (x, y) ∈ Z 2 p , computes h 1 = g x and h 2 = g y and sets sk = (x, y) and pk = (h 1 , h 2 ) ∈ G 2 .

Chapter 8. Conclusion and Open Questions of the most significant bits of an arbitrary large number of consecutive values U i of the sequence is output. Finally, we showed that the EC-PG is insecure if a proportion of at least 1 -1/e 2 of the most significant bits of the abscissa of an arbitrary large number of consecutive values V i of the sequence is output. Our results are theoretical since in practice, the performance of Coppersmith's method in our attacks is bad because of large dimension of the constructed lattice but they are good evidences of the weaknesses of these generators. These generators should then be used with great care.

• We presented lattice-based polynomial-time algorithms that recover the signer's secret in popular pairing-based signatures (Gentry signature, Boneh-Boyen signature and Sakai-Kasahara signature) when used to sign several messages under the assumption that N blocks of consecutive bits of the corresponding exponents are known by the attacker. This partial information can be obtained in practice easily through side-channels (such as the power consumption or the electromagnetic emanations of the device generating the signature). We considered known-message attacks and chosen-message attacks. We show that one can recover the secret key if the number of consecutive bits of each unknown block is smaller than the following values: provided that the number of signatures is sufficiently large. The efficiency of our (heuristic) attacks has been validated experimentally.

Open questions

Many open questions still remain:

• For the Naor-Reingold pseudo-random functions: the first question which is natural is Question 8.1. Can we generalize our bounds to smaller interpolating sets? • For lattice attacks on pairings-based schemes: In order to prevent the leakage of partial information on the exponent, it is customary to use a probabilistic algorithm to encode the sensitive values such that the cryptographic operations only occur on randomized 8.2. Open questions