Image for post
Image for post
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 following rules:

Image for post
Image for post

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:

Image for post
Image for post

and thus:

Image for post
Image for post

In pairing this then becomes:

Image for post
Image for post

and which becomes:

Image for post
Image for post

Peggy will then provide xG and Victor will check the pairings multiplied equals unity. If 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:

package mainimport (	"fmt"
"github.com/miracl/core/go/core"
"github.com/miracl/core/go/core/BN254"
"math/rand"
"time"
"os"
"strconv"
)
func Abs(x int) int {
if x < 0 {
return -x
}
return x
}
func FP12toByte(F *BN254.FP12) []byte {
const MFS int = int(BN254.MODBYTES)
var t [12 * MFS]byte
F.ToBytes(t[:])
return(t[:])
}
func randval() *core.RAND { s1 := rand.NewSource(time.Now().UnixNano())
r1 := rand.New(s1)
rng := core.NewRAND()
var raw [100]byte
for i := 0; i < 100; i++ {
raw[i] = byte(r1.Intn(255))
}
rng.Seed(100, raw[:])
return rng
}
func main() { x:=7
a:=-1
b:=-42
argCount := len(os.Args[1:]) if (argCount>0) {x,_= strconv.Atoi(os.Args[1])}
if (argCount>1) {a,_= strconv.Atoi(os.Args[2])}
if (argCount>2) {b,_= strconv.Atoi(os.Args[3])}
G1:= BN254.ECP_generator()
G2:= BN254.ECP2_generator()

xG1:=G1
xG2:=G2

xGa:=G2
xGb:=G2
// Equ: x^2 + ax + b = 0 if (x < 0) {
xG1 = BN254.G1mul(G1,BN254.NewBIGint(Abs(x))); xG1.Neg()
xG2 = BN254.G2mul(G2,BN254.NewBIGint(Abs(x))); xG2.Neg()
} else {
xG1 = BN254.G1mul(G1,BN254.NewBIGint(x))
xG2 = BN254.G2mul(G2,BN254.NewBIGint(x));
}
if (a < 0) {
xGa = BN254.G2mul(G2,BN254.NewBIGint(Abs(a))); xGa.Neg()
} else {
xGa = BN254.G2mul(G2,BN254.NewBIGint(a))
}
if (b<0) {
xGb = BN254.G2mul(G2,BN254.NewBIGint(Abs(b))); xGb.Neg()
} else {
xGb = BN254.G2mul(G2,BN254.NewBIGint(b))
}
if (b < 0 && a < 0) {
fmt.Printf("\nEqn: x^2 - %d x - %d\n",Abs(a),Abs(b))
} else if (b < 0) {
fmt.Printf("\nEqn: x^2 + %d x + %d\n",a,Abs(b))
} else if (a < 0) {
fmt.Printf("\nEqn: x^2 + %d x + %d\n",Abs(a),b)
} else {
fmt.Printf("\nEqn: x^2 + %d x + %d\n",a,b)
}
fmt.Printf("\nxG1: %s\n",xG1.ToString())
fmt.Printf("\nxG2: %s\n",xG2.ToString())
fmt.Printf("\nxGa: %s\n",xGa.ToString())
fmt.Printf("\nxGb: %s\n",xGb.ToString())
pair1:=BN254.Ate(xG2,xG1); pair1=BN254.Fexp(pair1)
pair2:=BN254.Ate(xGa,xG1); pair2=BN254.Fexp(pair2)
pair3:=BN254.Ate(xGb,G1); pair3=BN254.Fexp(pair3)
fmt.Printf("\nPair 1 - first 20 bytes:\t0x%x\n",FP12toByte(pair1)[:20])
fmt.Printf("\nPair 2 - first 20 bytes:\t0x%x\n",FP12toByte(pair2)[:20])
fmt.Printf("\nPair 3 - first 20 bytes:\t0x%x\n",FP12toByte(pair3)[:20])
pair1.Mul(pair2)
pair1.Mul(pair3)
fmt.Printf("\nPair Result - first 20 bytes:\t0x%x\n",FP12toByte(pair1)[:20])
if (pair1.Isunity()){ fmt.Printf("\n\nYou have proven you know the value of x") } else {
fmt.Printf("\n\nYou have NOT proven you know the value of x")
}
}

A sample run is [here]:

x =  -6
Eqn: x^2 - 1 x - 42
xG1: (047551bec1e6c80724663110982520fe8c88db44a4d42397ac219a1098d2763b,22936568b0f9da59025efcca3cbf0d40621e23ebd942985af7d213dcb427a922)xG2: ([1ce69dc8742f5bb8a732dfe653515a23347fabdb638b00576008db7cb187f95a,01f33ef07a1fc794b14791741384fc9d0fcbe6abfa3570a374a8fb17d23657ed],[0b07db18cf5c53ba0897aedd52a96c638f466da17188b24ae0faf8011a0ff385,21bb29f6350e41819f2f1f959bde4decefed111f37767b5530cc898cf65f2adc])xGa: ([061a10bb519eb62feb8d8c7e8c61edb6a4648bbb4898bf0d91ee4224c803fb2b,0516aaf9ba737833310aa78c5982aa5b1f4d746bae3784b70d8c34c1e7d54cf3],[230acce1d4506cbe1fa36ce996737de53763f5194241f6568d0f1f876e32d479,16683973c374eadb2ac709290a0c72d0b090f90028c636bc1cd2e51394c53178])xGb: ([02347e5c2f0802a05e43267fe89de3dedc77d64556b495610913e6a767db7871,079078e9427f50798e62c1f804562a9326760f5d94f0a4206dd149d3f037d680],[0d250f7544ee22bc914c8d902b0a18c8a8613543217c01a07a3e73b380ddf93f,0c7cdecc7b14c33886d39fd4275f079c6a2d1639dc582262f231eece38b1987b])Pair 1 - first 20 bytes: 0x006ce88251e092379d2d84308b8f76e908bf546e
Pair 2 - first 20 bytes: 0x05fb152b7cb6575543a9ac09ba4d8843da54f954
Pair 3 - first 20 bytes: 0x0b938a5c00b8130a459d660e1587afa15132a566
Pair Result - first 20 bytes: 0x0000000000000000000000000000000000000000You have proven you know the value of x

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

x =  5
Eqn: x^2 - 1 x - 42
xG1: (23edc69a751b579a14bc178029c6a6776a17fab345de03331bd905985b94daf0,215f727b315191c38806742b359c1aa7ebc35f65f5632eb8e9e6602f8890706b)xG2: ([0b1d84f4d56634326a9c59f8161dd78be24b56b48a728012afea461f9191d674,21c158326bd5f7b921e22d5a528740d1fa40d4ad5924ab1d11c56a9f0a80b0c4],[0070bea4ee500dced8932db3b13554cdb986169e1a1180575562c32a6697afc4,20164c93784ca3c6b1db4fde1f24b8063a7a26b61ab465944ddffa3ce9cba6e5])xGa: ([061a10bb519eb62feb8d8c7e8c61edb6a4648bbb4898bf0d91ee4224c803fb2b,0516aaf9ba737833310aa78c5982aa5b1f4d746bae3784b70d8c34c1e7d54cf3],[230acce1d4506cbe1fa36ce996737de53763f5194241f6568d0f1f876e32d479,16683973c374eadb2ac709290a0c72d0b090f90028c636bc1cd2e51394c53178])xGb: ([02347e5c2f0802a05e43267fe89de3dedc77d64556b495610913e6a767db7871,079078e9427f50798e62c1f804562a9326760f5d94f0a4206dd149d3f037d680],[0d250f7544ee22bc914c8d902b0a18c8a8613543217c01a07a3e73b380ddf93f,0c7cdecc7b14c33886d39fd4275f079c6a2d1639dc582262f231eece38b1987b])Pair 1 - first 20 bytes: 0x0992fbe1be5fa730dd57a1cb271d0b509d3bca98
Pair 2 - first 20 bytes: 0x2379e3f2a5512f8968af20800c70526b3a59897f
Pair 3 - first 20 bytes: 0x0b938a5c00b8130a459d660e1587afa15132a566
Pair Result - first 20 bytes: 0x0e7399bb64062eeab29b61a0067d9fd651f170b4You have NOT proven you know the value of x

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!

Written by

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