**
Efficient Non-interactive Secure Computaion
**

*
Yuval Ishai,
eyal Kushilevitz,
Rafail Ostrovsky,
Manoj Prabhankaran,
Amit Sahai
*

**
Abstract:
**

Suppose that a receiver r wishes to publish an encryption of her secret input x so that every sender S, holding an input y, can reveal f(x,y) to r by sending her a single message.This should be done while simultaneously protecting the secrecy of y against a corrupted R and preventing a corrupted S from having an unfair influence on the output of R beyond what is allowed by F.

When the parties are semi-honest, practical solutions can be based on Yao's garbled circuit technique.However, for the general problem when the parties, or even S alone, may be malicious, all known polynomial-time solutions are highly inefficient. This is due in part to the factthat known solutions make a non-black-box use of cryotigraohic primitives, e.g., for providing non-interactive zero-knowledge proofs of statements involving cryptographic computations on secrets.

Motivated by the above question, we consider the problem of secure two-party computation in a model that allows only parallel calls to an ideal oblivious transfer (OT) oracle with no additional interaction. We obtain the following results.

**Feasibility**. We present the first general protocols in this model which only make a "black-box" use of pseudorandom generator (PRG). All previous OT-based protocols either make a non-black-box use of cryptographic primitives or require multiple rounds of interaction.

**Efficiency**. we also consider the question of minimizing the asymptotic number of PRG calls made by such protocols. We show that "polylog (k) are sufficient for each gate in a (large) boolean circuit computing F, where k is a statistical security parameter guaranteeing at most 2^{- k } simulation error of a malicious sender.
Furthermore, the number of PRG calls per gate can be made "constant" by settling for a relaxed notion of security which allows Malicious S to arbitrarily correlate the event that R detects cheating with the input of R. This improves over the state of the art also for interactive constant-round black-box protocols, which required
Ω(k) PRG calls per gate, even with similar relaxations of the notion of Security.

combining the above results with 2-message (parallel) OT protocols in the CRS model, we get the first solutions to the initial motivating question which only make a black-box use of standard "cryptographic" primitives.

**comment:**
Eurocrypt 2011: 406-425

Fetch PDF file of the paper

Back to Publications List |