I recently started learning zero-knowledge proofs. I found that in many zero-knowledge arguments, the verifier is required to randomly select a challenge $r\in\mathbb{Z}_q$ and send it to the prover. Afterwards, the prover calculates the form $x_1=x_0+rx$ and sends it back to the verifier.

I noticed that the length of $x_1$ is extended. For example, if $x$ is a 4-bit number and q is a 160-bit prime number, $x_1$ will also become a 160-bit number. Is it possible to limit the value range of challenge r to reduce the length of $x_1$? For example, if the range of $r$ is limited to [1,1024], the length of $x_1$ is approximately 14 bits. In my scenario, the verifier should not learn anything secret about the prover, but the prover's occasional forged proofs can be tolerated. Although the prover has a 1/1024 probability of guessing the value of $r$ and thus falsifying the proof, which is acceptable.

  • $\begingroup$ The question could benefit from some clarifications. For starters, you wouldn't want $x$ to be 4 bits. That will negate your requirement for it to remain secret. In protocols, all these values are taken in $\mathbb Z_q$ and therefore are all the same size and limited to typically 32 bytes value. What is your use case? Why is this moo much in terms of data size? $\endgroup$ Commented Feb 12 at 12:34
  • $\begingroup$ Otherwise, yeah, the challenge space doesn't need to be $\mathbb Z_q$. It only needs to be large enough to prevent forgeries with the desired probability. I don't see a reason for the challenge to be chosen with another probability than uniform random. In the worst case, security degrades and forgeries are easy. $\endgroup$ Commented Feb 12 at 12:42
  • $\begingroup$ Thanks for your reply. I present the scenario to you. Consider a zero-knowledge inner product argument protocol, see Bulletproof. Now I have two high-dimensional vectors $u$ and $v$, each of which is an 8-bit number (this is common in quantized machine learning). The prover needs to prove to the verifier that $u v^{\top}=c$.@MarcIlunga $\endgroup$
    – Wing Sky
    Commented Feb 12 at 15:07
  • $\begingroup$ First, the prover commits to $u$ and $v$ via the vector Pedersen protocol, which hides the elements of $u,v$ perfectly. Afterwards, the prover needs to generate blind vectors $u^\prime$ and $v^\prime$ based on challenge $c\in\mathbb{Z}_q$ and send them to the verifier. When $q$ is a 160-bit prime number, $u^\prime,v^\prime$ are both 100 times larger than $u,v$ which brings high communication overhead. If the scope of the challenge $c$ can be limited, the communication overhead of the proof can be reduced.@MarcIlunga $\endgroup$
    – Wing Sky
    Commented Feb 12 at 15:10
  • $\begingroup$ Thanks for providing context. The question currently read as a Schnorr type protocol. But for an IPA protocol, I think you can reduce the challenge space but by not too much to keep forgeries low… So this will be a risk management question. Obviously, unless there are better protocols out there besides the vanilla Bulletproof protocol achieving the bandwidth characteristics that you want. But to explore further on this idea, if this protocol can be non-interactive there's maybe a way to only pay the increase in size only once. $\endgroup$ Commented Feb 12 at 15:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.