Secure multiparty computation (MPC) [31,20] enables a set of mutually distrustful parties to compute a joint function while keeping the privacy of their inputs and the correctness of their outputs. The seminal results from the '80s [31,20,5,11,30] as well as the vast majority 15:2
of MPC protocols in the literature were proven secure with respect to a static adversary; that is, security is guaranteed as long as the adversary decides which parties to corrupt at the onset of the execution. A more realistic setting, first considered by Beaver and Haber [4] and by Canetti et al. [10], considers an adaptive adversary, who can dynamically decide which parties to corrupt during the course of the protocol. Adaptive security is known to be strictly stronger than static security with many impossibility results separating the two notions, e.g., [10,9].
In this work we focus on the well-studied setting of perfect security, where all existing separations from the literature no longer hold. Perfectly secure protocols guarantee security facing computationally unbounded adversaries without any error probability. This is a highly desirable property that in some sense provides the strongest security notion for MPC. For example, Kushilevitz et al. [24] showed that any perfectly secure protocol that is proven secure in the standalone model using a straight-line and black-box simulation 1 automatically guarantees security under universal composition (UC) [8]. 2 Most relevant to our work, Canetti et al. [9] showed that any perfect statically secure protocol, satisfying basic requirements, remains secure also in the presence of adaptive adversaries. This result, however, comes with a caveat, since the transformation from static to adaptive security does not preserve the efficiency of the simulation.
Roughly speaking, a protocol is deemed secure if any attack on an execution of the protocol in the real world can be simulated also in an ideal world where a trusted party receives the inputs from all the parties and computes the function on their behalf. It is desirable that the simulator, i.e., the adversary who simulates the attack in the ideal world, will use roughly the same resources as the adversary who carries out the attack on the real-world protocol. In particular, we would like the simulator to run in polynomial time with respect to the running time of the real-world adversary; if so, we say that the simulation is efficient.
Unfortunately, the adaptive simulator in [9] does not run in polynomial time with respect to the real-world adversary. This means that given a perfectly secure protocol against static adversaries with an efficient simulator, the transformation in [9] guarantees adaptive security, albeit with an inefficient simulator. This leads us to the following fundamental question: Does perfect, static security with efficient simulation imply perfect, adaptive security with efficient simulation? Stated differently, is there another generic transformation from static to adaptive security, other than [9], that preserves the efficiency of the simulation? Are there other assumptions on the structure of the protocol and/or on the static simulation that might lead to such an efficient transformation? Or, perhaps, do there exist protocols that are statically secure but for which efficient adaptive simulation simply does not exist?
Efficient vs. inefficient simulation. One may ask whether the efficiency loss in the simulation makes a difference when considering perfect security: If security is anyway guaranteed against computationally unbounded adversaries, does it matter if the simulator is inefficient? Indeed, inefficient simulation is a weaker-yet-acceptable security notion when considering informationtheoretic security.
It turns out that inefficient simulation has an undesirable impact when considering composition of secure protocols. For example, consider a perfectly secure protocol π for computing a function f that is defined over secure communication channels, and consider a computationally secure realization of secure channels over authenticated channels (e.g., using non-committing encryption [10]). If π is secure with efficient simulation, then a composition theorem (e.g., from [7,8]) can be used to derive a computationally secure protocol for f over authenticated channels. However, if the simulation is inefficient then the composition will not go through since it will result with a super-polynomial time adversary that can break the cryptographic assumptions used to realize secure channels.
A case study: on the adaptive security of the BGW protocol. The seminal results of Ben-Or, Goldwasser, and Wigderson [5] and of Chaum, Crépeau, and Damgård [11] show that any function f can be computed by an n-party protocol with perfect security as long as t < n/2 of the parties are corrupted in the semi-honest setting, and as long as t < n/3 are corrupted in the malicious setting. A full proof of security for the BGW protocol was given in 2011 by Asharov and Lindell [1,2]. The proof was specified in the static, standalone setting, and universally composable security and security against adaptive adversaries were derived using the transformations of Kushilevitz et al. [24] and Canetti et al. [9], respectively. However, as discussed above, adaptive security is obtained with an inefficient simulation.
This issue was revisited by Damgård and Nielsen [15], who showed that the semi-honest version of the BGW protocol achieves adaptive security with efficient simulation. However, the result of [15] holds only for circuits in which each output wire is a direct output of a multiplication gate. Obviously, one can manually add such "multiplications with 1" to each output wire. While this seems suffice, there are two reasons why we revisit this problem: First, for linear functions, the semi-honest version of the BGW protocol can tolerate up to n corruptions, whereas the requirement that each output wire is a direct output of a multiplication gate reduces the corruption threshold to t < n/2. Second, this subtlety has been neglected by prior works that relied on [15], e.g., Lin et al. [26,Lem. 6.2] claimed that any degree-2 function can be computed by the BGW protocol in two rounds with adaptive security and efficient simulation. Yet, when adding multiplication gates the round complexity increases, which implies a gap in the literature as there is no proof for the claim mentioned in [26].
Alternatively, one can interpret this additional restriction on the circuit as adding some re-randomization step at the very end of the protocol before the parties reconstruct their output. Is this step essential to achieve adaptive security for all circuits? Can one prove the adaptive security of the original protocol directly, without the additional communication round?
Our work revisits the question of static versus adaptive in perfectly secure multiparty computation. We show that in contrast to the "weaker" definition of adaptive security (i.e., inefficient simulation), perfect static security no longer implies perfect adaptive security when demanding the simulation to be efficient, even when merely considering semi-honest adversaries. Complementarily, we show that the BGW protocol is adaptively secure with efficient simulation even without changing the underlying circuit; this answers an open question posed by Damgård and Nielsen [15]. We focus on semi-honest security, which is I T C 2 0 2 2 15:4
enough to highlight the subtleties that arise; indeed, the gap in the literature discussed above already appears in this setting. We conjecture that the analysis extends to the malicious case using standard secret-sharing techniques.
We proceed to describe our results in more details.
Separating perfect adaptive security from perfect static security. Our first result shows that under some cryptographic assumptions, there is no hope of finding an alternative (efficient) transformation to that of Canetti et al. [9], and that inefficiency of the adaptive simulation is inherent. More precisely, that there exist protocols that admit perfect, static security with efficient simulation but for which an efficient adaptive simulation does not exist.
▶ Theorem 1. Assume the existence of a one-way permutation. Then, there exists an n-party functionality f and a protocol that securely computes f with efficient perfect static simulation, but for which efficient perfect adaptive simulation does not exist.
The theorem is proven by showing a protocol for which all the additional requirements of [9] hold and therefore (inefficient) adaptive simulation does exist for this protocol, but an efficient adaptive simulator can be used to invert the one-way permutation with inversepolynomial probability. Interestingly, this implies that the protocol is regarded as adaptively secure in the perfect setting, but the exact same protocol is not adaptively secure in the computational setting, where both the adversary and the simulator should run in polynomial time in the security parameter. We therefore derive the following somewhat counter-intuitive corollary.
▶ Corollary 2. Assume the existence of a one-way permutation. Then, there exists an n-party functionality f and a protocol that securely computes f with perfect adaptive security, but that does not securely compute f with computational adaptive security.
Revisiting adaptive security in the standalone setting. The above does not rule out the possibility of finding additional requirements from the protocol that would imply efficient adaptive simulation. This is exactly the approach taken by Damgård and Nielsen [15], who showed that under additional requirements of the protocol, an efficient adaptive simulation exists.
The transformation of [15] is directly proved in the UC framework with its full generality, capturing reactive functionalities and concurrency issues at once. However, the strong guarantees do not come without a price, since the requirements from the static simulator must capture multiple input phases (as required for reactive computations) and deal with the technical overhead needed for concurrent composition, e.g., incorporating an "online" environment to the definition. As a small side contribution we simplify this transformation.
Specifically, in addition to proving perfect static security, the transformation of [15] requires an additional (efficient!) algorithm, called "Patch," for sampling randomness that explains the simulated protocol whenever a corruption occurs. The adaptive simulator invokes the static simulator on a dynamically growing set of corrupted parties (initially empty). At any point, the simulation of the protocol towards the adaptive adversary is done by forwarding messages from the adaptive adversary to the static simulator, and vice-versa. Upon a corruption of a new party, say of P i , the Patch algorithm receives the state of the static simulator until this point together with the input and output of P i , and outputs a new state for the static simulator that allows the continuation of the simulation as if P i was statically corrupted from the beginning.
We then propose an alternative recipe for proving universal composability and (efficient) adaptive security in the perfect setting: 1. Prove that the protocol is (efficiently) statically secure in the perfect standalone setting and that the protocol satisfies some natural requirements (similar to those in [9]). 2. Show the existence of an efficient "Patch" algorithm corresponding to the static simulator. 3. We show a transformation (which is essentially a distilled version of [15]) that the protocol is perfectly adaptively secure with an efficient simulator in the standalone setting. 4. Using [24], the protocol is also secure in the perfect adaptive setting with efficient simulation and with universal composability.
We remark that this result is not technically novel and is inspired by [15]. We hope that providing an alternative definition in the standalone setting would simplify proofs of efficient adaptive security in the future, as the designer of the protocol can focus on the standalone setting.
Adaptive security of the BGW protocol. Finally, we follow our recipe proposed above and show that the (semi-honest) BGW protocol is efficiently adaptively secure. No additional step to the protocol is needed, and the proof works for any circuit (as opposed to the proof of [15]). This result solves an open problem raised by [15], whether the assumption on the circuit (that each output wire is a direct output of a multiplication gate) is necessary. This reaffirms the security of the BGW protocol [5], and closes a gap in the proofs of [1,15], providing sound foundations for cryptography.
Further, if f is a linear function, the BGW protocol securely computes f with perfect adaptive security and efficient simulation facing a semi-honest adversary corrupting t < n parties.
Adaptive security is known to be strictly stronger than static security in many settings, with many impossibility results separating the two notions. Below, we compare our separation to existing separations between static and adaptive security from the literature.
The first separation was presented by [10] and relied on a positive error probability of the statically secure protocol. They considered a dealer that secret shares a value to a random set of parties and later announces their identities; an adaptive adversary can corrupt the members of the set and learn the value while a static adversary can only guess this set ahead of time and succeed with negligible (yet positive) probability. In this setting, the seminal protocol of Rabin and Ben-Or [30] that guarantees statistical information-theoretic security is not secure in the adaptive setting, as illustrated by Cramer et al. [14], who gave an adaptively secure variant of the protocol. Separations based on statistical security are different than ours as we consider perfect protocols that have zero error probability.
In the computational-security setting, many statically secure primitives do not remain secure under adaptive corruptions. For example, Nielsen [29] showed that public-key encryption for unbounded messages requires a programmable random oracle. Canetti et al. [9] separated adaptively secure commitments from statically secure ones. Lindell and Zarosim [27] showed that achieving adaptively secure oblivious transfer (OT) requires stronger assumptions than statically secure OT. Katz et al. [23] ruled out adaptively secure fully homomorphic I T C 2 0 2 2 15:6 Static vs. Adaptive Security in Perfect MPC encryption; the latter result was generalized in [13]. Separations based on computational assumptions are different than ours as we consider information-theoretic protocols that remain secure against computationally unbounded adversaries.
Canetti et al. [9] showed a separation based on the ability of the adversary to corrupt a party and change its input to the protocol based on messages that have already been transmitted. Similar separations were illustrated also for broadcast protocols [22,12]. Canetti et al. [9] showed that such separations no longer hold when considering protocols that have a committal round [28], i.e., a fixed round in which all inputs to the protocol are committed. These separations hold only for malicious adversaries that can deviate from the protocol; our separation applies for semi-honest adversaries that cannot deviate from the protocol in any way.
Other separations are known when considering restricted interaction patterns, as was shown by Garay et al. [17] for protocols with sublinear communication, and by Boyle et al. [6] for protocols whose communication graph admits a sublinear cut. Our separation relies on the BGW protocol that induces a complete communication graph.
Finally, Garg and Sahai [18] showed that constant-round MPC with black-box simulation in the plain model cannot tolerate corruption of all of the parties. Our result holds irrespective of the number of rounds and does not require corrupting all the parties.
Organization of the paper. In Section 2 we present a technical overview of our results, in Section 3 the preliminaries, and in Section 4 we prove our separation result, showing the existence of a protocol that has inefficient adaptive simulation but no efficient adaptive simulation (assuming one-way permutations exist). Due to space limitation we omit the definition of secure multiparty computation and the proof of adaptive security of the BGW protocol, and refer the reader to the full version of this paper.
We provide a technical overview of our results. In Section 2.1 we review our separation result, showing the existence of a protocol that has inefficient adaptive simulation but no efficient adaptive simulation (under some cryptographic assumptions). In Section 2.2, we review the adaptive security of the BGW protocol.
Definition of adaptive security. We first recall the definition of adaptive security. We remark that since the transformation of [9] assumes some additional properties from the statically secure protocol and its simulation (specifically, it assumes that the protocol has a straight-line, black-box simulation), our description here incorporates those properties in the informal definition. Given a protocol π, an adaptive adversary might corrupt parties on the fly as the protocol proceeds. Upon corruption, the adversary sees the corrupted party's random tape, the input it used, and all the messages it received so far. From that point on, the adversary completely controls the behavior of P i . As the protocol proceeds, the adversary might decide to corrupt additional parties, as a function of whatever it saw so far.
We follow the ideal/real simulation paradigm and say that a protocol is adaptively secure if for every such an adversary in the real world, there exists a simulator in the ideal world that simulates its behavior. In the ideal world, the simulator invokes the real-world adversary and simulates the honest parties sending their message to the corrupted parties (without knowing the inputs of the honest parties). At every round, the adversary might ask to corrupt some party P i in the simulated protocol, and the simulator corrupts the corresponding party in the ideal world. Upon corruption, the simulator learns the input of P i (and its output, if it was already computed by the trusted party), and it has to provide the adversary the input together with randomness that explains the messages sent by this party in the simulation until this point (known also as "equivocality" in the literature). This is the challenging part of the proof as the simulator has to first simulate P i without knowing its input, "commit" to some messages on its behalf, and later upon corruption find a randomness r i that explains all the messages that were sent so far according to the input x i . Note that the simulator is not allowed to rewind the adversary at any point of the execution, i.e., the simulation is "straight-line."
First attempt. The transformation of [9] shows that for any perfectly secure protocol, randomness r i describing the behavior of P i so far, exists. This implies that the simulator can always find it; however, finding it might not be an efficient procedure. Our first attempt is adding some cryptographic hardness while targeting exactly this procedure of finding the matching randomness. That is, our goal is making the finding of the randomness a computationally hard problem.
It is intuitive to simply take the BGW protocol, even just for semi-honest security and for computing a linear function, with one modification: Before a party starts the protocol, it takes its random tape r, and uses OWP(r) as its randomness in the protocol, where OWP is a one-way permutation. The intuition is that whenever the adversary asks to corrupt some party, the simulator would effectively have to invert the one-way permutation, which is computationally infeasible. The construction is still statically secure since the static simulator only goes "forward"; that is, it chooses some randomness r and then uses OWP(r) as the randomness of the simulated honest party. Moreover, an efficient simulation exists since r exists; however, it seems that an adaptive adversary will have to move "backward" and invert the one-way permutation.
To elaborate further, let n be the number of parties, and consider the function f (a 1 , . . . , a n ) = n i=1 a i ; that is, all parties receive the same output, which is the sum of their inputs. We consider some finite field F with |F| > n. The protocol is as follows:
Input: P i has a i ∈ F as input, and randomness r i . The protocol: 1. P i computes (r i,1 , . . . , r i,n-1 ) = OWP(r), where each r i,j ∈ F. 2. P i secret shares its input a i using Shamir's secret sharing scheme with degree n -1, using the polynomial h i (x) = a i + r i,1 x + . . . + r i,n-1 x n-1 . It gives to each party P j privately a point h i (α j ).
Upon receiving h 1 (α i ), . . . , h n (α i ) from all the parties, the party P i computes β i = n i=j h j (α i ) and sends β i to all other parties. 4. Upon receiving β 1 , . . . , β n , each party reconstructs the unique polynomial H(x) for which it holds for every α j that H(α j ) = β j , and outputs H(0).
The above protocol can be simulated for every t < n parties. Consider an adaptive simulator, and assume that the adversary already corrupted n -2 parties on the onset of the execution, say P 3 , . . . , P n . The simulator then simulates just two honest parties: P 1 and P 2 . As it does not know their inputs it just gives the adversary 2•(n-2) independent random points as the messages of the two honest parties it is simulating. For concreteness, assume that the messages the simulated P 1 sent are (γ 3 , . . . , γ n ), where γ i I T C 2 0 2 2 15:8
is supposed to be delivered to P i . Now, assume that the adversary asks to corrupt P 1 and that the simulator receives its input a 1 . The simulator can now find a random polynomial h 1 (x) of degree n -1 under the constraints that
Note that these constraints define overall n -1 points. Since h 1 (x) has n coefficients, there are |F| different polynomials that satisfy these n -1 constraints. The simulator can pick one more point at random, and then uniquely determine the polynomial h 1 (x) using interpolation.
For that particular polynomial, the simulator has to invert the one-way permutation and find the corresponding randomness.
The problem -the reduction to OWP. It is hard to use the above adaptive simulator to construct an inverter for the one-way permutation on some challenge point y * ∈ |F| n-1 , corresponding to the n -1 leading coefficients, say y * = (r 1,1 , . . , r 1,n-1 ). The problem is that once the adaptive simulator "commits" to the values (γ 3 , . . . , γ n ), it might be the case that there is no input a 1 for which the polynomial
That is, there is no input a 1 in the support that agrees with the challenge y * and with the simulated view, simultaneously.
Second attempt. To solve the above technicality, we change the functionality and the protocol. Instead of having the input of each party P i be just a i ∈ F, it is augmented to be a polynomial g i (x) of degree n -1 over F. The functionality is then defined as:
Note that the parties input polynomials, while all the leading coefficients do not affect the output of the computation. In the protocol, each party P i then invokes (r i,1 , . . . , r i,n-1 ) = OWP(ρ i ) where ρ i is its random tape, and then defines the polynomial h i (x) . . = g i (x) + r i,1 x + . . . + r i,n-1 x n-1 . It then sends to each other party P j the point h i (α j ), just as in
Step 2 in the previous protocol.
The difference is that now, no matter what points (γ 3 , . . . , γ n ) the adversary commits to as the messages P 1 had sent, for any challenge y * = (r * 1 , . . . , r * n-1 ), the inverter of the OWP can choose an input g 1 (x) such that the polynomial g 1 (x) + r * 1 x + . . . + r * n-1 x n-1 is in the support of the polynomials that the adaptive simulator might choose. To see that, given a challenge y * = (r * 1 , . . . , r * n-1 ) to the inverter, and given (γ 3 , . . . , γ n ) that were chosen by the simulator as the messages P 1 had sent in the first round, the inverter chooses two additional points γ 1 and γ 2 at random. It then interpolates the unique polynomial h(x) such that for every i ∈
), and gives g 1 (x) to the adaptive simulator as the input of P 1 .
The simulator now has to reply with some randomness ρ ′ for which (r
) and h ′ 2 (α 2 ) are not determined, the simulator essentially has |F| 2 different polynomials to chose from. However, one of them corresponds to the challenge y * . Moreover, y * is distributed uniformly in the support of all valid solutions for the simulator. Since the adaptive simulator simulates with perfect security, the inverter succeeds in inverting y * with probability 1/|F| 2 . By tuning the parameters (such that |F| is polynomial in the security parameter), this is an inverse-polynomial advantage. Assuming that OWP is a one-way permutation, this implies that the adaptive simulator cannot run in polynomial time.
Our static simulator. To guarantee such consistencies, our static simulator generates t random shares on each input wire and each output of a multiplication wire. That is, while the adversary corrupt some set I, the simulator, "in its head," chooses an arbitrary set Î ⊇ I of cardinality exactly t and simulates the shares for all parties in Î, while giving the adversary only shares for the parties in I. As a result, we have no random choice when simulating the output wires. The simulator holds t shares on each output wire, and also knows the constant term on the output wires of the corrupted parties. It can deterministically interpolate the polynomials on the output wire, and simulate the honest parties sending their shares on those wires. This guarantees that if there is any dependency between output wires, then the simulator provides consistent shares.
Our adaptive simulator. Assume that the adaptive adversary corrupts some party P i * . If i * ∈ Î \ I, then providing the view of that party is easy. The simulator has already sampled all the shares that P i * is supposed to receive. On the other hand, if i * ̸ ∈ Î \ I, then we face a new obstacle. This is because the simulator has already defined t shares on each wire, and defining an additional share on each wire would completely determine each polynomial. Let j * ∈ Î \ I. The key idea of our adaptive simulator is to "replace" the sampling of shares for party P j * with sampling shares for party P i * . Specifically, we show that each random choice made for P j * that leads to the current view of the adversary, can also be interpreted by a random choice made for P i * that leads to the exact same view. This procedure then changes the set of the simulator and "forgets" all the random choices made for P j * , but instead samples matching choices for P i * . This is essentially sampling random shares for P i * on the input wires of all honest parties and the outputs of f mult , under the constraints posed by the shares of P j * on the output wires. Such sampling can be performed efficiently by solving a linear set of equations. Then, we are back to the previous case, where the corruption is made on some i * ∈ Î \ I.
Our results hold in any natural model that captures perfect adaptive security, for example, [10,7,16,8,25,21]. For concreteness, we will state our results using the modular (nonconcurrent) composability framework of Canetti [7]. Indeed, the separation in this limited setting extends to any of the models listed above, whereas our positive results translate to the universal-composability setting via the transformation in [24]. Before describing the security model, we give basic notation and define the cryptographic primitive used in our separation.
Notation. We denote by λ the security parameter. For n ∈ N, let [n] = {1, . . . , n}. Let poly denote the set of all positive polynomials and let PPT denote a probabilistic algorithm that runs in strictly polynomial time. A function ν :
for every p ∈ poly and large enough λ. Given a random variable X, we write x ← X to indicate that x is selected according to X, and given a set X we write x ← X to indicate that x is selected uniformly at random from X .
One-way permutations. Our separation in Section 4 will rely on the existence of a one-way permutation (OWP); that is a one-way function which is length preserving and one-to-one; we refer the reader to [19] for more details.
▶ Definition 4 (OWP). A polynomial-time function f : {0, 1} * → {0, 1} * is a one-way permutation if the following conditions are satisfied. 1. For every λ ∈ N, f induces a permutation over {0, 1} λ , i.e., f : {0, 1} λ → {0, 1} λ is one-to-one and onto. 2. There exists a deterministic polynomial-time algorithm A such that on input x ∈ {0, 1} * the algorithm A outputs f (x). 3. For every PPT algorithm A, every positive polynomial p(•), and all sufficiently large λ's, it holds that
.
In this section we prove Theorem 1. We show a functionality together with a protocol that privately computes it with perfect static security and efficient simulation. Further, we show that if the protocol privately computes the functionality with perfect adaptive security and efficient simulation, then one-way permutations do not exist. We start by defining the functionality and the protocol. Next, in Lemma 6 we prove static security and in Lemma 9 we prove that adaptive security with efficient simulation cannot be achieved assuming OWP. Combined, this proves Theorem 1.
The n-party functionality f sum is parametrized by a finite binary field F 2 ℓ such that 2 ℓ > n. Looking ahead, having a binary field will enable using a one-way permutation OWP : {0, 1} * → {0, 1} * that is applied on a vector of field elements in a clean way. During the proof below, we will denote the field by F . . = F 2 ℓ . The private input of every party is a polynomial of degree (at most) n -1 over F, and the common output is the sum of the free coefficients.
Input: The input of party P i is a polynomial g i (x) of degree n -1, that is define by n coefficients a i,0 , . . . , a i,n-1 ∈ F such that
The n-party protocol π sum is parametrized by the field F and assumes the existence of a one-way permutation OWP :
Protocol 5: Separating Protocol π sum .
Private input: The input of party P i is a polynomial g i (x) of degree n -1 over F. Randomness: The random tape of party P i is ρ i ← F n-1 . Common inputs: n distinct non-zero elements α 1 , . . . , α n ∈ F. The protocol: code for party P i : 1. Compute (r i,1 , . . . , r i,n-1 ) = OWP(ρ i ).
I T C 2 0 2 2 15:12 Static vs. Adaptive Security in Perfect MPC 3. Send to every P j its share γ i→j . . = h i (α j ).
Having received all shares γ 1→i , . . . , γ n→i , party P i locally computes β i = n j=1 γ j→i and sends β i to all other parties. 5. Having received β 1 , . . . , β n , party P i finds the unique degree-(n -1) polynomial H(x)
satisfying H(α j ) = β j for every j ∈ [n]. Output: H(0).
We start by proving static security of π sum . We note that static security holds even if OWP is simply a permutation that is not necessarily one way and can be inverted efficiently.
▶ Lemma 6. Protocol π sum statically (n -1)-privately computes f sum with perfect semi-honest security and efficient simulation.
Proof. Let A be a static semi-honest adversary and let I ⊂ [n] of size |I| < n denote the set of corrupted parties' indices. We construct a simulator S as follows:
1. The simulator initially receives auxiliary information z and the inputs of the corrupted parties (g i (x)) i∈I . First, S sends (g i (x)) i∈I to the trusted party and receives back the output value y. Next, S invokes A on z and (g i (x)) i∈I . 2. To simulate the first round, for every j / ∈ I, the simulator chooses a random ρ j ← F n-1 and computes (r j,1 , . . . , r j,n-1 ) = OWP(ρ j ). Next, S chooses arbitrary polynomials (g j (x)) j̸ ∈I , each of degree at most n -1, under the constraint that j̸ ∈I gj (0) = y -i∈I g i (0), and defines for every j / ∈ I h j (x) = gj (x) + r j,1 x + . . . + r j,n-1 x n-1 .
Finally, for every j / ∈ I and i ∈ I, the simulator sends γ j→i . . = h j (α i ) to A as the message from an honest P j to a corrupted P i , and receives the messages γ i→j from A as the message from a corrupted P i to an honest P j . 3. To simulate the second round, for every j / ∈ I, the simulator computes β j . . = n k=1 γ k→j and sends β j as the message from P j . Next, S receives the message β i from A on behalf of every corrupted P i . 4. Finally, S outputs whatever A outputs, and halts.
Note that by construction, the simulator S runs in polynomial time in the running time of A.
Proof. Note that the only difference between the real execution of the protocol and the simulated execution in the ideal world is the construction of the constant terms of the polynomials (h j (x)) j̸ ∈I :
In the real protocol, these constant terms are the constant terms of the original inputs of the honest parties (g j (x)) j / ∈I . In this case, by the linearity of Shamir's secret sharing and by the correctness of the interpolation, it holds that the output equals n i=1 g i (0).
In the simulated execution, these constant terms are the constant terms of the polynomials (g j (x)) j / ∈I . These polynomials are generated under the constraint that j̸ ∈I gj (0) = y -i∈I g i (0), where y is computed by the trusted party to be n i=1 g i (0). It follows that j̸ ∈I gj (0) = j̸ ∈I g j (0).
The claim now follows by the perfect privacy of Shamir's secret sharing. ◁
This concludes the proof of Lemma 6. ◀
By the construction of the static simulator it is clear that the simulation is straight-line and black-box; further, since we consider a semi-honest adversary that in particular does not change the corrupted parties' inputs, "round zero" (the beginning of the protocol) can be set as the committal round. Therefore, we can use [9] to derive the following corollary.
▶ Corollary 8. Protocol π sum adaptively (n -1)-privately computes f sum with perfect semihonest security.
We proceed to prove that an efficient adaptive simulator can be used to invert the one-way permutation.
▶ Lemma 9. Assume that OWP is a one-way permutation. Then, Protocol π sum does not adaptively (n -1)-privately computes f sum with perfect semi-honest security and efficient simulation.
Proof. Let λ denote the security parameter, i.e., the one-way permutation is defined as OWP : {0, 1} λ → {0, 1} λ . For simplicity, assume that λ = (n -1) log(n + 1) for some n such that n + 1 is a power of 2 (this holds without loss of generality, since the security of the OWP holds for all sufficiently large λ's). We consider the n-party functionality f sum that is defined with respect to the field F = F 2 ℓ where ℓ = log(n + 1); then, indeed, |F| > n as required and OWP induces a permutation over F n-1 .
Defining the adversary and the environment. Consider the following adaptive, semi-honest, (n -1)-limited adversary A and the environment Z for π sum .
1. The environment does not send any auxiliary information to the adversary at the beginning.
The adversary A starts by corrupting the parties P 3 , . . . , P n and learns their inputs (g 3 (x), . . . , g n (x)) and random tapes (ρ 3 , . . . , ρ n ). The environment does not send any auxiliary information to the adversary for these corruptions.
Next, A receives first-round messages γ 1→3 , . . . , γ 1→n from P 1 and γ 2→3 , . . . , γ 2→n from P 2 . 4. The adversary completes the execution honestly and outputs its view. 5. The environment corrupts P 1 in the PEC phase and learns (amongst other things) its input g 1 (x), randomness ρ 1 , and the values (r 1,1 , . . . , r 1,n-1 ) computed in Step 1 of π sum . 6. The environment checks whether (r 1,1 , . . . , r 1,n-1 ) = OWP(ρ 1 ); if so it outputs real and otherwise ideal. The corresponding adaptive simulator. By the assumed security of π sum , there exists an efficient adaptive simulator S for A and Z. Note that by construction, the adversary A runs in polynomial time with respect to the parameter λ; hence, S is PPT with respect to λ. We will use S to construct a PPT inverter D for the OWP.
Constructing the inverter from the simulator. The inverter D receives as input the challenge y * ∈ {0, 1} λ . We will consider y * as element of F n-1 , i.e., y * = (r * 1 , . . . , r * n-1 ) ∈ F n-1 . The inverter D proceeds as follows: 1. D invokes the simulator S and emulates the ideal computation of f sum toward S; initially, D sends nothing as the auxiliary information to S. 2. When S corrupts the parties P 3 , . . . , P n in the emulated ideal computation, D chooses arbitrary polynomials (g 3 (x), . . . , g n (x)) of degree at most n -1 over F and hands g i (x) to S as the input value of P i ; D sends nothing as the auxiliary information to S. 3. When S sends inputs to the trusted party on behalf of the corrupted parties, D responds with an arbitrary output value y ∈ F. 4. Once S generates its output, containing the view of A, the inverter D extracts the firstround messages that each corrupted party received from the honest party P 1 , denoted γ 1→3 , . . . , γ 1→n . 5. D samples two field elements γ 1 , γ 2 ← F and interpolates the unique polynomial h of degree n -1 satisfying the constraints:
Next, D computes g 1 (x) = h(x) -n-1 k=1 r * k x k . 6. D sends a "corrupt P 1 " request to S during the PEC phase. When S corrupts P 1 in the emulated ideal computation, D sets the input of P 1 to be g 1 (x). Next, S responds with the view of P 1 , containing the content of its random tape ρ 1 . 7. D outputs ρ 1 .
Efficiently inverting the OWP. First, notice that by construction, the running time of the inverter D is polynomial with respect to its input y * and to the running time of S; therefore, D is PPT with respect to the parameter λ. We proceed to show that the success probability of D in inverting a random challenge y * ← {0, 1} λ is non-negligible. Proof. In our proof, we do not assume any specific behavior of the adaptive simulator S (i.e., we do not know how the simulator generates its output messages). However, based on the assumed perfect security of the protocol, the adaptive simulator S operates according to the following interface: 1. S corrupts parties P 3 , . . . , P n and learns their inputs (g 3 (x), . . . , g n (x)). 2. S sends the inputs (g 3 (x), . . . , g n (x)) to the trusted party and obtains the output value y.
3. S generates the simulated view of the adversary, which in particular contains the messages γ 1→3 , . . . , γ 1→n from P 1 to parties P 3 , . . . , P n . 4. S corrupts party P 1 and learns its input g 1 (x). 5. S outputs the view of P 1 , including its random tape ρ 1 and values (r 1,1 , . . . , r 1,n-1 ) = OWP(ρ 1 ), such that the polynomial h 1 (x) = g 1 (x) + n-1 k=1 r 1,k x k satisfies h 1 (α i ) = γ 1→i for i ∈ {3, . . . , n}.
Recall that in Step 5 of the construction of the inverter, D samples γ 1 , γ 2 ← F and interpolates the polynomial h(x) that satisfies the following constraints: h(α 1 ) = γ 1 , h(α 2 ) = γ 2 , h(α i ) = γ 1→i for i ∈ {3, . . . , n} .
First, for every choice of γ 1 , γ 2 ∈ F there exists a unique polynomial of degree n -1 over F satisfying these constraints. In the other direction, every polynomial h ′ (x) of degree at most n -1 over F, satisfying h ′ (α i ) = γ 1→i for i ∈ {3, . . . , n}, induces two points γ 1 = h ′ (α 1 ) and γ 2 = h ′ (α 2 ) in F.
It follows that the inverter succeeds in inverting y * if and only if h 1 (α 1 ) = γ 1 and h 1 (α 2 ) = γ 2 (where h 1 (x) is the polynomial defined by S). Indeed, in this case h 1 (x) = h(x), which means that h 1 (x) -g 1 (x) = h(x) -g 1 (x), i.e., n-1 k=1 r 1,k x k = n-1 k=1 r * k x k , and finally (r 1,1 , . . . , r 1,n-1 ) = (r * 1 , . . . , r * n-1 ). Since γ 1 and γ 2 are sampled uniformly at random from F, this happens with probability 1/|F| 2 . ◁ Finally, note that y * ∈ F n-1 , i.e., y * ∈ {0, 1} (n-1) log(n+1) = {0, 1} λ . However, the inverting probability is 1/|F| 2 = 1/2 2 log(n+1) = 1/(n + 1) 2 , which is non-negligible in λ. We conclude that D is PPT in λ and succeeds in inverting OWP with non-negligible probability. This contradicts the assumption that OWP is a one-way permutation.
◀
A simulator is called straight-line if it does not rewind the adversary, and is called black-box if it does not rely on the code of the adversary.
We note that Backes et al.[3] showed that this transformation no longer holds if the simulator is not straight-line.