Encrypted Keyword Searches Crypto Pairing and MIRACL

Encrypted Keyword Searches with Crypto Pairing 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]:

First we have two curves (G1 and G2) and initially we define a large prime number (q). First a trust server selects a point on the G2 curve (P), and generates a using a random number (s):

sk=s

Alice creates a public key with:

Apub=sP

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

Pr=rP

Trent hashes the word to search (M) to the G2 curve:

QW=H1(M)

And creates the pairing of:

(U,V)=(Pr,e (QW,Apub)^r

If Bob wants to search for W2, he matches to:

e (Tw,Pr)

and where Tw=sH1(W2)).

Coding

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 [here]:

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!

Go try it for yourself: