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).