Assume A owns t secret k-bit strings. She is willing to disclose one of them to B, at his choosing, provided he does not learn anything about the other strings. Conversely, B does not want A to learn which secret he chose to learn. A protocol for the above task is said to implement one-out-of-t string oblivious transfer, denoted (/sup t//sub 1/)-OT/sup k//sub 2/. This primitive is particularly useful in a variety of cryptographic settings. An apparently simpler task corresponds to the case k=1 and t=2 of two 1-bit secrets: this is known as one-out-of-two bit oblivious transfer, denoted (/sup 2//sub 1/)-OT/sub 2/. We address the question of implementing (/sup t//sub 1/)-OT/sup k//sub 2/ assuming the existence of a (/sup 2//sub 1/)-OT/sub 2/. In particular, we prove that unconditionally secure (/sup 2//sub 1/)-OT/sup k//sub 2/ can be implemented from /spl Theta/(k) calls to (/sup 2//sub 1/)-OT/sub 2/. This is optimal up to a small multiplicative constant. Our solution is based on the notion of self-intersecting codes. Of independent interest, we give several efficient new constructions for such codes. Another contribution of this paper is a set of information-theoretic definitions for correctness and privacy of unconditionally secure oblivious transfer.
Assume A owns t secret k-bit strings. She is willing to disclose one of them to B, at his choosing, provided he does not learn anything about the other strings. Conversely, B does not want A to learn which secret he chose to learn. A protocol for the above task is said to implement one-out-of-t string oblivious transfer, denoted (/sup t//sub 1/)-OT/sup k//sub 2/. This primitive is particularly useful in a variety of cryptographic settings. An apparently simpler task corresponds to the case k=1 and t=2 of two 1-bit secrets: this is known as one-out-of-two bit oblivious transfer, denoted (/sup 2//sub 1/)-OT/sub 2/. We address the question of implementing (/sup t//sub 1/)-OT/sup k//sub 2/ assuming the existence of a (/sup 2//sub 1/)-OT/sub 2/. In particular, we prove that unconditionally secure (/sup 2//sub 1/)-OT/sup k//sub 2/ can be implemented from /spl Theta/(k) calls to (/sup 2//sub 1/)-OT/sub 2/. This is optimal up to a small multiplicative constant. Our solution is based on the notion of self-intersecting codes. Of independent interest, we give several efficient new constructions for such codes. Another contribution of this paper is a set of information-theoretic definitions for correctness and privacy of unconditionally secure oblivious transfer.
Assume A owns t secret k--bit strings. She is willing to disclose one of them to B, at his choosing, provided he does not learn anything about the other strings. Conversely, B does not want A to learn which secret he chose to learn. A protocol for the above task is said to implement One-out-of-t String Oblivious Transfer, denoted ( t 1 )--OT k 2 . This primitive is particularly useful in a variety of cryptographic settings. An apparently simpler task corresponds to the case k = 1 and t = 2 of two one-bit secrets: this is known as One-out-of-two Bit Oblivious Transfer, denoted ( 2 1 )--OT 2 . We address the question of implementing ( t 1 )--OT k 2 assuming the existence of a ( 2 1 )--OT 2 . In particular, we prove that unconditionally secure ( 2 1 )--OT k 2 can be implemented from \\Theta(k) calls to ( 2 1 )--OT 2 . This is optimal up to a small multiplicative constant. Our solution is based on the notion of self-intersecting codes. Of independent interest, we give several...
i (:)-OT, (one-out-of-two Bit Oblivious Transfer) is a technique by which a party S owning two secret bits b,bl, can transfer one of them b, to another party R, who chooses c. This is done in a way that does not release any bias about bz to R nor any bias about c to S. How can one build a 2TO-(i) ((;)-OT2 from R to S) given a (i)-OT, (from S to a)? This question is interesting because in many scenarios, one of the two parties will be much more powerful than the other. In the current paper we answer this question and show a number of related extensions. One interesting extension of this transfer is the (:)-OTk (one-out-of-two String O.T.) in which the two secrets qo, q1 are elements of CFk(2) instead of bits. We show that $TO-(:) can be obtained at about the same cost as (3-OT:, in terms of number of cab to (i)-OTz.
We propose efficient and secure (string) oblivious transfer (OT/sup 1//sub n/) schemes for any n/spl ges/2. We build our OT/sup 1//sub n/ scheme from fundamental cryptographic techniques directly. The receiver's choice is unconditionally secure and the secrecy of the unchosen secrets is based on the hardness of the decisional Diffie-Hellman problem. Some schemes achieve optimal efficiency in terms of the number of rounds and the total number of exchanged messages for the case that the receiver's choice is unconditionally secure. The distinct feature of our scheme is that the system-wide parameters are independent of n and universally usable, that is, all possible receivers and senders use the same parameters and need no trapdoors specific to each of them. We extend our OT/sup 1//sub n/ schemes to distributed oblivious transfer schemes. Our distributed OT/sup 1//sub n/ schemes take full advantage of the research results of secret sharing. For applications, we present a method of transforming any (single-database) PIR protocol into a symmetric PIR protocol by slightly increasing the communication cost only.
Oblivious transfer, a central functionality in modern cryptography, allows a party to send two one-bit messages to another who can choose one of them to read, remaining ignorant about the other, whereas the sender does not learn the receiver's choice. Oblivious transfer the security of which is information-theoretic for both parties is known impossible to achieve from scratch. The joint behavior of certain bi-partite quantum states is non-local, i.e., cannot be explained by shared classical information. In order to better understand such behavior, which is classically explainable only by communication, but does not allow for it, Popescu and Rohrlich have described a "non-locality machine": Two parties both input a bit, and both get a random output bit the XOR of which is the AND of the input bits. We show a close connection, in a cryptographic sense, between OT and the "PR primitive." More specifically, unconditional OT can be achieved from a single realization of PR, and vice versa. Our reductions, which are single-copy, information-theoretic, and perfect, also lead to a simple and optimal protocol allowing for inverting the direction of OT
Roughly speaking a protocol is a way of exchanging messages so that each party gains some specified information. Correctness and privacy are fundamental constraints to the notion of a secure protocol. Essentially, correctness guarantees that the information the parties learn in executing a protocol is what was specified. Privacy guarantees that they cannot learn more than that. We investigate correctness and privacy for the primitive notion of oblivious transfer protocols. As introduced by Rabin, in an oblivious transfer a party S (the sender) owning a secret message m discloses this message to another party R (the receiver) with probability 1 2 . S does not find out whether R did get the message or not. A different version of this notion (1-out-of-2-oblivious transfer) was introduced by Even, Goldreich and Lempel. Traditionally, correctness and privacy were guaranteed assuming that the parties had bounded computational resources and that some appropriate mathematical problems were in...
Interactive Hashing has featured as an essential ingredient in protocols realizing a large variety of cryptographic tasks. We present a study of this important cryptographic tool in the information theoretic context. We start by presenting a security definition which is independent of any particular setting or application. We then show that a standard implementation of Interactive Hashing satisfies all the conditions of our definition. Our proof of security improves upon previous ones in several ways. Despite its generality, it is considerably simpler. Moreover, it establishes a tighter upper bound on the cheating probability of a dishonest sender. Specifically, we prove that if the fraction of good strings for a dishonest sender is f, then the probability that both outputs will be good is no larger than 15.6805· f. This upper bound is valid for any f and is tight up to a small constant since a sender acting honestly would get two good outputs with probability very close to f. We illustrate the potential of Interactive Hashing as a cryptographic primitive by demonstrating efficient reductions of String Oblivious Transfer with string length k to Bit Oblivious Transfer and several weaker variants. Our reductions incorporate tests based on Interactive Hashing that allow the sender to verify the receiver's adherence to the protocol without compromising the latter's privacy. This allows a much more efficient use of the available entropy without any appreciable impact on security. As a result, for Bit OT and most of its variants n = (1 + epsilon) k executions suffice, improving efficiency by a factor of two or more compared to the most efficient reductions that do not use Interactive Hashing. As it is theoretically impossible to achieve an expansion factor n/k smaller than 1, our reductions are in fact asymptotically optimal. They are also more general since they place no restrictions on the types of 2-universal hash families used for Privacy Amplification. Lastly, we present a direct reduction of String OT to Rabin OT which uses similar methods to achieve an expansion factor of 2 + epsilon which is again asymptotically optimal.