\(\hat{e}(aU,bV) = \hat{e}(U,V)^{ab} = \hat{e}(abU, V) = \hat{e}(U, abV ) = \hat{e}(bU,aV)\)
In this case we will encrypt a string, and then use crypto pairing to search for it. It uses the MIRACL library.
Encrypted search using crypto pairing with MIRACL in Rust
[MIRACL Home][Home]
With pairing-based cryptography we have two cyclic groups (\(G_1\) and \(G_2\)), and which are of an order of a prime number (\(n\)). A pairing on \((G_1,G_2,G_T)\) defines the function \(e:G_1 \times G_2 \rightarrow G_T\), and where \(g_1\) is a generator for \(G_1\) and \(g_2\) is a generator for \(G_2\). If \(U\) is a point on \(G_1\), and \(V\) is a point on \(G_2\), we have following rules:
\(\hat{e}(aU,bV) = \hat{e}(U,V)^{ab} = \hat{e}(abU, V) = \hat{e}(U, abV ) = \hat{e}(bU,aV)\) In this case we will encrypt a string, and then use crypto pairing to search for it. It uses the MIRACL library. |
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 \(\hat{e}(Q,P)\). For the points of \(P\) and \(Q\), this has special mappings of:
\( \hat{e}(sQ,rP) = \hat{e}(rQ,sP) = \hat{e}(rsQ,P) = \hat{e}(Q,rsP) = \hat{e}(sQ,P)^r = \hat{e}(Q,P)^{rs} \)
and:
\( \hat{e}(R+Q,P) = \hat{e}(R,P) \times \hat{e}(Q,P) \)
First we have two curves (\(G_1\) and \(G_2\)) and initially we define a large prime number (\(q\)). First Alice - who wants to search - selects a point on the \(G_2\) curve (\(P\)), and generates a using a random number (\(s\)):
\(sk=s\)
Alice then creates public key with:
\(P_{s}=sP\)
Next Bob creates a random value (\(r\)) and creates:
\(P_{r}=rP\)
Bob then hashes the word to search (\(m\)) to the G2 curve:
\(Q_W=H_1(m)\)
Bob takes Alice's public key (\(P_s\)) and his private key (\(r\)) and creates the pairing of:
\(\hat{e}{(Q_W,P_{s})}^r\)
If Alice wants to search for \(W_2\), she matches to:
\(\hat{e}(T_w,P_r)\)
and where \(T_w=s H_1(W_2))\)
This works because:
\( \hat{e}(T_w,P_r) = \hat{e}(s H_1(W_2),rP) = \hat{e}(r H_1(W_2),sP) = \hat{e}(Q_W,sP)^r = \hat{e}(Q_W,P_s)^r \)
The Rust code 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,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");} }
And a sample run:
Encrypted search using bn254 Pairings r=171AE2624C3CA1AD3F394E9EC6D1CC03F29085836125A40E50D7256EEF9D54B1 s=18278AAF23B7020AFC5B9F2E95F7326A1A2BA80C93D42840220E5B9EFDBF3F9B A_public (on G1)= (0266B0EE5A5F48400950139B8E97C8A5EDEE704DD7DEE5EDF7D4CE9C1E59915D,15E26D89F1D315ED6E46F3C67574D374A21E987C683A54808755CA40CAF12253) Search public (rP) (on G2)= (138DE1C41C15B4F10BFE410E1DE6909DFCCBDC28C53077B236927BCC5C9FCDBD,050A1BC50D3D2AD20CDA72C9040B49D73E032DCA4C09B1F9409899057FD6E0AD) --- Now let's search for it --- Found it