ROMAnTIC
RandOmness in MAthemaTIcal Cryptography
ANR (2012-2015)
Research project funded by the french Agence Nationale de la Recherche (2012-2016) in the Young Researchers program (JCJC - Jeunes Chercheuses et Jeunes Chercheurs).
Partner
- École normale supérieure / DI-ENS
- Help of the ANR 215,268 euros
- Beginning and duration of the scientific project: October 2012 - 48 Months
- Project coordinator: Damien Vergnaud
Project Members
Permanent Members
- Aurélie Bauer
- Duong Hieu Phan
- Damien Vergnaud
- David Xiao
Non-Permanent Members
- Sonia Belaid
- Angelo De Caro
- Jérémy Chotard
- Houda Ferradi
- Alain Passelègue
- Thierry Mefenza
Associated Members
- Céline Chevalier
- David Pointcheval
- Emmanuel Prouff
- Sylvain Ruhault
- Adrian Thillard
Project Summary
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. Modern cryptography intersects the disciplines of mathematics, computer science, and engineering.
Randomness is a key ingredient for cryptography. Random bits are necessary not only for generating cryptographic keys, but are also often an part of steps of cryptographic algorithms. In some cases, probabilistic protocols make it possible to perform tasks that are impossible deterministically. In other cases, probabilistic algorithms are faster, more space efficient or simpler than known deterministic algorithms. Cryptographers usually assumes 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 random or pseudorandom bits.
The research project ROMAnTIC (for RandOmness in MathemaTIcal Cryptography) goal 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). It is a basic research project that brings together academic researchers in the theory of cryptography with an expert from the french national IT systems security agency.
Cryptographic 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 perfect randomness abstraction 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 randomness.
The power of randomness in computation is a central problem in complexity theory and in cryptography. Cryptographers should definitely take these considerations into account when proposing new cryptographic schemes: there exist computational 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 of course depends in a crucial way on the quality of the random bits produced by the generator. Despite the importance, many protocols used in practice often leave unspecified what pseudorandom number generation to use. It is well-known that pseudorandom generators exist if and only if one-way functions exist and there exist efficient constructions based on various number-theoretic assumptions. Unfortunately, these constructions are too inefficient and many protocols used in practice rely on "ad-hoc" constructions. It is therefore interesting to propose more efficient constructions, to analyze 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 a 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.
Publications
2017
-
Polynomial interpolation of the Naor-Reingold pseudo-random function
Appl. Algebra Eng. Commun. Comput. 28, 3, pp. 237–255 (2017).
open access doi -
Full Disk Encryption: Bridging Theory and Practice
In Topics in Cryptology - CT-RSA 2017 - The Cryptographers’ Track at the RSA Conference 2017, San Francisco, CA, USA, February 14-17, 2017, Proceedings (Helena Handschuh, ed), Springer, Lecture Notes in Computer Science, vol. 10159, pp. 241–257 (2017).
open access doi
2016
-
Comment on "A strong provably secure IBE scheme without bilinear map" by M. Zheng, Y. Xiang and H. Zhou [J. Comput. Syst. Sci. 81 (2015) 125-131]
J. Comput. Syst. Sci. 82, 5, pp. 756–757 (2016).
open access doi -
Privately Outsourcing Exponentiation to a Single Server: Cryptanalysis and Optimal Constructions
In Computer Security - ESORICS 2016 - 21st European Symposium on Research in Computer Security, Heraklion, Greece, September 26-30, 2016, Proceedings, Part I (Ioannis G. Askoxylakis, Sotiris Ioannidis, Sokratis K. Katsikas, and Catherine A. Meadows, eds), Springer, Lecture Notes in Computer Science, vol. 9878, pp. 261–278 (2016).
open access doi -
Randomness Complexity of Private Circuits for Multiplication
In Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II (Marc Fischlin, and Jean-Sébastien Coron, eds), Springer, Lecture Notes in Computer Science, vol. 9666, pp. 616–648 (2016).
open access doi -
Easing Coppersmith Methods Using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness
In Public-Key Cryptography - PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II (Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang, eds), Springer, Lecture Notes in Computer Science, vol. 9615, pp. 36–66 (2016).
open access doi -
Lattice Attacks Against Elliptic-Curve Signatures with Blinded Scalar Multiplication
In Selected Areas in Cryptography - SAC 2016 - 23rd International Conference, St. John’s, NL, Canada, August 10-12, 2016, Revised Selected Papers (Roberto Avanzi, and Howard M. Heys, eds), Springer, Lecture Notes in Computer Science, vol. 10532, pp. 120–139 (2017).
open access doi -
Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function
In Arithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Ghent, Belgium, July 13-15, 2016, Revised Selected Papers (Sylvain Duquesne, and Svetla Petkova-Nikova, eds), Lecture Notes in Computer Science, vol. 10064, pp. 125–140 (2016).
open access doi -
Inferring Sequences Produced by a Linear Congruential Generator on Elliptic Curves Using Coppersmith’s Methods
In Computing and Combinatorics - 22nd International Conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings (Thang N. Dinh, and My T. Thai, eds), Springer, Lecture Notes in Computer Science, vol. 9797, pp. 293–304 (2016).
doi
2015
-
Robust Pseudo-Random Number Generators with Input Secure Against Side-Channel Attacks
In Applied Cryptography and Network Security - 13th International Conference, ACNS 2015, New York, NY, USA, June 2-5, 2015, Revised Selected Papers (Tal Malkin, Vladimir Kolesnikov, Allison Bishop Lewko, and Michalis Polychronakis, eds), Springer, Lecture Notes in Computer Science, vol. 9092, pp. 635–654 (2015).
open access doi -
Practical Key Recovery for Discrete-Logarithm Based Authentication Schemes from Random Nonce Bits
In Cryptographic Hardware and Embedded Systems - CHES 2015 - 17th International Workshop, Saint-Malo, France, September 13-16, 2015, Proceedings (Tim Güneysu, and Helena Handschuh, eds), Springer, Lecture Notes in Computer Science, vol. 9293, pp. 287–306 (2015).
open access doi
2014
-
Side-Channel Attack against RSA Key Generation Algorithms
In Cryptographic Hardware and Embedded Systems - CHES 2014 - 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings (Lejla Batina, and Matthew Robshaw, eds), Springer, Lecture Notes in Computer Science, vol. 8731, pp. 223–241 (2014).
doi -
Hardness of k-LWE and Applications in Traitor Tracing
In Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I (Juan A. Garay, and Rosario Gennaro, eds), Springer, Lecture Notes in Computer Science, vol. 8616, pp. 315–334 (2014).
doi
2013
-
Languages with Efficient Zero-Knowledge PCPs are in SZK
In Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings (Amit Sahai, ed), Springer, Lecture Notes in Computer Science, vol. 7785, pp. 297–314 (2013).
doi -
Security analysis of pseudo-random number generators with input: /dev/random is not robust
In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013 (Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, eds), ACM, pp. 647–658 (2013).
open access doi -
Time/Memory/Data Tradeoffs for Variants of the RSA Problem
In Computing and Combinatorics, 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings (Ding-Zhu Du, and Guochuan Zhang, eds), Springer, Lecture Notes in Computer Science, vol. 7936, pp. 651–662 (2013).
open access doi