Oblivious transfer

Oblivious transfer

In cryptography, 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. Rabin1. 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 Lempel2, 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, 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 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.3

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: that is given an implementation of oblivious transfer it is possible to securely evaluate any polynomial time computable function without any additional primitive.4

Contents

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 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 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), is general, but can be instantiated using RSA encryption as follows.

Alice Bob
Secret Public Calculus Secret Public Calculus
m0,m1 Messages to be sent
d N,e Generate RSA key pair and send public portion to Bob \Rightarrow N,e Receive public key
x0,x1 Generate two random messages \Rightarrow x0,x1 Receive random messages
k,b,xb Choose b \in (0,1), x_b \in (x_0, x_1) and generate random k
v \Leftarrow v = (x_b + k^e) \mod N Compute the encryption of k, blind with xb and send to Alice
\begin{align}k_0 & = (v - x_0)^d\mod N \\k_1 & = (v - x_1)^d \mod N\end{align} One of these will equal k, but Alice does not know which.
\begin{align}m'_0 = m_0 + k_0 \\ m'_1 = m_1 + k_1\end{align} Send both messages to Bob \Rightarrow m'0,m'1 Receive both messages
mb = m'bk Bob decrypts the m'b since he knows which xb he selected earlier.
  1. Alice has two messages, m0,m1, 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 N, the public exponent e and the private exponent d
  3. She also generates two random values, x0,x1 and sends them to Bob along with her public modulus and exponent.
  4. Bob picks b to be either 0 or 1, and selects either the first or second xb.
  5. He generates a random value k and blinds xb by computing v = (x_b + k^e)\mod N, which he sends to Alice.
  6. Alice doesn't know which of x0 and x1 Bob chose, so she attempts to unblind with both of her random messages and comes up with two possible values for k: k_0 = (v - x_0)^d\mod N and k_1 = (v - x_1)^d\mod N. One of these will be equal to k since it will correctly decrypt, while the other will produce another random value that does not reveal any information about k.
  7. She blinds the two secret messages with each of the possible keys, m'0 = m0 + k0 m'1 = m1 + k1, and sends them both to Bob.
  8. Bob knows which of the two messages can be unblinded with k, so he is able to compute exactly one of the messages mb = m'bk

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 (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 and Benny Pinkas [1], William Aiello, Yuval Ishai and Omer Reingold [2], Sven Laur and Helger Lipmaa [3].

Brassard, Crépeau and Robert further generalized this notion to k-n oblivious transfer5, 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 received6.

Generalized oblivious transfer

k-n Oblivious transfer is a special case of Generalized oblivious transfer, which was presented by Ishai and Kushilevitz7. 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 Rangan8, and another by Tamir Tassa9.

Origins

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[4]. 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.


See also

  • Secure multiparty computation
  • Zero knowledge proof

References

  • ^0. Stephen Wiesner, "Conjugate coding", Sigact News, vol. 15, no. 1, 1983, pp. 78 - 88; original manuscript written circa 1970.
  • ^1. Michael O. Rabin. "How to exchange secrets by oblivious transfer." Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981. Scanned handwriting on eprint.iacr.org archive. Typed version available on Dousti's homepage (Alternate link on Google Docs).
  • ^2. 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 Catuscia Palamidessi's page
  • ^3. 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
  • ^4. Joe Kilian. "Founding Cryptography on Oblivious Transfer", Proceedings, 20th Annual ACM Symposium on the Theory of Computation (STOC), 1988. Paper at ACM portal (subscription required)
  • ^5. Gilles Brassard, Claude Crépeau and Jean-Marc Robert. "All-or-nothing disclosure of secrets." In Advances in Cryptology: CRYPTO ’86, volume 263 of LNCS, pages 234–238. Springer, 1986.
  • ^6. Moni Naor and Benny Pinkas. "Oblivious transfer with adaptive queries." In Advances in Cryptology: CRYPTO ’99, volume 1666 of LNCS, pages 573–-590. Springer, 1999.
  • ^7. Yuval Ishai and Eyal Kushilevitz. "Private simultaneous messages protocols with applications." In Proc. of ISTCS’97, IEEE Computer Society, pages 174–-184, 1997.
  • ^8. Bhavani Shankar, Kannan Srinathan and C. Pandu Rangan. "Alternative protocols for generalized oblivious transfer". In Proc. of ICDCN’08, LNCS 4904, pages 304-–309, 2008.
  • ^9. Tamir Tassa. "Generalized oblivious transfer by secret sharing". Designs, Codes and Cryptography, Volume 58:1, pages 11-21, January 2011. Paper at openu.ac.il

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • oblivious transfer — noun A transfer in which a sender sends some information to a receiver but does not know what is received …   Wiktionary

  • oblivious — adjective a) Lacking awareness; unmindful. b) Failing to remember; forgetful. See Also: oblivion, oblivious transfer …   Wiktionary

  • Yao's Millionaires' Problem — is a secure multiparty communication problem which was introduced by Andrew Yao, a prominent computer scientist and computational theorist. The problem discusses two millionaires, Alice and Bob, who are interested in knowing which of them is… …   Wikipedia

  • Michael O. Rabin — Michael Oser Rabin Born September 1, 1931 (1931 09 01) (age 80) Breslau …   Wikipedia

  • Private information retrieval — In cryptography, a private information retrieval (PIR) protocol allows a user to retrieve an item from a server in possession of a database without revealing which item she is retrieving. PIR is a weaker version of 1 out of n oblivious transfer,… …   Wikipedia

  • Забывчивая передача — В криптографии, протокол Забывчивая передача (часто сокращается как OT oblivious transfer) это тип протокола передачи данных, в котором передатчик передает по одному возможные части информации получателю, но не запоминает (является забывчивым),… …   Википедия

  • Michael J. Fischer — Michael John Fischer (born 1942) is a computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity. Contents 1 Career 2 Work 2.1 …   Wikipedia

  • Quadratic residue — In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: Otherwise, q is called a quadratic nonresidue modulo n. Originally an abstract… …   Wikipedia

  • OT — may refer to: Contents 1 Organizations 2 Science and technology 3 Medicine …   Wikipedia

  • Shimon Even — Infobox Scientist name = Shimon Even image width = caption = birth date = birth date|1935|6|15 birth place = death date = death date|2004|5|1 death place = residence = citizenship = nationality = ethnicity = field = Computer Science, Cryptography …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”