OT-combiners via secure computation. (English) Zbl 1162.94366

Canetti, Ran (ed.), Theory of cryptography. Fifth theory of cryptography conference, TCC 2008, New York, USA, March 19–21, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78524-8/pbk). Lecture Notes in Computer Science 4948, 393-411 (2008).
Summary: An OT-combiner implements a secure oblivious transfer (OT) protocol using oracle access to \(n\) OT-candidates of which at most \(t\) may be faulty. We introduce a new general approach for combining OTs by making a simple and modular use of protocols for secure computation. Specifically, we obtain an OT-combiner from any instantiation of the following two ingredients: (1) a \(t\)-secure \(n\)-party protocol for the OT functionality, in a network consisting of secure point-to-point channels and a broadcast primitive; and (2) a secure two-party protocol for a functionality determined by the former multiparty protocol, in a network consisting of a single OT-channel. Our approach applies both to the “semi-honest” and the “malicious” models of secure computation, yielding the corresponding types of OT-combiners.
Instantiating our general approach with secure computation protocols from the literature, we conceptually simplify, strengthen the security, and improve the efficiency of previous OT-combiners. In particular, we obtain the first constant-rate OT-combiners in which the number of secure OTs being produced is a constant fraction of the total number of calls to the OT-candidates, while still tolerating a constant fraction of faulty candidates \((t = \Omega (n))\). Previous OT-combiners required either \(\omega (n)\) or poly\((k)\) calls to the \(n\) candidates, where \(k\) is a security parameter, and produced only a single secure OT.
We demonstrate the usefulness of the latter result by presenting several applications that are of independent interest. These include:
Constant-rate OTs from a noisy channel. We implement \(n\) instances of a standard \({2\choose 1}\)-OT by communicating just \(O(n)\) bits over a noisy channel (binary symmetric channel). Our reduction provides unconditional security in the semi-honest model. Previous reductions of this type required the use of \(\Omega (kn)\) noisy bits.
Better amortized generation of OTs. We show that, following an initial “seed” of \(O(k)\) OTs, each additional OT can be generated by only computing and communicating a constant number of outputs of a cryptographic hash function. This improves over a protocol of Ishai et al. (Crypto 2003), which obtained similar efficiency in the semi-honest model but required \(\Omega (k)\) applications of the hash function for generating each OT in the malicious model.
For the entire collection see [Zbl 1130.94001].


94A60 Cryptography
Full Text: DOI