Oblivious transfer

From Wikipedia, the free encyclopedia

In cryptography, an oblivious transfer protocol (often abbreviated OT) is a protocol by which a sender sends some information to the receiver, but remains oblivious as to what is received.

In the early seventies Stephen Wiesner introduced a primitive called multiplexing in his seminal paper "Conjugate Coding", which was the starting point of quantum cryptography^[1]. Unfortunately it took more than ten years to be published. Even though this primitive was equivalent to what was later called 1-2 oblivious transfer, Wiesner did not see its application to cryptography.

The first form of oblivious transfer was introduced in 1981 by Michael O. Rabin^[2]. In this form, the sender sends a message to the receiver with probability 1/2, while the sender remains oblivious as to whether or not the receiver received the message. Rabin's oblivious transfer scheme is based on the RSA cryptosystem. A more useful form of oblivious transfer called 1-2 oblivious transfer or "1 out of 2 oblivious transfer," was developed later by Shimon Even, Oded Goldreich, and Abraham Lempel^[3], in order to build protocols for secure multiparty computation. It is generalized to "1 out of n oblivious transfer" where the user gets exactly one database element without the server getting to know which element was queried. The latter notion of oblivious transfer is a strengthening of private information retrieval where one does not care about database's privacy.

Claude Crépeau showed that Rabin's oblivious transfer is equivalent to 1-2 oblivious transfer.^[4]

Further work has revealed oblivious transfer to be a fundamental and important problem in cryptography. It is considered one of the critical problems in the field, because of the importance of the applications that can be built based on it. In particular, it is a `complete' for secure multiparty computation: that is given an implementation of oblivious transfer it is possible to securely evaluate any polynomial time computable function without any additional primitive.^[5]

Contents 1 Rabin's oblivious transfer protocol 2 1-2 oblivious transfer 3 1-n oblivious transfer 4 See also 5 References 6 External links

[edit] Rabin's oblivious transfer protocol

In Rabin's oblivious transfer protocol, the sender generates an RSA public modulus N=pq where p and q are large prime numbers, and an exponent e relatively prime to (p-1)(q-1). The sender encrypts the message m as m^e mod N.

1. The sender sends N,e, and m^e mod N to the receiver.
2. The receiver picks a random x modulo N and sends x² mod N to the sender. Note that gcd(x,N)=1 with overwhelming probability, which ensures that there are 4 square roots of x² mod N.
3. The sender finds a square root y of x² mod N and sends y to the receiver.

If the y the sender finds is neither x nor -x modulo N, the receiver will be able to factor N and therefore decrypt m^e to recover m (see Rabin encryption for more details). However, if y is x or -x mod N, the receiver will have no information about m beyond the encryption of it. Since every quadratic residue modulo N has four square roots, the probability that the receiver learns m is 1/2.

[edit] 1-2 oblivious transfer

In a 1-2 oblivious transfer protocol, the sender has two messages m₀ and m₁, and the receiver has a bit b, and the receiver wishes to receive m_b, without the sender learning b, while the sender wants to ensure that the receiver receive only one of the two messages. The protocol of Even, Goldreich, and Lempel (which the authors attribute partially to Silvio Micali), is general, but can be instantiated using RSA encryption as follows.

1. The sender generates RSA keys, including the modulus N, the public exponent e, and the private exponent d, and picks two random messages x₀ and x₁, and sends N, e, x₀, and x₁ to the receiver.
2. The receiver picks a random message k, encrypts k, and adds x_b to the encryption of k, modulo N, and sends the result q to the sender.
3. The sender computes k₀ to be the decryption of q-x₀ and similarly k₁ to be the decryption of q-x₁, and sends m₀ + k₀ and m₁ + k₁ to the receiver.
4. The receiver knows k_b and subtracts this from the corresponding part of the sender's message to obtain m_b.

[edit] 1-n oblivious transfer

A 1-n oblivious transfer protocol can be defined as a natural generalization of a 1-2 oblivious transfer protocol. Specifically, a sender has n messages, and the receiver has an index i, and the receiver wishes to receive the i-th among the sender's messages, without the sender learning i, while the sender wants to ensure that the receiver receive only one of the n messages. Intuitively, it can also be considered as the effect of adding an additional database's privacy requirement to some existing private information retrieval protocol.

The existence of 1-n oblivious transfer protocols from any private information retrieval protocol was first established by Giovanni Di Crescenzo, Tal Malkin and Rafail Ostrovsky in [6]. Additional constructions of 1-n oblivious transfer protocols also related to private information retrieval, were proposed, e.g., by Moni Naor and Benny Pinkas [7], William Aiello, Yuval Ishai and Omer Reingold [8], Sven Laur and Helger Lipmaa [9].

[edit] See also

• Secure multiparty computation
• Zero knowledge proof

[edit] References

• ^  Stephen Wiesner, "Conjugate coding", Sigact News, vol. 15, no. 1, 1983, pp. 78 - 88; original manuscript written circa 1970.
• ^  Michael O. Rabin. "How to exchange secrets by oblivious transfer." Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981. Paper on eprint.iacr.org archive
• ^  S. Even, O. Goldreich, and A. Lempel, "A Randomized Protocol for Signing Contracts", Communications of the ACM, Volume 28, Issue 6, pg. 637-647, 1985. Paper at ACM portal (subscription required)
• ^  Claude Crépeau. "Equivalence between two flavours of oblivious transfer". In Advances in Cryptology: CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 350--354. Springer, 1988
• ^  Joe Kilian. "Founding Cryptography on Oblivious Transfer", Proceedings, 20th Annual ACM Symposium on the Theory of Computation (STOC), 1988. Paper on Joe Kilian's home page

[edit] External links

• Helger Lipmaa's collection of Web links on the topic