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.
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.
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.
Interactive hashing has featured as an essential ingredient in protocols realizing a large variety of cryptographic tasks, notably oblivious transfer in the bounded storage model. In interactive hashing, a sender transfers a bit string to a receiver such that two strings are received, the original string and a second string that appear to be chosen at random. This paper presents a self-contained, information theoretic study of interactive hashing. We start by formalizing the notion of interactive hashing as a cryptographic primitive, disentangling it from the specifics of its various implementations. To this end, we present an application-independent set of information theoretic conditions that all interactive hashing protocols must ideally satisfy. We then provide a detailed analysis of a standard implementation of interactive hashing which is shown to satisfy all the conditions of our definition. Our analysis represents a significant improvement over previous attempts in more restricted contexts. Despite its generality, it offers a considerably simpler proof of security. Moreover, it establishes a tighter upper bound on the cheating probability of a dishonest sender, who wishes to manipulate the protocol so that both output strings have some rare desirable property. In particular, we prove that if the set of desirable strings for the dishonest sender represents a fraction f of all strings, then the probability that both outputs will be from this set 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 outputs from this set with probability very close to f. We illustrate the power of interactive hashing as a cryptographic tool by surveying protocols achieving oblivious transfer in the bounded storage model, which typically rely heavily on interactive hashing.
Rabin oblivious transfer is the cryptographic task where Alice wishes to receive a bit from Bob but it may get lost with probability 1/2. In this work, we provide protocol designs which yield quantum protocols with improved security. Moreover, we provide a constant lower bound on any quantum protocol for Rabin oblivious transfer. To quantify the security of this task with asymmetric cheating definitions, we introduce the notion of cheating advantage which may be of independent interest in the study of other asymmetric cryptographic primitives.
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.
Abstract. In this paper we propose an efficient OT N 1 scheme in the bounded storage model, which is provably secure without complexity assumptions. Under the assumption that a public random string of M bits is broadcasted, the protocol is secure against any computationally unbounded dishonest receiver who can store τM bits, τ < 1. The protocol requires the sender and the receiver to store N · O ( √ kM) bits, where k is a security parameter. When N = 2, our protocol is similar to that of Ding [10] but has more efficient round and communication complexities. Moreover, in case of N> 2, if the sender and receiver can store N ·O ( √ kM) bits, we are able to construct a protocol for OT N 1 which has almost the same complexity as in OT 2 1 scheme. Ding’s protocol was constructed by using the interactive hashing protocol which is introduced by Noar, Ostrovsky, Venkatesan and Yung [15] with very large roundcomplexity. We propose an efficiently extended interactive hashing and analyze its security. This protocol answers partially an open problem raised in [10]. 1
Oblivious transfer (OT) protocol is an essential tool in cryptography that provides a wide range of applications such as secure multi-party computation, private information retrieval, private set intersection, contract signing, and privacy-preserving location-based services. The OT protocol has different variants such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. In the OT (one-out-of-2, one-out-of- n , and OT extension) protocol, the sender has a set of messages, whereas the receiver has a key. The receiver sends that key to the sender in a secure way; the sender cannot get any information about the received key. The sender encrypts every message by operating on every message using the received key and sends all the encrypted messages to the receiver. The receiver is able to extract only the required message using his key. However, in the k -out-of- n OT protocol, the receiver sends a set of k keys to the sender, and in replay, the sender sends all the encrypted messages. The receiver uses his keys and extracts the required messages, but it cannot gain any information about the messages that it has not requested. Generally, the OT protocol requires high communication and computation cost if we transfer millions of oblivious messages. The OT extension protocol provides a solution for this, where the receiver transfers a set of keys to the sender by executing a few numbers of OT protocols. Then, the sender encrypts all the messages using cheap symmetric key cryptography with the help of a received set of keys and transfers millions of oblivious messages to the receiver. In this work, we present different variants of OT protocols such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. Furthermore, we cover various aspects of theoretical security guarantees such as semi-honest and malicious adversaries, universally composable, used techniques, computation, and communication efficiency aspects. From the analysis, we found that the semi-honest adversary-based OT protocols required low communication and computation costs as compared to malicious adversary-based OT protocols.