International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 13 February 2016

Geoffroy Couteau, Thomas Peters, David Pointcheval
ePrint Report ePrint Report
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 of proving that a committed integer lies in a public interval. By the way, it can also 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 Damgård-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. Thereafter, we show that this commitment scheme over the integers is compatible with a commitment scheme modulo a prime p, which allows for more efficient proofs of relations between the committed values, still under the RSA assumption. Our second contribution is thus a more efficient and more secure interactive technique to prove Diophantine relations. We illustrate it with the most efficient range proofs. In addition, the security is proven under the sole RSA assumption.
Expand

Additional news items may be found on the IACR news page.