JCJC SIMI 2 - JCJC - SIMI 2 - Science informatique et applications

RandOmness in MAthemaTIcal Cryptography – ROMAnTIC

ROMAnTIC

Randomness in Mathematical Cryptography

General objective

The goal of the research project ROMAnTIC (for RandOmness in MathemaTIcal Cryptography) is to get a better understanding of the interplay between randomness and cryptography and to study the security of various cryptographic protocols at different levels (information-theoretic and computational security, number-theoretic assumptions, design <br />and provable security of new and existing constructions).

- Reductionnist security
- Cryptanalysis (statistical, lattice-based)
- Coding Theory

- Constructions and Analysis of Pseudorandom Number Generators with Inputs
- Study of Number-Theoretic Pseudorandom Number Generators
- Analysis of Cryptographic Algorithms with Weak (pseudo)Randomness
- Randomness complexity of multi-party computation and side-channel attacks countermeasures

- Study of Foundations of Pseudorandom Numbers Generation.
- Exploring the Use of PCP in Group-Oriented Cryptographic Protocols
- Randomness/Efficiency Tradeoffs

International conferences (TCC 2013, CCS 2013, COCOON 2013, Crypto 2014, CHES 2014, CHES 2015)
Vulgarisation journal (VMWare Technical Journal – Winter 2013)

Over the past three decades, cryptography has evolved considerably and today everyone is likely to be either a direct user or be affected by its use. Randomness is a key ingredient for cryptography. Random bits are necessary not only for generating keys, but are also often part of steps of cryptographic algorithms. Cryptographers usually assume that parties have access to perfect randomness but in practice this assumption is often violated and a large body of research is concerned with obtaining such a sequence of (pseudo)random bits.

The goal of the research project ROMAnTIC (for RandOmness in MathemaTIcal Cryptography) is to get a better understanding of the interplay between randomness and cryptography and to study the security of various cryptographic protocols at different levels (information-theoretic and computational security, number-theoretic assumptions, design and provable security of new and existing constructions).

The cryptography literature usually pays no attention to the fact that in practice randomness is quite difficult to generate and that it should be considered as a resource like space and time. Moreover since the abstraction of perfect uniform randomness is not physically realizable, it is interesting to determine whether imperfect randomness is “good enough” for certain cryptographic algorithms and to design algorithms that are robust with respect to deviations of the random sources from true uniform randomness.

There exist cryptographic tasks that we only know how to perform efficiently using randomness but conversely it is sometimes possible to remove randomness from probabilistic algorithms to obtain efficient deterministic counterparts. Since these constructions may hinder the security of cryptographic schemes, it is of high interest to study the efficiency/security tradeoff provided by randomness in cryptography.

Quite often in practice, the random bits in cryptographic protocols are generated by a pseudorandom number generation process. When this is done, the security of the scheme depends in a crucial way on the quality of the random bits produced by the generator. It is well-known that pseudorandom generators exist if and only if one-way functions exist and there exist reasonably efficient constructions based on various number-theoretic assumptions. Unfortunately, these are often still not efficient enough for real-world use, and many real-world protocols rely on “ad-hoc” constructions. It is therefore interesting to propose more efficient secure constructions, to analyse the security of existing ones and of specific cryptographic constructions that use weak pseudorandom number generators.

The project ROMAnTIC aims to undertake research in these three aspects. The approach adopted will be both theoretical and practical, since we will provide security results in mathematical frameworks (information theoretic or computational) with the aim to design protocols among the most efficient known. The project will notably involve discrete mathematical structures to model information security problems and number-theoretic cryptanalysis and mathematical analysis of cryptographic constructions.

Project coordinator

Monsieur Damien Vergnaud (Département d'Informatique de l'Ecole Normale Supérieure) – damien.vergnaud@ens.fr

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

DI-ENS Département d'Informatique de l'Ecole Normale Supérieure

Help of the ANR 215,268 euros
Beginning and duration of the scientific project: October 2012 - 48 Months

Useful links