The Magic of Schnorr and Fiat-Shamir … Meet NI-ZKPs

The Magic of Schnorr and Fiat-Shamir … Meet NI-ZKPs

With Zero-Knowledge Proofs (ZKPs), I can prove I have knowledge of my data, without revealing it. This might relate to my password, my face biometrics, or even any digital data that I want to keep secret. So, let’s take an example of doing with the Schnorr methods and which implement a Fiat-Shamir approach. Our approach will be for Bob to register a secret (such as a password), and then create his own proof whenever required (such as logging into a system). Alice will then prove that he knows the secret, without Bob ever revealing it to her. As Bob generates his own proof, we define this as a Non-Interactive ZKP (NI-ZKP).

For the demo, I will use the Kryptology library for this and prove the knowledge of a text string. The demo is here:

https://asecuritysite.com/kryptology/ecc_zkp?b0=Testing%20123&a0=K256

Registering the secret

If we have a secret X, Bob first takes a hash of this:

X=Hash(x)

Bob then computes a statement (Y) of:

Y=X.G

and where G is the base point on the curve. This statement value can be registered with Alice, and Bob can now prove it with (C,S).

Creating the proof

To create a proof, Bob generates a random value (k) and generates a random point:

R=k.G

Next Bob generates a value of C by taking a hash of the following byte values:

C=H(X||G||Y||R)

S=k+x.G

Bob now passes the statement (Y), C and S to Alice as a proof of the knowledge of x.

Verifying

First Alice computes:

G_S=S.G

and next:

X_C=Y×(−C)

and then recovers R from:

R=G_S+X_C

Alice now can compute:

C′=H(X||G||Y||R)

and which check this against the C. If they are the same, the proof has been verified. This works because:

R=G_S+X_C=S.G+Y×(−C)=(k+x.C).G−k.G.C=k.G

Coding

The outline code is [here]:

For the P256 curve and a message of “Test 123” we get [here]:

Message to prove: Test 123
Curve: P-256

Proof Statement: 038e1abb750975191287dcf7df8d9026cf78ea49763c50d395fe57bc168d973df9
Proof C: cecc95d5efaabeb9f10d924f14696551ba2d53b10c39764cc2bcdc777f903869
Proof S: 5bb571b6e55242b4a5110d164d8785c3677be6b48c2006c50c8317a367acbb8b
ZKP has been proven

Note that the Proof statement is an elliptic curve point in a compressed format. We with we compress the point, by only storing the x-axis value, and whether the y-axis point is odd or even. A compressed point that starts with a “03” is an odd value or “02” for an even value. For a compressed point, we do not need to store the y-axis point, as we can derive this from the x-axis point. A “04” identifies an uncompressed point for sepc256k1 and P256. The values of C and S are scalar values.

Conclusions

So, just to recap. Bob has a secret (x) and registers a statement (Y). Whenever required, Bob then creates his own proof for it and sends C and S to Alice. Alice uses Y, C and S, and proves that Bob still knows x. Magic!