Oblivious Transfer: Discrete Logs and Elliptic Curves
Translating from discrete logs to elliptic curves can be useful if we go from research papers to real implementations, as research papers often outline the discrete log form, whereas in real life we would typically implement with elliptic curves. In this case we will implement a simple oblivious transfer method [1].
Bob the Investigator
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.
First Alice and Bob generate random numbers (a and b) and agree on a prime number (N). Alice then takes a generator value of g and raises it to the power of a:
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:
Alice receives the value from Bob (B). She then calculates two keys: the hash of B to the power of a, and the hash of BA to the power of a.
In this case, we can determine the inverse of A(modN) and then multiple the value with B. She then encrypts the two messages (M0 and M1 ) with each of the keys, and returns the ciphers to Bob.
Bob calculates the decryption key (which will only work for one of the them) as the hash of A to the power of b :
Bob will then try to decrypt the two ciphers with Kbob and only one will work. This works because if he selects c=0, he will generate:
and K0 will be:
If Bob selected c=1 then:
The overview is defined in [1]:
The coding for this is here:
Elliptic Curves
Now we have the theory covered, let’s implement with elliptic curves. For this we change exponations to point multiplications, multiplications to point additions and divisions to point subtractions. So:
First Alice and Bob generate random numbers (a and b) and agree on a based point (G). Alice takes the base point and mutiples by her random number:
She passes this to Bob. If Bob is interested in the first record he calculates b.G, else if it is the second record, he takes the value passed by Alice (A), and multiplies by b. Bob then sends one of these back:
Alice receives the value from Bob (B). She then calculates two keys:
She then encrypts the two messages (M0 and M1) with each of the keys, and returns the ciphers to Bob.
Bob calculates the decryption key (which will only work for one of the them) as the hash of bA:
Bob will then try to decrypt the two ciphers with Kbob and only one will work.
This works because if he selects c=0, he will generate:
and K0 will be:
If Bob selected c=1 then:
The code for this is [here]:
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("Msg0: %s\n",msg0)
fmt.Printf("Msg1: %s\n",msg1)
fmt.Printf("Key0: %x\n",e0)
fmt.Printf("Key1: %x\n\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)
}
}and a sample run [here]:
Msg0: It was Bob!
Msg1: It was Alice!
Key0: 5761f04c98262b3fb464a88bf798cb5ef182ab42c633af3bd78968d9355558cbffa3882c70a325
Key1: 8853695c047522500ebd348c801db66de4e9004c3dd6fdc4adf0dbea32c08f76c745d993157882a8b9
c: 0
Decrypted message: It was Bob!
Cannot decrypt with Key1Conclusions
If you are interested in Oblivious Transfer (OT), try here:
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.
