Oblivious Transfer 1-from-NLet's say that Alice has some data, and Bob wants to pick one of the values of data, but does not want Alice to know which one he has picked. Alice also wants to make sure that Bob onto can reveal one of the data values. For this we can use a 1-from-N oblivious transfer method. In the following, Alice generates 10 encryption keys for each of the data elements, and passes them to Bob. Bob will then be able to create the same encryption key for the index value that he has requested. |
Method
Let’s say that Alice has some data, and Bob wants to pick one of the values of data but does not want Alice to know which one he has picked. Alice also wants to make sure that Bob can only reveal one of the data values. For this, we can use a 1-from-N oblivious transfer (OT) method. In the following, Alice generates unique encryption keys for each of the data elements and passes them to Bob. Bob will then be able to create the same encryption key for the index value that he has requested.
In Figure 1, we can see that Bob is investigating Wendy, and needs to ask Alice (her employer) for the required data. For this Bob asks for data on a range of people, and locks in on the index of Wendy. Alice then creates encryption keys for each of the subjects, and encrypts these data, and sends them to Bob. Bob will then only have an encryption key to decrypt the one that can decrypt the one that relates to Wendy. Alice will have no idea which one he has picked.
Figure 1: Wendy is under investigation, and where Bob can discover her data without Alice knowing which person he has selected to reveal her data
Initially Alice selects:
\(a \in Z_p\)
and then computes the elliptic curve point of:
\(A=a.G\)
and:
\(T=a.A\)
Alice then sends \(A\) to Bob.
Bob then selects the index value (\(c\)) from \(n\) items that he wants:
\(c \in Z_n\)
and then generates:
\(b \in Z_p\)
and then computes the point:
\(R = c.A + b.G\)
Bob sends \(R\) to Alice. She then computes encryption keys for each of the items:
\(K_i = a.R - i.T \)
She will then encrypt each data element \(i\) with \(K_i\) and then passes the encrypted values to Bob. Bob will then be able to generate the correct key for item \(i\) with:
\(K_b=b.A\)
This works because:
\(K_b=b.A = a.b.G\)
\(K_c=a.R - c.T = a.(c.A + b.G) - a.c.A = a.b.G\)
This is outlined with:
Outline
The following is the code:
package main import ( "bytes" crand "crypto/rand" "crypto/sha256" "fmt" "math/rand" "os" "strconv" "time" "github.com/coinbase/kryptology/pkg/core/curves" ) func main() { cval := 4 argCount := len(os.Args[1:]) if argCount > 0 { cval, _ = strconv.Atoi(os.Args[1]) } fmt.Printf("Bob select index: %d\n",cval) rand.Seed(time.Now().UnixNano()) curve := curves.K256() G := curve.Point.Generator() a := curve.Scalar.Random(crand.Reader) A := G.Mul(a) T := A.Mul(a) fmt.Printf("\nAlice sends:\n") fmt.Printf("A=%x\n", A.ToAffineUncompressed()) c := curve.Scalar.New(cval) b := curve.Scalar.Random(crand.Reader) R1 := A.Mul(c) R2 := G.Mul(b) R := R1.Add(R2) fmt.Printf("Bob sends:\n") fmt.Printf("R=%x\n", R.ToAffineUncompressed()) var ke [10][32]byte fmt.Printf("\nAlice generates keys:\n") for i := 0; i < 10; i++ { e := curve.Scalar.New(i) ke1 := R.Mul(a) ke2 := T.Mul(e) keval := ke1.Sub(ke2) ke[i] = sha256.Sum256(keval.ToAffineUncompressed()) fmt.Printf("k%d=%x\n", i, ke[i]) } kr := A.Mul(b) key := sha256.Sum256(kr.ToAffineUncompressed()) fmt.Printf("\nBob computes key:\n") fmt.Printf("\nkr=%x\n", key) if bytes.Equal(ke[cval][:], key[:]) { fmt.Printf("Key matches") } }
A sample run is:
Bob select index: 0 Alice sends: A=04cc188925c2ba480910b87669b7fdfe09bcfac06f49fc8bd1e4175b70cf9d76ff7d8f3b31f4637945dcc3885a5f6f827b30880543de54d901518b75099fd7f82c Bob sends: R=04f4a8c999c56ff55ec5a29349dffb4b84307b649394789cbe026eacff7c5cd4f7174941633be78d8a46c9037c1cdba0a73c8f9b2edd9697bdc2efd69d39a4184b Alice generates keys: k0=6bf3e49209700188f839559cdf9c89270f2df6d78f1253bab7f63044f56f21cd k1=134a649c062ec63e2b0476dcdbcbce1c94b27245fe7d21f0075b7ff794f08707 k2=429ae035191d2b05f49722853b0377be659ec1b48e81edfbdd0fb42b0ec665bd k3=efafc92d839775746c90bd688ceecd5da0baaec1308ed00a60da6e3b898e0b43 k4=a3c12dbdbdd7f5e942712849a8d4e3627d8aba3e8055138a523e89c39fb3053e k5=0d14c297792db6446a8a6a9b72ae0f05337755968b508c03b111ae28b948d6ae k6=e49b8134d59d1d4cf303ff335b3bbc12bf03d7f732a48ac25e54e2b571eee980 k7=73e9653f3add292ae3f4e58f06108e34fc3da04c0987a32cbc5d4bce2329ccee k8=c0a98677e2991063ca2bd8e8c9489264c2f035d456c6a2b27c124bd935ea965f k9=a4c113dd2a2b1c6b09874310588323ef395f434e0c290a976ae8ee97637580bd Bob computes key: kr=6bf3e49209700188f839559cdf9c89270f2df6d78f1253bab7f63044f56f21cd Key matches