Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Boolean Circuits
Non Interactive Zero Knowledge
Oblivious Transfer
Polynomial Time
Secure Computation
Secure Twoparty Computation
Subscribe
Academic
Publications
Efficient Noninteractive Secure Computation
Efficient Noninteractive Secure Computation,10.1007/9783642204654_23,Yuval Ishai,Eyal Kushilevitz,Rafail Ostrovsky,Manoj Prabhakaran,Amit Sahai
Edit
Efficient Noninteractive Secure Computation
BibTex

RIS

RefWorks
Download
Yuval Ishai
,
Eyal Kushilevitz
,
Rafail Ostrovsky
,
Manoj Prabhakaran
,
Amit Sahai
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 semihonest, 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 polynomialtime solutions are highly inefficient. This is due in part to the fact that known solutions make a nonblackbox use of cryptographic primitives, e.g., for providing noninteractive zeroknowledge proofs of statements involving cryptographic computations on secrets. Motivated by the above question, we consider the problem of
secure twoparty 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 blackbox use of a pseudorandom generator (PRG). All previous OTbased protocols either make a nonblackbox 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 constantround blackbox protocols, which required Ω(κ) PRG calls per gate, even with similar relaxations of the notion of security. Combining the above results with 2message (parallel) OT protocols in the CRS model, we get the first solutions to the initial motivating question which only make a blackbox use of standard cryptographic primitives.
Conference:
Theory and Application of Cryptographic Techniques  EUROCRYPT
, pp. 406425, 2011
DOI:
10.1007/9783642204654_23
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
References
(43)
Computationally Private Randomizing Polynomials and Their Applications
(
Citations: 28
)
Benny Applebaum
,
Yuval Ishai
,
Eyal Kushilevitz
Conference:
Annual IEEE Conference on Computational Complexity  CCC
, pp. 260274, 2005
Precomputing Oblivious Transfer
(
Citations: 44
)
Donald Beaver
Conference:
International Crytology Conference  CRYPTO
, pp. 97109, 1995
Correlated pseudorandomness and the complexity of private computations
(
Citations: 39
)
Donald Beaver
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 479488, 1996
Multiparty Computation with Faulty Majority
(
Citations: 91
)
Donald Beaver
,
Shafi Goldwasser
Conference:
International Crytology Conference  CRYPTO
, pp. 589590, 1989
The Round Complexity of Secure Protocols (Extended Abstract)
(
Citations: 32
)
Donald Beaver
,
Silvio Micali
,
Phillip Rogaway
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 503513, 1990