Oblivious Transfer


prepared by Antonius Cahya Prihandoko

mc-otOblivious Transfer (OT) is a cryptographic protocol which allows two parties to exchange one or more secret messages, where in the end of the protocol the sender does not know whether the recipient actually received the information. The first OT protocol, introduced by Michael Rabin (1981),  was intended to overcome the exchange of secrets (EOS) problem. In their protocol, the receiver can access the message with probability \frac{1}{2} and the sender will not know whether the receiver can access the message. To describe this protocol we use two well-known players in cryptography, Bob and Alice.

Bob and Alice each have a secret, S_{B} and S_{A}, respectively, which they want to exchange. For example, S_{B} may be the password to a file that Alice wants to access. The file is sent by Bob to Alice and referred as Alice’s file. Similarly, S_{A} is the password to Bob’s file. The question is how they can exchange their secrets without using a trusted third party.

EOS Assumptions and Problems

Assume that the use of incorrect password will erase the file. With this assumption, S_{A} and S_{B} can be taken to be single bits. However, it is possible for Bob to give Alice a wrong password such that while he is able to read his file, Alice will destroy her file. Or, Alice can receive the correct S_{B} and read her file without giving S_{A} to Bob.

To overcome such problems, an EOS protocol need to be constructed such that when Bob knows S_{A}, Alice can deduce S_{B}. Or if a party interrupts the protocol, no party will know the secrets. The assumption that if Bob uses S_{A} to read his file then Alice will know about this and vice versa, will make such a protocol feasible.

EOS protocol

Assume that Bob and Alice each have a public key, K_{B} and K_{A}, respectively, that can be used for encryption and digital signatures. The protocol consists of 3 rounds.

Round 1. In the first round, Alice chooses two large primes p, q and creates a one-time key n_{A} = pq. Similarly,Bob creates n_{B}. Alice effects an oblivious transfer of n_{A} to Bob as follows.

  • Alice send her one-time key n_{A} to Bob
  • Bob chooses randomly an x \leq n_{A}, computes c=x^{2} \bmod n_{A}, and send E_{K_{B}}(x) and c to Alice
  • Alice who knows the factors p, q of n_{A}, calculates an x_{1} such that x_{1}^{2} = c \bmod n_{A}. She then send x_{1} to Bob.
  • Bob calculates gcd(x-x_{1},n_{A})=d. As p[d=p or d=q] =\frac{1}{2}, Bob will know the factorization n_{A} =pq with probability \frac{1}{2}. However, since Alice does not know x, she does not know whether Bob has the factorization of n_{A}.

Using the same steps, Bob also effects an oblivious transfer of n_{B} to Alice.

Round 2. After the oblivious transfer of n_{A}, Bob determines his knowledge of the factorization of n_{A}. He defines v_{B} = 0 if d = p or d = q, otherwise v_{B} = 1. Bob then forms

\epsilon_{B} = S_{B} \oplus v_{B}

and send \epsilon_{B} to Alice. Knowledge of \epsilon_{B} , however, does not make Alice can access her file as she does not know v_{B}.

Reversely, Alice defines v_{A} and communicates \epsilon_{A} in a similar way.

Round 3. Alice places S_{A} as the centerbit in a random message m_{A}, and encodes m_{A} as E_{n_{A}}(m_{A})=d_{A} using any public-key system which requires the factor p, q of n_{A} for decoding. Alice then sends d_{A} to Bob in a signed message.

Bob does the similar way for his S_{B} and n_{B}.

 Analysis. Assume that Alice has given d_{A} to Bob. If Bob knows the factorization of n_{A} = pq, then he can decode d_{A} and find  m_{A} and S_{A}. If Bob uses S_{A} to read his file, then by assumption, Alice will know this. Of course, Bob would attempt to read his file if he knows S_{A} with certainty, otherwise he will destroy his file. Therefore, Alice will know that v_{B} = 0 and hence she knows S_{B} = \epsilon_{B}.

The notion of Rabin’s EOS protocol basically can be adopted for secret exchange between content provider and user in a digital transaction. Content provider send the user the secret key that can be used to decrypt the protected content. In exchange, user send the content provider the secret key that can be used to access user’s personal information.

A Proposed OT Protocol for DRM Implementation

An oblivious transfer protocol, basically, has to be set in such a way to achieve the sender’s security and the receiver’s privacy. The former means that the receiver will not be able to learn more than he was supposed to learn. While the later means that the sender will not know what the receiver has learned.

We propose an oblivious transfer “buyer-seller” protocol that is more flexible and appropriate for the DRM implementation. The protocol achieves unconditionally security and privacy with an efficient computation. In addition, it may also provide a solution for the cost problem of the OTP construction.

Our protocol utilizes tamper-proof devices, such as smart-cards. A tamper-proof device means any device that can be used only in a particular way; otherwise the device will be corrupted and its content will not be accessible any more. The device can also be set in such a way that it can self destruct. Utilizing tamper-proof devices in this protocol is less expensive. The device contains only two types of functions and performs efficient computations. With this characteristics, the device can be mass produced with a low cost.

In this protocol, each device contains a pair of functions (GetKey, GetContent). GetKey allows the user to ask for the key, that is, the input parameter to GetContent function. Whereas GetContent requires an authorized key to reveal the message stored in it. It is reasonable and may be more efficient when a single device contains all pairs of functions (GetKey, GetContent). However, for a clear explanation in this article, we assume that one device contains a pair of functions (GetKey,GetContent).

Suppose the content provider (Alice) provides N contents (e.g. movies), M_{1}, ..., M_{N}, and the customer (Bob) wishes to access K, where K < N, of these contents. Alice has a secret code S to access the contents, and utilizes Shamir’s secret sharing schemes, with the threshold parameter N-K, to share the secret. That is, she split the secret into N pieces such that any set of at least N-K shares can reconstruct the secret.

The detail protocol is as follows. To share the secret and send the contents, Alice performs the following:

  • She secretly chooses random N-K-1 elements of Z_{p}, denoted a_{1}, ..., a_{N-K-1} and form the polynomial f(x) = S + a_{1}x^{1} + ... + a_{N-K-1}x^{N-K-1}
  • For i = 1, ..., N, she computes s_{i}, where s_{i}=f(i) \bmod p
  • She loads device d_{i} with s_{i} as the key value, and M_{i} as the content value.
  • She gives all devices and an access code to Bob.

After delivering the devices there is no subsequent communication between Alice and Bob. Bob can access K contents if he accepts to sacrifice N-K contents that are not supposed to be accessed. This condition apply with assumption that once a device is executed, it will be corrupted or destroy itself.

  • Let M_{1}, ..., M_{K} be the K contents the Bob wants to access. Bob then performs the GetKey function on the devices d_{K+1},...,d_{N} to obtain N-K shares.
  • With the N-K shares, Bob can reconstruct the polynomial, e.g. using the Lagrange interpolation, and learn the secret S.
  • Using the access code S, Bob performances the GetContent function on devices d_{1}, ..., d_{K} to obtain the contents M_{1}, ..., M_{K}.

The scenario can also be applied when customer request N accesses, instead of N items. For example, a customer wants to watch a movie for K times. The movie provider can send the customer a package containing N pairs (GetKey,GetContent) with the sharing threshold is N-K. In this case, all GetContent functions contains movie of the same title.

Analysis of Security and Privacy

With assumption that tamper-proof devices exist, the proposed protocol achieve unconditional seller’s security. In the proposed protocol, the contents are stored in tamper-proof devices. The buyer cannot access content without obtaining the secret key. The key, however, is split into several piece of shares and distributed among the devices using Shamir’s secret sharing scheme. This scheme is perfect, that is knowing less than a predetermined number of shares gives absolutely no idea about the secret. Therefore, buyer can only obtain the secret key if and only if he sacrifices all contents that he is not supposed to access. It means that the buyer is not able to access anything more than the contents that are supposed to be accessed.

With the same assumption, we claim that the proposed protocol provides unconditionally buyer’s privacy protection. In the proposed protocol, there is no interaction between seller and buyer after the seller gives all devices to the buyer. There is no way for the seller to figure out which devices the buyer has used. As all devices are corrupted at the end of the protocol, the seller has no knowledge on which content that has been access by the buyer. Therefore, buyer’s privacy is fully protected.

Townsville, 6 March 2013


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s