Encrypted Searches Using Crypto Pairing, Rust and MIRACL

Encrypted Searches Using Crypto Pairing, Rust and MIRACL

We give away too much information. Let’s say I have to search to see if a given post code is on a database, but I want to keep the search and search term secret. In this case we will implement the following [paper]:

With crypto pairing we have two elliptic curves: G1 and G2, and then map onto a third curve: Gt. The pairing of the points on G1 (P) and G2 (Q) is defined as a pairing function, and where we determine e (Q,P). For the points of P and Q, this has special mappings of:

e (sQ,rP)=e (rQ,sP)=e (rsQ,P)=e (Q,rsP)=e (sQ,P)r=e (Q,P)rs

and:

e (R+Q,P)=e (R,P)×e (Q,P)

First we have two curves (G1 and G2) and initially we define a large prime number (q). First Alice — who wants to perform the search — selects a point on the G2 curve (P), and generates a using a random number (s):

sk=s

Alice then creates public key with:

Ps=sP

Next Bob creates a random value (r) and creates:

Pr=rP

Bob then hashes the word to search (m) to the G2 curve:

QW=H1(m)

Bob takes Alice’s public key (Ps) and his private key (r) and creates the pairing of:

e (QW,Ps)^r

If Alice wants to search for W2, she matches to:

e (Tw,Pr)

and where Tw=sH1(W2))

This works because:

e (Tw,Pr)=e (sH1(W2),rP)=e (rH1(W2),sP)=e (QW,sP)r=e (QW,Ps)^r

Coding

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

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 sha2::{Sha256, Sha512,Digest};

use rand::Rng;
use std::env;

fn get_random() ->RAND_impl{
  let random_bytes = rand::thread_rng().gen::<[u8; 32]>();
  let mut rng = RAND_impl::new();

rng.seed(32, &random_bytes);
  rng
}

fn main() {

let mut rng = get_random();

println!("Encrypted search using bn254 Pairings");

let P = ecp::ECP::generator();
  
    let max = big::BIG::new_ints(&rom::CURVE_ORDER);
    let r = big::BIG::randomnum(&max, &mut rng);
    let s = big::BIG::randomnum(&max, &mut rng);

let A_public = pair::g1mul( &P, &s);
    let rP=  pair::g1mul(&P, &r);

let mut message="password";
    let mut tofind="password";

let args: Vec<String> = env::args().collect();
  
    if args.len() >1 { message = args[1].as_str();}
    if args.len() >2 { tofind = args[2].as_str();}

println!("r={}",r.to_string());
    println!("s={}",s.to_string());
    println!("\nA_public (on G1)= {}",A_public);
    println!("Search public (rP) (on G2)= {}",rP);
    println!("\nMessasge= {}",message);
    println!("\nWord to find= {}",tofind);

let mut hasher = Sha256::new(); hasher.update(message.as_bytes());
    let result = hasher.finalize();

let mut Qw=ecp2::ECP2::mapit(result.as_slice());
 
    let mut p1 = pair::ate(&Qw, &A_public);
    p1 = pair::fexp(&p1);
    p1=p1.pow(&r);

println!("--- Now let's search for it ---");

let mut hasher = Sha256::new(); hasher.update(tofind.as_bytes());
    let result = hasher.finalize();

Qw=ecp2::ECP2::mapit(result.as_slice());

let sQw=pair::g2mul(&Qw, &s);

let mut p2 = pair::ate(&sQw, &rP);
   p2 = pair::fexp(&p2);
 
  
  if (p1.equals(&p2)) { println!("Found it");}
  else { println!("Not Found");}

}

A sample run is [here]:

Encrypted search using bn254 Pairings
r=07B1E91F0FA4A1401F255FFEC386DD0FAB13B86955A38494A9E62C2665351182
s=1B0BE6A42EBB67FF5827B995914D344EC7A6B344BBBC61DEC0D47600B3587171

A_public (on G1)= (0FA55551E12EF58F6F12FEEDF9C2F12645CFF6B3AE4B839D3448BD83DFCB64E4,20C7DF6FCF73D00AF71CF94BD203BC6CF43A8F0B1439B7F9EA9713D8F3582E23)
Search public (rP) (on G2)= (0D5FF73D7F1713843C6649594CAD8091AA265C2CEEB1BA18E770039F4E022FF5,0E960F2ACA203ECCB2EF3E6DFF6B562D5F2DEBC9EA4FC29AA2D6C370BF7DBDD8)

Messasge= hello

Word to find= hello
--- Now let's search for it ---
Found it

and a false search:

Encrypted search using bn254 Pairings
r=1A6E5292FA89777EA9F1548930B0009944898CA4DDB177E916E3BE5BC954C3E3
s=189F4B2FC764CD0CAEB50FB625165BB121430BD1FC21ED3826C8EC39FC8C9D60

A_public (on G1)= (00D52F76FD3FDA13B0CC3AEC01F0AE534FD8523D7C268BC6285FBEB2192BC6C8,224E883078BEC41CAB8423DF1C12E6B9DA795E48A44BCD343DA00BC752FC267A)
Search public (rP) (on G2)= (1D6EFC11E7C5D1F32C9B4020EF316E9942B0A1031A2870A107B63971B8E1D09A,0D2F61EC6323EB45C0518031EF99B1554FACEBE6AC5B551C6F08C51A9FA4E546)

Messasge= hello

Word to find= hello123
--- Now let's search for it ---
Not Found

Go try it for yourself:

https://asecuritysite.com/rust/rust_miracl02

and here is the running code: