Oblivious transfer

Last updated

In cryptography, an oblivious transfer (OT) protocol 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.

Contents

The first form of oblivious transfer was introduced in 1981 by Michael O. Rabin. [1] 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, [2] 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, in which the database is not kept private.

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]

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 λ(N) = (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, Alice the sender has two messages m0 and m1, and wants to ensure that the receiver only learns one. Bob, the receiver, has a bit b and wishes to receive mb without Alice learning b. 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.

AliceBob
CalculusSecretPublicPublicSecretCalculus
Messages to be sent
Generate RSA key pair and send public portion to BobReceive public key
Generate two random messagesReceive 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 BobReceive 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. Bob does not want Alice to know which one he receives.
  2. Alice generates an 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 .
  5. Bob generates a random value uses it to blind by computing , which he sends to Alice.
  6. Alice combines with both of her random values to produce: and . Now will be equal to and the other will be a meaningless random value. However since Alice does not know the value of that Bob chose, she cannot determine which of and is equal to .
  7. She combines the two secret messages with each of the possible keys, and , and sends them both to Bob.
  8. Bob knows , so he is able to compute . However, since he does not know , he cannot compute and so cannot determine .

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. However, assuming single server PIR is a sufficient assumption in order to construct 1-out-of-2 Oblivious Transfer. [5]

1-out-of-n oblivious transfer protocol with sublinear communication was first constructed (as a generalization of single-server PIR) by Eyal Kushilevitz and Rafail Ostrovsky. [6] More efficient constructions were proposed by Moni Naor and Benny Pinkas, [7] William Aiello, Yuval Ishai and Omer Reingold, [8] Sven Laur and Helger Lipmaa. [9] In 2017, Kolesnikov et al., [10] proposed an efficient 1-n oblivious transfer protocol which requires roughly 4x the cost of 1-2 oblivious transfer in amortized setting.

Brassard, Crépeau and Robert further generalized this notion to k-n oblivious transfer, [11] 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. [12]

Generalized oblivious transfer

k-n Oblivious transfer is a special case of generalized oblivious transfer, which was presented by Ishai and Kushilevitz. [13] 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 the 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, [14] and another by Tamir Tassa. [15]

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

Quantum oblivious transfer

Protocols for oblivious transfer can be implemented with quantum systems. In contrast to other tasks in quantum cryptography, like quantum key distribution, it has been shown that quantum oblivious transfer cannot be implemented with unconditional security, i.e. the security of quantum oblivious transfer protocols cannot be guaranteed only from the laws of quantum physics. [17]

See also

Related Research Articles

<span class="mw-page-title-main">Diffie–Hellman key exchange</span> Method of exchanging cryptographic keys

Diffie–Hellman key exchange is a mathematical method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Published in 1976 by Diffie and Hellman, this is the earliest publicly known work that proposed the idea of a private key and a corresponding public key.

<span class="mw-page-title-main">Quantum teleportation</span> Physical phenomenon

Quantum teleportation is a technique for transferring quantum information from a sender at one location to a receiver some distance away. While teleportation is commonly portrayed in science fiction as a means to transfer physical objects from one location to the next, quantum teleportation only transfers quantum information. The sender does not have to know the particular quantum state being transferred. Moreover, the location of the recipient can be unknown, but to complete the quantum teleportation, classical information needs to be sent from sender to receiver. Because classical information needs to be sent, quantum teleportation cannot occur faster than the speed of light.

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest that is widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.

The Digital Signature Algorithm (DSA) is a public-key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. DSA is a variant of the Schnorr and ElGamal signature schemes.

<span class="mw-page-title-main">Blind signature</span> Form of digital signature

In cryptography a blind signature, as introduced by David Chaum, is a form of digital signature in which the content of a message is disguised (blinded) before it is signed. The resulting blind signature can be publicly verified against the original, unblinded message in the manner of a regular digital signature. Blind signatures are typically employed in privacy-related protocols where the signer and message author are different parties. Examples include cryptographic election systems and digital cash schemes.

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party can prove to another party that a given statement is true, while avoiding conveying to the verifier any information beyond the mere fact of the statement's truth. The intuition underlying zero-knowledge proofs is that it is trivial to prove the possession of certain information by simply revealing it; the challenge is to prove this possession without revealing the information, or any aspect of it whatsoever.

Secure multi-party computation is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike traditional cryptographic tasks, where cryptography assures security and integrity of communication or storage and the adversary is outside the system of participants, the cryptography in this model protects participants' privacy from each other.

<span class="mw-page-title-main">Alice and Bob</span> Characters used in cryptography and science literature

Alice and Bob are fictional characters commonly used as placeholders in discussions about cryptographic systems and protocols, and in other science and engineering literature where there are several participants in a thought experiment. The Alice and Bob characters were invented by Ron Rivest, Adi Shamir, and Leonard Adleman in their 1978 paper "A Method for Obtaining Digital Signatures and Public-key Cryptosystems". Subsequently, they have become common archetypes in many scientific and engineering fields, such as quantum cryptography, game theory and physics. As the use of Alice and Bob became more widespread, additional characters were added, sometimes each with a particular meaning. These characters do not have to refer to people; they refer to generic agents which might be different computers or even different programs running on a single computer.

In cryptography, a private information retrieval (PIR) protocol is a protocol that allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. PIR is a weaker version of 1-out-of-n oblivious transfer, where it is also required that the user should not get information about other database items.

The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher Elgamal in 1985.

In cryptography, the Rabin signature algorithm is a method of digital signature originally proposed by Michael O. Rabin in 1978.

Secure two-party computation (2PC) a.k.a. Secure function evaluation is sub-problem of secure multi-party computation (MPC) that has received special attention by researchers because of its close relation to many cryptographic tasks. The goal of 2PC is to create a generic protocol that allows two parties to jointly compute an arbitrary function on their inputs without sharing the value of their inputs with the opposing party. One of the most well known examples of 2PC is Yao's Millionaires' problem, in which two parties, Alice and Bob, are millionaires who wish to determine who is wealthier without revealing their wealth. Formally, Alice has wealth , Bob has wealth , and they wish to compute without revealing the values or .

In cryptography, a three-pass protocol for sending messages is a framework which allows one party to securely send a message to a second party without the need to exchange or distribute encryption keys. Such message protocols should not be confused with various other algorithms which use 3 passes for authentication.

Entanglement distillation is the transformation of N copies of an arbitrary entangled state into some number of approximately pure Bell pairs, using only local operations and classical communication.

Yao's Millionaires' problem is a secure multi-party computation problem introduced in 1982 by computer scientist and computational theorist Andrew Yao. The problem discusses two millionaires, Alice and Bob, who are interested in knowing which of them is richer without revealing their actual wealth.

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical communication. For example, it is impossible to copy data encoded in a quantum state. If one attempts to read the encoded data, the quantum state will be changed due to wave function collapse. This could be used to detect eavesdropping in quantum key distribution (QKD).

Garbled circuit is a cryptographic protocol that enables two-party secure computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a Boolean circuit.

Consider two remote players, connected by a channel, that don't trust each other. The problem of them agreeing on a random bit by exchanging messages over this channel, without relying on any trusted third party, is called the coin flipping problem in cryptography. Quantum coin flipping uses the principles of quantum mechanics to encrypt messages for secure communication. It is a cryptographic primitive which can be used to construct more complex and useful cryptographic protocols, e.g. Quantum Byzantine agreement.

Quantum secret sharing (QSS) is a quantum cryptographic scheme for secure communication that extends beyond simple quantum key distribution. It modifies the classical secret sharing (CSS) scheme by using quantum information and the no-cloning theorem to attain the ultimate security for communications.

References

  1. Michael O. Rabin. "How to exchange secrets with oblivious transfer." Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981. Scanned handwriting + typed version on eprint.iacr.org archive. Typed version available on Dousti's homepage.
  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.
  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. Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky: Single Database Private Information Retrieval Implies Oblivious Transfer. EUROCRYPT 2000: 122-138
  6. Eyal Kushilevitz, Rafail Ostrovsky: Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. FOCS 1997: 364-373
  7. Moni Naor and Benny Pinkas (1990). Oblivious Polynomial Evaluation 31st STOC
  8. William Aiello, Yuval Ishai and Omer Reingold (2001) Priced Oblivious Transfer: How to Sell Digital Goods EUROCRYPT '01 Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, pages 119–135
  9. Sven Laur and Helger Lipmaa (2007). "A New Protocol for Conditional Disclosure of Secrets And Its Applications". In Jonathan Katz and Moti Yung, editors, ACNS, Lecture Notes in Computer Science4521: 207–225. Springer, Heidelberg.
  10. Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu (2017). "Efficient batched oblivious prf with applications to private set intersection". In Edgar R.Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 16, pages 818–829. ACM Press, October 2016.
  11. 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.
  12. 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.
  13. Yuval Ishai and Eyal Kushilevitz. "Private simultaneous messages protocols with applications." In Proc. of ISTCS’97, IEEE Computer Society, pages 174–184, 1997.
  14. 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.
  15. 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
  16. Stephen Wiesner, "Conjugate coding", Sigact News, vol. 15, no. 1, 1983, pp. 78–88; original manuscript written circa 1970.
  17. Lo, H.-K. (1997). "Insecurity of quantum secure computations". Phys. Rev. A. 56 (2): 1154–1162. arXiv: quant-ph/9611031 . Bibcode:1997PhRvA..56.1154L. doi:10.1103/PhysRevA.56.1154. S2CID   17813922.