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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\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.

Improve this answer
$\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
    May 30 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$
    – Sacha Servan-Schreiber
    May 31 at 9:47

Your Answer

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

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