Efficient non-interactive secure computation

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 fact that known solutions make a non-black-box use of cryptographic 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 a 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(κ) calls are sufficient for each gate in a (large) boolean circuit computing f, where κ is a statistical security parameter guaranteeing at most 2 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 a 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 Ω(κ) 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2011, 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Pages406-425
Number of pages20
DOIs
StatePublished - 2011
Event30th Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, EUROCRYPT 2011 - Tallinn, Estonia
Duration: May 15 2011May 19 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6632 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other30th Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, EUROCRYPT 2011
CountryEstonia
CityTallinn
Period5/15/115/19/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient non-interactive secure computation'. Together they form a unique fingerprint.

Cite this