A party A gives me a commitment of a message $m$ and want to convince B that is $|m|=L$. The proof myst be:

  • Non-interactive (a prover can convince me by sending me one message)
  • Succint (constant or sublinear size in the length of m)

I was looking into the NIZK space but I could not think of any solution.

Note: I have a candidate which however, it really is an overkill:

Create a SNARK proof that proves the witness: $m$ such that length is $L$ and hash is $H(m)$, where $H$ is a cryptographic hash function and $H(m)$ is public knowledge (so verifier knows)

  • $\begingroup$ Your question is not well defined. Is the message encrypted, is it committed? How? $\endgroup$ – Yehuda Lindell Apr 25 '17 at 12:03
  • $\begingroup$ @YehudaLindell I just updated the question $\endgroup$ – graphtheory92 Apr 26 '17 at 22:04

If the commitment is additively homomorphic then there are methods of doing this. They relate more to the numeric range, but these are essentially equivalent. First, it is possible to use the proofs of non-negativity of Helga Lipmaa in On Diophantine Complexity and Statistical Zero-Knowledge Arguments. These prove maximum by using the additive homomorphic property to subtract the minimum value, and then have the prover prove that the result is non-negative. Simpler solutions (some a bit weaker) appear in Efficient Proofs that a Committed Number Lies in an Interval. I don't remember if these can be made non-interactive using Fiat-Shamir, but I think that they can (and they are enough for you to start doing your own research into it).


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.