Oblivious Transfer 1-from-N

Oblivious Transfer 1-from-N

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 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.

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.

Initially, Alice selects:

a∈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∈Z_n

and then generates:

b∈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:

Kb=b.A

This works because:

Kb=b.A=a.b.G

Kc=a.R−c.T=a.(c.A+b.G)−a.c.A=a.b.G

This is outlined with:

The following is the code [here]:

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

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