Helger Lipmaa's publications

A Non-Interactive Range Proof with Constant Communication

Rafik Chaabouni, Helger Lipmaa and Bingsheng Zhang. A Non-Interactive Range Proof with Constant Communication. In Angelos Keromytis, editor, FC 2012, volume 7397 of Lecture Notes in Computer Science, pages 179--199, Bonaire, The Netherlands, February 27--March 2, 2012. Springer, Heidelberg.

File: [.pdf (526 KB)] pdf recommended.


In a range proof, the prover convinces the verifier in zero-knowledge that he has encrypted or committed to a value $a \in [0, H]$ where $H$ is a public constant. Most of the previous non-interactive range proofs have been proven secure in the random oracle model. We show that one of the few previous non-interactive range proofs in the common reference string (CRS) model, proposed by Yuen et al.~in COCOON 2009, is insecure. We then construct a secure non-interactive range proof that works in the CRS model. The new range proof can have (by different instantiations of the parameters) either very short communication ($14\,080$ bits) and verifier's computation ($81$ pairings), short combined CRS length and communication ($\log^{1 / 2 + o (1)} H$ group elements), or very efficient prover's computation ($\Theta (\log H)$ exponentiations)..

Keywords: NIZK, pairings, progression-free sets, range proof.


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.