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

Prof Bill Buchanan OBE

Dec 18, 2020·5 min read

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.

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:

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 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.

Coding

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 - 42xG1: (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:	0x0b938a5c00b8130a459d660e1587afa15132a566Pair 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 - 42xG1: (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:	0x0b938a5c00b8130a459d660e1587afa15132a566Pair 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!