Proving I Know Alice, Bob, Carol and Dave

We release too much of our information to others. Every time we enter our password into a system, we are revealing it for others to see…
Photo by Austin Distel on Unsplash

Proving I Know Alice, Bob, Carol and Dave

We release too much of our information to others. Every time we enter our password into a system, we are revealing it for others to see. So, why can’t we just prove some knowledge of our secrets, in order that we know our secret? Well, this is the objective of Zero-Knowledge Proofs (ZKPs). With Interactive ZKPs, Alice sends a challenge to Bob, and Bob produces a ZKP for the secret. In a Non-interactive ZKP, Bob produces his own challenge, and also the ZKP. Alice then regenerates the challenge and checks the proof.

So, let’s see if Bob can prove that he knows the first names of the first four cybersecurity characters: Alice, Bob, Carol and Dave. Whenever required, he will be able to produce proof that he knows them to Alice.

For this, we will use the Schnorr proof. Initially, Bob has a secret value of x (and which could be his private key), and sends Alice the value of:

X=x.G

and which could be his public key. If we have secret messages of: m_1, m_2, m_3 and m_4. He then hashes each of these messages:

M_1=Hash(m_1)

M_2=Hash(m_2)

M_3=Hash(m_3)

M_4=Hash(m_4)

Then he produces a challenge of:

C=H(M_1||M_2||M_3||M_4 || x.G)

and where H() is a hash function, and “||” is a concatenation of the bytes. Bob then creates a random value of k to produce:

R=k.G

and where G is a base point on a curve. Next, he creates:

S=k+x.C

Bob now passes the statements R and S to Alice as a proof.

Verifying

First Alice computes:

GS=S.G

and next:

XC=Y×(−C)

and then recovers R from:

R=G_S+X_C

Alice will know the hashes of the messages and can now compute:

C′=H(M1||M2||M3||M4||x.G)

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

The outline code is [here]:

A sample run is [here]:

Message 1: Bob
Message 2: Alice
Message 3: Carol2
Message 4: Dave
Proof Statement: 021c621a546eb13c08ea1a8eb25957d41e646ee7baee63b37146ffab2c7b55491f
Proof R: 30c2b588c9867ccea8da9a7706d3de77812b4ac1bed3d77dcbef6a3339332b00
Proof S: ff1742e8199b69e1438623306606c12050e25faf4f489ffdd870b5c4bb21599f
ZKP has been proven
== Now trying the wrong message ==
ZKP has NOT been proven with incorrect message (good)

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.