\(\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.
Searching for Encrypted Data with Identity Based Encryption (IBE)
[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 outline coding using the library from the MIRACL library [here] is
package main import ( "fmt" "github.com/miracl/core/go/core" "github.com/miracl/core/go/core/BN254" "math/rand" "time" "os" ) func FP12toByte(F *BN254.FP12) []byte { const MFS int = int(BN254.MODBYTES) var t [12 * MFS]byte F.ToBytes(t[:]) return(t[:]) } func ECPtoByte(F *BN254.ECP2) []byte { const MFS int = int(BN254.MODBYTES) var t [12 * MFS]byte F.ToBytes(t[:],true) 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 xor(a []byte, b []byte) []byte{ for i := 0; i < len(a); i++ { a[i]=(a[i]^b[i]) & 0xff } return a } func main() { msg:="Hello" search:="Hello" argCount := len(os.Args[1:]) if (argCount>0) {msg= os.Args[1]} if (argCount>1) {search= os.Args[2]} q := BN254.NewBIGints(BN254.CURVE_Order) s:=BN254.Randomnum(q,randval()) r:=BN254.Randomnum(q,randval()) P := BN254.ECP_generator() // Alice's public key: A_public A_public:=BN254.G1mul(P,s) rP:=BN254.G1mul(P,r) M := []byte(msg) sh:=core.NewHASH256() for i:=0;i < len(M);i++ { sh.Process(M[i]) } Q_W:=sh.Hash() QW := BN254.ECP2_mapit(Q_W) pair:=BN254.Ate(QW,A_public); pair=BN254.Fexp(pair) pair=pair.Pow(r) M = []byte(search) sh=core.NewHASH256() for i:=0;i < len(M);i++ { sh.Process(M[i]) } Q_WS:=sh.Hash() QWS := BN254.ECP2_mapit(Q_WS) Tw:=BN254.G2mul(QWS,s) fmt.Printf("Encrypted Message:\t%s\n\n",msg) fmt.Printf("Word to find:\t%s\n\n",search) fmt.Printf("Alice QA:\t%s\n\n",QW.ToString()) fmt.Printf("s:\t%s\n",s.ToString()) fmt.Printf("r:\t%s\n\n",r.ToString()) pair2:=BN254.Ate(Tw,rP); pair2=BN254.Fexp(pair2) fmt.Printf("\nPairing 1 e(QW,A_public)^r:\t%x\n",FP12toByte(pair)[:20]) fmt.Printf("\nPairing 2 e(Tw,P_r):\t%x\n",FP12toByte(pair2)[:20]) if pair.Equals(pair2) { fmt.Printf("\nWord search found!\n") } else { fmt.Printf("\nWord NOT found!\n") } }
A sample run is:
Encrypted Message: Hello Word to find: Hello Alice QA: ([1ccca930dd8db6e1a24fbe4c678328a8514023ac6c4b154adec96e5bb02f367e,1c90a422c4dcf4505a326f5a913dc5809f83ba7b72a5b774e0a4f84b5ed89b00],[18af9c5e9b35e66e5776acc3f4c52aa24c020d5611fa5397940e9a651b223970,146f4cdcdb8bf1d8675136ef9388799e8b38f2386035d5f24e710678216a79ef]) s: 07156368a68d02fa0bb85c9b1a28062e009153f45bac9c7777951c94bced9465 r: 05c9a41714cfb88c8be401c6c2137a3ec25a0de12d854e45a5eed9aa23ed415d Pairing 1 e(QW,A_public)^r: 2394ece9dcda3c192cf01b4e054ee6de0bfd5f9c Pairing 2 e(Tw,P_r): 2394ece9dcda3c192cf01b4e054ee6de0bfd5f9c Word search found!
and a false search:
Encrypted Message: Hello Word to find: Goodbye Alice QA: ([1ccca930dd8db6e1a24fbe4c678328a8514023ac6c4b154adec96e5bb02f367e,1c90a422c4dcf4505a326f5a913dc5809f83ba7b72a5b774e0a4f84b5ed89b00],[18af9c5e9b35e66e5776acc3f4c52aa24c020d5611fa5397940e9a651b223970,146f4cdcdb8bf1d8675136ef9388799e8b38f2386035d5f24e710678216a79ef]) s: 00f96ad3f2f5626d49d781e8f6ffec68d08f267a77e6a82d683d1be73efc43cb r: 19e3759303ac588f063fce02b9d13cfb30549e4cc90e2862cfdfc75436c45404 Pairing 1 e(QW,A_public)^r: 15ff85bbf4dbd26dc5efef6ee016a192ed5f172a Pairing 2 e(Tw,P_r): 0fb9f1e01642f3ad046ee03592fc554cbcccfe2d Word NOT found!