Score:1

Is there a ZKP that proves knowledge of a particular elliptic curve point?

bv flag

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.

Score:0
sb flag

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.

Joe Rowell avatar
bv flag
Hi: thanks for the answer! I was actually thinking of a situation where `V` is not known directly but instead hidden behind some commitment.
Sacha Servan-Schreiber avatar
sb flag
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](https://link.springer.com/content/pdf/10.1007/3-540-68339-9_17.pdf).
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.