Oblivious Transfer (OT) Protocol
Tech blog series #2, we will introduce Oblivious Transfer (OT) Protocol today! OT initially proposed by Rabin in 1981, has become a fundamental building block for various secure multi-party computation and privacy-preserving applications. In this blog, we will discuss the concept of OT and its different variations, including Base OT, ECDH OT, and Random OT. Let’s dive in!
OT Concept
The OT (Oblivious Transfer) protocol is a cryptographic protocol initially proposed by Rabin in 1981, It mainly has three variations(introduced by Beaver):
1）OT [Rabin81]
Rabin’s original protocol involves Alice sending a bit, b, and Bob randomly receiving either (0,0) indicating failure or (1,b) indicating receipt of b. However, Alice remains unaware of which event occurred.
2）1/2 OT [EGL82]
The One-out-of-two Oblivious Transfer (OT) protocol involves Alice having two input bits b0 and b1, while Bob receives a pair (c,bc) where c is a randomly chosen value that is outside of Bob’s control. However, Alice does not learn the value of c.
3）Base OT / Standard OT
For the “Chosen one-out-of-two Oblivious Transfer” protocol, Alice has input bits b0 and b1. Bob selects a random bit c from {0,1} and obtains the value bc, but Alice is not aware of the value of c.
In practice we often focus on Standard OT, the essential idea behind OT is that two parties, the sender and the receiver, aim to establish a secure communication channel on a public network. The sender has a set of messages and intends to transmit one of them to the receiver, who wishes to keep the chosen message confidential. At the same time, the sender remains unaware of which message the receiver has chosen.
There are many ways to implement OT protocol, such as RSA, elliptic curve cryptography, discrete logarithms, Diffie-Hellman key exchange, etc. but in common, they all need public key encryption.
OT is based on the concept of a one-time pad, a cryptographic technique that uses random keys to encrypt and decrypt messages. In OT, the sender and receiver establish a shared secret key and use it for encrypting and decrypting messages. The sender encrypts all messages using this key and the receiver selects one of the messages by sending a message to the sender, which generates a random mask applied to all encrypted messages. Finally, the sender sends the masked messages to the receiver, who can only decrypt the selected message without revealing any information about the other messages to the sender.
Standard OT
Firstly, we can assume that in the OT protocol, there’s a trusted third party responsible for completing the process. The Receiver inputs the selection bit c, the Sender inputs the encryption keys m0 and m1, and the trusted third party returns one of m0 and m1 to the Receiver. The Receiver does not know the other m, and the Sender does not know the Receiver’s choice bit c.
4) ECDH OT (Elliptic Curve Diffie-Hellman OT)
Let’s implement an OT protocol based on elliptic curves.
(1) The Sender generates a secret a∈Z(p), calculates A=a·G based on the base point G on the elliptic curve, and then sends it to the Receiver.
(2) The Receiver generates a secret b∈Z(p), and calculates a different B based on the selected bit c:
If c=0: B=b·G
If c=1: B=A + b·G
Finally, the Receiver sends B to the Sender.
(3) The Sender calculates the encryption keys based on the received B:
k0=a·B
k1=a·(B-A)
(4) The Sender inputs valuable information m0 and m1, and encrypts them as m0 ⊕ k0 and m1 ⊕ k1, respectively.
(5) The Receiver calculates the decryption key k=b·A and decrypts the encrypted information sent by the Sender. Note that regardless of whether the Receiver’s selection bit c is 0 or 1, they can only decrypt one message from the Sender:
If c=0: m0 ⊕ k0 ⊕ k = m0 ⊕ A b ⊕ b A = m0
If c=1: m1 ⊕ k1 ⊕ k = m1 ⊕ A b ⊕ b A = m1
Random OT
The main issue with Standard OT is the high computation cost required in the online phase, which makes it inefficient. To address this problem, Random OT was introduced. Random OT can be produced in the offline phase, pre-generate a set of m0/1 keys and random c values, and then conducts MPC during the online phase.
A classic implementation of Random OT is described in [Beaver91]. The implementation can be explained as follows:
(1) In the offline phase, the Sender randomly generates r0 and r1; the Receiver randomly generates selection bits s∈{0,1} and a secret a∈Z(p).
(2) The Sender calculates c0=g^r0 and c1=g^r1, and sends them to the Receiver.
(3) The Receiver constructs the key according to the selection bit s:
s=0 : Pk0=g^a
s=1: Pk1=g^a and Pk0=c1/Pk1
Finally, the Receiver sends Pk0 to the Sender.
(4) The Sender calculates k0=Pk0^r0 and k1=(c1/Pk0)^r1.
(5) The Sender inputs messages m0 and m1, encrypts them, and sends them to the Receiver: m0 ⊕ k0 and m1 ⊕ k1.
(6) The Receiver calculates the decryption key k=c0^a = g^(a·r0). Note that regardless of whether the Receiver’s selection bit s is 0 or 1, he can only decrypt one message from the Sender:
s=0 : m0 ⊕ k0 ⊕ k = m0 ⊕ (k0 ⊕ k) = m0
s=1: m1 ⊕ k1 ⊕ k = m1 ⊕ (k1 ⊕ k) = m1
(7) Derandmoize:c$ is randomly selected in the offline phase, but in the online phase it may not be the selection bit we want, so we need a correction bit for it, look at Fig1, Receiver send d to sender, and then sender will exchange the keys denpends on the value of d=c xor c$, if d=0 which means c==c$, then sender will use m0$ encrypt m0 and m1$ encrypt m1.but if d=1 whitch means c!=c$, then the sender will use m1$ encrypt m0 and m0$ encrypt m1.thus we can change the random c$ to the chosen c.
Next Blog
While Random OT generates many keys at once, it still needs public key encryption for generating every OT instance, which is highly costly for computation. In the next chapter, we will introduce an OT extension scheme based on the semi-honest model, namely OT Extension [IKNP03], so stay tuned.
