# Schnorr NIZK over Ed25519

I am trying to implement the following Schnorr non-interactive zero-knowledge protocol: https://www.rfc-editor.org/rfc/rfc8235#page-7

I'm using the libsodium 1.0.16 and GNU MP libraries.

I just can't seem to get it working. Here are some questions:

In the setup of the scheme, Alice publishes her public key
A = G x [a], where a is the private key chosen uniformly at random
from [1, n-1].

The protocol works in three passes:

1.  Alice chooses a number v uniformly at random from [1, n-1] and
computes V = G x [v].  She sends V to Bob.

2.  Bob chooses a challenge c uniformly at random from [0, 2^t-1],
where t is the bit length of the challenge (say, t = 80).  Bob
sends c to Alice.

3.  Alice computes r = v - a * c mod n and sends it to Bob.

At the end of the protocol, Bob performs the following checks.  If
any check fails, the verification is unsuccessful.

1.  To verify A is a valid point on the curve and A x [h] is not the
point at infinity;

2.  To verify V = G x [r] + A x [c].

Regarding step (3) on the computation of r = v - a * c mod n it means that this step is using regular modular arithmetic?

Regarding step (2) on the verification V = G x [r] + A x [c], can you please explain how that would hold? Is the following equivalent: V = ed25519_scalarmult(r, ED25519-BASE) + ed25519_scalarmult(c, A) where ed25519_scalarmult(scalar, point i.e. publickey)? And most importantly that + is Ed25519 point addition?

• This looks very interactive not NIZK Nov 15, 2019 at 15:42
• It is "non-interactive" because there are only 3 steps or so, instead of at least n interactive steps for a 2^n security level. Nov 16, 2019 at 16:33
• If it's Alice, Bob, Alice and then Bob verifies I call this interactive. Nov 16, 2019 at 16:35
• You can make this non-interactive by using the Fiat-Shamir heuristic. You replace step 2 by c = Hash(X || A || G). This step can be computed by Alice and the whole scheme is now non-interactive. Feb 10, 2020 at 16:30
• @stojanman Yes. For reference, that is what Substrate (parity.io/substrate) uses for most of its signatures. The exception is the block validation protocol, which still uses Ed25519. Feb 12, 2020 at 21:09

Regarding step (3) on the computation of r = v - a * c mod n it means that this step is using regular modular arithmetic?

Yes.

Is the following equivalent: V = ed25519_scalarmult(r, ED25519-BASE) + ed25519_scalarmult(c, A) [...]?

Yes, see also section 1.2 (near the end) where it says "P x [b]: multiplication of a point P with a scalar b over E(Fp)".

And most importantly that + is Ed25519 point addition?

Yes, that is indeed the case, + represents the group operation here, which is modular-reduced multiplication for the finite field and point-addition for the EC case. This can be seen when looking at section 2.2.

V = G x [r] + A x [c], can you please explain how that would hold?

I'll use a slightly more tense notation ($$\xleftarrow{\\\}$$ means that the variable on the left is sampled uniformly at random from the set on the right).

1. Pick and publish your public key $$A=[a]G$$ with $$a\xleftarrow{\\\}\{1,...,n-1\}$$
2. Pick $$v\xleftarrow{\\\}\{1,...,n-1\}$$, send $$V=[v]G$$.
3. Pick $$c\xleftarrow{\\\}\{1,..,2^t-1\}$$, for some security parameter $$t$$, send $$c$$
4. Compute $$r=v-a\cdot c\bmod n$$ and send $$r$$.

Now the question is why $$V=[r]G+[c]A$$ holds in an honest protocol execution. Well $$[c]A+[r]G=[c\cdot a]G+[v-a\cdot c]G=[c\cdot a+v-a\cdot c]G=[v]G=V$$

• I have another question. n is I'm assuming the order of the curve? Therefore for 25519 that would be 2^252 + 27742317777372353535851937790883648493? Mar 16, 2018 at 21:00
• @stojanman yes. Mar 16, 2018 at 21:01
• Thank you so much! I still haven't gotten it to work, but I think the fault is somewhere in the bit order of the libraries. Mar 16, 2018 at 21:28
• P.S. This is how long it took to get it working. Main fault was in libsodium, in that it clamps the scalars according to some awkward rule. I will submit a PR on libsodium that does not do this. Mar 17, 2018 at 14:52