Proving You Know The Answer, Without Revealing It, Using Crypto Pairs and Kryptology
Proving You Know The Answer, Without Revealing It, Using Crypto Pairs and Kryptology
It is the dream of many teachers to mark a student’s work, without actually revealing the answer. Why? Because the minute the student writes the answer, it can be revealed to their other classmates, and thus be copied. So can we prove proof of a correct answer, without revealing it? Well, we can with zk-Snarks, and which uses pairing-based cryptography to perform its magic. In this case, I will keep things simple, and show how we can prove things without revealing the knowledge that we have — a Zero Knowledge Proof (ZKP).
Pairing-based cryptography
Before we start, let’s look at the magic that is pairing-based cryptography. With pair-based cryptography we have two cyclic groups (G1 and G2), and which are of an order of a prime number (n). A pairing on (G1,G2,GT) defines the function e:G1×G2→GT, and where g1 is a generator for G1 and g2 is a generator for G2. If U is a point on G1, and V is a point on G2, we have the following rules:
Proving something
In this case, we will use pairing crypto to prove that we know the value of x which solves x²+ax+b=0. For example, if we have x²−x−42=0 has the solution of x=7 and x=−6 as (x−7)(x+6)=0.
First, we two groups (G1 and G2). Crypto pairs can then be used to prove that Peggy still knows a secret. Now Peggy has to pass something to Victor to prove that she knows the solution, without giving away the value.
For this, we have a point on an elliptic curve of G, and use the pairing property of:
when k=0 (and will not be one for any other value of k). So we can have:
In pairing this then becomes:
and which becomes:
Peggy will then provide xG and Victor will check the pairings multiplied equals unity. In real-life x will be a large value, and it will not be possible to determine x from xG.
Implementation
The outline coding using the library from the Krytology library is [here]:
A sample run is [here]:
a=-1
b=-42
Solution: x=7
Eqn: x^2 - 1 x - 42
You have proven it!
If we try an incorrect value, such as x=5, we get a not proven result:
a=-1
b=-42
Solution: x=5
Eqn: x^2 - 1 x - 42
You have NOT proven it!
Conclusions
And there you go … just crypto magic!
If you are interested inthe Coinbase Kryptology library, there are more examples here:
https://asecuritysite.com/kryptology
and more pairing-based cryptography here: