3
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ This looks very interactive not NIZK $\endgroup$
    – Meir Maor
    Nov 15, 2019 at 15:42
  • $\begingroup$ 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. $\endgroup$
    – stojanman
    Nov 16, 2019 at 16:33
  • $\begingroup$ If it's Alice, Bob, Alice and then Bob verifies I call this interactive. $\endgroup$
    – Meir Maor
    Nov 16, 2019 at 16:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alex Pinto
    Feb 10, 2020 at 16:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – Alex Pinto
    Feb 12, 2020 at 21:09

1 Answer 1

2
$\begingroup$

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$$

$\endgroup$
4
  • $\begingroup$ I have another question. n is I'm assuming the order of the curve? Therefore for 25519 that would be 2^252 + 27742317777372353535851937790883648493? $\endgroup$
    – stojanman
    Mar 16, 2018 at 21:00
  • $\begingroup$ @stojanman yes. $\endgroup$
    – SEJPM
    Mar 16, 2018 at 21:01
  • $\begingroup$ 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. $\endgroup$
    – stojanman
    Mar 16, 2018 at 21:28
  • $\begingroup$ 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. $\endgroup$
    – stojanman
    Mar 17, 2018 at 14:52

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.