Black-Box Constructions of Protocols
for Secure Computation∗
Iftach Haitner†Yuval Ishai‡Eyal Kushilevitz†Yehuda Lindell§
Erez Petrank†
March27,2010
Abstract
It is well known that secure computation without an honest majority requires computational assumptions.An interesting question that therefore arises relates to the way such computational
assumptions are used.Specifically,can the secure protocol use the underlying ,
a one-way trapdoor permutation)in a black-box way,treating it as an oracle,or must it be
nonblack-box(by referring to the code that computes the primitive)?Despite the fact that
many general constructions of cryptographic schemes refer to the underlying primitive in a
black-box wayonly,there are some constructions that are inherently nonblack-box.Indeed,all
known constructions of protocols for general secure computation that are secure in the presence
of a malicious adversary and without an honest majority use the underlying primitive in a
nonblack-box way(requiring to prove in zero-knowledge statements that relate to the primitive).
In this paper,we study whether such nonblack-box use is essential.We answer this question in the negative.Concretely,we present a fully black-box reduction from oblivious transfer with
security against malicious parties to oblivious transfer with security against semi-honest parties.
As a corollary,we get thefirst constructions of general multiparty protocols(with security
against malicious adversaries and without an honest majority)which only make a black-box use
of semi-honest oblivious transfer,or alternatively a black-box use of lower-level primitives such
as enhanced trapdoor permutations or homomorphic encryption.
Keywords:Theory of cryptography,secure computation,black-box reductions,oblivious transfer
∗This paper combines the results appearing in[17]and[22].The last four authors were supported by grant36/03 from the Israel Science Foundation.
block truncated†Microsoft Research,New ail:iftach@microsoft.Most of this work was performed while at the Weizmann Institute of Science.
‡Department of Computer Science,ail:{yuvali,eyalk,erez}@cs.technion.ac.il
§Department of Computer Science,Bar-Ilan ail:lindell@cs.biu.ac.il.Much of this work was carried out while the author was visiting the Technion.
1Introduction
It is a known fact that most cryptographic tasks require the use of computational hardness as-sumptions.These assumptions typically come in two types:specific assumptions like the hardness of factoring,RSA,discrete log and others,and general assumptions like the existence of one-way functions,trapdoor permutations and others.In this paper,we refer to general assumptions and how they are used.Specifically,we consider an intriguing question regarding how secure protocols utilize a primitive that is assumed to carry some hardness property.Here again,there is a clear distinction between two types of uses:
1.Black-box usage:a protocol(or construction)uses a primitive in a black-box way if it
refers only to the input/output behavior of the primitive.1For example,if the primitive is a trapdoor permutation,then the protocol may sample a permutation and its domain,and may compute the permutation and its inverse(if the trapdoor is given).Beyond this,no reference is made to the primitive.In particular,the code used to compute the permutation(or carry out any other task)is not referred to by the protocol.The vast majority of constructions in cryptography are of this black-box type.
2.Nonblack-box usage:a protocol(or construction)uses a primitive in a nonblack-box way
if it refers to the code for computing its functionality.A typical example of a nonblack-box construction is where a Karp reduction is applied to the circuit computing the function,say, in order to prove an N P zero-knowledge proof,as in[15].
A rich and fruitful body of work,initiated in[21],attempts to draw the borders between possibility and impossibility for black-box constructions in cryptography.While many of the relations between primitives are well understood,there are still some important tasks for which the only constructions that we have rely on nonblack-box access to the assumed primitive,yet the existence of a black-box construction is not ruled out.In particular,this is the case for all constructions of public-key encryption s
chemes that are secure against chosen-ciphertext attacks[8,37,30].More relevant to this work is the fact that all known general constructions of multiparty protocols that are secure without an honest majority and in the presence of malicious adversaries,originating from[16],use nonblack-box access to the assumed primitive.2(We note that by“general constructions”,we mean construction that can be used to securely compute any functionality.)
The above phenomenon begs the following informally-stated question:
Is it possible to construct general protocols for secure computation without an honest
majority and with malicious adversaries,given only black-box access to a“low-level”
primitive?
1It is typically also required that the security proof of the construction be black-box in the sense that an adversary breaking the protocol can be used as an oracle in order to break the underlying primitive.In such a case the construction is referred to as a fully black-box reduction.All of the constructions in this paper are in fact fully black-box reductions.See Section2.3and[11,12,36]for further discussion of reductions in cryptography.
2We stress that the above discussion is only true when considering general assumptions.Furthermore,it is only true when considering“low-level primitives”like trapdoor permutations.Specifically,there do exist constructions of secure multiparty protocols that use only black-box access to an oblivious transfer protocol with security against malicious parties[25].However,since it is not known how to construct the latter oblivious transfer protocols using only black-box access to,say trapdoor permutations,the overall construction obtained does not use its“low-level”primitive in a black-box way.
1
Answering the above question is of interest for the following reasons.First,it is of theoretical interest to understand whether or not nonblack-box access to a primitive is necessary for these tasks.An answer to this question would enhance our understanding of how hardness assumptions can(or must)be used.Second,as we have mentioned,the nonblack-box use of the underlying primitive is typically utilized in order to apply a Karp reduction for the purpose of using a(general) zero-knowledge proof.Such reductions are highly inefficient and are unlikely to be very useful in practice.Furthermore,in these protocols the communication complexity depends on the complexity of computing the primitive and the computational complexity grows more than linearly with that of the primitive.(An exception to th
is rule is the communication-efficient compiler presented in[33], which relies on the communication-efficient arguments of[27,31].However,the computational complexity of the protocol of[33]is even worse than the GMW protocol[16].) To illustrate the type of inefficiency resulting from current nonblack-box constructions,con-sider the following hypothetical scenario.Suppose that,due to major advances in cryptanalytic techniques,the security parameter must be large enough so that all basic cryptographic primitives require a full second of computation on a fast CPU.In such a case,would it still be possible to carry out a distributed task like oblivious transfer?Current nonblack-box ,the GMW protocol[16])require parties to prove in zero-knowledge statements that involve the compu-tation of the underlying primitive,say a trapdoor permutation.These zero-knowledge protocols, in turn,invoke cryptographic primitives for any gate of a circuit computing a trapdoor permuta-tion.Since(by our assumption)a trapdoor permutation takes one second to compute,its circuit implementation contains trillions of gates,thereby requiring the protocol trillions of second to run. In contrast,a black-box construction of oblivious transfer from the trapdoor permutation primitive would make the number of invocations of the primitive independent of the complexity of imple-menting the primitive,thus making oblivious transfer feasible even in the hypothetical scenario described above.
We conclude that the current nonblack-box use of the underlying primitives constitutes an obstacle to e
fficiency.It is therefore of great interest to know whether or not it is possible to obtain solutions to these tasks that do not suffer from this obstacle.(We note that the inefficiency of nonblack-box constructions here is quite ironic because in many areas of cryptography,black-box constructions have been shown to have inherent computational limitations[28,10].)Despite the above,we stress that the focus of this paper is not on efficiency,but rather on the theoretical question of whether or not it is possible to obtain the aforementioned black-box constructions.We believe this question to be interesting in its own right.
Our results.We show how to construct protocols for general secure multiparty computation(for the case of no honest majority and malicious adversaries),given black-box access to any oblivious transfer protocol with security against semi-honest adversaries.Using previous constructions,the latter oblivious transfer protocol can be based(in a black-box way)on either homomorphic en-cryption schemes(cf.[1])or enhanced trapdoor permutations(cf.[13]).We note that the standard general constructions of secure computation protocols from“low-level”primitives rely on either enhanced trapdoor permutations or homomorphic encryption schemes.However,all previous pro-tocols used these primitives in an inherently nonblack-box way.This was the case even for protocols that implement very simple functionalities,such as oblivious transfer[35,9].More concretely,we prove the following:
Theorem1.1There exist protocols for securely computing any multiparty functionality without
2
an honest majority and in the presence of static malicious adversaries,that rely only on black-box access to a semi-honest-secure oblivious transfer protocol,to a family of enhanced trapdoor permutations,or to a homomorphic encryption scheme.
We remark that nonblack-box access is not typically used when considering semi-honest ad-versaries[39,16].Rather,the nonblack-box access is utilized in known protocols in order to have the parties prove(in zero-knowledge)that they are correctly following the protocol specification. This is necessary for preventing a malicious adversary from effectively deviating from the protocol instructions.We note also that in the case of an honest majority,it is possible to securely compute any functionality information-theoretically,and without any hardness assumption[2,5].Thus,no primitive at all is needed.For this reason,we focus on the case of no honest majority(including the important two-party case)and malicious adversaries.
Techniques.We prove Theorem1.1by showing that it is possible to construct an oblivious transfer protocol that is secure in the presence of malicious adversaries given only black-box access to an oblivious transfer protocol that is secure in the presence of semi-honest adversaries.Our construction i
s fully black-box meaning that the protocol that is secure in the presence of malicious adversaries uses only black-box access to the semi-honest protocol,and our proof of security shows the existence of an adversary that breaks the semi-honest protocol given black-box access to any adversary that breaks the malicious protocol.Formally,we prove the following:
Theorem1.2The exists a fully black-box reduction from oblivious transfer that is secure in the presence of malicious adversaries to oblivious transfer that is secure in the presence of semi-honest adversaries.
In order to prove Theorem1.2,we begin by constructing oblivious transfer protocols that use only black-box access to semi-honest oblivious transfer,but provide rather weak security guarantees. We then“boost”the security of these protocols in order to obtain protocols that are secure in the presence of malicious adversaries.Previous constructions that have followed this paradigm apply general zero-knowledge proofs to have the parties prove that they are behaving according to the specification of the semi-honest protocol[16].Importantly,these proofs employ a Karp reduction on the protocol specification,they are not black-box.Since we wish to make our construction black-box,we take a different route.Specifically,we begin by introducing the notion of a defensible adversary.In order to describe this notion,we describe what a defense is:a defense is an input and random-tape that is provi
ded by the adversary after the protocol execution concludes.A defense is good if the honest party upon that input and random-tape would have sent the same messages as the adversary sent.Such a defense is a supposed“proof”of honest behavior.However,the adversary need not actually behave honestly and can construct its defense retroactively(after the execution concludes).A protocol is said to be private in the presence of defensible adversaries if privacy is preserved in the event that an adversary provides a good defense.However,in the case that the adversary doesn’t provide a good defense,nothing is guaranteed,and the entire honest party’s input may be learned.This notion is therefore rather weak.We note that known oblivious transfer protocol like that of[9]are not secure under this notion.Thefirst step of our proof is therefore a proof that any semi-honest oblivious transfer protocol can be efficiently modified–in a black-box way–into one that is secure under this notion.Next,we show that it is possible to construct oblivious transfer that is secure in the presence of malicious adversaries from oblivious
3
transfer that is private in the presence of defensible adversaries.Once again,this construction is fully black-box.
We now give a more detailed overview of the construction.Recall that thefirst step is con-structing oblivious transfer protocols that are private in the presence of defensible adversaries from any oblivious transfer that is secure in the presence of semi-honest adversaries.This construction is essentially a very degenerate version of the GMW compiler[16].Specifically,it works by having the parties run a coin-tossing and input commitment protocol.The parties are then supposed to run the protocol using the committed inputs and coins.The defense is then just a decommit-ment;observe that given such a decommitment it is possible to check that the parties behaved in a semi-honest manner,as required.We remark that our transformation from semi-honest security to defensible security is generic and works for all protocols(and not just for oblivious transfer).
Having obtained oblivious transfer that is secure for defensible adversaries,we use this to construct a new oblivious transfer protocol that is still private in the presence of defensible senders, but is secure in the presence of malicious receivers(where security is“full security”according to the ideal/real simulation paradigm).This is achieved using the so-called cut-and-choose technique. That is,many oblivious transfer executions(using random inputs)are run,and the receiver is asked to present a defense for its behavior in half of them.If it indeed presents good defenses,then we are guaranteed that it behaved somewhat honestly in most of the executions.Finally,the oblivious transfer executions are combined into a single instance of oblivious transfer which has the stronger security guarantee.
We stress that much of the difficulty in implementing and analyzing the above step comes from the requirement that the protocol be secure according to the ideal/real simulation paradigm,rather than just private.Indeed,some efficient protocols for oblivious transfer from the literature[34,1,24] are private for both(malicious)parties,but are not fully secure for either party.Nevertheless,we are able to boost both the type of adversary resisted by the protocol(from a defensible to a malicious adversary)and its security guarantee(from privacy to full simulation-based security).
Next,we“reverse”the oblivious transfer ,by switching the sender and receiver roles)in order to obtain a protocol with reversed security properties.Specifically,this next protocol is secure in the presence of malicious senders and private in the presence of defensible receivers. At this point,we reapply our security boosting technique in order to obtain a protocol that is “fully secure”;that is,a protocol that is secure in the presence of malicious senders and receivers. See Figure1for the series of oblivious transfer protocols that we construct.Needless to say,each protocol uses its subprotocol in a black-box way.
Protocol number Security for corrupted sender Security for corrupted receiver
3.3Private for defensible sender Private for defensible receiver
4.2Private for defensible sender Secure for malicious receiver
5.1Secure for malicious sender Private for defensible receiver
In Theorem6.1Secure for malicious sender Secure for malicious receiver Figure1:The progression of our constructions:each protocol uses the previous one as a subprotocol.
We note that Protocol3.3uses any semi-honest oblivious transfer as a starting point and works for any protocol problem and not just oblivious transfer.This is in contrast to our other constructions that are all specifically tailored to oblivious transfer.
4

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。