# Oblivious Transfer

OBLIVIOUS TRANSFER: PROTOCOL TO ACHIEVE SECURITY AND PRIVACY IN THE DRM SYSTEMS

prepared by Antonius Cahya Prihandoko

Oblivious 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