Oblivious transfer allows a sender to not know the information that a receiver has read. If c is a '0', we will be able to read Message 0, if it is a '1' we will be able to read Message 1 [1]. In this case we will use Elliptic Curves (P256) for the computation.
Oblivious Transfer (OT) with Elliptic Curves |
Method
So, we are Bob the Investigator and investigating a serious crime, and we suspect that Eve is the person who is involved in the crime. We now need to approach her employer (Alice) and ask for some information on her. So how do we do this without Alice knowing that we suspect Eve? Well oblivious transfer (OT) performs this. Let's say that HackerZForU employ Eve and Trent, and we are only interested in getting information on Eve. Alice runs the company.
Now the method we will use is based on the Diffie-Hellman key exchange (DHE) method, but is modified so that we generated two keys for Alice to pass the data. One will work and the other will be useless. Alice will have no idea which of the keys will work, and the information that we can look at. In this case we'll ask for data from both Eve and Trent, and Alice will not know which of them is the suspect.
To convert from a discrete log problem [here] to an elliptic curve problem we convert:
\(g^a\) becomes \(a.G\)
\(g^a.g^b\) becomes \(a.G + b.G\)
\(\frac{g^a}{g^b}\) becomes \(a.G - b.G\)
and where \(g\) is a discrete log generator, and \(G\) is the base point of a curve.
First Alice and Bob generate random numbers (\(a\) and \(b\)) and agree on a base point (\(G\)). Alice then multiples the base point with \(a\):
\(A = aG \)
She passes this to Bob. If Bob is interested in the first record he calculates \(g\) to the power \(b\), else if it is the second record, he calculates the value passed from Alice (A), and multiplies this value with \(g\) to the power of \(b\). Bob then sends one of these back:
\( if (c==0): B = bG\)
\( if (c==1): B = A+bG \)
Alice receives the value from Bob (\(B\)). She then calculates two keys:
\( K_0 = \text{Hash}(a.B )\)
\( K_1 = \text{Hash}(a.(B-A))\)
She then encrypts the two messages (\(M_0\) and \(M_1\)) with each of the keys, and returns the ciphers to Bob.
\( e_0 = E_{K_0}(M_0)\)
\( e_1 = E_{K_1}(M_1)\)
Bob calculates the decryption key (which will only work for one of the them) as the hash of \(bA\):
\( K_{bob} = \text{Hash}(b.A )\)
Bob will then try to decrypt the two ciphers with \( K_{bob}\) and only one will work.
This works because if he selects \(c=0\), he will generate:
\(k_r=\text{H}(b.A) = \text{H}(ab.G)\)
and \(K_0\) will be:
\(K_0 = \text{H}(a.B) = \text{H}(ab.G) \)
If Bob selected \(c=1\) then:
\(K_1 = \text{H}({a(B-A)}) = \text{H}{(a(A+bG-A)}) = \text{H}(ab.G) \)
The overview is defined in discrete log form as [1]:
Presentation
Code
An outline of the code is here (and is based on [2]):
package main import ( "os" "fmt" "crypto/aes" "strconv" "io" "golang.org/x/crypto/sha3" "crypto/cipher" "errors" "github.com/cloudflare/circl/group" "crypto/rand" ) const keyLength = 16 func aesEncGCM(key, plaintext []byte) []byte { block, err := aes.NewCipher(key) if err != nil { panic(err) } aesgcm, err := cipher.NewGCM(block) if err != nil { panic(err.Error()) } nonce := make([]byte, aesgcm.NonceSize()) if _, err := io.ReadFull(rand.Reader, nonce); err != nil { panic(err) } ciphertext := aesgcm.Seal(nonce, nonce, plaintext, nil) return ciphertext } func aesDecGCM(key, ciphertext []byte) ([]byte, error) { block, err := aes.NewCipher(key) if err != nil { panic(err) } aesgcm, err := cipher.NewGCM(block) if err != nil { panic(err.Error()) } nonceSize := aesgcm.NonceSize() if len(ciphertext) < nonceSize { return nil, errors.New("ciphertext too short") } nonce, encryptedMessage := ciphertext[:nonceSize], ciphertext[nonceSize:] plaintext, err := aesgcm.Open(nil, nonce, encryptedMessage, nil) return plaintext, err } func main() { myGroup:=group.P256 c := 0 msg0:="Hello" msg1:="Goodbye" argCount := len(os.Args[1:]) if (argCount>0) {c,_= strconv.Atoi(os.Args[1])} if (argCount>1) {msg0= string(os.Args[2])} if (argCount>2) {msg1= string(os.Args[3])} m0:=[]byte(msg0) m1:=[]byte(msg1) a:= myGroup.RandomNonZeroScalar(rand.Reader) k0 := make([]byte, keyLength) k1 := make([]byte, keyLength) A := myGroup.NewElement() A.MulGen(a) b := myGroup.RandomNonZeroScalar(rand.Reader) kR := make([]byte, keyLength) bG := myGroup.NewElement() bG.MulGen(b) AorI := myGroup.NewElement() AorI.CMov(c, A) B := myGroup.NewElement() B.Add(bG, AorI) aB := myGroup.NewElement() aB.Mul(B, a) maA := myGroup.NewElement() maA.Mul(A, a) maA.Neg(maA) aBaA := myGroup.NewElement() aBaA.Add(aB, maA) // Alice generates k0 AByte, _ := A.MarshalBinary() BByte, _ := B.MarshalBinary() aBByte, _:= aB.MarshalBinary() hashByte0 := append(AByte, BByte...) hashByte0 = append(hashByte0, aBByte...) s := sha3.NewShake128() _, _ = s.Write(hashByte0) _, _= s.Read(k0) // Alice generates k1 aBaAByte, _ := aBaA.MarshalBinary() hashByte1 := append(AByte, BByte...) hashByte1 = append(hashByte1, aBaAByte...) s = sha3.NewShake128() _, _ = s.Write(hashByte1) _, _ = s.Read(k1) // Bob generates kR bA := myGroup.NewElement() bA.Mul(A, b) bAByte, _ := bA.MarshalBinary() hashByte := append(AByte, BByte...) hashByte = append(hashByte, bAByte...) s = sha3.NewShake128() _, _= s.Write(hashByte) _, _ = s.Read(kR) e0 := aesEncGCM(k0, m0) e1 := aesEncGCM(k1, m1) fmt.Printf("Key0: %x\n",e0) fmt.Printf("Key1: %x\n",e1) fmt.Printf("c: %d\n",c) mc1, errDec := aesDecGCM(kR, e0) if errDec != nil { fmt.Printf("Cannot decrypt with Key0\n") } else { fmt.Printf("Decrypted message: %s\n",mc1) } mc2, errDec := aesDecGCM(kR, e1) if errDec != nil { fmt.Printf("Cannot decrypt with Key1\n") } else { fmt.Printf("Decrypted message: %s\n",mc2) } }
A sample run:
Msg0: Hello Msg1: Goodbye Key0: 1421659515975ab04ecb8cb55758f009d383efa29a17f0c51bdcc4d3fc8f7ceb7a Key1: c9a021a4e607c9d56740ca5205b5f850389537307f7d2cdc437771e9c4e5409da83a79 c: 1 Cannot decrypt with Key0 Decrypted message: Goodbye
References
[1] Chou, T., & Orlandi, C. (2015). The simplest protocol for oblivious transfer. In Progress in Cryptology--LATINCRYPT 2015: 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015, Proceedings 4 (pp. 40-58). Springer International Publishing.
[2] https://github.com/cloudflare/circl/blob/main/ot/simot/