Pseudo-Random Generators and Pseudo-Random Functions: Cryptanalysis and Complexity Measures
Générateurs et fonctions pseudo-aléatoires: cryptanalyse et mesures de complexité
Résumé
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.
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...