Proving You Know Answer to a Quadratic Equation, Without Giving The Answer … using Rust, Crypto…

As a teacher you mark your student’s work, but where they give away the answer each time. So can we find a method to prove that a student…

Proving You Know Answer to a Quadratic Equation, Without Giving The Answer … using Rust, Crypto Pairing and MIRACL

As a teacher you mark your student’s work, but where they give away the answer each time. So can we find a method to prove that a student has finished their coursework, without them telling you the answer. So let’s say we have Peggy the student and Victor the teacher. Victor sets Peggy a problem:

“Prove to me that you know the value of x for x²+5x-150=0, but don’t tell me the answer!”

Peggy scratches her head. She knows that x²+5x-150=0 is (x-15)(x+10)=0, and can solve this for x=15 or x=-10. But she cannot tell Victor the answer. Well, she needs to create a proof of correctness.

Here is the proof for x=10, x²+5x-150=0:

https://asecuritysite.com/rust/rust_miracl03?x=10&a=5&b=-150

How do we do it? Well, crypto pairing for zero-knowledge proofs supports this.

Zero-knowledge Proofs

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 verify) 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. In this we use the pairing property (e()) of:

e(aU,bV) = e(U,abV) = e(U,V)^{ab} = e(bU,aV)

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²+5x−150=0

Then, we will ask Peggy to prove that she knows the value of x. In this case, the solution is x=15 or x=−10. 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 where e() is the pairing function):

e(G,G)^k=1

and thus:

e(G,G)^{x²+5x−150}=1

In pairing this then becomes:

e(G,G)^{x2^} (G,G)^{5x} e(G,G)^{−150}=1

and which becomes:

e(xG,xG) e(xG,5G) e(G,−150G)=1

Peggy will then provide xG and Victor will check the pairings multiplied together 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 MIRACL library is [here]:

extern crate rand_core;

use mcore::bn254::big;
use mcore::bn254::ecp;
use mcore::bn254::ecp2;
use mcore::bn254::fp2;
use mcore::bn254::pair;
use mcore::bn254::rom;
use mcore::rand::{RAND,RAND_impl};



use std::env;


fn main() {
    



    println!("Zero knowledge proof using bn254 Pairings");


    let G1 = ecp::ECP::generator();
    let G2 = ecp2::ECP2::generator();


    let args: Vec<String> = env::args().collect();
  

      let mut x:isize=7;
      let mut a:isize=-1;
      let mut b:isize=-42;

      if args.len() >1 { x = args[1].parse().unwrap();}
      if args.len() >2 { a = args[2].parse().unwrap();}
      if args.len() >3 { b = args[3].parse().unwrap();}

      println!("Solution proposed: {}",x);
    
      // Equ: x^2 + ax + b = 0
      let mut xbig=mcore::bn254::big::BIG::new_int(isize::abs(x));
      let mut xG1 = pair::g1mul(&G1,&xbig);
      let mut xG2 = pair::g2mul(&G2,&xbig);
      if (x < 0) { 

        xG1.neg();
       
        xG2.neg()
      } 
      let mut abig=mcore::bn254::big::BIG::new_int(isize::abs(a));
      let mut xGa = pair::g2mul(&G2,&abig);

      if (a < 0) { xGa.neg();}

      let mut bbig=mcore::bn254::big::BIG::new_int(isize::abs(b));
      let mut xGb = pair::g2mul(&G2,&bbig);
      // let xGa = BN254.G2mul(G2,BN254.NewBIGint(Abs(a))); 
      if (b < 0) { xGb.neg();}

    
      if (b < 0 && a < 0) { 
        println!("\nEqn: x^2 - {} x - {}\n",isize::abs(a),isize::abs(b)) ;
      } else if (b < 0) { 
        println!("\nEqn: x^2 + {} x + {}\n",a,isize::abs(b)); 
      } else if (a < 0) { 
        println!("\nEqn: x^2 + {} x + {}\n",isize::abs(a),b) ;
      } else {
        println!("\nEqn: x^2 + {} x + {}\n",a,b) ;
      }
 
      println!("\nxG1: {}\n",xG1.to_string()) ;
      println!("\nxG2: {}\n",xG2.to_string()) ;
      println!("\nxGa: {}\n",xGa.to_string()) ;
      println!("\nxGb: {}\n",xGb.to_string()) ;
    
      let mut p1 = pair::ate(&xG2, &xG1); p1 = pair::fexp(&p1);
      let mut p2 = pair::ate(&xGa, &xG1); p2 = pair::fexp(&p2);
      let mut p3 = pair::ate(&xGb, &G1); p3 = pair::fexp(&p3);

      p1.mul(&p2);
      p1.mul(&p3);

      if (p1.isunity()) {println!("You have proven it"); }
      else { println!("You have not proven" );}


}

