Journal of Xidian University

Oblivious transfer with extractors

Boting Yang

Published Jan 1, 2004• 0 citations

Abstract

Reductions among oblivious transfers have a long history in cryptography. This paper describes a 21-OT~k protocol that can be reduced to a single execution of UOT by using privacy amplification with extractors. An extractor allows to efficiently isolate the randomness of some source into virtually-random bits, using a small number of perfectly-random bits as a catalyst. With extractors, less information is transmitted and the leaked information is at most 2~(-n~(-1/2-o(1))) bits. The conditions under which the protocol is unconditionally secure are investigated.

Related papers

Extracting Correlations

Yuval Ishai, Eyal Kushilevitz Z, Rafail Ostrovsky +1 more

Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.

Annual Symposium on Foundations of Computer ScienceOct 1, 200947 citations

Oblivious-Transfer Amplification

Jürg Wullschleger

Oblivious transfer is a primitive of paramount importance in cryptography or, more precisely, two- and multi-party computation due to its universality. Unfortunately, oblivious transfer cannot be achieved in an unconditionally secure way for both parties from scratch. Therefore, it is a natural question what information-theoretic primitives or computational assumptions oblivious transfer can be based on. The results in our thesis are threefold. First, we present a protocol that implements oblivious transfer from a weakened oblivious transfer called universal oblivious transfer, where one of the two players may get additional information. Our reduction is about twice as efficient as previous results. Weak oblivious transfer is an even weaker form of oblivious transfer, where both players may obtain additional information about the other player's input, and where the output can contain errors. We give a new, weaker definition of weak oblivious transfer, as well as new reductions with a more detailed analysis. Finally, we carry over our results to the computational setting and show how a weak oblivious transfer that is sometimes incorrect and only mildly secure against computationally bounded adversaries can be strengthened.

arXiv:cs/0608076Aug 18, 20065 citations

More Efficient Oblivious Transfer and Extensions for Faster Secure Computation.

Gilad Asharov, Yehuda Lindell, Thomas H. Schneider +1 more

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure com-putation becomes more practical, the need for practical large scale oblivious transfer protocols is becoming more evident. Oblivious transfer extensions are protocols that enable a relatively small number of “base-OTs ” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (CRYPTO 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (CRYPTO 2012) presented an efficient OT extension protocol for the setting of active adversaries, that is secure in the random oracle model. In this work, we present an OT extension protocol for the setting of malicious adversaries that is more efficient and uses less communication than previous works. In addition, our protocol can be proven secure in both the random oracle model, and in the standard model with a type of correlation robustness. Given the importance of OT in many secure computation protocols, increasing the efficiency of OT extensions is another important step forward to making secure

Jan 1, 20130 citations

Efficient oblivious transfer protocols

Moni Naor, Benny Pinkas B

1 IntroductionOblivious Transfer (OT) protocols allow one party, the sender, to transmit part of its inputs to another party, the chooser, in a manner that protects both of them: the sender is assured that the chooser does not receive more information than it is entitled, while the chooser is assured that the sender does not learn which part of the inputs it received. OT is used as a key component in many applications of cryptography. Its computational requirements are quite demanding and they are likely to be the bottleneck in many applications that invoke it.1.1 Contributions.This paper presents several significant improvements to oblivious transfer (OT) protocols of strings, and in particular: (i) Improving the efficiency of applications which many invocations of oblivious transfer. (ii) Providing the first two-round OT protocol whose security analysis does not invoke the random oracle model.

Symposium on Discrete AlgorithmsJan 9, 2001646 citations

reduction of 1 out of n oblivious transfers in random oracle model

Bao Li, Hongda Li, Guangwu Xu +1 more

We first present a protocol which reduces 1-out-of-n oblivious transfer OT m to 1out-of-n oblivious transfer OT k for n > 2 in random oracle model, and show that the protocol is secure against malicious sender and semi-honest receiver. Then, by employing a cut-and-choose technique, we obtain a variant of the basic protocol which is secure against a malicious receiver.

Jan 1, 20030 citations

Efficient reduction of 1 out of n oblivious transfers in random oracle model.

Bao Li, Hongda Li, Guangwu Xu +1 more

We first present a protocol which reduces 1-of-n oblivious transfer OT m for n > 2 in random oracle model, and show that the protocol is secure against malicious sender and semi-honest receiver. Then, by employing a cut-and-choose technique, we obtain a variant of the basic protocol which is secure against a malicious receiver.

Jan 1, 20056 citations