A Non-interactive Range Proof with Constant Communication

In a range proof, the prover convinces the verifier in zero-knowledge that he has encrypted or committed to a value a ∈ [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 (14080 bits) and verifier's computation (81 pairings), short combined CRS length and communication (log1/2+o(1) H group elements), or very efficient prover's computation (Θ(log H) exponentiations).


Editor(s):
Keromytis, Angelos D.
Published in:
Financial Cryptography and Data Security, 7397, 179-199
Presented at:
Financial Cryptography and Data Security 2012, Bonaire, February 27–March 2, 2012
Year:
2012
Publisher:
Berlin, Heidelberg, Springer Berlin Heidelberg
ISBN:
978-3-642-32945-6
Keywords:
Laboratories:




 Record created 2013-06-30, last modified 2018-09-13

n/a:
Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)