Photo by Antoine Dautry on Unsplash

How Do I Prove I Know The Answer to x²-x-42, Without Giving You The Answer?

We give away too much of our data. Why should we give away our password every single time that we log into a system? Why can’t we just prove that we still know it? Thus Victor (the verifier) can prompt Peggy (the prover) with a puzzle, and where she can show that she can solve it. This is the method that zero-knowledge proof (ZKP) uses to prove things. In this case, we will use the method used by zk-SNARKs to prove that we still know a secret. This method is used in blockchain methods to anonymise transactions.

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:GG2→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:

In this case, we will use pairing crypto to prove that we know the value of x which solves +ax+b=0. For example, if we have x−42=0 has the solution of x=7 and x=−6 as (x−7)(x+6)=0.

First, we have two elliptic curves (G1 and G2). Crypto pairs can then be used to prove that Peggy still knows a secret. For this, we may have a quadratic equation of:

x²−x−42=0

Then, we will ask Peggy to prove that she knows the value of x. In this case, the solution is x=7 or x=−6. 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:

and thus:

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.

The outline coding using the library from the MIRACL library [here] is:

A sample run is [here]:

If we try an incorrect value, such as x=5, we get a not proven result:

Now we can prove or not prove these:

  • x=-3, x²−2x−15. Success. Try!
  • x=5, x²−2x−15. Success. Try!
  • x=4, x²−2x−15. Failure. Try!
  • x=-15, x²+5x−150. Success. Try!
  • x=10, x²+5x−150. Success. Try!
  • x=-8, x²+5x−15 . Failure. Try!

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store