1
$\begingroup$

I am reading What are elliptic curve pairings? by Marek Leip, specifically the section called Linear Relations.

There, it says that:

  • Prover has some numbers $(x_1, x_2, ...)$ and uses $c$ to calculate $c_1x_1 + c_2x_2$ which is the number prover shares with verifiers, among $\varphi(x_1), \varphi(x_2)$.
  • Verifier clearly already knows $c_1$ and $c_2$, as he must be able to calculate: $c_1\varphi(x_1) + c_2\varphi(x_2)$.

In the end of that section, it says that this is what's used in ECDSA signature verification.

In ECSDA, Alice(signer of the message) calculates the following:

$s = k^{-1}(z + R_xd)$ where $R_x = kG$ and $d$ is a private key. z is related to the message itself.

I am trying to see what $x_1, x_2, c_1, c_2$ are here in Alice/Bob for ECDSA - I want to mimic it to the explanation that I shared as a link, but with no luck. Because $x_1, x_2$ has to be numbers whereas $\varphi(x_1), \varphi(x_2)$ are points. $x_1$ is clearly $d$, but what's $d$ and $c_1, c_2$ ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

In Zellic’s setup, the prover holds secret numbers $x_1, x_2, \dots$ and shares a linear combination $c = c_1 x_1 + c_2 x_2 + \dots$ plus images $\varphi(x_1), \varphi(x_2), \dots$ under a homomorphism $\varphi$ (e.g., $\varphi(t) = t G$, scalar-multiplying base point $G$). The verifier, knowing $c_1, c_2$, checks $\varphi(c) = c_1 \varphi(x_1) + c_2 \varphi(x_2) + \dots$.

ECDSA uses this via the linearity of elliptic curve scalar multiplication ($\varphi: \mathbb{Z}_n \to \langle G \rangle$, $\varphi(t) = t G$):

  • Hidden numbers (prover/signer Alice’s secrets): $x_1 = d$ (private key), $x_2 = k$ (ephemeral nonce).
  • Their images (points verifier Bob can use): $\varphi(x_1) = Q = d G$ (public key, fully known), $\varphi(x_2) = R = k G$ (nonce point; only $r = x(R) \mod n$ shared, not full $R$).
  • Public coefficients (known to verifier from signature $(r, s)$): $c_1 = -r$, $c_2 = s$.
  • Shared “combined number” $c$: $z$ (message hash mod $n$).

The signing equation $s \equiv k^{-1}(z + r d) \pmod{n}$ rearranges to the linear relation: $(-r) d + s k \equiv z \pmod{n}$.

Apply $\varphi$: $(-r) Q + s R = z G$.

Verifier checks indirectly (without full $R$): Compute $R' = s^{-1} (z G + r Q)$, verify $x(R') \mod n = r$ (implies $R' = R$, confirming the relation). This proves the secrets satisfy the equation via the homomorphism, without revealing them—directly adapting Zellic’s concept to ECDSA’s $x$-coordinate encoding.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.