I want to know whether there is any additively homomorphic schemes that can make a non-interactive range proof.

For example, I have a pair of public and private key pairs $(K_p,K_v)$ that satisfying a additively homomorphic schemes $E$, and I want to prove that the plaintext of $C=E_{K_p}(m)$ belongs to $[a,b]$, where $m, a$ and $b$ are both positive numbers. Is there any additively homomorphic schemes and non-interactive range proof scheme that I can use to prove the plaintext inside $C$ belongs to $[a,b]$.


Yes, you can use Paillier encryption as the homomorphic encryption scheme, and prove the encrypted plaintext falls within a range.

An interactive protocol can be found in Appendix A of this paper: Fast Secure Two-Party ECDSA Signing, by Yehuda Lindell, Crypto 2017.

A non-interactive protocol can be found in this paper: Non-interactive Zero-Knowledge Arguments for Voting, by Jens Groth, ACNS 2005.

|improve this answer|||||
  • $\begingroup$ Thank you, sir. But I notice that this scheme is a interactive range proof scheme. Do you know any scheme that is non-interactive or do you have any ideas to transfer this scheme to non-interactive? $\endgroup$ – Felix LL Jun 20 '18 at 11:39
  • $\begingroup$ @FelixLL see the modified answer. $\endgroup$ – Changyu Dong Jun 20 '18 at 13:02
  • $\begingroup$ Thank you, sir. I am not familiar with this paper. I think the range proof scheme of the second paper is for homomorphic commitment scheme instead of homomorphic encryption scheme by a quick look. I will read this paper in detail, or try to transfer the scheme of the first paper to non-interactive by Fiat–Shamir heuristic. I hope it works. Thank you again. $\endgroup$ – Felix LL Jun 21 '18 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.