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).
ChaabouniLZ12.pdf
openaccess
439.42 KB
Adobe PDF
7ca76db4c6d1c741366ef961a7a53f72