Oblivious transfer
Encyclopedia
In cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, an oblivious transfer protocol (often abbreviated OT) is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred.

The first form of oblivious transfer was introduced in 1981 by Michael O. Rabin
Michael O. Rabin
Michael Oser Rabin , is an Israeli computer scientist and a recipient of the Turing Award.- Biography :Rabin was born in 1931 in Breslau, Germany, , the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine...

. In this form, the sender sends a message to the receiver with probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...

 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
Shimon Even
Shimon Even was an Israeli computer science researcher. His main topics of interest included algorithms, graph theory and cryptography. He was a member of the Computer Science Department at the Technion since 1974...

, Oded Goldreich
Oded Goldreich
Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation...

, and Abraham Lempel
Abraham Lempel
Abraham Lempel is an Israeli computer scientist and one of the fathers of the LZ family of lossless data compression algorithms.Lempel was born on 10 February 1936 in Lwów, Poland . He studied at Technion - Israel Institute of Technology, and received a B.Sc. in 1963, M.Sc. in 1965, and D.Sc. in...

, in order to build protocols for secure multiparty computation
Secure multiparty computation
Secure multi-party computation is a sub field of cryptography. The goal of methods for secure multi-party computation is to enable parties to jointly compute a function over their inputs, while at the same time keeping these inputs private...

. 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, and without the user knowing anything about the other elements that were not retrieved. The latter notion of oblivious transfer is a strengthening of private information retrieval
Private information retrieval
In cryptography, a private information retrieval protocol allows a user to retrieve an item from a server in possession of a database without revealing which item they are retrieving...

 where one does not care about database's privacy.

Claude Crépeau
Claude Crépeau
Dr. Claude Crépeau is a professor in the School of Computer Science at McGill University. Ηe was born in Montreal, Quebec, Canada, in 1962. He received a Masters degree from the Université de Montréal in 1986, and obtained his Ph.D. in Computer Science from MIT in 1990, working in the field of...

 showed that Rabin's oblivious transfer is equivalent to 1-2 oblivious transfer.

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 complete for secure multiparty computation
Secure multiparty computation
Secure multi-party computation is a sub field of cryptography. The goal of methods for secure multi-party computation is to enable parties to jointly compute a function over their inputs, while at the same time keeping these inputs private...

: that is, given an implementation of oblivious transfer it is possible
to securely evaluate any polynomial time computable function without any additional primitive.

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 number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

s, and an exponent e relatively prime to (p-1)(q-1). The sender encrypts the message m as me mod N.
  1. The sender sends N, e, and me mod N to the receiver.
  2. The receiver picks a random x modulo N and sends x2 mod N to the sender. Note that gcd(x,N)=1 with overwhelming probability, which ensures that there are 4 square roots of x2 mod N.
  3. The sender finds a square root y of x2 mod N and sends y to the receiver.


If the receiver finds y is neither x nor -x modulo N, the receiver will be able to factor
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

 N and therefore decrypt me 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.

1-2 oblivious transfer

In a 1-2 oblivious transfer protocol, the sender has two messages m0 and m1, and the receiver has a bit b, and the receiver wishes to receive mb, 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
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...

), is general, but can be instantiated using RSA encryption as follows.
Alice Bob
Secret Public Calculus Secret Public Calculus
Messages to be sent
Generate RSA key pair and send public portion to Bob Receive public key
Generate two random messages Receive random messages
Choose , and generate random
Compute the encryption of , blind with and send to Alice
One of these will equal , but Alice does not know which.
Send both messages to Bob Receive both messages
Bob decrypts the since he knows which he selected earlier.

  1. Alice has two messages, , and wants to send exactly one of them to Bob, but does not want to know which Bob receives.
  2. Alice generates a RSA key pair, comprising the modulus , the public exponent and the private exponent
  3. She also generates two random values, and sends them to Bob along with her public modulus and exponent.
  4. Bob picks to be either 0 or 1, and selects either the first or second .
  5. He generates a random value and blinds by computing , which he sends to Alice.
  6. Alice doesn't know which of and Bob chose, so she attempts to unblind with both of her random messages and comes up with two possible values for : and . One of these will be equal to since it will correctly decrypt, while the other will produce another random value that does not reveal any information about .
  7. She blinds the two secret messages with each of the possible keys, , and sends them both to Bob.
  8. Bob knows which of the two messages can be unblinded with , so he is able to compute exactly one of the messages

1-out-of-n oblivious transfer and k-out-of-n oblivious transfer

A 1-out-of-n oblivious transfer protocol can be defined as a natural generalization of a 1-out-of-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.

1-out-of-n oblivious transfer is incomparable to private information retrieval
Private information retrieval
In cryptography, a private information retrieval protocol allows a user to retrieve an item from a server in possession of a database without revealing which item they are retrieving...

 (PIR).
On the one hand, 1-out-of-n oblivious transfer imposes an additional privacy requirement for the database: namely, that the receiver learn at most one of the database entries. On the other hand, PIR requires communication sublinear in n, whereas 1-out-of-n oblivious transfer has no such requirement.

1-n oblivious transfer protocols were proposed, e.g., by Moni Naor
Moni Naor
Moni Naor is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His adviser was Manuel Blum....

 and Benny Pinkas http://www.wisdom.weizmann.ac.il/~bennyp/PAPERS/ot.ps, William Aiello, Yuval Ishai and Omer Reingold
Omer Reingold
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs...

 http://www.wisdom.weizmann.ac.il/~reingold/publications/AIR.PS, Sven Laur and Helger Lipmaa http://www.cs.ut.ee/~lipmaa/papers/ll07.

Brassard
Gilles Brassard
Gilles Brassard was born in Montreal, Canada, in 1955. He received a Masters degree from the Université de Montréal in 1975, and obtained his Ph.D. in Computer Science from Cornell University in 1979, working in the field of cryptography with John Hopcroft as his advisor...

, Crépeau
Claude Crépeau
Dr. Claude Crépeau is a professor in the School of Computer Science at McGill University. Ηe was born in Montreal, Quebec, Canada, in 1962. He received a Masters degree from the Université de Montréal in 1986, and obtained his Ph.D. in Computer Science from MIT in 1990, working in the field of...

 and Robert further generalized this notion to k-n oblivious transfer, wherein the receiver obtains a set of "k" messages from the "n" message collection. The set of k messages may be received simultaneously ("non-adaptively"), or they may be requested consecutively, with each request based on previous messages received.

Generalized oblivious transfer

k-n Oblivious transfer is a special case of Generalized oblivious transfer, which was presented by Ishai and Kushilevitz. In that setting, the sender has a set U of n messages, and the transfer constraints are specified by a collection A of permissible subsets of U.
The receiver may obtain any subset of the messages in U that appears in the collection A. The sender should remain oblivious of the selection made by the receiver, while the receiver cannot learn the value of the messages outside the subset of messages that he chose to obtain. The collection A is monotone decreasing, in the sense that it is closed under containment (i.e., if a given subset B is in the collection A, so are all of the subsets of B).
The solution proposed by Ishai and Kushilevitz uses parallel invocations of 1-2 oblivious transfer while making use of a special model of private protocols. Later on, other solutions that are based on secret sharing were published --- one by Bhavani Shankar, Kannan Srinathan, and C. Pandu Rangan, and another by Tamir Tassa.

Origins

In the early seventies Stephen Wiesner
Stephen Wiesner
Stephen J. Wiesner is a research physicist currently living in Israel. As a graduate student at Columbia University in New York in the late 1960s and early 1970s, he discovered several of the most important ideas in quantum information theory, including quantum money , quantum multiplexing...

 introduced a primitive called multiplexing in his seminal paper "Conjugate Coding",
which was the starting point of quantum cryptography
Quantum cryptography
Quantum key distribution uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages...

. 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.

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK