1
$\begingroup$

Let E be an elliptic curve of prime order n. If we assume that Alice and Bob both know a scalar value z, is there a known zero-knowledge protocol (ideally a Sigma protocol) that allows Bob to convince Alice that he knows some point R such that zR satisfies some equation?

The context of this is as follows. I've recently been looking at ZKAttest, which allows a prover to display knowledge of an authentic ECDSA signature without revealing the identity of the signer to the verifier. In this work, the majority of the heavy lifting is done by proving a scalar multiplication of a given point i.e. that some commitment opens to zR. In this case, z is hidden via commitment, and R is revealed to the verifier. However, I'm interested in the other case, where we reveal z but hide R.

$\endgroup$

2 Answers 2

1
$\begingroup$

If I understand your question, you want a sigma protocol for a prover to convince a verifier that for some curve point $V$ and scalar $z$ (known to both the prover and the verifier), the prover knows an $R$ such that $V=zR$. Because $V$ and $z$ are known to the verifier, $R$ can be directly recomputed as $(z^{-1})V = R$, which defeats the purpose of a zero-knowledge protocol. In other words, this is a language in P rather than a language in NP, therefore the verifier can efficiently verify the statement itself without needing an NP witness.

$\endgroup$
2
  • $\begingroup$ Hi: thanks for the answer! I was actually thinking of a situation where V is not known directly but instead hidden behind some commitment. $\endgroup$
    – Joe Rowell
    Commented May 30, 2023 at 11:56
  • $\begingroup$ Ah, I see. In that case a generic solution could be to have some cryptographic hash function H and commit to V as H(V). A generic ZKP could be used to prove that H(zR) = H(V) but that would likely be inefficient. I'm not sure, but given that you are no longer working "in the exponent" of the group, there is some loss in the nice algebraic properties that make ZKP over groups efficient. One pointer would be to maybe use ideas from "double discrete log" proofs; see Section 3.3 of Publicly Verifiable Secret Sharing. $\endgroup$ Commented May 31, 2023 at 9:47
1
$\begingroup$

Okay, this is a good question, and it helps illustrate what the actual point of a ZKP is. You want to prove that you possess a witness that is hard to compute for a given instance.

So our instance in this case would be a commitment $C$ to the coordinates of a point $V$, and a public scalar $z$.

The witness might be the opening of the commitment $V$, (and the randomness used for the commitment $r$), and the point $R$ such that $V = zR$.

On the other hand, a ZKP for proving knowledge of an opening of the commitment $C$ would have a witness $V$ and the randomness $r$. So the only difference was that the witness in the first case also had a point $R$.

But given a witness for the second problem, one can easily compute a witness for the first problem. Since knowing $V$, you can compute $R = z^{-1}V$.

What this means is that a proof of opening is sufficient to proving the first relation (since you can efficiently compute a witness for the first, given one for the second). However, for this reason, I'm not sure proving this kind of relation would be very meaningful.

$\endgroup$

Your Answer

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

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