A sample run for x²-x-42=0, with x=7 as the solution is [here]:

Zero knowledge proof using bn254 Pairings
Solution proposed: 7

Eqn: x^2 - 1 x - 42


xG1: (03264DCCFF0E7C8DE83D9BAA1BC15615E93C3D8E13755F21D45CFC62911993B0,0B4DDF7264812FFDE94BD4359C7DC035AADE884795E828D71B5CBF3C1054BA2E)

xG2: ([08CA1AC367CF4DC0A1B75066FA911AA896956BA89246C5F3C25094FC0F0D7AB2,1ED25C11E74CEAD06A7BAA51FC41F0E6085B4CB26F5735416F12237953C792A2],[19E12AF084B06ED6DBDED38695D6DBA7AA05F62250835346B9574309B35DCFEA,1CAE33085867FE051412632C8CC4229B3FB65E617FE975C07D2482688F4AE826])

xGa: ([061A10BB519EB62FEB8D8C7E8C61EDB6A4648BBB4898BF0D91EE4224C803FB2B,0516AAF9BA737833310AA78C5982AA5B1F4D746BAE3784B70D8C34C1E7D54CF3],[230ACCE1D4506CBE1FA36CE996737DE53763F5194241F6568D0F1F876E32D479,16683973C374EADB2AC709290A0C72D0B090F90028C636BC1CD2E51394C53178])

xGb: ([02347E5C2F0802A05E43267FE89DE3DEDC77D64556B495610913E6A767DB7871,079078E9427F50798E62C1F804562A9326760F5D94F0A4206DD149D3F037D680],[0D250F7544EE22BC914C8D902B0A18C8A8613543217C01A07A3E73B380DDF93F,0C7CDECC7B14C33886D39FD4275F079C6A2D1639DC582262F231EECE38B1987B])

You have proven it

If we try an incorrect value, such as x=6, we get a not proven result [here]:

Zero knowledge proof using bn254 Pairings
Solution proposed: 6

Eqn: x^2 - 1 x - 42


xG1: (047551BEC1E6C80724663110982520FE8C88DB44A4D42397AC219A1098D2763B,028FFF198F0625A8B7D550B5C340F2C7FF02DC1426BD67B8AF2DEC234BD856F1)

xG2: ([1CE69DC8742F5BB8A732DFE653515A23347FABDB638B00576008DB7CB187F95A,01F33EF07A1FC794B14791741384FC9D0FCBE6ABFA3570A374A8FB17D23657ED],[1A1B896970A3AC47B19C9EA2AD5693A4D1DA925E8E774DC8C60507FEE5F00C8E,03683A8C0AF1BE801B052DEA6421B21B7133EEE0C88984BE7633767309A0D537])

xGa: ([061A10BB519EB62FEB8D8C7E8C61EDB6A4648BBB4898BF0D91EE4224C803FB2B,0516AAF9BA737833310AA78C5982AA5B1F4D746BAE3784B70D8C34C1E7D54CF3],[230ACCE1D4506CBE1FA36CE996737DE53763F5194241F6568D0F1F876E32D479,16683973C374EADB2AC709290A0C72D0B090F90028C636BC1CD2E51394C53178])

xGb: ([02347E5C2F0802A05E43267FE89DE3DEDC77D64556B495610913E6A767DB7871,079078E9427F50798E62C1F804562A9326760F5D94F0A4206DD149D3F037D680],[0D250F7544EE22BC914C8D902B0A18C8A8613543217C01A07A3E73B380DDF93F,0C7CDECC7B14C33886D39FD4275F079C6A2D1639DC582262F231EECE38B1987B])

You have not proven it

Conclusions

We have many things in life where we have to prove things, but we perhaps give away too much of our data, so crypto pairing comes to our rescue. The method we have shown is useful in zero-knowledge proof applications, and is part of zkSnarks.

Here is the final solution:

https://asecuritysite.com/rust/rust_miracl03

and the Repl.it code: