BRICS RS-00-14 Cramer et al.: Multiparty Computation from Threshold Homomorphic Encryption BRICS

Basic Research in Computer Science

Multiparty Computation from Threshold Homomorphic Encryption

Ronald Cramer Ivan B. Damgård Jesper Buus Nielsen BRICS Report Series RS-00-14 ISSN 0909-0878 June 2000 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2000, Ronald Cramer & Ivan B. Damgård &

Jesper Buus Nielsen. BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/00/14/

Multiparty Computation from Threshold Homomorphic Encryption

Ronald Cramer  Ivan Damgård  Jesper Buus Nielsen

June, 2000

Abstract

We introduce a new approach to multiparty computation (MPC) basing it on homomorphic threshold crypto-systems. We show that given keys for any sufficiently efficient system of this type, general MPC protocols for n players can be devised which are secure against an active adversary that corrupts any minority of the players. The total number of bits sent is O(nk|C|), where k is the security parameter and |C| is the size of a (Boolean) circuit computing the function to be securely evaluated. An earlier proposal by Franklin and Haber with the same complexity was only secure for passive adversaries, while all earlier protocols with active security had complexity at least quadratic in n. We give two examples of threshold cryptosystems that can support our construction and lead to the claimed complexities.

Contents

1 Introduction 1

2 Our Results 2 2.1 Road map to the Paper . . . . . . . . . . . . . . . . . . . . . . 3

3 An Informal Description 3

4 Preliminaries and Notation 5

5 The MPC Model 6

6 Σ-Protocols 9

6.1 The Random oracle model . . . . . . . . . . . . . . . . . . . . . 10 6.1.1 Doing without a Random Oracle . . . . . . . . . . . . . 12

7 Homomorphic Threshold Encryption 13

8 General MPC from Threshold Homomorphic Encryption 15

8.1 Some Sub-Protocols . . . . . . . . . . . . . . . . . . . . . . . . 16 8.1.1 The ASS (Additive Secret Sharing) Protocol . . . . . . 16 8.1.2 The PrivateDecrypt Protocol . . . . . . . . . . . . . . . 17 8.1.3 The Mult Protocol . . . . . . . . . . . . . . . . . . . . . 18

8.2 The FuncEval_{f} Protocol (Deterministic f) . . . . . . . . . . . . 20 8.3 The FuncEval_{f} Protocol (Probabilistic f) . . . . . . . . . . . . 31 8.4 Generalisations . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

9 Examples of Threshold Homomorphic Cryptosystems 32

9.1 Basing it on Paillier’s Cryptosystem . . . . . . . . . . . . . . . 32 9.1.1 Threshold decryption . . . . . . . . . . . . . . . . . . . 32 9.1.2 Proving multiplications correct . . . . . . . . . . . . . . 33 9.1.3 Proving you know a plaintext . . . . . . . . . . . . . . . 34

9.2 Basing it on QRA and DDH . . . . . . . . . . . . . . . . . . . . 34 9.2.1 Threshold decryption . . . . . . . . . . . . . . . . . . . 35 9.2.2 Proving you know a plaintext . . . . . . . . . . . . . . . 35 9.2.3 Proving multiplications correct . . . . . . . . . . . . . . 37

1 Introduction

The problem of multiparty computation (MPC) dates back to the papers by Yao [18] and Goldreich et al. [12]. What was proved there was basically that a collection of n players can efficiently compute the value of an n-input function, such that everyone learns the correct result, but no other new information. More precisely, these protocols can be proved secure against a polynomial time bounded adversary who can corrupt a set of less than n/2 players initially, and then make them behave as he likes, we say that the adversary is active. Even so, the adversary should not be able to prevent the correct result from being computed and should learn nothing more than the result and the inputs of corrupted players. Because the set of corrupted players is fixed from the start, such an adversary is called static or non-adaptive.

There are several different proposals on how to define formally the security of such protocols [15, 2, 4], but common to them all is the idea that security means that the adversary’s view can be simulated efficiently by a machine that has access to only those data that the adversary is entitled to know.

Proving correctness of a simulation in the case of [12] requires a complexity assumption, such as existence of trapdoor one-way permutations. This is because the model of communication considered there is such that the adversary may see every message sent between players, this is sometimes known as the cryptographic model. Later, unconditionally secure MPC protocols were proposed by Ben-Or et al. and Chaum et al.[3, 5], in the model where private channels are assumed between every pair of players. In this paper, however, we are only interested in the cryptographic model with an active and static adversary.

Over the years, several protocols have been proposed which, under specific computational assumptions, improve the efficiency of general MPC, see for instance [7, 11]. Virtually all proposals have been based on some form of verifiable secret sharing (VSS), i.e., a protocol allowing a dealer to securely distribute a secret value s among the players, where the dealer and/or some of the players may be cheating. The basic paradigm that has been used is to ensure that all inputs and intermediate values in the computation are VSS’ed, since this prevents the adversary from causing the protocol to terminate early or with incorrect results. In all these earlier protocols, the total number of bits sent was Ω(n^{2}k|C|), where n is the number of players, k is a security parameter, and |C| is the size of a circuit computing the desired function. Here, C may be a Boolean circuit, or an arithmetic circuit over a finite field, depending on the protocol. We note that all complexities mentioned here and in the next section are for computing deterministic functions. Handling probabilistic functions introduces some overhead for generating secure random bits, but this will be the same for all protocols we mention here, and so does not affect any comparisons we make.

In [10] Franklin and Haber propose a protocol for passive adversaries which achieves complexity O(nk|C|). This protocol is not based on VSS (there is no need since the adversary is passive) but instead on a so called joint encryption scheme, where a ciphertext can only be decrypted with the help of all players, but still the length of an encryption is independent of the number of players.

2 Our Results

In this paper, we present a new approach to building multiparty computation protocols with active security, namely we start from any secure threshold encryption scheme with certain extra homomorphic properties. This allows us to avoid the need to VSS all values handled in the computation, and therefore leads to more efficient protocols, as detailed below.

The MPC protocols we construct here can be proved secure against an active and static adversary who corrupts any minority of the players. Like the protocol of [10], our construction requires once and for all an initial phase where keys for the threshold cryptosystem are set up. This can be done by a trusted party, or by any general purpose MPC. We stress, however, that unlike some earlier proposals for preprocessing in MPC, the complexity of this phase does not depend on the number or the size of computations to be done later. It is even possible to do a computation only for some subset of the players that participated in the first phase, provided the subset is large enough compared to the threshold that the cryptosystem was set up to handle. Moreover, since supplying input values to the computation consists essentially of just sending encryptions of these values, we can easily handle scenarios where one (large) group of players supply inputs, whereas a different (smaller) group of players does the actual computation. This will be secure, even from the point of view of the input suppliers since our protocol automatically ensures that correctness of the computation is publicly verifiable.

In the following we therefore focus on the complexity of the actual computation. In our protocol the computation can be done only by broadcasting a number of messages, no encryption is needed to set up private channels. The complexities we state are therefore simply the number of bits broadcast. This does not invalidate comparison with earlier protocols because first, the same measure was used in [10] and second, the earlier protocols with active security have complexity quadratic in n even if one only counts the bits broadcast. For the most efficient version of our protocol which requires the random oracle model to prove security, the complexity is O(nk|C|) bits. To the best of our knowledge, this is the most message-efficient general MPC protocol proposed to date for active adversaries.

The random oracle assumption can be removed at the cost of slightly larger complexity, in this case we can obtain O(n · max(n, k)|C|). This is still better than the Ω(n^{2}k|C|) of earlier protocols, and moreover for most realistic values of the parameters, we will have k ≥ n, in which case there is no difference between the two models.

Here, C is an arithmetic circuit over a ring R determined by the cryptosystem used, e.g., R = Z_{n} for an RSA modulus n. While such circuits can simulate any Boolean circuit with a small constant factor overhead, this also opens the possibility of building an ad-hoc circuit over R for the desired function, possibly exploiting the fact that with a large R, we can manipulate many bits in one arithmetic operation.

The complexities given here assume existence of sufficiently efficient threshold cryptosystems. We give two examples of such systems with the right properties. One is based on Paillier’s cryptosystem [16], the other one is a variant of Franklin and Haber’s cryptosystem [10], which is secure assuming that both the quadratic residuosity assumption and the decisional Diffie-Hellman assumption are true (this is essentially the same assumption as the one made in [10]). While the first example is known (from [8] and independently in [9]), the second is new and may be of independent interest.

Franklin and Haber in [10] left as an open problem to study the communication requirements for active adversaries. We can now say that under the same assumption as theirs, protection against active adversaries comes essentially for free.

2.1 Road map to the Paper

In the following, we first give a brief explanation of the main ideas in Section 3. Some notation and the model we use for proving security of protocols is presented in Sections 4 and 5. Sections 6, 7 and 8 state more formally the properties needed from the sub-protocols and the encryption scheme, and describe and prove the protocols we can build based on these properties. Finally Section 9 give our examples of threshold encryption schemes that could be used as basis of our construction.

For an overview of the basic ideas only, one can read Sections 3 and 9 separately from the rest of the paper.

3 An Informal Description

In this section, we give a completely informal introduction to some main ideas. All the concepts introduced here will be treated more formally later in the paper. We will assume that from the start, the following scenario has been established: we have a semantically secure threshold public-key system given, i.e., there is a public encryption key pk known by all players, while the matching private decryption key has been shared among the players, such that each player holds a share of it.

The message space of the cryptosystem is assumed to be a ring R. In practice R might be Z_{n} for some RSA modulus n. For a plaintext a ∈ R, we let ā denote an encryption of a. We then require certain homomorphic properties: from encryptions ā, b̄, anyone can easily compute (deterministically) an encryption of a + b, which we denote ā ⊞ b̄. We also require that from an encryption ā and a constant α ∈ R, it is easy to compute a random encryption of αa.

Finally we assume that three secure (and sufficiently efficient) sub-protocols are available:

Proving you know a plaintext If P_{i} has created an encryption ā, he can give a zero-knowledge proof of knowledge that he knows a (or more accurately, that he knows a and a witness to he fact that the plaintext is a).

Proving multiplications correct Assume P_{i} is given an encryption ā, chooses a constant α, computes a random encryption \overline{αa} and broadcasts ᾱ, \overline{αa}. He can then give a zero-knowledge proof that indeed \overline{αa} contains the product of the values contained in ᾱ and ā.

Threshold decryption For the third sub-protocol, we have common input pk and an encryption ā, in addition every player also uses his share of the private key as input. The protocol computes securely a as output for everyone.

We can then sketch how to perform securely a computation specified as a circuit doing additions and multiplications in R. Note that this allows us to simulate a Boolean circuit in a straightforward way using 0/1 values in R.

The MPC protocol would simply start by having each player publish encryptions of his input values and give zero-knowledge proofs that he knows these values and also, if need be, that the values are 0 or 1 if we are simulating a Boolena circuit. Then any operation involving addition or multiplication by constants can be performed with no interaction: if all players know encryptions ā, b̄ of input values to an addition gate, all players can immediately compute an encryption of the output \overline{a + b}. This leaves only the following problem:

Given encryptions ā, b̄ (where it may be the case that no players knows a nor b), compute securely an encryption of c = ab. This can be done by the following protocol:

1. Each player P_{i} chooses at random a value d_{i} ∈ R, broadcasts an encryption d̄_{i} and proves that he knows d_{i}.

2. Let d = d_{1} + … + d_{n}. All players can now compute d̄_{1} ⊞ ... ⊞ d̄_{n}, an encryption of a + d. This ciphertext is decrypted using the third subprotocol, so all players know a + d.

3. Player P_{1} sets a_{1} = (a + d) − d_{1}, all other players P_{i} set a_{i} = −d_{i}. Note that every player can compute an encryption of each a_{i}, and that a = a_{1} + … + a_{n}.

4. Each P_{i} broadcasts an encryption \overline{a_{i}b}, and we invoke the second subprotocol with inputs b̄, ā_{i} and ā_{i}b.

5. Let C be the set of players for which the previous step succeeded, and let F be the complement of C. We now first decrypt the ciphertext ⊞_{i∈F} ā_{i}, giving us the value a_{F} = ∑_{i∈F} a_{i}. This allows everyone to compute an encryption \overline{a_{F} b}. From this, and \{\overline{a_{i}b}| i ∈ C\}, all players can compute an encryption (⊞_{i∈C} \overline{a_{i}b}) ⊞ \overline{a_{F} b}, which is indeed an encryption of ab.

This protocol is a somewhat more efficient version of a related idea from [10], with protection against faults added in the final step.

At the final stage we know encryptions of the output values, which we can just decrypt. Intuitively this is secure if the encryption is secure because, other than the outputs, only random values and values already known to the adversary are ever decrypted. We will give proofs of this intuition in the following.

Note also that this by no means shows the complexities we claimed earlier. This depends entirely on the efficiency of the encryption scheme and the subprotocols. We will substantiate this in the final sections.

4 Preliminaries and Notation

Let A be a probabilistic polynomial time (PPT) algorithm, which on input x ∈ {0, 1}^{∗} and random bits r ∈ {0, 1}^{p(|x|)} for some polynomial p(·) outputs a value y ∈ {0, 1}^{∗}. We write y ← A(x)[r] to denote that y should be computed by running A on input x and random bits r and write y = A(x)[r] to denote that y equals a value computed like this. By y ← A(x) we mean that y should be computed by running A on input x and random bits r, where r is chosen uniformly random in {0, 1}^{p(|x|)}. By y ∈ A(x) we mean that y is among the values, that A(x) might output with non-zero probability. I.e. there exists r ∈ {0, 1}^{p(|x|)} such that y = A(x)[r]. We use N to denote the set {1, 2, …, n} and by \overline{Q} for Q ⊂ N we denote the set N \ Q.

A distribution ensemble is a sequence X = {X(k, a)}_{k∈N,a∈D}, where k is the security parameter, D is some arbitrary domain, typically {0, 1}^{∗}, and X(k, a) is a random variable. We call D the index set.

We have three primary notions for comparisons of distribution ensembles.

Definition 1 (Equality of ensembles) We say that two distribution ensembles X and Y indexed by D are equal if for all k and all a ∈ D we have that X(k, a) and Y (k, a) are identically distributed. We write X =^{d} Y.

Definition 2 (Statistical indistinguishability of ensembles) Let δ : N → [0, 1]. We say that two distribution ensembles X and Y indexed by D have statistical distance at most δ if there exists k_{0} such that for every k > k_{0} and all a ∈ D we have that

\frac{1}{2} ∑_{y∈\{0,1\}^{∗}} | Pr[X(k, a) = y] − Pr[Y (k, a) = y]| < δ(k)

If X and Y have statistical distance at most δ for some negligible δ then we say that X and Y are statistically indistinguishable and write X ≈^{s} Y.

Definition 3 (Computational indistinguishability of ensembles [13, 19]) Let δ : N → [0, 1]. Let D be any TM which is PPT in its first input, let k ∈ N, a ∈ D, and let w ∈ {0, 1}^{∗} be some arbitrary auxiliary input. By the advantage of D on these inputs we mean

adv_{D}(k, a, w) = | Pr[D(1^{k}, a, w, X(k, a)) = 1] − Pr[D(1^{k}, a, w, Y (k, a)) = 1]|

where the probabilities are taken over the random variables X(k, a) and Y (k, a) and the random choices of D.

We say that two distribution ensembles X and Y indexed by D have computational distance at most δ if for every adversary D, there exists k_{D} such that for every k > k_{D}, all a ∈ D, w ∈ {0, 1}^{∗} we have that

adv_{D}(k, a, w) < δ(k)

If X and Y have computational distance at most δ for some negligible δ then we say that X and Y are computationally indistinguishable and write X ≈^{c} Y.

5 The MPC Model

We use the MPC model from [4] which we refer to for a more complete description of the model. Here we only mention the setting in which we use it, our notational conventions, and some small extensions to the model.

The Real-Life Model Let π be a n-party protocol. We look at the situation, where the protocol is executed on an open broadcast network with rushing in the presence of an active static adversary A. As a small extension to the model in [4] we allow each party P_{i} to receive a secret input x_{i}^{s} and a public input x_{i}^{p} and return a secret output y_{i}^{s} and a public output y_{i}^{p}. The adversary receives the public input and output of all parties.

Let x⃗ = (x_{1}^{s}, x_{1}^{p}, …, x_{n}^{s}, x_{n}^{p}) be the parties’ input, let r⃗ = (r_{1}, …, r_{n}, r_{A}) be the parties’ and the adversary’s random input, let C ⊂ N be the corrupted parties, and let a ∈ {0, 1}^{∗} be the adversary’s auxiliary input.

By ADVR_{π,A}(k, x⃗, C, a, r⃗) and EXEC_{π,A}(k, x⃗, C, a, r⃗)_{i} we denote the output of the adversary A resp. the output of party P_{i} after A attacking a real-life execution of the protocol π with the given input. Let

EXEC_{π,A}(k, x⃗, C, a, r⃗) = ( ADVR_{π,A}(k, x⃗, C, a, r⃗),
EXEC_{π,A}(k, x⃗, C, a, r⃗)_{1},
…,
EXEC_{π,A}(k, x⃗, C, a, r⃗)_{n})

and denote by EXEC_{π,A}(k, x⃗, C, a) the random variable EXEC_{π,A}(k, x⃗, C, a, r⃗), where r⃗ is chosen uniformly random.

Let Γ be a monotone adversary structure and define a distribution ensemble with security parameter k and index (x⃗, C, a) by

EXEC_{π,A} = {EXEC_{π,A}(k, x⃗, C, a)}_{k∈N,x⃗∈({0,1}^{∗})^{2n},C∈Γ,a∈{0,1}^{∗}} .

The Ideal Model Let f : N × ({0, 1}^{∗})^{2n} × {0, 1}^{∗} → ({0, 1}^{∗})^{2n} be a probabilistic n-party function computable in PPT. We name the inputs and outputs as follows (y_{1}^{s}, y_{1}^{p}, …, y_{n}^{s}, y_{n}^{p}) ← f(k, x_{1}^{s}, x_{1}^{p}, …, x_{n}^{s}, x_{n}^{p}, r), where k is the security parameter and r is the random input. In the ideal model the parties send their inputs to a incorruptible trusted party T which draws r uniformly random, computes f on the inputs and returns to the party P_{i} its output share (y_{i}^{s}, y_{i}^{p}). The execution takes place in the presence of an active static ideal-model adversary S. Again the adversary sees the values x_{i}^{p} and y_{i}^{p} for all parties — we imagine that x_{i}^{p} and y_{i}^{p} are send over an open point-to-point channel whereas x_{i}^{s} and y_{i}^{s} are send over a secure point-to-point channel.

We let

IDEAL_{f,S}(k, x⃗, C, a, r⃗) = ( ADVR_{f,S}(k, x⃗, C, a, r⃗),
IDEAL_{f,S}(k, x⃗, C, a, r⃗)_{1},
…,
IDEAL_{f,S}(k, x⃗, C, a, r⃗)_{n})

denote the collective output distribution of the parties and the adversary and define a distribution ensemble by

IDEAL_{f,S} = {IDEAL_{f,S}(k, x⃗, C, a)}_{k∈N,x⃗∈({0,1}^{∗})^{2n},C∈Γ,a∈{0,1}^{∗}} .

The Hybrid Model In the (g_{1}, …, g_{l})-hybrid model the execution of a protocol π proceeds as in the real-life model, except that the parties have access to a trusted party T for evaluating the n-party functions g_{1}, …, g_{l}. These ideal evaluations proceeds as in the ideal-model^{1}. We define as for the other models a distribution ensemble

EXEC_{π,A}^{g_{1},... ,g_{l}} = {EXEC_{π,A}^{g_{1},... ,g_{l}}(k, x⃗, C, a)}_{k∈N,x⃗∈({0,1}^{∗})^{2n},C∈Γ,a∈{0,1}^{∗}} .

Security We now define security by requiring, that a real-life execution or (g_{1}, …, g_{l})-hybrid execution of a protocol π for computing a function f should reveal no more information to an adversary than do the ideal evaluation of f. To unify terminology let us denote the real-life model by the ()-hybrid model.

Definition 4 Let f be a n-party function, let π be a n-party protocol, and let Γ be a monotone adversary structure for n parties. We say, that π Γ-securely evaluates f in the (g_{1}, …, g_{l})-hybrid model if for any active static (g_{1}, …, g_{l})- hybrid adversary A, which corrupts only subsets C ∈ Γ, there exists a static active ideal-model adversary S such that IDEAL_{f,S} ≈^{c} EXEC_{π,A}^{g_{1},... ,g_{l}}.

Security Preserving Modular Composition In [4] a modular composition operation was defined and it was proven that it is security preserving. What this basicly means is the following. Assume that π Γ-securely evaluates f in the (g_{1}, …, g_{l})-hybrid model and π_{g_{i}} Γ-securely evaluates g_{i} in the (g_{1}, …, g_{i−1}, g_{i+1}, …, g_{l})-hybrid model. Then the protocol π′, which is π with oracle calls to g_{i} replaced by executions of the protocol π_{g_{i}}, Γ-securely evaluates f in the (g_{1}, …, g_{i−1}, g_{i+1}, …, g_{l})-hybrid model. In this way oracle calls can by replaced be protocol executions to construct a protocol for f in the real-life model.

For a detailed description of the model see [4]. We describe some extensions to the model.

The Random Oracle Model In the random oracle model the parties have access to a trusted party, RO, which on any input x ∈ {0, 1}^{∗} returns a uniformly random bitstring from some domain, say {0, 1}^{k}, where k is the security parameter. If the oracle is queried on the same string again it answers with the same output. The queries and answers are communicated over secure point-to-point channels.

It can be verified that the modular composition operation in the MPC model in [4] is still security preserving in the random oracle model. The only difference is that the involved distributions are now taken also over the random choices of the oracle.

1The ideal-model is in fact just the f-hybrid model, where the parties make just one oracle call with their protocol inputs and return the result of the oracle call.

Restricted Input Domains The definition in [4] refers to functions where the input domain of the parties is ({0, 1}^{∗})^{2n}. Often we can only implement a protocol securely on a restricted domain. In [4] it is noted that if we prove the protocol secure on a restricted domain D ⊂ ({0, 1}^{∗})^{2n} and can prove that the protocol is always called with inputs from that domain, then the security preserving composition theorem still holds.

We will in the specification use the terms common input and common output to denote a public input resp. public output that all honest parties agree on. We cannot specify that a protocol expects a common input using a restriction of the form D ⊂ ({0, 1}^{∗})^{2n}. We can only express that e.g. a majority input the same value. This majority could however consist mostly of corrupted parties allowing all honest parties to disagree on the common input. We therefore allow restrictions of the form D ⊂ Γ × ({0, 1}^{∗})^{2n} to allow to say that e.g. all honest parties’ input the same value to the protocol. We then restrict the distribution ensembles IDEAL_{f,S} and EXEC_{π,A}^{g_{1},... ,g_{l}} to be over indexes (x⃗, C, a), where (C, x⃗) ∈ D. If we prove the protocol secure in contexts where (C, x⃗) ∈ D, and make sure it is only called in such contexts, then it is fairly straight forward to check that the modular composition operation is still security preserving.

6 Σ-Protocols

In this section, we look at two-party zero-knowledge protocols of a particular form. The auxiliary protocols for proving plaintext knowledge and multiplication correctness will be assumed to be of this form. Assume we have a binary relation R consisting of pairs (x, w), where we think of x as a (public) instance of a problem and w as a witness, a solution to the instance. Assume also that we have a 3-move proof of knowledge for R, where the verifier sends a random challenge as the second message. More precisely, this protocol gets a string x as common input for prover and verifier, whereas the prover gets as private input w such that (x, w) ∈ R. Conversations in the protocol are of form (a, e, z), where the prover chooses a, z. There is a security parameter k, such that the length of both x and e are linear in k. We will only look at protocols where also the length of a and z are linear in k. Such a protocol is said to be a Σ-protocol if we have the following:

• The protocol is complete: if the prover gets a correct w as input, the verifier always accepts.

• The protocol is special honest verifier zero-knowledge: from a challenge value e, one can efficiently generate a correctly distributed conversation (a, e, z).

• A cheating prover can answer only one of the possible challenges: more precisely, from the common input x and any pair of accepting conversations (a, e, z), (a, e′, z′) where e ≠ e′, one can compute efficiently w such that (x, w) ∈ R.

It is easy to see that the definition of Σ-protocols is closed under parallel composition. One can also prove that any Σ-protocol satisfies the standard definition of knowledge soundness with knowledge error 2^{−t} where t is the challenge length, but we will not use this explicitly in the following.

We now explain how we can use Σ-protocols in our multiparty setting, both in the random oracle model, and in the real-life model.

6.1 The Random oracle model

In the random oracle model, we use a variant of the Fiat-Shamir heuristic, where the challenge is computed as an output from the oracle H.

More precisely, in our global protocol there are a number of proof phases. In each such phase, each player in some subset is supposed to give a proof of knowledge where P_{i} uses as public an x_{i} which is known to all players at this point. We then do the following:

1. Each P_{i} computes and broadcasts the first message a_{i} in his proof. If P_{i} is not doing a proof in this phase, he broadcasts a random value for a_{i}. We let A be the concatenation of all the a_{i}’s.

2. Each P_{i} who does a proof in this phase computes a challenge e_{i} = H(ID(P_{i}), A), where ID(P_{i}) is the (unique) identity of P_{i}, and broadcasts the answer z_{i} to challenge e_{i}

3. Every player can check every proof given by recomputing e_{i} and verifying that a_{i}, e_{i}, z_{i} is accepting in the original Σ-protocol.

It is clear that such a proof phase has communication complexity no larger than n times the complexity of a single Σ-protocol, i.e. O(nk) bits. We now describe a procedure S_{Σ} that will be used as subrutine in the simulation of our overall protocol. It interacts with an adversary against the overall protocol, starting from the x_{i}’s and a state for the adversary.

It will apparent later that for every Σ-protocol we use, the first message is uniformly distributed in a domain of size 2^{Ω(k)}. Also, we can assume without loss of generality that the length of a challenge is k bits. Assuming this, S_{Σ} will have the following properties:

• S_{Σ} runs in expected polynomial time and outputs a view for the adversary of a proof phase that is statistically indistinguishable from a view in a real execution.

• Except with negligible probability, the following holds: for every corrupt player P_{i}, when the output view contains a correct proof from P_{i}, S_{Σ} also outputs a valid witness w_{i} with respect to x_{i}.

The algorithm of S_{Σ} is as follows:

1. For each P_{i}: if P_{i} is honest, run the honest verifier simulator to make a conversation (a_{i}, e_{i}, z_{i}), if P_{i} is corrupt, receive a_{i} from the adversary. Note that, except with negligible probability, the simulator has defined none of the values H(ID(P_{i}), A) earlier, so it is free to do so in the following. We stop and give up if this is not the case.

2. For each P_{i} do:

if P_{i} is honest, define the output of H on input ID(P_{i}), A to be e_{i}, send z_{i} on behalf of this player and go on to next P_{i}.

If P_{i} is corrupt, define a random value e_{i} as H(ID(P_{i}), A). Receive z_{i} from the adversary. If (a_{i}, H(ID(P_{i}), A), z_{i}) is not an accepting conversation, go on to next P_{i}. Otherwise, save the current state of the adversary and execute the following loop (to try to extract a witness for x_{i}). After the loop is finished, restore the state of the adversary and go on to next P_{i}.

(a) Rewind the adversary to the point just before it asked for the value of H(ID(P_{i}), A). This point is with overwhelming probability after A was produced and before z_{i} is sent. If this is not the case, we give up and stop.

(b) Define a new random value e′_{i} as H(ID(P_{i}), A), and receive z′_{i} from the adversary.

(c) If e′_{i} ≠ e_{i} and (a_{i}, e′_{i}, z′_{i}) is accepting, compute a witness for x_{i} by the special soundness property and exit the loop. If the loop has now done 2^{k} iterations, also exit. Otherwise go to 2a.

It is clear by inspection that whenever we do not give up, we produce a correctly distributed view for the adversary. So the simulation is statistically good since we give up with negligible probability.

For the running time, assume P_{i} is corrupt and let ϵ be the probability that the adversary outputs a correct z_{i} given some fixed but arbitrary value of the adversary’s view up to the quiry for H(ID(P_{i}), A). Observe that the contribution from the loop to the running time is ϵ times the expected number of times the loop is executed before terminating. For any ϵ > 0, it can be seen that the expected number of times around the loop is O(1/ϵ) (note that the minimal value of ϵ is 2^{−k}), so the overall expected running time is polynomial. As for the probability of computing correct witnesses, observe that we do not have to worry about cases where ϵ is small, say ϵ < 2^{−k/2}. However, is ϵ ≥ 2^{−k/2}, the probability that the loop runs 2^{k} times without finding a witness is negligible, by Markov’s inequality.

The n-party version constructed this way from the Σ-protocol for proof of plaintext knowledge will be called the POPK protocol and the n-party version of the proof of correct multiplication will be called the POCM protocol. The corresponding versions of our general simulation rutine S_{Σ} for these protocols will be called S_{POPK}, S_{POCM}.

6.1.1 Doing without a Random Oracle

If we only care about soundness, it is clear that we can do without the random oracle, if for each proof to be given, we let the prover do the original Σ-protocol independently with each of the other players, but this corresponds to giving n times a proof of the same statement and costs O(nk) bits of communication. This will mean that the overall protocol will have complexity quadratic in n. Can we do better? It may seem tempting to make a mutually trusted random challenge by having each player broadcast an encryption and decrypt the sum of all these. But this would lead to circularity because secure and efficient decryption already requires zero-knowledge proofs of the kind we are trying to construct. So here is one simple way of doing better: let m = 3 max(n, k). We can assume without loss of generality that the basic Σ-protocol allows challenges of length m bits (if not, just repeat it in parallel a number of times). Write m as m = tn + r. Then, we create an m bit challenge by letting each player choose t bits, except P_{1} who chooses t + r bits, and concatenate all these strings. It is easy to see that with this construction, at least k bits of a challenge are chosen by honest players and are therefore random, since a majority of players are assumed to be honest. In fact, this this is completely equivalent to doing a Σ-protocol where the challenge length is the number of bits chosen by honest players. The cost of doing such a proof is O(max(n, k)) bits.

The modified protocol we just described is sound, but not zero-knowledge. One way to make a zero-knowledge protocol without severe extra cost is to use a standard trick which in our context works as follows. We can assume that the KD sub-protocol returns as public output (pk, \overline{u}), where \overline{u} is a random encryption of a uniformly random element u from R_{pk}. This guarantees that u is unknown to all parties. Alternatively we could generate \overline{u} after the key generation phase using an interactive protocol among the players. A possibility for the latter case is to have each player publish an encryption ū_{i} and give a zero-knowledge proof that he knows u_{i}. To avoid circularity here, this must be done using rewindable zero-knowledge with short challenges. This does not hurt efficiency since it only needs to be done once and for all. We could then compute \overline{u} as ū_{1} ⊞ … ⊞ ū_{n}.

Later when a prover claims some statement, we ask him to show (using a witness indistinguishable proof) that his statement is true, or that he knows u. Since we already assume that we have a Σ-protocol for proof of plaintext knowledge, this can be done efficiently by techniques from [6] and costs only a constant factor in efficiency. It will preserve soundness, since the prover needs to break the encryption to ”prove” a false statement. For zero-knowledge observe that a simulator can choose to learn u. With the knowledge of u, simulation of the subsequent proofs becomes trivial. If \overline{u} is supplied by the KD protocol, the simulator can simulate the KD by generating correct keys and an encryption \overline{u}, where u is known to the simulator. If \overline{u} is computed as ū_{1} ⊞ … ⊞ ū_{n} it is shown in Section 8.1.2 how the simulator learns u.

In the following we describe the protocols in the random oracle model and prove security in the random oracle model. Using the construction of n-party zero-knowledge protocols from Σ-protocols describe here, the results carry over to the real-life model, as follows: Along the lines we just sketched it is straightforward to build a simulation subrutine for the real-life construction with essentially the same functionality as S_{Σ} had in the random oracle model. Using this subrutine in our simulator for the global protocol in stead of S_{Σ} directly produces a simulator for the real life model. It can be proved to work by the same arguments as for the random oracle model.

7 Homomorphic Threshold Encryption

Definition 5 (Threshold Encryption Scheme) A tuple (K, KD, R, E, Decrypt) is called a threshold encryption scheme with access structure Π ^{2} and security parameter k if the following holds.

Key Generation The keyspace K = {K_{k}}_{k∈N} is a sequence of finite sets of keys of the form (pk, sk_{1}, …, sk_{n}). We call pk the public key and call sk_{i} a private key share. KD is a \overline{Π}-secure protocol, which on security parameter k as input computes as common output pk and as secret output sk_{i} for party P_{i}, where (pk, sk_{1}, …, sk_{n}) is uniform over K_{k}.

We call Q ⊂ N a qualified set of indices if Q ∈ Π and call it a non-qualified set of indices otherwise. By sk_{C} for C ⊂ N we denote the set {sk_{i}}_{i∈C}.

Message Sampling There exists a PPT algorithm R, which on input pk (a public key) outputs a uniformly random element from a set R_{pk}. We write m ← R_{pk}.

2An access structure is a subset Π ⊂ 2^{N} of all subset of the parties which is closed under superset, i.e. if C ∈ Γ and C ⊂ C′ ⊂ N, then C′ ∈ Γ. The complement (in 2^{N}) of Π is named \overline{Π} and is of course closed under subset and is therefore an adversary structure for n parties.

Encryption There exists a PPT algorithm E, which on input pk and m ∈ R_{pk} outputs an encryption \overline{m} ← E_{pk}(m) of m. By C_{pk} we denote the set of possible encryptions for the public key pk.

Decryption There exists a \overline{Π}-secure protocol Decrypt which on common input (\overline{m}, pk) and secret input sk_{i} for the honest party P_{i}, where sk_{i} is the secret key share of the public key pk and \overline{m} is any encryption under the public key pk, returns the common output m.

Threshold semantic security Let A be any PPT algorithm, which on input 1^{k}, C ∈ \overline{Π}, public key pk, and corresponding private keys sk_{C} outputs two messages m_{0}, m_{1} ∈ R_{pk} and some arbitrary value s ∈ {0, 1}^{∗}. Let X_{i}(k, C) denote the distribution of (s, c_{i}), where (pk, sk_{1}, …, sk_{n}) is uniformly random over K_{k}, (m_{0}, m_{1}, s) ← A(1^{k}, C, pk, sk_{C}), and c_{i} ← E_{pk}(m_{i}). Then X_{i} = \{X_{i}(k, C)\}_{k∈N,C∈\overline{Π}} for i = 0, 1 are distribution

ensembles over the index set \overline{Π}. We require that X_{0} ≈^{c} X_{1}.

In addition to the threshold properties we need the following properties:

Message ring For all public keys pk, the message space R_{pk} is a ring in which we can compute efficiently using the public key only. We denote the ring (R_{pk}, ·_{pk}, +_{pk}, 0_{pk}, 1_{pk}).

+_{pk}-homomorphic There exists a PPT algorithm, which given public key pk and encryptions \overline{m}_{1} ∈ E_{pk}(m_{1}) and \overline{m}_{2} ∈ E_{pk}(m_{2}) outputs a uniquely determined encryption \overline{m} ∈ E_{pk}(m_{1} +_{pk} m_{2}). We write \overline{m} ← \overline{m}_{1} ⊞_{pk} \overline{m}_{2}. Further more there exists a similar algorithm for subtraction: \overline{m}_{1} ⊟_{pk} \overline{m}_{2} ∈ E_{pk}(m_{1} − m_{2}).

Multiplication by constant There exists a PPT algorithm, which on input pk, m_{1} ∈ R_{pk} and \overline{m}_{2} ∈ E_{pk}(m_{2}) outputs a random encryption \overline{m} ← E_{pk}(m_{1} ·_{pk} m_{2}). We assume that we can multiply a constant from both left and right. We write \overline{m} ← m_{1} ⊡_{pk} \overline{m}_{2} ∈ E_{pk}(m_{1} ·_{pk} m_{2}) and \overline{m} ← \overline{m}_{1} ⊡_{pk} m_{2} ∈ E_{pk}(m_{1} ·_{pk} m_{2}). Thus m_{1} ⊡_{pk} \overline{m}_{2} is not determined from m_{1} and \overline{m}_{2}. We let m_{1} ⊡_{pk} \overline{m}_{2}[r] denote the unique encryption produced by using r as random coins in the multiplication-by-constant algorithm.

Addition by constant There exists a PPT algorithm, which on input pk, m_{1} ∈ R_{pk} and \overline{m}_{2} ∈ E_{pk}(m_{2}) outputs a uniquely determined encryption \overline{m} ∈ E_{pk}(m_{1} +_{pk} m_{2}). We write \overline{m} ← m_{1} ⊞_{pk} \overline{m}_{2}.

Blindable There exists a PPT algorithm Blind, which on input pk, \overline{m} ∈ E_{pk}(m) outputs an encryption \overline{m}′ ∈ E_{pk}(m) such that \overline{m}′ =^{d} E_{pk}(m)[r], where r is chosen uniformly random.

Check of ciphertextness Given y ∈ {0, 1}^{∗} and pk where pk is a public key it is easy to check whether y ∈ C_{pk}^{3}.

Proof of plaintext knowledge Let L_{1} = {(pk, y)|pk is a public key ∧ y ∈ C_{pk}}. There exists a Σ-protocol for proving the relation over L_{1} × ({0, 1}^{∗})^{2} given by (pk, y) ∼ (x, r) ⇔ x ∈ R_{pk} ∧ y = E_{pk}(x)[r] .

Proof of correct multiplication Let L_{2} = {(pk, x, y, z)|pk is a public key∧ x, y, z ∈ C_{pk}}. There exists a Σ-protocol for proving the relation over L_{2} × ({0, 1}^{∗})^{3} given by (pk, x, y, z) ∼ (d, r_{1}, r_{2}) ⇔ y = E_{pk}(d)[r_{1}] ∧ z = (d ⊡_{pk} x)[r_{2}] .

We will usually drop the pk index when the key is given by the context or when stating something, that is true for all keys.

Remark 1 The existence of the algorithm for addition with a constant is given by the additive homomorphism. Simply let m_{1} ⊞ \overline{m}_{2} = E(m_{1})[r] ⊞ \overline{m}_{2} for some fixed random string r.

Remark 2 If 1_{pk} spans all of the additive group of R_{pk} and we can easily find n ∈ Z such that n1_{pk} = m for m ∈ R_{pk}, then the algorithm for multiplying by a constant can be implemented using a double and add algorithm combined with the blinding algorithm.

8 General MPC from Threshold Homomorphic Encryption

Assume that we have a threshold homomorphic encryption schema as described in Section 7. In this section we describe the FuncEval_{f} protocol which securely computes any PPT computable n-party f using an arithmetic circuit over the rings R_{pk} by computing on encrypted values. We focus on functions (y_{1}, …, y_{n}) ← f(x_{1}, …, x_{n}, r) with private inputs and outputs only and unrestricted domains.

We will describe and prove the protocols in the hybrid model where an ideal implementation (oracle) for decryption is given. By the composition theorem, this can be replaced by the secure implementation of decryption we have assumed.

3This check can be either directly or using a Σ-protocol: we will always use the test in a context, where a party publishes an encryption and then the recipients either check locally that y ∈ C_{pk} or the publisher proves it using a Σ-protocol. In the following sections we adopt the terminology to the case, where the recipients can perform the test locally. Details for the case where a Σ-protocol is used is easy extractable.

Since our encryption scheme is only +-homomorphic we will be needing a sub-protocol Mult for computing an encryption from E(m_{1}m_{2}) given encryptions from E(m_{1}) and E(m_{2}). We start by constructing the Mult sub-protocol.

Besides the Mult sub-protocol we will need a sub-protocol called Private-Decrypt which is used to decrypt an encryption \overline{a} in a way that only one specific party learns a.

After describing these sub-protocols and proving some results about their security, the remaining protocol and its security follows fairly directly.

In all sub-protocols we give as common input a set N′ ⊂ N. This is the subset of parties that is still participating in the computation. The set X = N \ N′ is called the excluded parties. Parties are excluded if they are caught deviating from the protocol. It is always the case that X ⊂ C, where C is the corrupted parties. At the start and termination of all subprotocols all honest parties agree on the set N′ of participating parties. This is ensured by the protocols. We will not mention N′ explicitly as input to all sub-protocols. Neither will we at all points where a party can deviate from the protocol mention that any party deviating should be excluded. E.g. will obvious syntactic errors in the broadcasted data automatically exclude a party from the remaining computation.

8.1 Some Sub-Protocols

8.1.1 The ASS (Additive Secret Sharing) Protocol

The first and crucial observation is that given a threshold homomorphic encryption scheme n parties can efficiently additively secret share an unknown value a ∈ R_{pk} given an encryption \overline{a} ∈ E_{pk}(a). We call the protocol for doing this ASS.

Description The participating parties N′ know a public encryption \overline{a} ∈ E_{pk}(a) for some possible unknown a ∈ R_{pk}. For i ∈ N′ the party P_{i} is to receive a secret share a_{i} ∈ R_{pk} such that a = ∑_{i∈N′} a_{i}. However, some of the parties in N′ might try to cheat. We define N^{(3)} to be N′ without those parties caught cheating and require that a is shared between the parties in N^{(3)}. Further more all parties output a common value A = \{\overline{a}_{i}\}_{i∈N^{(3)}}, where \overline{a}_{i} is an encryption of the share a_{i}.

Implementation

1. P_{i}, for i ∈ N′ chooses a value d_{i} uniformly at random in R_{pk}, computes an encryption \overline{d}_{i} ← E(d_{i}) and broadcasts it.

2. Let X be the subset of parties failing to broadcast a value from C_{pk} and set N′′ ← N′ \ X.

3. For i ∈ N′′ the participating parties run POPK to check that indeed each P_{i} knows r ∈ \{0, 1\}^{p(k)} and d ∈ R_{pk} such that \overline{d}_{i} = E_{pk}(d)[r].

4. Let X′ be the subset failing the proof of knowledge and set N^{(3)} ← N′′ \ X′.

5. Let d denote the sum ∑_{i∈N^{(3)}} d_{i}. All parties compute \overline{d} = ⊞_{i∈N^{(3)}} \overline{d}_{i} and \overline{e} = \overline{a} ⊞ \overline{d}.

6. The parties in N^{(3)} call Decrypt to compute the value a + d from \overline{e}.

7. The party in N^{(3)} with smallest index sets \overline{a_{i}} ← \overline{e}⊟\overline{d_{i}} and a_{i} ← a+d−d_{i}. The other parties in N^{(3)} set \overline{a_{i}} ← ⊟\overline{d_{i}} and a_{i} ← −d_{i}.

The ASS protocol secret shares a between all participating parties. Sharing it between fewer parties is also possible. To share between a subset S of the parties simply let P_{i} for i ∈ S generate the d_{i} values and run the above protocol with the remaining parties participating only as verifiers in the proofs of knowledge and when decrypting \overline{e}. A subrutine for simulating the ASS protocol follows later.

In the special case, where S = {i} is just one party the protocol just opens \overline{a} while revealing a only to some specific party P_{i}. We call this the PrivateDecrypt protocol and review the construction for completeness.

8.1.2 The PrivateDecrypt Protocol

Description The participating parties N′ know a public encryption \overline{a} ∈ E_{pk}(a) for some possible unknown a ∈ R_{pk}. The parties agree on a party P_{i} who is to receive a secretly.

Implementation

1. P_{i} chooses a value d uniformly at random in R_{pk}, computes an encryption \overline{d} ← E(d) and broadcasts it.

2. If \overline{d} is not an encryption from C_{pk} the parties terminate the protocol.

3. Now the participating parties run POPK where only P_{i} proves knowledge of r ∈ \{0, 1\}^{p(k)} and d ∈ R_{pk} such that \overline{d} = E_{pk}(d)[r].

4. If P_{i} fails to prove this the parties terminate the protocol.

5. All participating parties compute \overline{e} = \overline{a} ⊞ \overline{d}.

6. The participating parties call Decrypt to get the value e = a + d from \overline{e}.

7. P_{i} computes a = e − d.

The PrivateDecrypt Sub-Simulator

0. We are given as input (pk, \overline{a}, b) for some unknown a ∈ R_{pk} and known b ∈ E_{pk}. We want to simulate a private decryption, where we make it look as if E_{pk}(a) contains b.

1. If P_{i} is corrupt, then receive from the adversary \overline{d}. If P_{i} is honest then generate \overline{d} according to the protocol.

2. If P_{i} is corrupt, then check that \overline{d} ∈ C_{pk} and terminate if not.

3. Run S_{POPK}. If P_{i} is corrupt, then with overwhelming probability, this will either give us d or terminate because P_{i} failed the proof.

4. There is no need to compute \overline{e} = \overline{a} ⊞ \overline{d}.

5. Receive inputs for the Decrypt protocol from the adversary.

6. Give e = b + d to the adversary.

Denote by Private-Decrypt_{A}(pk, sk, \overline{a}) the view of the adversary A of an execution of the PrivateDecrypt protocol opening an encryption of a in the hybrid model with ideal evaluation of Decrypt. Denote by Private-Decrypt_{A}(pk, \overline{a}, b) the view of the adversary A of a simulation of an opening of \overline{a} faked to look as if it opened to b.

Theorem 1 For all a ∈ R_{pk} and \overline{a} ∈ E_{pk}(a) the random variables Private-Decrypt_{A}(pk, sk, \overline{a}) and PrivateDecryptSim_{A}(pk, \overline{a}, a) are statistically indistinguishable.

Proof: This is trivial by inspection of the protocol and the simulator. □

Surprisingly the proof of security of the global protocol that uses the PrivateDecrypt protocol does not need any properties about the PrivateDecrypt protocol, when a ≠ b. This situation will therefore not be analysed.

8.1.3 The Mult Protocol

Description Each party P_{i} knows common values \overline{a} ∈ E(a) and \overline{b} ∈ E(b) and wants to compute a common value \overline{c} ∈ E(ab).

Implementation

1. First all participating parties additively secret share the value of a using the ASS protocol. Let N^{(3)} be the parties still participating after this. For i ∈ N^{(3)} let a_{i} and \overline{a}_{i} be the share resp. the public encryption of the share of P_{i}.

2. Each party P_{i} for i ∈ N^{(3)} computes \overline{f}_{i} ← a_{i} ⊡ \overline{b} and broadcasts it.

3. Each party P_{i} for i ∈ N^{(3)} proves that \overline{f}_{i} by running POCM.

4. Let X′′ be the subset failing the proof and let N^{(4)} ← N^{(3)} \ X′′.

5. The parties compute \overline{a}_{X′′} = ⊞_{i∈X′′} \overline{a}_{i} and decrypt it using Decrypt to obtain a_{X′′} = +_{i∈X′′}a_{i}.

6. All parties compute \overline{c} ← (⊞_{i∈N^{(4)}} \overline{f}_{i}) ⊞ (a_{X′′} ⊡ \overline{b}) ∈ E_{pk}(ab).

A Sub-Simulator for the Mult Protocol We construct a sub-simulator for the Mult Protocol. It receives as input a public key pk and encryptions \overline{a}, \overline{b}, and an encryption of c = ab, denoted \overline{c}′. It then simulates the multiplication protocol as if it was run on input \overline{a} and \overline{b}.

1. First we simulate the ASS sub-protocol.

(a) Let s be the smallest index of an honest player, and let H be the set of remaining honest players. Generate d_{i} and \overline{d_{i}} correctly for i ∈ H, and define d_{s} to be d′_{s} − a for uniformly randomly chosen d′_{s} and set \overline{d}_{s} ← E_{pk}(d′_{s}) ⊟ \overline{a}. Hand these value to the adversary and receive from the adversary \{(i, \overline{d}_{i})\}_{i∈N′}.

(b) Define N′′ as in the ASS protocol.

(c) Run S_{POPK}, thus obtaining (with large probability) all d_{i}’s from corrupt players that continue to participate.

(d) Define N^{(3)} as in the ASS protocol.

(e) Compute e = a+d. This is possible as ∑_{i∈N^{(3)}} d_{i} = (∑_{i∈N^{(3)}\{s}} d_{i})+ d′_{s} − a, so e = (∑_{i∈N^{(3)}\{s}} d_{i}) + d′_{s}.

(f) Compute \overline{d} and \overline{e} as specified by the protocol. Observe that \overline{d} and \overline{e} are indeed encryptions of d = ∑_{i∈N^{(3)}} d_{i} resp. e = a + d.

(g) We now need to simulate the Decrypt to A. This is easy as we know the plaintext of \overline{e}. We simply hand e to the adversary.

2. For i ∈ H compute the \overline{f}_{i} values correctly as a_{i} ⊡ \overline{b}. For s we must compute a_{s} ⊡ \overline{b} = (d′_{s} − a) ⊡ \overline{b} ∈ E_{pk}(d′_{s}b − ab). We do this as \overline{f}_{s} ← Blind((d′_{s} ⊡ \overline{b}) ⊟ \overline{c}′). Hand these values to the adversary and receive the \overline{f}_{i} values for the corrupted parties that are still participating.

3. Run S_{POCM}

4. Let X′′ be the subset failing the proof and let N^{(4)} be as in the protocol.

5. For i ∈ X′′ we know a_{i} and can easily simulate the Decrypt protocol by handing a_{X′′} = +_{i∈N′′}a_{i} to the adversary.

6. The final step in the protocol is non-interactive, so the simulator does not need to produce anything. But note that the result following from the simulation is \overline{c} ← (⊞_{i∈N^{(4)}} \overline{f}_{i}) ⊞ (a_{X′′} ⊡ \overline{b}) ∈ E_{pk}(ab).

Theorem 2 The view presented to A during the simulation of a multiplication of \overline{a} and \overline{b} is distributed statistically indistinguishable from the view presented to A during a Decrypt-hybrid-model execution of the Mult protocol on input \overline{a} and \overline{b}.

Proof: Observe that except for \overline{d}_{s}, \overline{f}_{s}, and the two simulated zero-knowledge proofs for \overline{d}_{s} and \overline{f}_{s} the simulation of the Mult protocol just follows the protocol and is thus distributed exactly as in the Decrypt-hybrid-model execution.

In the Decrypt-hybrid-model execution the value of \overline{d}_{s} is a random encryption of a uniformly random element from R_{pk}. In the simulation d′_{s} is uniformly random from R_{pk}, so d′_{s} − a is uniformly random and thus \overline{d}_{s} is an encryption of a uniformly random element from R_{pk}. We generate E_{pk}(d′_{s}) randomly and by assumption we therefore have that E_{pk}(d′_{s}) ⊟ \overline{a} is distributed as a random encryption of d′_{s} − a. All in all \overline{d}_{s} is distributed identically in the simulation and the Decrypt-hybrid-model execution.

In the Decrypt-hybrid-model execution the value of \overline{f}_{s} is by assumption distributed as a random encryption of a_{s}b. Because of the use of Blind this is the case in the simulation too.

We now have that except for two simulated zero-knowledge proofs the simulation is distributed exactly as in the Decrypt-hybrid-model execution.

The theorem now follows from the properties we have shown earlier for S_{POPK} and S_{POCM}. □

8.2 The FuncEval_{f} Protocol (Deterministic f)

We are set up to present the FuncEval_{f} protocol for deterministic f. The protocol evaluates any deterministic n-party function f : N × ({0, 1}^{∗})^{n} → ({0, 1}^{∗})^{n} over the rings R_{pk} using a uniform polynomially sized family of arithmetic circuits. One way of doing this is to write f as a boolean circuit with only ∧ and ¬-gates and then evaluate this circuit using the standard arithmetisation identifying 0 and 1 with 0_{pk} resp. 1_{pk} and identifying ∧ and ¬ with (x, y) ↦ x ·_{pk} y resp. x ↦ 1 −_{pk} x. Depending on the rings R_{pk} and f much more efficient embeddings might be possible. We therefore make minimal assumptions about the way the computation of the function f is embedded into the rings R_{pk}.

We assume that we are given three PPT algorithms: the input encoder I, the circuit generator H, and the output decoder O.

The Input Encoder On input pk, i ∈ N, and x_{i} ∈ {0, 1}^{∗} the input encoder I outputs an encoding ξ_{i} ∈ (R_{pk})^{l_{i}(k)} for some polynomial l_{i}(k). We call the value ξ_{i} the legal circuit input of P_{i}. Let Ξ_{pk,i} ⊂ (R_{pk})^{l_{i}} denote the codomain of I(pk, i, ·). We require that I is PPT invertible in x_{i}, i.e. there exists a PPT algorithm I^{−1} which on input pk, i, and ξ_{i} ∈ Ξ_{pk,i} computes x_{i} such that I(pk, i, x_{i}) = ξ_{i}. By \overline{Ξ}_{pk,i} ⊂ (C_{pk})^{l_{i}(k)} we denote the set

\{(\overline{ξ}_{1}, …, \overline{ξ}_{l_{i}(k)}) ∈ (C_{pk})^{l_{i}(k)}|(ξ_{1}, …, ξ_{l_{i}(k)}) ∈ Ξ_{pk,i}\}

of legal encrypted circuit inputs.

We require that we have a Σ-protocol allowing a party that knows x_{i} ∈ \{0, 1\}^{∗}, has computed (ξ_{1}, …, ξ_{l_{i}(k)}) ← I(pk, i, x_{i}), and published (\overline{ξ}_{1}, …, \overline{ξ}_{l_{i}(k)}) ∈ \overline{Ξ}_{pk,i} to prove that the published value is indeed an encrypted circuit input. For the simulation of Boolean circuits mentioned above, such protocols are easily constructed in our example cryptosystems shown later.

The Circuit Generator On input 1^{k} and pk H outputs an arithmetic circuit H_{pk} over R_{pk} using inputs and constants from R_{pk}, and addition, subtraction, and multiplication over R_{pk}. The circuit H_{pk} is given as a list of gates (H_{pk}^{1}, …, H_{pk}^{l}) and n lists O_{1}, …, O_{n} of output gates O_{i} = (O_{i,1}, …, O_{i,o_{i}}). We require that no gate H_{pk}^{j} depends on a gate H_{pk}^{j′} where j′ ≥ j and that 1 ≥ O_{i,j} ≤ l for i = 1, …, n, j = 1, …, o_{i}. The gates is on one of the following forms.

• H_{pk}^{j} = (input, i, j_{1}), where 1 ≤ i ≤ n and 1 ≤ j_{1} ≤ l_{i}(k).

• H_{pk}^{j} = (constant, v), where v ∈ R_{pk}.

• H_{pk}^{j} = (+, j_{1}, j_{2}), where 1 ≥ j_{1}, j_{2} < j.

• H_{pk}^{j} = (−, j_{1}, j_{2}), where 1 ≥ j_{1}, j_{2} < j.

• H_{pk}^{j} = (·, j_{1}, j_{2}), where 1 ≥ j_{1}, j_{2} < j.

We call (h^{1}, …, h^{l}) ∈ (R_{pk})^{l} a plaintext evaluation of H_{pk} on circuit input (ξ_{1}, …, ξ_{n}) if the following holds. If H_{pk}^{j} = (input, i, j_{1}), then h^{j} = ξ_{i,j_{1}}; if H_{pk}^{j} = (constant, v), then h^{j} = v; if H_{pk}^{j} = (+, j_{1}, j_{2}), then h^{j} = h^{j_{1}} +_{pk} h^{j_{2}}; if H_{pk}^{j} = (−, j_{1}, j_{2}), then h^{j} = h^{j_{1}} −_{pk} h^{j_{2}}; and if H_{pk}^{j} = (·, j_{1}, j_{2}), then h^{j} = h^{j_{1}} ·_{pk} h^{j_{2}}.

We call (\overline{h}^{1}, …, \overline{h}^{l}) ∈ (C_{pk})^{H_{pk}} a ciphertext evaluation of H_{pk} on input (ξ_{1}, …, ξ_{n}) if (h^{1}, …, h^{l}), where h^{j} is the plaintext of \overline{h}^{j}, is a plaintext evaluation of H_{pk} on input (ξ_{1}, …, ξ_{n}).

For function input (x_{1}, …, x_{n}) ∈ ({0, 1}^{∗})^{n} the circuit input (ξ_{1}, …, ξ_{n}) ∈ Ξ is uniquely given and thereby the plaintext evaluation is uniquely given. Of course many ciphertext evaluations exists. Let (h^{1}, …, h^{l}) be the plaintext evaluation on circuit input (ξ_{1}, …, ξ_{n}) (function input (x_{1}, …, x_{n})). We call (h^{O_{i,1}}, h^{O_{i,2}}, …, h^{O_{i,l_{i}}}) the circuit output of P_{i} on circuit input (ξ_{1}, …, ξ_{n}) (function input (x_{1}, …, x_{n})).

The Output Decoder For all function inputs (x_{1}, …, x_{n}) and corresponding circuit output (h^{O_{i,1}}, h^{O_{i,2}}, …, h^{O_{i,l_{i}}}) of party P_{i} the output decoder O outputs y_{i} ∈ {0, 1}^{∗} such that y_{i} = f(x_{1}, …, x_{n})_{i}. We require that O is invertible in the circuit output and that O^{−1}(pk, i, y_{i}) is computable in PPT.

The FuncEval_{f} Algorithm (Deterministic f) The protocol runs in the (RO, KD, Decrypt)-hybrid model and proceeds as follows.

1. The parties make an oracle call to the KD oracle.

2. The party P_{i} obtains pk as public output and sk_{i} as secret output.

3. Each party generates (H_{pk}, O_{pk,1}, …, O_{pk,n}) ← H(pk).

4. Each party P_{i} computes ξ_{i} = (ξ_{i,1}, …, ξ_{i,l_{i}}) ← I(pk, i, x_{i}).

5. For i = 1 to n, j = 1 to l_{i} do the following

• Party P_{i} computes an encryption ξ̄_{i,j} ← E_{pk}(ξ_{i,j})[r_{i,j}] for uniformly random r_{i,j} and broadcasts it.

The parties run the POPK protocol to check that each P_{i} does in fact know the plaintext of \overline{ξ}_{i,j}.

6. All parties P_{i} not failing the above proofs of plaintext knowledge prove in zero-knowledge that \overline{ξ}_{i} = (\overline{ξ}_{i,1}, …, \overline{ξ}_{i,l_{i}}) ∈ \overline{Ξ}_{i}.

Let X be the set of parties failing either a proof of plaintext knowledge or a proof that \overline{ξ}_{i} is a legal encrypted circuit input. For i ∈ X all other parties take x_{i} to be ϵ and compute ξ_{i} ← I(pk, i, x_{i}) and \overline{ξ}_{i,j} ← E_{pk}(ξ_{i,j})[r_{i,j}] for some fixed agreed upon string r_{i,j} = r ∈ {0, 1}^{p(k)}, say r = 0^{p(k)}.

In this way all parties get to know legal encrypted circuit inputs for all parties.

7. For j = 1 to l do the following.

(a) If H_{pk}^{j} = (input, i, j_{1}) then all parties set \overline{h}^{j} to \overline{ξ}_{i,j_{1}}.

(b) If H_{pk}^{j} = (constant, v) then all parties set \overline{h}^{j} to \overline{v} = E_{pk}(v)[r] for some fixed agreed upon string r ∈ {0, 1}^{p(k)}.

(c) If H_{pk}^{j} = (+, j_{1}, j_{2}) then all parties set \overline{h}^{j} to \overline{h}^{j_{1}} ⊞ \overline{h}^{j_{2}}.
(d) If H_{pk}^{j} = (−, j_{1}, j_{2}) then all parties set \overline{h}^{j} to \overline{h}^{j_{1}} ⊟ \overline{h}^{j_{2}}.

(e) If H_{pk}^{j} = (·, j_{1}, j_{2}) then the parties execute the Mult protocol on

the encryptions \overline{h}^{j_{1}} and \overline{h}^{j_{2}} and set \overline{h}^{j} to be the result of the Mult protocol.

8. For each party P_{i} still participating and j = 1, …, o_{i} the parties execute the PrivateDecrypt protocol and reveals h^{O_{i,j}} to P_{i}.

9. Each party P_{i} computes y_{i} ← O(pk, i, (h^{O_{i,1}}, h^{O_{i,2}}, …, h^{O_{i,o_{i}}})).

The Simulator for the FuncEval_{f} Protocol (Deterministic f) Let A be any (RO, KD, Decrypt)-hybrid-model adversary. We construct a corresponding ideal-model adversary I(A). The inputs for the adversary I(A) is a set of corrupted parties C, their secret inputs {x_{i}}_{i∈C}, an auxiliary string a, and a random input r_{S}.

0. Initialise the hybrid adversary A with C, {x_{i}, r_{i}}_{i∈C}, a, and r_{A}, where r_{i} and r_{A} are uniformly random.

1. Simulate the oracle call to KD: for the honest parties use the correct input and receive from A the inputs from the corrupted parties.

2. Generate a key (pk, sk_{1}, …, sk_{n}) and give {(i, (sk_{i}, pk))}_{i∈C} to A. The simulator will not use sk_{i} for i ∈ \overline{C}.

3. Generate (H_{pk}, O_{pk,1}, O_{pk,n}).

4. Generate the circuit inputs (ξ_{i,1}, …, ξ_{i,l_{i}}) for the honest parties using x_{i} = ϵ.

5. For i = 1 to n, j = 1 to l_{i} do the following

• If P_{i} is honest then compute \overline{ξ}_{i,j} = E_{pk}(ξ_{i,j})[r_{i,j}] as in the protocol. Otherwise receive the encryption \overline{ξ}_{i,j} from A.

Run S_{POPK}, in particular we obtain from this ξ_{i,j} for those corrupted P_{i} that continue to participate.

6. Following the algorithm of S_{Σ}, simulate the proof phase with proofs that \overline{ξ}_{i} ∈ \overline{Ξ}_{pk,i}. In particular, extract ξ_{i,j} for corrupted parties continuing to participate.

If any corrupted party fails the above proofs then handle this as in the protocol. Since the plaintexts ξ_{i,j} of all corrupted parties completing the above proofs were extracted the simulator now knows a legal plaintext circuit input for all parties. From these compute the corresponding plaintext evaluation (h^{1}, …, h^{l}) and an ciphertext evaluation (h̃^{1}, …, h̃^{l}).

From the legal plaintext circuit inputs of the corrupted parties compute the corresponding function input x_{i} = I^{−1}(pk, i, (ξ_{i,1}, …, ξ_{i,l_{i}})). Use these function inputs as the corrupted parties inputs in the idealevaluation. From the ideal evaluation we obtain y_{i} for all corrupted parties and compute the plaintext circuit output (h^{O_{i,1}}, …, h^{O_{i,o_{i}}}) = O^{−1}(pk, i, y_{i}) of all corrupted parties.

7. For j = 1 to l do the following.

(a) If H_{pk}^{j} = (input, i, j_{1}) then set \overline{h}^{j} = \overline{ξ}_{i,j_{1}}.

(b) If H_{pk}^{j} = (constant, v) then set \overline{h}^{j} = E_{pk}(v)[r].

(c) If H_{pk}^{j} = (+, j_{1}, j_{2}) then set \overline{h}^{j} = \overline{h}^{j_{1}} ⊞ \overline{h}^{j_{2}}.

(d) If H_{pk}^{j} = (−, j_{1}, j_{2}) then set \overline{h}^{j} = \overline{h}^{j_{1}} ⊟ \overline{h}^{j_{2}}.

(e) If H_{pk}^{j} = (·, j_{1}, j_{2}) then let h̃^{j} be the encryption computed in Step

6 and run the Mult-simulator on the inputs (\overline{h}^{j_{1}}, \overline{h}^{j_{2}}, h̃^{j}). Set \overline{h}^{j} to be the result of the simulation.

8. For each party P_{i} still participating and j = 1, …, o_{i} do the following. If P_{i} is corrupted, then run the PrivateDecrypt sub-simulator on the input (\overline{h}^{O_{i,j}}, h^{O_{i,j}}), where h^{O_{i,j}} is the value computed in Step 6. If P_{i} is honest we do not know what we should decrypt to, and it does not matter, so run the sub-simulator PrivateDecrypt on say (\overline{h}^{O_{i,j}}, 1_{pk}).

9. Now for all corrupted parties P_{i} we have that y_{i} = O(pk, i, (h^{O_{i,1}}, h^{O_{i,2}}, …, h^{O_{i,o_{i}}}) as should be, where y_{i} is the secret output of P_{i} from the idealevaluation in Step 6.

It is clear from the description that this simulation runs in expected polynomial time. In order to argue that the output distribution is correct, we need to define an ”intermediary” distribution:

Yet Another Distribution We describe two distributions over the indices (k, x⃗, C, a). The idea is to define them by one procedure taking an encryption of a bit b̄ as input. The two distributions result from b = 0, respectively b = 1. The procedure will be constructed such that if b = 1, it produces something close to the adversary’s view of a real execution, whereas b = 0 results in something close to a simulation. Our result then follows from semantic security of the encryption.

Let A be any (RO, KD, Decrypt)-hybrid-model adversary, let pk be a public key, and let \overline{b} ∈ E_{pk}(b) be an encryption, where b is either 0_{pk} or 1_{pk}. For v_{0}, v_{1} ∈ R_{pk} let d(v_{0}, v_{1}, \overline{b}) = Blind((v_{1} ⊡ \overline{b}) ⊞ (v_{0} ⊡ (1_{pk} ⊟ \overline{b}))). Observe that d(v_{0}, v_{1}, \overline{b}) is a random encryption of v_{0} if b = 0_{pk} and a random encryption of v_{1} if b = 1_{pk}.

By YAD_{A}^{pk,sk_{C},\overline{b}}(k, x⃗, C, a) we denote the distribution produced as follows.

0. Initialise the hybrid adversary A with C, {x_{i}, r_{i}}_{i∈C}, a, and r_{A}, where r_{i} and r_{A} are uniformly random

1. Simulate the oracle call to KD: for the honest parties use the correct input, show these to A, and receive from A the inputs from the corrupted parties.

2. Now we use the public key pk and secret key shares sk_{C}. We give {(i, (sk_{i}, pk))}_{i∈C} to A.

3. Generate (H_{pk}, O_{pk,1}, …, O_{pk,n}).

4. For the honest parties we use as plaintext input to the circuit either the values ξ_{i}^{1} = I(pk, i, x_{i}), where x_{i} is given in the index of the distribution YAD or ξ_{i}^{0} = I(pk, i, ϵ) as in the simulator. We make the choice conditioned on b using the method described above.

5. For i = 1 to n, j = 1, …, l_{i} do the following

• If P_{i} is honest then compute \overline{ξ}_{i,j} as d(ξ_{i,j}^{0}, ξ_{i,j}^{1}, \overline{b}) and broadcast. Otherwise receive the encryption \overline{ξ}_{i,j} from A.

Run S_{POPK}, in particular obtain ξ_{i,j} for those corrupt P_{i} that still participate.

6. Following the algorithm of S_{Σ}, simulate the proof phase with proofs that \overline{ξ}_{i} ∈ \overline{Ξ}_{pk,i}. In particular, extract ξ_{i,j} for corrupted parties continuing to participate.

If any corrupted party fails the proofs, then handle this as in the protocol. Since the plaintext circuit inputs of all corrupted parties completing the proofs were extracted we now know plaintext circuit inputs for all corrupted parties. We don’t know the plaintext values for the honest parties’ input lines as these depend on the value of b.

Let (h_{1}^{0}, h_{2}^{0}, …, h_{n}^{0}) be the plaintext evaluation corresponding to function input x_{i} for the honest parties (b = 1), let (h_{1}^{1}, h_{2}^{1}, …, h_{n}^{1}) be the plaintext evaluation corresponding to function input ϵ for the honest parties (b = 0), and let h̃^{j} ← b(h_{0}^{j}, h_{1}^{j}, \overline{b}) for j = 0, …, l. Then obviously (h̃^{1}, …, h̃^{l}) is ciphertext evaluation of H_{pk} on the ciphertext input published in Step 5.

From the legal plaintext circuit inputs of the corrupted parties compute the corresponding function input x_{i} = I^{−1}(pk, i, (ξ_{i,1}, …, ξ_{i,l_{i}})). Use these function inputs as the corrupted parties’ function inputs, use x_{i} as given in the index of YAD as the honest parties’ function inputs, and compute (y_{1}, …, y_{n}) ← f(x_{1}, …, x_{n}). We then compute the plaintext circuit output (h^{O_{i,1}}, …, h^{O_{i,o_{i}}}) = O^{−1}(pk, i, y_{i}) of all corrupted parties.

7. For i = 1 to n, j = 1 to l_{i} do the following

(a) If H_{pk}^{j} = (input, i, j_{1}) then set \overline{h}^{j} = \overline{ξ}_{i,j_{1}}.

(b) If H_{pk}^{j} = (constant, v) then set \overline{h}^{j} = E_{pk}(v)[r].

(c) If H_{pk}^{j} = (+, j_{1}, j_{2}) then set \overline{h}^{j} = \overline{h}^{j_{1}} ⊞ \overline{h}^{j_{2}}.

(d) If H_{pk}^{j} = (−, j_{1}, j_{2}) then set \overline{h}^{j} = \overline{h}^{j_{1}} ⊟ \overline{h}^{j_{2}}.

(e) If H_{pk}^{j} = (·, j_{1}, j_{2}) then let h̃^{j} be the encryption computed in Step

6 and run the Mult-simulator on the inputs (\overline{h}^{j_{1}}, \overline{h}^{j_{2}}, h̃^{j}). Set \overline{h}^{j} to be the result of the simulation.

8. For each party P_{i} still participating and j = 1, …, o_{i} do the following. If P_{i} is corrupted, then run the PrivateDecrypt sub-simulator on the input (\overline{h}^{O_{i,j}}, h^{O_{i,j}}), where h^{O_{i,j}} is the value computed in Step 6. If P_{i} is honest we do not know what we should decrypt to, and it does not matter, so run the sub-simulator PrivateDecrypt on (\overline{h}^{O_{i,j}}, 1_{pk}).

9. Now for all honest parties P_{i} take the output to be y_{i} as computed in Step 6 and for the corrupted parties let the output be y_{i} = ⊥. Receive the final output z from A and set YAD_{A}^{pk,sk_{C},\overline{b}}(k, x⃗, C, a) = (y_{1}, …, y_{n}, z).

For b ∈ \{0, 1\} let YAD_{A}^{b}(k, x⃗, C, a) be YAD_{A}^{pk,sk_{C},\overline{b}}(k, x⃗, C, a) where the keys are uniformly random over K_{k} and \overline{b} is a random encryption of b_{pk}. Let YAD_{A}^{b} denote the distribution ensemble

{YAD_{A}^{b}(k, x⃗, C, a)}_{k∈N,x⃗∈({0,1}^{∗})^{n},a∈{0,1}^{∗}} .

Lemma 1

EXEC

RO,KD,Decrypt FuncEval_{f} ,I(A)

≈^{s} YAD

1 A

Proof: We simply look at how the distributions EXEC_{FuncEval_{f} ,I(A)}^{RO,KD,Decrypt}(k, x⃗, C, a) and YAD_{A}^{1}(k, x⃗, C, a) are defined an observe that they maintain statistically indistinguishability for each step.

0. In both distributions the adversary is initialised with k, C, {(i, x_{i})}_{i∈C}, a, and uniformly random input r_{A}.

1. Then the oracle call to KeyGeneration is performed identically in both distributions.

2. Then in both distributions A receives {(i, (sk_{i}, pk))}_{i∈C} for keys chosen uniformly random in K_{k}.

3. Then all parties locally generate (H_{pk}, O_{pk,1}, …, O_{pk,l_{i}}).

4. The function inputs x_{i} used by the honest parties are the same in the two distributions as they are a part of the index.

5. Then the inputs are distributed

(a) In the real-life execution the honest parties broadcast a random encryption of ξ_{i,j} and in the YAD^{1} distribution the value b(ξ_{i,j}^{0}, ξ_{i,j}^{1}, \overline{b}) is distributed as random encryption of ξ_{i,j}^{1} = ξ_{i,j}.

(b) In the real-life execution the honest parties all run the POPK protocol correctly. In the YAD^{1} distribution the protocol is simulated. However in the random oracle model this simulation is statistically indistinguishable from a real execution. The knowledge extraction in the YAD^{1} distribution which does of course not occur in the real-life execution is not detectable by the adversary as the adversary is rewound first and will afterwards continue execution as if the extraction never took place.

6. In the YAD^{1} distribution the honest parties simulate the proof that \overline{ξ}_{i} ∈ \overline{Ξ}_{i}, but again this is statistically indistinguishable from a real execution of the zero-knowledge protocol.

Obviously the values h̃^{j} preprocessed in the YAD^{1} distribution for gate j will contain exactly the same plaintext as the encryption \overline{h}^{j} computed for that gate in the (RO, KD, Decrypt)-hybrid-model execution.

7. Now the gates are evaluated in both distributions.

(a-d) Inputting, constant assignment, addition, and subtraction are local computations and are performed exactly the same way in both distributions.

(e) In the (RO, KD, Decrypt)-hybrid-model execution multiplications are carried out using the Mult protocol to compute \overline{h}^{j}. In the YAD^{1} distribution they are carried out using the Mult sub-simulator on the inputs (\overline{h}^{j_{1}}, \overline{h}^{j_{2}}, h̃^{j}). But the inputs \overline{h}^{j_{1}} and \overline{h}^{j_{2}} are as noted distributed statistically indistinguishable in the two distributions and as noted in Step 6 the encryptions h̃^{j} and \overline{h}^{j} contain the same plaintext. It then follows from Theorem 2 that indeed \overline{h}^{j} is statistically indistinguishable in the two distributions.

8. Using Theorem 1 and the fact that I^{−1} computes the correct plaintext output of the circuit, we get that the adversary’s view of the decryptions in the two views are computationally indistinguishable.

9. Now in both distributions the output of honest party P_{i} is y_{i}, where y_{i} = O(pk, i, (h^{O_{i,1}}, h^{O_{i,2}}, …, h^{O_{i,o_{i}}}) in the execution and y_{i} = O(pk, i, (h^{O_{i,1}}, h^{O_{i,2}}, …, h^{O_{i,o_{i}}}) in YAD^{1} as the the values h^{O_{i,j}} are statistically indistinguishable in the two distributions. In both distributions y_{i} = ⊥ for the corrupted parties. Since the views presented to the adversary in the two distributions are computationally indistinguishable, so is z, the final output of the adversary. All in all the value (y_{1}, …, y_{n}, z) is statistically indistinguishable in the two distributions, and so are then the distributions.

□

Lemma 2

IDEAL_{f,A} =^{d} YAD_{A}^{0}

Proof: This is a simple comparison of the definitions of the distributions as done in the proof of Lemma 1. □

Lemma 3

YAD_{A}^{0} ≈^{c} YAD_{A}^{1}

Proof:

Assume that we have a hybrid adversary A and a distinguisher D for the distributions YAD_{A}^{0} and YAD_{A}^{1} that does better than negligible. That means that for any negligible function δ and any k ∈ N there exists (x⃗_{δ,k}, C_{δ,k}, a_{δ,k}) ∈ (\{0, 1\}^{∗})^{n} × \overline{Π} × \{0, 1\}^{∗} and w_{δ,k} ∈ \{0, 1\}^{∗} such that

| Pr[D(k, x⃗_{δ,k}, C_{δ,k}, a_{δ,k}, w_{δ,k}, YAD_{A}^{0}(k, x⃗_{δ,k}, C_{δ,k}, a_{δ,k})) = 1] −
Pr[D(k, x⃗_{δ,k}, C_{δ,k}, a_{δ,k}, w_{δ,k}, YAD_{A}^{1}(k, x⃗_{δ,k}, C_{δ,k}, a_{δ,k})) = 1]|
≥ δ(k)

From D we build a distinguisher D′ for the distributions (C, pk, sk_{C}, \overline{0_{pk}}) and (C, pk, sk_{C}, \overline{1_{pk}}) as follows. On input (k, C, pk, sk_{C}, \overline{b}, w′), where w′ ∈ {0, 1}^{∗} is an auxiliary input, interpret a prefix of w′ as an input x⃗ = (x_{1}, …, x_{n}) for the function f and an auxiliary input a for A. Denote the remaining part of w′ by w. Then compute a value YAD according to the distribution YAD_{A}^{pk,sk_{C},\overline{b}}(k, x⃗, C, a). Observe that since the keys are chosen uniformly random YAD is drawn from the distribution YAD_{A}^{b}(k, x⃗, C, a). Now run D on the input (k, x⃗, C, a, w, YAD) and output the same as D.

Now for any negligible function δ and any k let C′_{δ,k} = C_{δ,k} and let w′_{δ,k} = x⃗_{δ,k}, a_{δ,k}, w_{δ,k}. Then

| Pr[D′(k, C′_{δ,k}, pk, sk_{C}, \overline{0_{pk}}, w′_{δ,k}) = 1] − Pr[D′(k, C′_{δ,k}, pk, sk_{C}, \overline{1_{pk}}, w′_{δ,k}) = 1]| =

| Pr[D(k, x⃗_{δ,k}, C_{δ,k}, a_{δ,k}, w_{δ,k}, YAD_{A}^{0}(k, x⃗_{δ,k}, C_{δ,k}, a_{δ,k})) = 1] −

Pr[D(k, x⃗_{δ,k}, C_{δ,k}, a_{δ,k}, w_{δ,k}, YAD_{A}^{1}(k, x⃗_{δ,k}, C_{δ,k}, a_{δ,k})) = 1]| ≥ δ(k)

This is in contradiction with the threshold semantic security assumption, which guarantees that the distributions (pk, C, sk_{C}, \overline{0_{pk}}) and (pk, C, sk_{C}, \overline{1_{pk}}) are computationally indistinguishable for C ∉ Π and uniformly random key (pk, sk_{1}, …, sk_{n}). □

We note that the threshold homomorphic encryption schemes we present in Section 9 are all secure against the minority threshold adversary structure, where the adversary can corrupt any minority of the parties. When we remove the random oracle assumption by doing the zero-knowledge proofs as described in Section 6.1.1 we can only prove security against essentially the minority threshold adversaries anyway (as k bits of the challenge must be random). We therefore formulate the following theorems for the minority threshold adversaries.

Theorem 3 Let f be any deterministic n-party function. The FuncEval_{f} protocol as described above, but with oracle calls replaced by real-life executions of the KD and Decrypt protocols of an encryption scheme with the assumed properties and the majority threshold access structure securely evaluates f in the presence of active static minority threshold adversaries in the random oracle model.

The communication complexity of the protocol is O((nk +d)|f|) bits, where |f| denotes the size of the circuit for evaluating f^{4} and d denotes the communication complexity of a decryption.

Proof: The security claim follows directly from Lemmas 1, 2, and 3 and the modular composition theorem of the MPC model[4].

The communication complexity follows by inspection. The gates that give rise to communication is the input, multiplication, and output gates. The communication used to handle these gates is in the order of n encryptions (O(nk) bits), n zero-knowledge proofs (O(nk) bits as we have assumed that the Σ-protocols have communication complexity O(k)) and 1 decryption (O(d) bits by definition). The total communication complexity therefore is O((nk+d)|f|) as claimed.

Observe that this communication complexity holds even when parties are caught deviating from the protocol. The only place, where correcting faulty behaviour has a significant cost is in Step 5 in the Mult protocol, where an execution of the Decrypt protocol is necessary. The Mult protocol does however already use an execution of the Decrypt protocol, so the fault handling only costs a constant factor. □

The threshold homomorphic encryption schemes we present in Section 9 both have d = O(kn). It follows that for deterministic f the FuncEval_{f} protocol based on any of these schemes has communication complexity O(nk|f|) bits in the random oracle model.

In the scheme based on Paillier’s cryptosystem [16] the expansion factor of the encryption is constant and the plaintext space is Z_{n} for a RSA modulus n. If the function f is over Z it might therefore very well be possible to embed its computation into Z_{n} in a way, where each encryption in a ciphertext evaluation represents O(k) bits of an arithmetic circuit for computing f. In this case the communication complexity would be O(nT (f)), where T (f) is the circuit complexity of f over Z.

Theorem 4 Let f be any deterministic n-party function. The FuncEval_{f} protocol as described above, but doing the zero-knowledge proofs as described in Section 6.1.1 and with oracle calls replaced by real-life executions of the KD and Decrypt protocols of an encryption scheme with the assumed properties and the majority access structure securely evaluates f in the presence of active static minority threshold adversaries in the real-life model.

The communication complexity of the protocol is O((n max(k, n) + d)|f|) bits.

4If this size depends for the public key one can adopt either a worstcase or expect complexity measure.

Proof: The security claim follows from the discussion in Section 6.1.1. From the proof of Theorem 3 we see that the factor k in the term nk is the communication complexity of the zero-knowledge proofs. This factor becomes max(k, n) in the real-life model and the claimed communication complexity follows directly. □

Using the threshold homomorphic encryption schemes we present in Section 9 the communication complexity becomes O(n max(k, n)|f|) as they both have d = O(n max(k, n)) in the real-life model.

8.3 The FuncEval_{f} Protocol (Probabilistic f)

Assume now that f takes a random input r. We can simply regard r as the input of a (n+1)th party and let the n parties in corporation choose a random input for that party. Our MPC model obviously requires that the parties does not learn the random input. How to choose the random input depends on the input encoding. Assume that we simply represent r ∈ {0, 1}^{p(k)} in the trivial way over {0_{pk}, 1_{pk}}^{p(k)}. The parties then need to be able to choose an encryption \overline{b} of a uniformly random value b ∈ \{0, 1\}.

One way to do this is to let the parties each choose at random a bit x_{i} and then use the FuncEval protocol to compute the function ⊕(x_{1}, …, x_{n}) = x_{1} ⊕ ⋯ ⊕ x_{n} as if the result was for a (n + 1)th party, i.e. up to, but not including the execution of P rivateDecrypt on the final result \overline{x_{1} ⊕ ⋯ ⊕ x_{n}}. As the result was computed as if b was to be revealed only to the n+1th party, the value b is unknown to the n actual parties. Using that a ⊕ b = a + b − 2ab we can compute ⊕(x_{1}, …, x_{n}) = x_{1} ⊕ ⋯ ⊕ x_{n} using n − 1 invocations of the Mult protocol.

8.4 Generalisations

First of all, the same key can be used for evaluating several circuits. It is easy to see that this is indeed secure. Whether the circuits are evaluated one at a time or we consider them one circuit and evaluate them at the same time really doesn’t matter.

The second generalisation is to allow only a subset of parties that participated in the key generation to participate in the actual computation. This is in particular interesting in a setting, where the same key is used for several evaluations. The protocol is already set up to handle this using the variable N′ of participating parties. The adversary structure on the participating parties is given by the restriction that the union of the corrupted parties and the non-participating set N \ N′ is not a qualified set.

Above we imagine that only parties which do not input to a evaluation retract from the actual computation. Another possibility is the a party first publishes its encrypted circuit input and then retract from the computation.

In this case the remaining participating parties will then do the ciphertext evaluation. There are several possibilities for key distribution in this setting. Typically we would have that secret key distributed only among the computing parties (we can imagine them being a distributed trusted party doing computation for some clients). We would then use a variant of the PrivateDecrypt, where the client, which is to receive the output, adds in d and therefore is the only one to learn the actual output.

9 Examples of Threshold Homomorphic Cryptosystems

In this section, we describe some concrete examples of threshold systems meeting our requirements, including Σ-protocols for proving knowledge of plaintexts, correctness of multiplications and validity of decryptions.

Both our examples involve choosing as part of the public key a k-bit RSA modulus N = pq, where p, q are chosen such that p = 2p′ + 1, q = 2q′ + 1 for primes p′, q′ and both p and q have k/2 bits. For convenience in the proofs to follow, we will assume that the length of the challenges in all the proofs is k/2 − 1.

9.1 Basing it on Paillier’s Cryptosystem

In [16], Paillier proposes a probabilistic public-key cryptosystem where the public key is a k-bit RSA modulus N and an element g ∈ Z_{n^{2}}^{∗} of order divisible by N. The plaintext space for this system in Z_{N}, and to encrypt a ∈ Z_{N}, one chooses r ∈ Z_{N^{2}}^{∗} at random and computes the ciphertext as

ā = g^{a}r^{N} mod N^{2}

The private key is the factorisation of N, i.e., ϕ(N) or equivalent information.

Under an appropriate complexity assumption given in [16], this system is semantically secure, and it is trivially homomorphic over Z_{n} as we require here: we can set

ā ⊞ b̄ = ā · b̄ mod N^{2}.

Furthermore, from α and an encryption ā, a random encryption of αa can be obtained by multiplying ā^{α} mod N^{2} by a random encryption of 0.

9.1.1 Threshold decryption

In [8] and independently in [9], threshold versions of this system have been proposed, based on a variant of Shoup’s [17] technique for threshold RSA. We do not need to go into the details here, it is enough to note that the threshold decryption protocols for these systems have been proved secure in exactly the sense we need here, and that the efficiency of these protocols is such that to decrypt a ciphertext, each player broadcasts one message and does a Σprotocol proving that this was correctly computed. The total number of bits broadcast is therefore O(kn).

9.1.2 Proving multiplications correct

We now describe a Σ-protocol for securely multiplying an encrypted value by a constant. So we have as input encryptions C_{a} = g^{a}r^{N} mod N^{2}, C_{α} = g^{α}s^{N} mod N^{2}, D = C_{a}^{α}γ^{N} mod N^{2} and a player P_{i} knows in addition α, s, γ. What we need is a proof that D encrypts αa mod N^{5}. We proceed as follows:

1. P_{i} chooses x ∈ Z_{N} and v, u ∈ Z_{N^{2}}^{∗} at random, computes and sends

A = C_{a}^{x}v^{N} mod N^{2}, B = g^{x}u^{N} mod N^{2}

2. The verifier sends a random challenge e.

3. P_{i} computes and sends

w = x + eα mod N, z = us^{e}g^{t} mod N^{2}, y = vC_{a}^{t}γ^{e} mod N^{2}

where t is defined by x + eα = w + tN.

4. The verifier checks that

g^{w}z^{N} = BC_{α}^{e} mod N^{2}, C_{a}^{w}y^{N} = AD^{e} mod N^{2}

and accepts if and only if this is the case.

Lemma 4 The above protocol is a Σ-protocol proving knowledge of α, s and γ such that C_{α} = g^{α}s^{N} mod N^{2} and D = C_{a}^{α}γ^{N} mod N^{2}.

Proof With respect to zero-knowledge, it is straightforward to make a correctly distributed conversation given any challenge e: one just chooses the values w, y, z at random in their respective domains and computes matching values A, B using the equations g^{w}z^{N} = BC_{α}^{e} mod N^{2}, C_{a}^{w}y^{N} = AD^{e} mod N^{2}.

Completeness is straightforward to check. For soundness, if we assume that P_{i} could for the some value of A, B answer correctly two distinct values e, e′, we would have values satisfying equations

g^{w}z^{N} = BC_{α}^{e} mod N^{2}, C_{a}^{w}y^{N} = AD^{e} mod N^{2}

5A multiplication protocol was also given in [8], but it requires that the prover knows all involved factors and so cannot be used here

g^{w′}z′^{N} = BC_{α}^{e′} mod N^{2}, C_{a}^{w′}y′^{N} = AD^{′e} mod N^{2}

which immediately implies that

g^{w−w′}(z/z′)^{N} = C_{α}^{e−e′} mod N^{2}, C_{a}^{w−w′}(y/y′)^{N} = D^{e−e′} mod N^{2}

The gcd of e − e′ and N must be 1 because e − e′ is numerically smaller than p, q. So let β be such that β(e−e′) = 1+mN for some m. Then by raising both equations to power β and straightforward manipulations, we get expressions that ”open” both C_{α} and D:

g^{(w−w′)β}((z/z′)^{β}C_{α}^{−m})^{N} = C_{α} mod N^{2}, C_{a}^{(w−w′)β}((y/y′)^{β}D^{−m})^{N} = D mod N^{2}

From this we can conclude that α = (w − w′)β mod N, s = (z/z′)^{β}C_{α}^{−m} mod N^{2} and that hence D indeed encrypts a value that is αa modulo N. □

9.1.3 Proving you know a plaintext

Finally, we need that after having created an encryption ᾱ player P_{i} can do a Σ-protocol proving that he knows α. But this is already implicit in the above protocol: if P_{i} sends only B in the first step and responds to e by the values w, z, we have a Σ-protocol proving knowledge of α, s such that C_{α} = g^{α}s^{N} mod N^{2}.

9.2 Basing it on QRA and DDH

In this section, we describe a cryptosystem which is a simplified variant of Franklin and Haber’s system [10], a somewhat similar (but non-threshold) variant was suggested by one the authors of this paper and appears in [10].

For this system, we choose an RSA modulus N = pq, where p, q are chosen such that p = 2p′ + 1, q = 2q′ + 1 for primes p′, q′. We also choose a random generator g of SQ(N), the subgroup of quadratic residues modulo N (which here has order p′q′). We finally choose x at random modulo p′q′ and let h = g^{x} mod N. The public key is now N, g, h while x is the secret key.

The plaintext space of this system is Z_{2}. We set Δ = n! (recall that n is the number of players). Then to encrypt a bit b, one chooses at random r modulo N^{2} and a bit c and computes the ciphertext

((−1)^{c}g^{r} mod N, (−1)^{b}h^{4Δ^{2}r} mod N)

The purpose of choosing r modulo N^{2} is to make sure that g^{r} will be close to uniform in the group generated by g even though the order of g is not public. It is clear that a ciphertext can be decrypted if one knows x. The purpose of having h^{4Δ^{2}r} (and not h^{r}) in the ciphertext will be explained below.

The system clearly has the required homomorphic properties, we can set:

(α, β) ⊞ (γ, δ) = (αγ mod N, βδ mod N)

Finally, from an encryption (α, β) of a value a and a known b, one can obtain a random encryption of value ba mod 2 by first setting (γ, δ) to be a random encryption of 0 and then outputting (α^{b}γ mod N, β^{b}δ mod N).

We no argue that under the Quadratic Residuosity Assumption (QRA) and the Decisional Diffie Hellman Assumption (DDH), the system is semantically secure. Recall that DDH says that the distributions (g, h, g^{r} mod p, h^{r} mod p) and (g, h, g^{r} mod p, h^{s} mod p) are indistinguishable, where g, h both generate the subgroup of order p′ in Z_{p}^{∗} and r, s are independent and random in Z_{p′}. By the Chinese remainder theorem, this is easily seen to imply that also the distributions (g, h, g^{r} mod N, h^{r} mod N) and (g, h, g^{r} mod N, h^{s} mod N) are indistinguishable, where g, h both generate SQ(N) and r, s are independent and random in Z_{p′q′}. Omitting some tedious details, we can then conclude that the distributions

(g, h, (−1)^{c}g^{r} mod N, h^{4Δ^{2}r} mod N)
(g, h, (−1)^{c}g^{r} mod N, h^{4Δ^{2}s} mod N)
(g, h, (−1)^{c}g^{r} mod N, −h^{4Δ^{2}s} mod N)
(g, h, (−1)^{c}g^{r} mod N, −h^{4Δ^{2}r} mod N)

are indistinguishable, using (in that order) DDH, QRA and DDH.

9.2.1 Threshold decryption

Shoup’s method for threshold RSA [17] can be directly applied here: he shows that if one secret-shares x among the players using a polynomial computed modulo p′q′ and publishes some extra verification information, then the players can jointly and securely raise an input number to the power 4Δ^{2}x. This is clearly sufficient to decrypt a ciphertext as defined here: to decrypt the pair (a, b), compute ba^{−4Δ^{2}x} mod N. We do not describe the details here, as the protocol from [17] can be used with no change at all. We only note that decryption can be done by having each player broadcast a single message and prove by a Σ-protocol that it is correct. The communication complexity of this is O(nk) bits.

9.2.2 Proving you know a plaintext

We will need an efficient way for a player to prove in zero-knowledge that a pair (α, β) he created is a legal ciphertext, and that he knows the corresponding plaintext. A pair is valid if and only if α, β both have Jacobi symbol 1 (which can be checked easily) and if for some r we have (g^{2})^{r} = α^{2} mod N and (h^{8Δ^{2}})^{r} = β^{2} mod N. This last pair of statements can be proved noninteractively and efficiently by a standard equality of discrete log proof appearing in [17]. Note that the squarings of α, β ensure that we are working in SQ(N), which is necessary to ensure soundness.

This protocol has the standard 3-move form of a Σ-protocol. It proves that an r fitting with α, β exists. But it does not prove that the prover knows such an r (and hence knows the plaintext), unless we are willing to also assume the strong RSA assumption^{6}. With this assumption, on the other hand, the equality of discrete log proof is indeed a proof of knowledge.

However, it is possible to do without this extra assumption: observe that if β was correctly constructed, then the prover knows a square root of β (namely h^{2Δ^{2}r} mod N) iff b = 0 and he knows a root of −β otherwise. One way to exploit this observation is if we have a commitment scheme available that allows committing to elements in Z_{N}. Then P_{i} can commit to his root α, and prove in zero-knowledge that he knows α and that α^{4} = β^{2} mod N. This would be sufficient since it then follows that α^{2} is β or −β.

Here is a commitment scheme (already well known) for which this can be done efficiently: choose a prime P, such that N divides P − 1 and choose elements G, H of order n modulo P, but where no player knows the discrete logarithm of H base G. This can all be set up initially (recall that we already assume that keys are set up once and for all). Then a commitment to α has form (G^{r} mod P, G^{α}H^{r} mod P), and is opened by revealing α, r. It is easy to see that this scheme is unconditionally binding, and is hiding under the DDH assumption (which we already assumed). Let [α] denote a commitment to α and let [α][β] mod P be the commitment you obtain in the natural way by componentwise multiplication modulo P. It is then clear that [α][β] mod P is a commitment to α + β mod N.

It will be sufficient for our purposes to make aΣ-protocol that takes as input commitments [α], [β], [γ], shows that the prover knows α and shows that αβ = γ mod N. Here follows such a protocol:

1. Inputs are commitments [α], [β], [γ] where P_{i} claims that αβ = γ mod N. P_{i} chooses a random δ and makes commitments [δ], [δβ].

2. The verifier send a random e.

3. P_{i} opens the commitments [α]^{e}[δ] mod P to reveal a value e_{1}. P_{i} opens the commitment [β]^{e_{1}}[δβ]^{−1}[γ]^{−e} mod P to reveal 0.

4. The verifier accepts if an only if the commitments are correctly opened as required.

6that is, assume that it is hard to invert the RSA encryption function, even if the adversary is allowed to choose the public exponent

By arguments similar to those for Lemma 4, it is straightforward to show that this protocol is a Σ-protocol.

9.2.3 Proving multiplications correct

Finally, we need to consider the scenario where player P_{i} has been given an encryption C_{a} of a, has chosen a constant b, and has published encryptions C_{b}, D, of values b, ba, and where D has been constructed P_{i} as we described above. It follows from this construction that if b = 1, then D = C_{a} ⊞ E where E is a random encryption of 0. Assuming b = 1, E can be easily reconstructed from D and C_{a}.

Now we want a Σ-protocol that P_{i} can use to prove that D contains the correct value. Observe that this is equivalent to the statement

((C_{b} encrypts 0) AND (D encrypts 0)) OR
((C_{b} encrypts 1) AND (E encrypts 0))

We have already seen how to prove by a Σ-protocol that an encryption (α, β) contains a value b, by proving that you know a square root of (−1)^{b}β. Now, standard techniques from [6] can be applied to building a new Σ-protocol proving a monotone logical combination of statements such as we have here.

References

[1] Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, Chicago, Illinois, 2–4 May 1988.

[2] D. Beaver. Foundations of secure interactive computing. In Joan Feigenbaum, editor, Advances in Cryptology - Crypto ’91, pages 377–391, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science Volume 576.

[3] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In ACM [1], pages 1–10.

[4] Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143–202, winter 2000.

[5] David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In ACM [1], pages 11–19.

[6] R. Cramer, I. B. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Yvo Desmedt, editor, Advances in Cryptology - Crypto ’94, pages 174–187, Berlin, 1994. Springer-Verlag. Lecture Notes in Computer Science Volume 839.

[7] Ronald Cramer, Ivan Damgård, and Ueli Maurer. General secure multi-party computation from any linear secret-sharing scheme. In Bart Preneel, editor, Advances in Cryptology - EuroCrypt 2000, pages 316–334, Berlin, 2000. Springer-Verlag. Lecture Notes in Computer Science Volume 1807.

[8] Ivan B. Damgård and Mads J. Jurik. Efficient protocols based on probabilistic encryption using composite degree residue classes. Research Series RS-00-5, BRICS, Department of Computer Science, University of Aarhus, March 2000.

[9] P. Fouque, G. Poupard, and J. Stern. Sharing decryption in the context of voting or lotteries. In Proceedings of Financial Crypto 2000, 2000.

[10] Matthew Franklin and Stuart Haber. Joint encryption and message-efficient secure computation. Journal of Cryptology, 9(4):217–232, Autumn 1996.

[11] R. Gennaro, M. Rabin, and T. Rabin. Simplified vss and fast-track multiparty computations with applications to threshold cryptography. In Proc. ACM PODC’98, 1998.

[12] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 218– 229, New York City, 25–27 May 1987.

[13] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, April 1984.

[14] IEEE. 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, 3–5 November 1982.

[15] S. Micali and P. Rogaway. Secure computation. In Joan Feigenbaum, editor, Advances in Cryptology - Crypto ’91, pages 392–404, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science Volume 576.

[16] P. Paillier. Public-key cryptosystems based on composite degree residue classes. In Michael Wiener, editor, Advances in Cryptology - EuroCrypt ’99, pages 223– 238, Berlin, 1999. Springer-Verlag. Lecture Notes in Computer Science Volume 1666.

[17] Victor Shoup. Practical treshold signatures. In Bart Preneel, editor, Advances in Cryptology - EuroCrypt 2000, pages 207–220, Berlin, 2000. Springer-Verlag. Lecture Notes in Computer Science Volume 1807.

[18] Andrew C. Yao. Protocols for secure computations (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science [14], pages 160–164.

[19] Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science [14], pages 80–91.

Recent BRICS Report Series Publications

RS-00-14 Ronald Cramer, Ivan B. Damgård, and Jesper Buus Nielsen. Multiparty Computation from Threshold Homomorphic Encryption. June 2000. ii+38 pp.

RS-00-13 Ondřej Klíma and Jiří Srba. Matching Modulo Associativity and Idempotency is NP-Complete. June 2000. 19 pp. To appear in Mathematical Foundations of Computer Science: 25 th International Symposium, MFCS ’00 Proceedings, LNCS, 2000.

RS-00-12 Ulrich Kohlenbach. Intuitionistic Choice and Restricted Classical Logic. May 2000. 9 pp.

RS-00-11 Jakob Pagter. On Ajtai’s Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem. May 2000. 18 pp.

RS-00-10 Stefan Dantchev and Søren Riis. A Tough Nut for Tree Resolution. May 2000. 13 pp.

RS-00-9 Ulrich Kohlenbach. Effective Uniform Bounds on the Krasnoselski-Mann Iteration. May 2000. 34 pp.

RS-00-8 Nabil H. Mustafa and Aleksandar Pekeč. Democratic Consensus and the Local Majority Rule. May 2000. 38 pp.

RS-00-7 Lars Arge and Jakob Pagter. I/O-Space Trade-Offs. April 2000. To appear in 7th Scandinavian Workshop on Algorithm Theory, SWAT ’98 Proceedings, LNCS, 2000.

RS-00-6 Ivan B. Damgård and Jesper Buus Nielsen. Improved Non-Committing Encryption Schemes based on a General Complexity Assumption. March 2000. 24 pp.

RS-00-5 Ivan B. Damgård and Mads J. Jurik. Efficient Protocols based on Probabilistic Encryption using Composite Degree Residue Classes. March 2000. 19 pp.

RS-00-4 Rasmus Pagh. A New Trade-off for Deterministic Dictionaries. February 2000.