Removing the Strong RSA Assumption from Arguments over the Integers

Geoffroy Couteau 1, 2 Thomas Peters 3 David Pointcheval 2, 1
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
3 Groupe Crypto
ICTEAM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
Abstract : Committing integers and proving relations between them is an essential ingredient in many cryptographic protocols. Among them, range proofs have shown to be fundamental. They consist in proving that a committed integer lies in a public interval, which can be seen as a particular case of the more general Diophantine relations: for the committed vector of integers x, there exists a vector of integers w such that P (x,w) = 0, where P is a polynomial. In this paper, we revisit the security strength of the statistically hiding commitment scheme over the integers due to Damgard-Fujisaki, and the zero-knowledge proofs of knowledge of openings. Our first main contribution shows how to remove the Strong RSA assumption and replace it by the standard RSA assumption in the security proofs. This improvement naturally extends to generalized commitments and more complex proofs without modifying the original protocols. As a second contribution, we design an interactive technique turning commitment scheme over the integers into commitment scheme modulo a prime p. Still under the RSA assumption, this results in more efficient proofs of relations between committed values. Our methods thus improve upon existing proof systems for Diophantine relations both in terms of performance and security. We illustrate that with more efficient range proofs under the sole RSA assumption.
Type de document :
Communication dans un congrès
EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2017, Paris, France. Advances in Cryptology – EUROCRYPT 2017, 〈10.1007/978-3-319-56614-6_11〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01471901
Contributeur : David Pointcheval <>
Soumis le : lundi 20 février 2017 - 13:08:27
Dernière modification le : mardi 17 avril 2018 - 11:26:46

Identifiants

Collections

Citation

Geoffroy Couteau, Thomas Peters, David Pointcheval. Removing the Strong RSA Assumption from Arguments over the Integers. EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2017, Paris, France. Advances in Cryptology – EUROCRYPT 2017, 〈10.1007/978-3-319-56614-6_11〉. 〈hal-01471901〉

Partager

Métriques

Consultations de la notice

296