In this thesis, we present constructions of leakage-resilient cryptographic primitives, and we give black-box impossibility results for certain classes of constructions of pseudo-random number generators. The traditional approach for preventing side-channel attacks has been primarily hardware-based. Recently, there has been significant progress in developing algorithmic approaches for preventing such attacks. These algorithmic approaches involve modeling side-channel attacks as {\em leakage} on the internal state of a device; constructions secure against such leakage are {\em leakage-resilient}. We first consider the problem of storing a key and computing on it repeatedly in a leakage-resilient manner. For this purpose, we define a new primitive called a {\em key proxy}. Using a fully-homomorphic public-key encryption scheme, we construct a leakage-resilient key proxy. We work in the ``only computation leaks'' leakage model, tolerating a logarithmic number of bits of polynomial-time computable leakage per computation and an unbounded total amount of leakage. We next consider the problem of verifying that a message sent over a public channel has not been modified, in a setting where the sender and the receiver have previously shared a key, and where the adversary controls the public channel and is simultaneously mounting side-channel attacks on both parties. Using only the assumption that pseudo-random generators exist, we construct a leakage-resilient shared-private-key authenticated session protocol. This construction tolerates a logarithmic number of bits of polynomial-time computable leakage per computation, and an unbounded total amount of leakage. This leakage occurs on the entire state, input, and randomness of the party performing the computation. Finally, we consider the problem of constructing a large-stretch pseudo-random generator given a one-way permutation or given a smaller-stretch pseudo-random generator. The standard approach for doing this involves repeatedly composing the given object with itself. We provide evidence that this approach is necessary. Specifically, we consider three classes of constructions of pseudo-random generators from pseudo-random generators of smaller stretch or from one-way permutations, and for each class, we give a black-box impossibility result that demonstrates a contrast between the stretch that can be achieved by adaptive and non-adaptive black-box constructions.

In this thesis, we present constructions of leakage-resilient cryptographic primitives, and we give black-box impossibility results for certain classes of constructions of pseudo-random number generators. The traditional approach for preventing side-channel attacks has been primarily hardware-based. Recently, there has been significant progress in developing algorithmic approaches for preventing such attacks. These algorithmic approaches involve modeling side-channel attacks as {\em leakage} on the internal state of a device; constructions secure against such leakage are {\em leakage-resilient}. We first consider the problem of storing a key and computing on it repeatedly in a leakage-resilient manner. For this purpose, we define a new primitive called a {\em key proxy}. Using a fully-homomorphic public-key encryption scheme, we construct a leakage-resilient key proxy. We work in the ``only computation leaks'' leakage model, tolerating a logarithmic number of bits of polynomial-time computable leakage per computation and an unbounded total amount of leakage. We next consider the problem of verifying that a message sent over a public channel has not been modified, in a setting where the sender and the receiver have previously shared a key, and where the adversary controls the public channel and is simultaneously mounting side-channel attacks on both parties. Using only the assumption that pseudo-random generators exist, we construct a leakage-resilient shared-private-key authenticated session protocol. This construction tolerates a logarithmic number of bits of polynomial-time computable leakage per computation, and an unbounded total amount of leakage. This leakage occurs on the entire state, input, and randomness of the party performing the computation. Finally, we consider the problem of constructing a large-stretch pseudo-random generator given a one-way permutation or given a smaller-stretch pseudo-random generator. The standard approach for doing this involves repeatedly composing the given object with itself. We provide evidence that this approach is necessary. Specifically, we consider three classes of constructions of pseudo-random generators from pseudo-random generators of smaller stretch or from one-way permutations, and for each class, we give a black-box impossibility result that demonstrates a contrast between the stretch that can be achieved by adaptive and non-adaptive black-box constructions.

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. / 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 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.