\(\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 Kryptology library.
Encrypted Words Search with Kryptology
[Pairing 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 Kryptology 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 Kryptography library is
package main import ( "crypto/rand" "fmt" "math/big" "os" "crypto/sha256" bls12381 "github.com/coinbase/kryptology/pkg/core/curves/native/bls12-381" ) func main() { m := "hello" tof := "hello" argCount := len(os.Args[1:]) if argCount > 0 { m = os.Args[1] } if argCount > 1 { tof = os.Args[2] } fmt.Printf("Encrypted word: %s\n\n", m) fmt.Printf("Word to find: %s\n\n", tof) bls := bls12381.NewEngine() g1, g2 := bls.G1, bls.G2 gt := bls.GT() msg := []byte(m) tofind := []byte(tof) HW, _ := g1.HashToCurve(sha256.New, msg, []byte("")) ToF, _ := g1.HashToCurve(sha256.New, tofind, []byte("")) r := make([]byte, 32) rand.Read(r) rval := new(big.Int).SetBytes(r) s := make([]byte, 32) rand.Read(s) sval := new(big.Int).SetBytes(s) G2 := g2.One() sP := g2.New() rP := g2.New() sToF := g1.New() g2.MulScalar(sP, G2, sval) g2.MulScalar(rP, G2, rval) g1.MulScalar(sToF, ToF, sval) fmt.Printf("s = %x\n", s) fmt.Printf("r = %x\n\n", r) e0, _ := bls.AddPair(HW, sP).Result() gt.Exp(e0, e0, rval) e1, _ := bls.AddPair(sToF, rP).Result() fmt.Printf("First part of e0 pairing: %+v\n", e0[0][0][0]) fmt.Printf("First part of e1 pairing: %+v\n", e1[0][0][0]) if e0.Equal(e1) { fmt.Printf("We have found it...") } else { fmt.Printf("Cannot find!") } }
A sample run is:
Encrypted word: Hello Word to find: Hello s = 1229b2836a548cca3bc9ac238cd0c634635535f3a5b6f12aac78fd5fa096a77c r = 2fce640d56121d278b20dedd00ecc442e3a1c536de98209f4f10f551b15072e9 First part of e0 pairing: [5509936851070022305 4957573568693525133 3532086020062769437 5031641048332977130 18248703594105518599 657243605775503017] First part of e1 pairing: [5509936851070022305 4957573568693525133 3532086020062769437 5031641048332977130 18248703594105518599 657243605775503017] We have found it...
and a false search:
Encrypted word: Hello Word to find: Hello123 s = 3398a4ecba24cc114291082613ed0f49a5e482ee72d829cdd33fefd404f91ca6 r = cf2c6448553df07deb10b4e70dd0e2e113a4d3318d87d1c08d735528f9754dde First part of e0 pairing: [9433419437807457542 14827067878769968193 9757426493516444139 5593213596321565194 10129867375955106600 81638192315469051] First part of e1 pairing: [9963009439914925460 13665328121908137426 1398638186177370014 5695327681334410247 16635414863332113065 1808470817875180072] Cannot find!