Bob Investigates Wendy and Needs to Ask Alice

1-to-N Oblivious Transfer

Bob Investigates Wendy and Needs to Ask Alice

1-to-N Oblivious Transfer

Preface

I was asked by someone about how I got into cryptography, and the answer was rather easy for me. It all happened in 2009 when my Ph.D. student (Zibi Kwecka) outlined a method of using commutative encryption for oblivious transfer [1]:

Zibi used RSA as a commutative encryption method to implement his research [here], and where he told the story of Bob and Alice sharing data, and where Alice could not tell the data that Bob was selecting. I was hooked!

Overall, Zibi used a modified version of RSA and which is known as SRA [here], and where the encryption keys could be used in any order. His scenario made sense to me, and where Bob is investigating Wendy and needs to get data on her from Alice.

So how does Bob get that data, without Alice knowing that Wendy is under investigation? Well, Bob can ask for data on a range of people, and how are indexed. Bob then locks in the index value he wants, but Wendy does not know which one he has selected. Then Alice produces a unique encryption key for each of the people in the index and encrypts them for Bob. Bob will then only be able to decrypt the one that selects Wendy. Alice will have no idea which one Bob was able to read, and thus does not know that Wendy is under investigation. Basically, Zibi implemented a 1-from-N oblivious transfer system.

Bob investigates Wendy and asks Alice

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

Implementing 1-to-N OT

If we want to implement a 1-from-2, we can use a simple OT method, as defined [here]. But, let’s scale this so that Bob can ask for N data subjects. For this, initially, Alice selects:

a∈Zp

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 elliptic curve point:

R=c.A+b.G

Bob sends R to Alice. She then computes encryption keys for each of the items:

Ki=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:

Coding

Now we can implement the method defined above with Golang [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")
	}
}

In this case, we have generated elliptic curve points, and then convert them into a byte array using the ToAffineUncompress() method. Once we have this byte array, we can then just take the byte array data and hash it with SHA-256 to produce a 256-bit key encryption. 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

Conclusions

OT methods are used in many places and aim to preserve privacy, by creating a population to hide the target of the data sample. Here’s the method we have implemented for this:

https://asecuritysite.com/golang/go_otn

References

[1] Kwecka, Z., Buchanan, W. J., & Spiers, D. (2009). Application and Analysis of Private Matching Schemes Based on Commutative Cryptosystems. In Proceedings of the 8th European Conference on Information Warfare and Security: ECIW (p. 154). Academic Conferences Limited.

[2] Chou, T., & Orlandi, C. (2015, August). The simplest protocol for oblivious transfer. In International Conference on Cryptology and Information Security in Latin America (pp. 40–58). Springer, Cham.