BRICS RS-97-28 Cramer et al.: Span Programs and General Secure Multi-Party Computation BRICS

Basic Research in Computer Science

Span Programs and General Secure Multi-Party Computation

Ronald Cramer Ivan B. Damgård Ueli Maurer BRICS Report Series RS-97-28 ISSN 0909-0878 November 1997 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1997, 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/97/28/

Span Programs and General Secure Multi-Party Computation

Ronald Cramer (ETH Zurich ^{∗}) Ivan Damgård (Aarhus University ^{†} & BRICS ^{‡}) Ueli Maurer (ETH Zurich ^{§})

Abstract

The contributions of this paper are three-fold. First, as an abstraction of previously proposed cryptographic protocols we propose two cryptographic primitives: homomorphic shared commitments and linear secret sharing schemes with an additional multiplication property. We describe new constructions for general secure multi-party computation protocols, both in the cryptographic and the information-theoretic (or secure channels) setting, based on any realizations of these primitives.

Second, span programs, a model of computation introduced by Karchmer and Wigderson, are used as the basis for constructing new linear secret sharing schemes, from which the two above-mentioned primitives as well as a novel verifiable secret sharing scheme can efficiently be realized.

Third, note that linear secret sharing schemes can have arbitrary (as opposed to threshold) access structures. If used in our construction, this yields multi-party protocols secure against general sets of active adversaries, as long as in the cryptographic (information-theoretic) model no two (no three) of these potentially misbehaving player sets cover the full player set. This is a strict generalization of the threshold-type adversaries and results previously considered in the literature. While this result is new for the cryptographic model, the result for the information-theoretic model was previously proved by Hirt and Maurer. However, in addition to providing an independent proof, our protocols are not recursive and have the potential of being more efficient.

1 Introduction and Related Work

The main goal of this paper is to propose new efficient secure multi-party computation protocol constructions based on generic primitives and to show that these primitives can be realized by using linear secret sharing schemes based on span programs. It is our hope that this link between span programs and multi-party computation can be the basis for the discovery of further relations between these two areas that have recently received a lot of attention.

∗Dept. of Computer Science, ETH Zurich, CH-8092 Zurich, Switzerland. Email: cramer@inf.ethz.ch.

†Maths. & Comp. Sc. Dept., Ny Munkegade, Aarhus, Denmark. Email: ivan@daimi.aau.dk ‡Basic Research in Computer Science, Center of the Danish National Research Foundation §Dept. of Computer Science, ETH Zurich, CH-8092 Zurich, Switzerland. Email: maurer@inf.ethz.ch.

Supported by the Swiss National Science Foundation.

Secure multi-party computation can be defined as the problem of n players to compute an agreed function of their inputs in a secure way, where security means maintaining correctness of the output while keeping the players’ inputs private, even in the presence of adversarial behavior by some of the players.

One can distinguish between passive and active cheaters: passive cheaters follow the protocol but pool their information in order to violate the other players’ privacy. Active cheaters can use an arbitrary joint strategy in order to violate the correctness and/or privacy of the computation. Usually, this is modeled by assuming the existence of a passive or active adversary who can monitor or control some subset of the players. It is (at least initially) unknown to the correct players which subset is affected.

Two basic models have been considered in the literature. In the cryptographic model, all players are assumed to have access to messages exchanged between players, and hence privacy and correctness can only be guaranteed in a cryptographic sense, i.e. assuming that the adversary cannot solve some computational problem. Privacy here means that an adversary’s entire view of the protocol can efficiently be simulated in a manner indistiguishable from a real execution of the protocol. In the information-theoretic (also called secure channels) model, it is assumed that the players can communicate pairwise over secure channels, and the privacy as well as the correctness can then be guaranteed even when the adversary has unbounded computing power. Privacy here means that an adversary’s view, when given the output of the computation, is statistically independentent of the other player’s inputs and hence gives no Shannon information about them. We consider both the cryptographic and the information-theoretic models, assuming synchronous communication and static adversaries^{1}.

The classical results for the information-theoretic model due to Ben-Or, Goldwasser and Wigderson [4] and Chaum, Crépeau and Damgård [8] state that every function can securely be computed if and only if less than n/2 passive or less than n/3 active cheaters are present. These result were generalized by Hirt and Maurer [15] who considered as the potential adversaries general sets of subsets of the player set, not necessarily specified by their cardinality.

Using terminology from secret sharing and from [15], we call a set of subsets of the players a structure and we consider security (privacy and correctness) of a protocol with respect to an adversary structure, meaning that the protocol remains secure even when an arbitrary set in the structure happens to be controlled by an adversary (which may be passive or active). Let Q2 (and Q3) be the conditions on a structure that no two (no three) of the sets in the structure cover the full player set. Note that the threshold situations considered in [4], [8], [14] and [20] are special cases, where the adversary structure would contain all sets of size less than n/2 or n/3.

1In the information-theoretic model, our results also hold for adaptive (dynamic) adversaries, i.e. when an adversary decides adaptively which players to corrupt.

The result of [15] can then be stated as follows: secure multi-party computation is possible in the information-theoretic scenario, while tolerating a passive (active) adversary, if and only if the adversary structure satisfies Q2 (Q3). One - perhaps somewhat surprising - consequence of this is that in some situations, a majority of passive cheaters can be tolerated, provided we do not have to tolerate any dishonest majority. The protocols proposed in [15] rely on applying a protocol for the threshold case (e.g. [4]) recursively, so that subsets of players together run threshold protocols to simulate virtual players in higher level protocols. In general, the emphasis in [15] was on existence of protocols rather than on efficiency.

In this paper, we present protocols that directly and perhaps more naturally implement protection against any Q2 passive or any Q3 active adversary in the information-theoretic scenario. The Q2 and Q3 conditions arise directly from a natural condition on the underlying secret sharing schemes, and this also leads to a potentially more efficient solution than that of [15]. In particular, the complexity of our protocols is directly related to the size of a monotone span program [16] that rejects all potentially misbehaving player sets and accepts their complements and enjoys a special multiplication property^{2}. One ”spin-off” from our results that may be of independent interest is a new construction that builds from a monotone span program a verifiable secret sharing scheme for the information-theoretic scenario tolerating any Q3 active adversary (the multiplication property is not needed here). Like in [4] and [15], our protocols have zero probability of successful cheating by an active adversary.

In the cryptographic model with an active adversary, the most general previous result was shown by Goldreich, Micali and Wigderson [14] who proved that any minority of active cheaters can be tolerated, assuming that trapdoor one-way permutations exist. In this paper, we show that any Q2 active adversary can be tolerated, assuming that one-way group homomorphisms with specific extra properties exist. Particular assumptions sufficient for this include: the RSA assumption, hardness of discrete log in prime order groups, or polynomial security of Diffie-Hellman encryption. To the best of our knowledge, this is the first result for the cryptographic model that goes beyond the threshold case. It can be generalized to rely only on the existence of trapdoor one-way permutations, but only with loss of efficiency.^{3}

2Span program are the most powerful known method for designing linear secret sharing schemes (combine the results of [3] and [16]).

3Even for the threshold case, our protocol yields substantial efficiency improvements over earlier proposals:

if the computation is specified as an arithmetic circuit of size m operations over GF (q), where q is a k-bit prime, then with security parameter value k, our protocol has communication complexity O(kmf(n)^{2}) bits, when based on the most efficient implementations of the primitives, and where f(n) is the size of the monotone span program we need for the particular adversary structure considered. In particular, if we want to tolerate any minority of active cheaters, we will have f(n) = n.

This paper draws on three ideas appearing in [13]: the observation that in [4] the product of two shared values is defined as a linear function of the products of the shares, the idea (independently discovered in the course of our research) of using homomorphic cryptographic commitments to build verifiable secret sharing, and the idea of using a specialized zero-knowledge proof for proving correctness of multiplied commitments. One of the achievements of this paper is to show how general linear secret sharing schemes (not only Shamir’s polynomial threshold scheme as in [13]) can be applied in multi-party computation, both in the cryptographic and information-theoretic setting.

2 The Tools: Shared Commitments and Secret Sharing

In this section we introduce some notation and state, at an abstract level, the required properties for our two main tools used in both the cryptographic and the information-theoretic model. Shared commitments (often also simply called commitments in this paper) are a generalization of conventional cryptographic commitments, which are in fact used as the implementation of shared commitments in the cryptographic scenario.

We use the following notation throughout the paper. The set of players is denoted {P_{1}, ..., P_{n}}. In all models, we consider a particular monotone set A of subsets of {P_{1}, ..., P_{n}}, called the adversary structure, as potential adversaries, and every set in A is called an admissible adversary. The set A usually satisfies the Q2 or the Q3 condition. When considering one particular adversary A in A, then we refer to the players not in A as correct players. The function to be computed is assumed to be defined as an arithmetic circuit C over some finite field K.

2.1 Notation and Required Properties for Shared Commit-

ments

To protect against active adversaries in a given adversary structure A, we will need a commitment scheme for elements in K. A shared commitment scheme consists of two protocols, Commit and Open. Both of these are initiated by one of the players, called the committer, in order to commit to or reveal a value a ∈ K, respectively. During Commit the committer distributes some information to the other players, possibly also involving interaction between the players. By the commitment, we mean the total information distributed to the correct players. We need the following basic properties:

1. Binding: For any committer and any admissible adversary, some value a is uniquely determined from the commitment, and an execution of Open based on this commitment results either in all correct players retrieving a, or in all correct players rejecting the outcome of Open.

2. Hiding: If the committer is a correct player and commits to value a, any admissible adversary learns nothing about a from his view of the Commit protocol. Moreover, executing Open based on this commitment always results in all correct players retrieving a.

In the information-theoretic (cryptographic) scenario, both properties hold unconditionally (relative to some complexity assumption).^{4}

We will need the following extra properties, where the Multiplication Protocol is only needed in case of an active adversary:

• Homomorphic: From commitments A and B containing a ∈ K and b ∈ K, respectively, the players can, without communicating, compute a commitment containing a + b ∈ K, or compute one containing a − b ∈ K. Motivated by the particular known realizations of homomorphic cryptographic commitments, we will denote these commitments by A·B and AB^{−1}, respectively. This property also implies that without communication, constants can be multiplied or added into commitments. We will let A^{c}, cA, cA^{−1} denote commitments to ca, c + a, c − a, as computed from A. Each new commitment computed in this way can be opened by the committer, but we require that opening A · B reveals no information about a and b other than a + b (and similar for the other operations).

• Multiplication Protocol: This protocol allows a player P_{i} who has previously committed to values a and b by commitments A and B to commit to a value c using commitment C, such that:

1. For any P_{i} and any admissible adversary, either c = ab or all correct players reject the outcome of the protocol (for the cryptographic scenario, a superpolynomially small error probability, taken over the coin flips of correct players, is allowed).

2. If P_{i} is a correct player, the protocol always results in c = ab, and any admissible adversary learns nothing about c except that c = ab. Moreover, opening C reveals no information about a and b other than ab.

2.2 Notation and Required Properties for Secret Sharing

A secret sharing scheme can be defined as a probabilistic polynomial time algorithm which takes as input an element s in K and outputs n shares s_{1}, ..., s_{n}. The share s_{i} will be a d_{i}-vector of elements in K, and in the course of our protocols, the share s_{i} will be given to P_{i} (but will initially be unknown to all other players). Let d = d_{1} + ... + d_{n}. For C ⊆ {P_{1}, …, P_{n}} we call a vector of length ∑_{i:P_{i}∈C} d_{i} a d_{C}-vector. For any t and any t-vectors u, v, the t-vector u ∗ v will denote the coordinatewise product of u and v. The standard inproduct of u and v is denoted by ⟨u, v⟩.

4In the information-theoretic setting, and without the uniqueness condition on the committed value, this corresponds to Weak Secret Sharing defined in [20, 19].

There is a monotone collection of qualified subsets of players, called the access structure. Any qualified set can efficiently reconstruct the shared secret while any non-qualified set has no information about the secret (perfect secrecy). A set of values that can be interpreted as the shares of a secret s of a qualified set in a secret sharing sheme will be said to consistently determine s.

In our protocols, the set of non-qualified subsets (the complement of the access structure) will coincide with A, the subsets of players that may potentially be under the adversary’s control. Because we are dealing with only Q2 or Q3 adversary structures, the set of correct players is always qualified.

We will need the following extra properties from our secret sharing schemes, where the strong multiplication property is only required in the case of an active Q3adversary:

• Linearity: If values s, s′ ∈ K have been shared resulting in sets of shares s = (s_{1}, …, s_{n}) resp. s′ = (s′_{1}, …, s′_{n}), then the set (s_{1} + s′_{1}, …, s_{n} + s′_{n}) is a consistent set of shares uniformly chosen among those that determine s + s′. As for commitments, this property implies that players can, without communicating, also compute from a sharing of s a set of shares determining cs or c + s, for any constant c ∈ K.

• Multiplication property: assume values s, s′ ∈ K have been shared resulting in sets of shares s resp. s′. Note that these sets of shares can be viewed as d-vectors. We require that there exists a fixed d-vector r, called the recombination vector^{5} such that ⟨r, s ∗ s′⟩ = ss′.

• Strong multiplication property: With respect to an adversary structure A, the following additional property holds: let C be any set of players with C = {P_{1}, …, P_{n}} − A for some A ∈ A. Let (s ∗ s′)_{C} be the d_{C}-vector obtained by extracting from s ∗ s′ the coordinates corresponding to players in C. We then require that there exists a d_{C}-vector r_{C} such that ⟨r_{C}, (s ∗ s′)_{C}⟩ = ss′.

2.3 The Commitment Distribution Protocol

This protocol is only required in the case of an active adversary and is defined relative to an adversary structure A and with respect to a secret sharing scheme for which A consists of the non-qualified sets. It allows a player P_{i} who has committed to a value s ∈ K by commitment C to share s among the players P_{1}, …, P_{n} such that in the presence of any adversary in A, 1. Either each player P_{j} for 1 ≤ j ≤ n is committed to (the coordinates of) a

5The definition of this property was motivated by an observation of M. Rabin described in [13], and it can in fact be seen as an abstraction or generalization of the multiplication trick described in [13].

d_{j}-vector s_{j}, such that s_{1}, ..., s_{n} is a set of shares consistently determining s; or all correct players reject the outcome of the protocol^{6}.

2. If P_{i} is a correct player, any admissible adversary learns nothing about s.

Any commitment distribution protocol can be used to realize verifiable secret sharing (VSS).^{7} This is achieved by having the dealer first commit to the secret s and then use the commitment distribution protocol. Reconstruction is immediate by having each P_{j} open the commitments to s_{j}: incorrect players cannot contribute false shares, and shares will be available from at least the correct players, which is a qualified set.

3 Multi-Party Computation: The Main Protocol

In this section, we give a bird’s eye view of our multi-party computation protocol based on the tools^{8} of Section 2. This view will be valid both in the informationtheoretic and the cryptographic scenario.

A remark on broadcast is appropriate here. Note that we may assume throughout that players can broadcast information. This is trivial in the cryptographic scenario, and can be simulated through a protocol in the information-theoretic scenario. This is non-trivial only with an active Q3-adversary. In this case a solution follows from using the result of [15]. We conjecture that an alternative solution is to use the protocol of Feldman and Micali [11] together with our VSS protocol described below, but at the time of writing, this has not yet been completely investigated.

Our main protocol has the same overall structure as many known multiparty computation protocols. There are three main parts: the Input distribution, Computation, and Output reconstruction phases. We note that the description is for the case of an active adversary. A (much simpler) description for the case of a passive adversary can be obtained by removing the commitments and subprotocols that force players to act correctly.

After the input distribution phase, each input value x to the computation is represented by a set of shares x_{1}, ..., x_{n}, such that each P_{i} has committed to (the coordinates of) his share x_{i}. During the computation phase, we work our way through the circuit C one field operation (multiplication or addition) at a time. Finally, the outputs can be reconstructed since each output value will be represented in the same way as the inputs.

Here follows a more concrete description:^{9} 1. For each player P_{i} and each input value x to be chosen by P_{i}, P_{i} commits to

6for the cryptographic scenario, a superpolynomially small error probability, taken over the coin flips of correct players, is allowed.

7A VSS can be seen as a shared commitment for which it is additionally guaranteed that the secret can efficiently be reconstructed by the players.

8In case of a passive adversary, the Commitment Distribution Protocol, the Strong Multiplication for Secret Sharing and the Multiplication Protocol for Commitments are not needed.

9This protocol draws on ideas in [13] (see also the end of the introduction) and [8].

x and uses the Commitment Distribution Protocol to ensure that each P_{j} is committed to a valid share x_{j} of x. If a player P_{i} fails to execute this phase correctly, he is clearly corrupt, and the correct players assume default values for his inputs and shares.

2. For the computation phase, we maintain an invariant stating that whenever y is an input value or an intermediate result in C that has already been computed, each P_{i} is committed to a valid share y_{i} of y (initally, no intermediate results are computed). Let x, y be input values to an operation to be done in C, where both x, y are either inputs or already computed intermediate results. This means that each P_{i} is committed to valid shares x_{i}, y_{i} of x, y by two vectors of commitments X_{i,1}, .., X_{i,d_{i}} and Y_{i,1}, .., Y_{i,d_{i}}. Let, as before, x and y denote the full sets of shares in x and y, and define z = xy. If the operation is addition, the players now locally compute for each i the vector of commitments X_{i,1} · Y_{i,1}, …, X_{i,d_{i}} · Y_{i,d_{i}}. This commits P_{i} to x_{i} + y_{i} using linearity of commitments. By linearity of the secret sharing, this set of shares consistently determines x + y. If the operation is a multiplication, each P_{i} uses for j = 1 … d_{i} the Multiplication Protocol with inputs X_{i,j}, Y_{i,j} to produce a commitment W_{i,j} to the j-th coordinate of x_{i} ∗ y_{i}. For each j = 1 … d_{i}, player P_{i} now uses the Commitment Distribution Protocol with input W_{i,j} to have each P_{k} commit to (the coordinates of) a valid share in the j-th coordinate of x_{i} ∗ y_{i}.

3. The following only applies when the previous operation was a multiplication. If the secret sharing scheme has only the standard multiplication property, and some P_{i} fails to complete his multiplication step correctly, he is deemed corrupt, the players make public all the information sent to him so far, and simulate him openly after this point (this tells the adversary nothing he did not already know). Thus we proceed as if P_{i} still participated in the protocol. If the scheme has the strong multiplication property, a player P_{i} failing to complete his multiplication step correctly, is simply deemed corrupt and is ignored for the rest of the protocol. Now, each player does the following (our description is for strong multiplication; in the other case, read C as the full player set, d_{C} as d, and r_{C} as r). Let C be the set of participants that still participate at this point. Suppose (x ∗ y)_{C} (defined as in Section 2.2) is a d_{C}-vector. Now, for every P_{k} ∈ C and every l = 1 … d_{k}, m = 1 … d_{C}, player P_{k} has made a commitment Z_{k,l,m} to the l-th coordinate of a share z_{k,m} in the m’th coordinate of (x ∗ y)_{C}. Each P_{k} now privately computes z_{k} = r_{1}z_{k,1} + ... + r_{d_{C}}z_{k,d_{C}}, and the players compute, for l = 1 … d_{k}, the commitments Z_{k,l} = Z_{k,l,1}^{r_{1}} ·. . .·Z_{k,l,d_{C}}^{r_{d_{C}}} to the l-th coordinate of z_{k}, where r_{C} = (r_{1}, ..., r_{d_{C}}) is the recombination vector guaranteed by the strong multiplication property. Note that by the properties of the secret sharing, z_{k} is a valid share of z = xy, and so we have built a correct representation of z.

4. For the output reconstruction phase, we may assume that each output value is represented by a set of d commitments, containing a full set of shares of the value. Reconstruction is therefore straightforward by opening all these commitments, ignoring values that are not opened correctly.

4 Span Programs and Secret Sharing 4.1 Notation and Definitions

Let f : {0, 1}^{n} ⟶ {0, 1}, f ≢ 0, 1, be a monotone function. A min-term x of f is a string with f(x) = 1 such that no x′ < x (usual Boolean ordering) satisfies f(x′) = 1. A max-nonterm y of f is a string with f(y) = 0 and for no y′ > y satisfies f(y′) = 0. Its dual f^{∗} : {0, 1}^{n} ⟶ {0, 1} is defined by f^{∗}(x) = f(x ⊕ 1) ⊕ 1 for all x ∈ {0, 1}^{n}, where 1 denotes the all-one bit string and ⊕ denotes bit-wise xor. A function f is called self-dual if f = f^{∗}. Let A denote a subset of {1, …, n}. By abuse of notation we shall take f(A) to mean f(I_{A}), where I_{A} is bit string characterizing A, i.e. the i-th bit of I_{A} is set to 1 if i ∈ A and set to 0 otherwise. If f(A) = 1, we shall say that A is qualified. Otherwise, A is non-qualified. Hence, the min-terms of f correspond to minimal qualified sets of the associated access structure and the max-nonterms correspond to the maximal non-qualified sets.

If V is a finite dimensional vector space over a field K then dim_{K}V denotes its dimension. If W is a subspace, then W^{⊥} denotes the orthogonal complement of W in V. Relative to a standard basis, ⟨x, y⟩ denotes the inproduct of x, y ∈ V. For example for V = K^{d}, x = (x_{1}, …, x_{d}) ∈ V and y = (y_{1}, …, y_{d}) ∈ V, x ∗ y denotes (x_{1}y_{1}, …, x_{d}y_{d}) ∈ V.

If M is a matrix with entries in K then M^{t} denotes the transpose of M (we will sometimes use cols(M) and rows(M) to refer to the number of rows and columns of a matrix M, respectively). The image of M is denoted Im M and its kernel (null-space) by Ker M. Finally, a useful fact from elementary linear algebra is that Im M^{t} = (Ker M)^{⊥}.

4.2 Monotone Span Programs

Span programs were introduced by Karchmer and Wigderson [16] as a linear algebraic model of computation. In this paper, we will consider only monotone span programs. Karchmer and Wigderson also described how span programs give rise to secret sharing schemes.

4.2.1 Definition

Let K be a finite field and let M be a matrix with entries in K, having d rows and e columns.^{10} We assume that M is labelled in the sense that each row is indexed by some integer i with 1 ≤ i ≤ n, for some n, where every index i between 1 and n occurs at least once as the index of a row. Finally, let a ∈ K^{e} \ 0 be given. A monotone span program is a triple (K, M, a), defined as above.^{11} Sometimes we will treat M just as a matrix, ignoring the labelling.

Let i ≤ n be a positive integer. By M_{i} we denote the matrix consisting of the rows in M indexed by i. For each 1 ≤ i ≤ n, write d_{i} for the number of rows in M_{i}. Similarly, for ∅ ≠ A ⊂ {1, …, n}, M_{A} denotes the matrix consisting of all rows in M indexed with elements j ∈ A, and d_{A} denotes the number of rows in M_{A}. For a vector s = (s_{1}, …, s_{d}) ∈ K^{d}, we define s_{i} and s_{A} similarly.

Let f : {0, 1}^{n} ⟶ {0, 1} be a monotone function. If for all ∅ ≠ A ⊂ {1, …, n}

f(A) = 1 ⟺ a ∈ Im M_{A}^{t},

then the monotone span program (K, M, a) is said to compute f.

We note that any given monotone span program computes a monotone Boolean function in a natural way. Namely, it computes the monotone Boolean function f defined f(x_{1}, …, x_{n}) = 1 if and only if a ∈ Im M_{A}^{t} where A = {1 ≤ i ≤ n|x_{i} = 1}. Furthermore, it is well known that any monotone Boolean function can be computed by a monotone span program.

4.2.2 A Secret Sharing Scheme

Let f(x_{1}, …, x_{n}) be a monotone Boolean function and let (K, M, a) be a monotone span program computing it. Wlog we may assume that a = (10 ⋯ 0) (by applying a suitable linear transformation on the rows). A perfect secret sharing scheme for f is now constructed as follows [16] (notations as above).

Share Distribution: (K, M, a) is public knowledge. Let s ∈ K be the secret. The dealer chooses ρ_{1}, …, ρ_{e−1} ∈ K at random and puts b ← (s, ρ_{1}, …, ρ_{e−1}). For i = 1 … n, he sends the share s_{i}, computed as s_{i} ← M_{i}b, privately to player i. Note that s_{i} ∈ K^{d_{i}}.

Reconstruction:

Let A ⊂ {1, …, n} satisfy f(A) = 1, and let λ_{A} satisfy M_{A}^{t}λ_{A} = a. Then we have s = ⟨λ_{A}, s_{A}⟩, where s_{A} denotes the superposition of the s_{i} with i ∈ A.

Note that λ_{A}, s_{A} ∈ K^{d_{A}}, where d_{A} = ∑_{i∈A} d_{i}.

10We may assume wlog that e ≤ d. Keeping only a collection of columns (including the first) that span the column space does not affect the multiplication property defined later.

11Note that the labelling of M is only implicit in this definition.

For completeness, we prove the scheme correct and secure. Correctness: For A with f(A) = 1 we have s = ⟨a, b⟩ = ⟨M_{A}^{t}λ_{A}, b⟩ = ⟨λ_{A}, M_{A}b⟩ = ⟨λ_{A}, s_{A}⟩. Privacy: Observe that when f(A) = 0 a ∉ Im M_{A}^{t} implies that, by our choice of a and by the fact that Im M_{A}^{t} = (Ker M_{A})^{⊥}, Ker M_{A} contains a vector with non-zero first coordinate. Hence, the equation M_{A}b′ = s_{A}, which has solution space equal to b + Ker M_{A}, has the same number of solutions for each possible choice of a secret s′. The argument is completed by noting that the ρ_{i}’s appearing in the definition of b have been chosen at random by the dealer.

As a final remark, if we do not take a = (10 ⋯ 0), then the dealer chooses b at random s. t. ⟨a, b⟩ = s. The changes for reconstruction and the proof are trivial.

4.3 Span Programs with Multiplication

Recall the definition of the (strong) multiplication property for linear secret sharing schemes from Section 2.2. For completeness, we now give a formal definition in terms of monotone span programs.

Definition 1 We say that (K, M, a, r) is a monotone span program with multiplication if (K, M, a) is a monotone span program and the recombination vector r has the property that for all b, b′ we have

⟨r, Mb ∗ Mb′⟩ = ⟨a, b⟩ · ⟨a, b′⟩.

Strong multiplication is defined analogously.

We state a property of the recombination vector that we will use later. Let f(x_{1}, …, x_{n}) be the monotone Boolean function computed by (K, M, a, r). Say r = (r_{1}, …, r_{n}), and define sup r = {1 ≤ k ≤ n|r_{k} ≠ 0}. Then we have f(sup r) = 1. It is easy to see that f(sup r) = 0 would imply that the non-qualified set sup r could compute the secret in any execution of the secret sharing scheme, which is a contradiction.^{12}

4.4 Constructions of Span Programs

We characterize the monotone Boolean functions f computable by monotone span programs with multiplication. We also give an upper bound of the minimal achievable size of the monotone span program in terms of certain logical formulae computing f.

Definition 2 Let f : {0, 1}^{n} → {0, 1} be a monotone function. We say [15] that f is Q2-monotone if for all A, A′ ⊂ {1, …, n} with f(A) = f(A′) = 0 we have A ∪ A′ ≠ {1, …, n}.

12Furthermore, by elementary linear algebra, it is easy to show that the multiplication property is preserved under linear transformations on the rows of the monotone span program.

By the above definition, f(A) = f(A^{c}) = 0 is impossible. Also, let f(B) = 1 and f(A)=0. Then A^{c} ∩ B = ∅ would imply B ⊂ A^{c}. Hence, f(A^{c}) = 1, a contradiction. We have the following lemma.

Lemma 1 For any Q2-monotone function f, and for any B with f(B) = 1 and A with f(A) = 0, we have f(A^{c}) = 1 and A^{c} ∩ B ≠ ∅.

Proposition 1 Let (K, M, a, r) be a monotone span program with multiplication computing the monotone Boolean function f. Then f is Q2-monotone.

Proof. Suppose not. Then there exists a non-empty set A such that f(A) = f(A^{c}) = 0. This implies that there exists a vector κ whose first coefficient is equal to 1, such that M_{A^{c}}κ = 0 (assuming wlog that a = 10 ⋯ 0). Then we have for each b (write s for its first coefficient) that ⟨r, Mκ ∗ Mb⟩ = 1 · s. But since M_{A^{c}}κ = 0, s must be computable from r (public information) and M_{A}b. But this contradicts the security of the secret sharing scheme from Section 4.2. △

We will also prove that the converse is true. To this end we first address how to construct new monotone span programs (with or without multiplication) from old. Let f, g_{1}, …, g_{n} be any monotone Boolean functions such that each of them can be computed by span programs with multiplication. Say that f reads n bits, and the g_{i}’s read m_{i} bits (i.e. f and the g_{i}’s have n and m_{i} literals, respectively). Write (K, F, a, r_{0}), (K, G_{i}, a, r_{i}), i = 1 … n, for their respective span programs (assume wlog that for each of these programs a denotes the first unit vector in each of their respective vector spaces of definition). Write F_{i} for the rows of F that correspond to the i-th literal of f (i.e. indexed by i). The following proposition is proved in the Appendix.

Proposition 2 f(g_{1}, …, g_{n}) is computable by a monotone span program (K, M, a, r) with multiplication. Furthermore, rows(M) ≤ ∑_{i=1}^{n} rows(F_{i}) · rows(G_{i}).

Remark. The claim in our result also holds if we disregard the multiplication property. Viewed in that way, our result is a slight improvement for the monotone span program complexity upper bound given in [18], Theorem 3.4, 4-th claim. However, our main goal is to incorporate multiplication.

Definition 3 Let the threshold function ^{13} f_{t,n} : {0, 1}^{n} → {0, 1} output 1 if and only if the input string has Hamming-weight at least t. We call f_{t,n} majority accepting if 2t ≤ n + 1. If 3t ≤ n + 2, we call f_{t,n} 1/3-accepting.

Lemma 2 Let f_{t,n} be an arbitrary threshold function. Then f_{t,n} can be computed by a monotone span program (K, M, a) having n rows, provided that |K| > n if t > 1. If additionally f_{t,n} is majority accepting, then the monotone span program is with multiplication.

13Note that in general the dual of a threshold function f_{t,n} is the threshold function f_{n−t+1,n}.

Proof. The first part of the claim (not dealing with multiplication) is wellknown. If t = 1, we have the trivial monotone span program (K, 1, 1). Else, let M_{t,n} denote a Vandermonde matrix (over a field K with |K| > n) with n rows and t columns, the i-th row being of the form 1, α_{i}, …, α_{i}^{t−1} and α_{i} ≠ α_{j} if i ≠ j. It is easy to see that M_{t,n} can be viewed as a span program computing f_{t,n}, with root a = (10 ⋯ 0). In this case the associated secret sharing scheme (as defined in Section 4.2) is identical to Shamir’s [21].

To see that (K, M_{t,n}, a) has multiplication, observe that the product h = f·g of any two polynomials f, g ∈ K[X], both of degree at most t−1, can be interpolated given n points if 2t ≤ n+1. In particular, if we are given distinct values P_{1}, …, P_{n} ∈ K\0, and the evaluations h(P_{1}), …, h(P_{n}), we can reconstruct the coefficients of h by linear operations (coefficients only depending on the P_{i}’s) on the h(P_{i})’s. This holds in particular for the lowest order coefficient of h, which is the product of the secrets distributed by f and g in an execution of Shamir’s scheme with threshold (t, n). This part of the claim is due to M. Rabin [13]. We cast it here in our model.

△

Proposition 3 The class of Q2-monotone Boolean functions coincides with the class of functions computable by Boolean formulas consisting of majority accepting gates.

Proof. Let Φ be a formula consisting of majority accepting gates. Suppose that (the monotone function computed by) Φ is not Q2. Then there is a set A with Φ^{∗}(A) = Φ^{∗}(A^{c}) = 1. But in each gate of Φ^{∗} (obtained by dualizing the gates of Φ), the threshold is larger than in the corresponding gate of Φ. Thus Φ^{∗}(A) implies Φ(A) = 1, a contradiction. The other direction of the proof is given in the Appendix. △

Definition 4 The size |Φ| of a logical formula Φ is defined as the number of input wires to Φ. For any monotone Boolean function f, the size of the smallest formula computing f and consisting of any threshold gates f_{t,n} is denoted ϕ(f). If f is computable by a formula with majority accepting gates (resp. 1/3-accepting gates), then ϕ_{ma}(f) (resp. ϕ_{1/3}(f)) is defined similarly to ϕ(f).

We are now ready to prove the main claims for this section.

Theorem 1 A monotone Boolean function f has a span program with multiplication if and only if f is Q2-monotone. Any Q2-monotone function f can be computed by a monotone span program with multiplication, having at most ϕ_{ma}(f) rows and over any field K with^{14} |K| > ϕ_{ma}(f).

14It is sufficient that |K| > N, where N is the largest fan-in among the gates with threshold greater than 1.

Proof. Proposition 1 takes care of one direction of the first claim. Now if f is Q2-monotone, it can be computed by a formula Φ with majority accepting gates by Proposition 3. By applying Proposition 2 recursively (applying Lemma 2 to the gates of Φ and choosing the field K large enough), we obtain a span program with multiplication computing the same function as Φ, having as many rows as Φ has input wires. △

If we only consider ordinary monotone span programs (not caring about multiplication), then we have from Proposition 2 and the well-known fact that any monotone function can be computed by a monotone span program over any finite field:

Proposition 4 Every monotone Boolean function f can be computed by a monotone span program with at most ϕ(f) rows, over any field K with |K| > ϕ(f).

Finally, we define Q3-monotone functions, a subclass of the Q2-monotone functions. These functions are important for our results in Section 5.

Definition 5 Let f : {0, 1}^{n} → {0, 1} be a monotone function. We say [15] that f is Q3 if for all A, A′, A′′ ⊂ {1, …, n} with f(A) = f(A′) = f(A′′) = 0 we have A ∪ A′ ∪ A′′ ≠ {1, …, n}.

Proposition 5 The class of Q3-monotone functions coincides with the class of functions computable by Boolean formulas consisting of 1/3-accepting gates.

Proof. Let Φ = f_{t,m}(Φ_{1}, … Φ_{m}) where 3t ≤ m + 2 and the Φ_{j}’s are formulas with 1/3-accepting gates. Note that f_{t,m} is Q3. By induction on the number of gates, we prove that Φ is Q3. Say A_{i}, i = 1, 2, 3, contradict the claim. Then for each A_{i}, Φ^{∗}(A_{i}^{c}) = 1. Let W_{i} = {j|Φ_{j}^{∗}(A_{i}^{c}) = 1}. We have |W_{i}| ≥ m − t + 1. But since 3t ≤ m + 2, the intersection W of the W_{i}’s is non-empty. Let j ∈ W. Then Φ_{j}(A_{i}) = 0, i = 1, 2, 3, and the A_{i} cover the literals read by Φ_{j}. A contradiction. The other part of the proof is quite similar to that of Proposition 3, using f_{1,2}-, f_{1,3}-, and f_{2,4}-gates (in the recursion, use f_{3,4}-gates and replace them by f_{2,4}-gates afterwards). △

The following theorem is proved in the Appendix.

Theorem 2 A monotone Boolean function f has a monotone span program with strong multiplication if and only if f is Q3-monotone. Any Q3-monotone function f can be computed by a monotone span program with strong multiplication, having at most ϕ_{1/3}(f) rows and over any field K with |K| > ϕ_{1/3}(f).

5 Multi-Party Computation in the Information-Theoretic Scenario

5.1 Passive Adversaries

Let f(x_{1}, …, x_{n}) be a Q2-monotone Boolean function and let (K, M, a, r) with multiplication be a monotone span program computing it. We show how a multi party computation in the secure channels setting among n players allows them to securely compute the product of s and s′. Refer to Section 3 for the the general description of the protocol.

Let M_{i} denote the d_{i} rows in M (with d rows and e columns) that are associated with x_{i}, and let R_{i} denote their indices, i = 1, …, n. For any s, s′ ∈ K and for any σ, σ′ ∈ K^{e−1}, let s = (s_{1}, …, s_{d}) denote M(s, σ) and let s′ = (s′_{1}, …, s′_{d}) denote M(s′, σ′). Let t = (t_{1}, …, t_{d}) denote s∗s′. Let r = (r_{1}, …, r_{d}) be the recombination vector. Each player i initially holds s_{i} = M_{i}(s, σ) and s′_{i} = M_{i}(s′, σ′), i = 1, …, n. Each player i does the following

Re-Sharing: For each k ∈ R_{i} choose ρ_{k} ∈ K^{e−1} at random. Then, for each 1 ≤ j ≤ n, compute u_{kj} ← M_{j}(t_{k}, ρ_{k}), and send u_{kj} privately to player j.

Recombination: Each player i computes v_{i} ← ∑_{k=1}^{d} r_{k}u_{ki}.

Product-Reconstruction: Each player i broadcasts v_{i}.

As for its correctness, note that: (v_{1}, …, v_{n}) = (∑_{k=1}^{d} r_{k}u_{k1}, …, ∑_{k=1}^{d} r_{k}u_{kn}) = (∑_{k=1}^{d} r_{k}M_{1}(t_{k}, ρ_{k}), …, ∑_{k=1}^{d} r_{k}M_{n}(t_{k}, ρ_{k})) = ∑_{k=1}^{d} r_{k}M(t_{k}, ρ_{k}) = M(ss′, ∑_{k=1}^{d} r_{k}ρ_{k}). As to security, let A be a non-qualified set, i.e. f(A) = 0. The situation for A is equivalent to the following. The passive collusion A receives M_{A}(s, σ), M_{A}(s′, σ′) and M_{A}(ss′, ∑_{k=1}^{d} r_{k}ρ_{k}), where the ρ_{j} with j ∈ A are chosen by the players in A. First, by the observations in Section 4.3 there exists k such that r_{k} ≠ 0 and the k-th row of M does not belong to any of the players in A. Hence, from the point of view of A the latter is just a random (independent from anything else) sharing. The sharings of s and s′ are random as well. Hence, right after the re-sharing stage, the players in A have no information about s, s′ or ss′. Finally, after the productreconstruction, the players in A indeed learn ss′. But since the sharings of s and s′ are independent of that of ss′, they learn nothing beyond the product of s and s′.

5.2 Active Adversaries

5.2.1 How to Do Commitments

We first present a generic transformation that converts a span program secret sharing scheme ^{15} (see Section 4.2) into another such scheme. Schemes of this new type will serve as the basis of our commitment and commitment distribution protocols. They are in fact robust against cheaters when the dealer is honest, but this will not be needed here. The proofs are given in the Appendix.

15The multiplication property for monotone span programs is not needed here.

Let f(x_{1}, …, x_{n}) be a Q3-monotone function and let (K, M, a) be a a monotone span program computing f, where M has d rows and e columns.

Share Distribution:

(K, M, a) is public knowledge. Let s ∈ K be the secret to be distributed. The dealer chooses at random a symmetric e by e matrix R over K, subject to the constraint that the upper-left corner of R contains s. For i = 1 … n, the dealer puts U_{i} ← M_{i}R, and sends the matrix U_{i} privately to player i. The actual share s_{i} of player i is defined as the first column of U_{i}. Note that s_{i} = M_{i}b, where b is the first column of R (whose first entry is s).

Reconstruction:

Each player i broadcasts Ũ_{i} (supposedly what the dealer sent). Let s̃_{i} denote the first column of Ũ_{i}. Let G be the n by n (0,1)-matrix whose (i, j)-entry is 1 if and only if M_{j}Ũ_{i}^{t} = (M_{i}Ũ_{j}^{t})^{t}. Let B_{i} = {j : G(i, j) = 0} and B = {i : f(B_{i}) = 0}. Then f(B) = 1 and s̃_{i} = s_{i} for all i ∈ B. Hence, s can be recovered as in Section 4.2.

Proposition 6 The transformed scheme is a secret sharing scheme for f as well. For each i, j, we have M_{i}Uj^{t} = U_{i}M_{j}^{t}. Moreover, the scheme is robust against cheaters if the dealer is honest.

We will now extend the above scheme such that even with a faulty dealer, correct players are guaranteed to receive consistent shares of a secret. Note that M_{i}U_{j}^{t} = (M_{j}U_{i}^{t})^{t} can be computed by player i. Hence, by sending M_{j}U_{i}^{t} to player j, player i demonstrates that he has shares in share s_{j} belonging to player j.

The protocol for distributing and checking shares is defined as follows.

Step 1: Let s ∈ K be the secret to be distributed by the dealer. Privately to each player i, the dealer sends the matrix U_{i}. The actual share s_{i} of player i is again defined as the first column of U_{i}.

Step 2: Each player i puts, for j = 1 … n, check_{ij} ← U_{i}M_{j}^{t}, and sends the matrix check_{ij} privately to player j, who verifies that check_{ij} = M_{i}U_{j}^{t}. Note that check_{ij} has d_{i} rows and e columns. If player i did not receive U_{i} of the right format, player i sends ϵ (representing the empty string) to player j.

Step 3: For each player j, if player j finds disagreements in values received from a qualified set of players, he broadcasts an accusation against the dealer, asking him to make public all information sent to player j (since he can now conclude that the dealer must be faulty). If there are only disagreements with values received from a non-qualified set, player j broadcasts a complaint, asking the dealer to make public those check_{ij} for which he received a wrong value from player i.

Step 4: In response to the complaints and accusations broadcast, the dealer must make public all values asked for. All players check what they received against the information made public, and accuse the dealer if there is a disagreement. Now, the dealer must make public everything he sent to the new accusing players. This process goes on until no new accusations are made.

Step 5: If at this point a qualified set has accused the dealer, or if the information made public by the dealer contradicts itself, the players take a fixed default set of shares to represent the dealers secret (in this case the dealer is clearly faulty). Otherwise, the complaining players take the public information as their shares.

The following two theorems are proved in the Appendix.

Theorem 3 If the dealer is a correct player, the adversary learns nothing about s, and the shares held by correct players consistently determine s.

Theorem 4 For any dealer and any active adversary, the above protocol results in the correct players holding consistent shares s_{i} of some secret s.

These two theorems enable us to establish the commitments we need. The COM-MIT protocol works as follows. To commit to value a, we execute the above share distribution protocol for s = a where the committer acts as the dealer. From this phase, the players only need to remember the actual shares (s_{1}, …, s_{n}) that they received.

As to the OPEN protocol, to open a commitment the committer broadcasts a, s′_{1}, …, s′_{n}, and claims that a is the value committed to. Each player i checks whether the set of s′_{j}’s consistently determines a and whether s′_{i} = s_{i}. If any of these verifications fail, player i broadcasts a complaint. If all but a non-qualified set of players agree, the opening is accepted, otherwise it is rejected.

Theorems 3, 4, and the Q3 property trivially implies the hiding and binding properties required, and the linearity of the span program used directly translates into the homomorphic property we need for commitments: to add committed values, the players add their shares. The multiplication protocol required is described below.

5.2.2 Commitment Distribution Protocol A dealer be commited to value z ∈ K by commitment Z.

Step 1: The dealer makes shares z_{1}, ..., z_{n} of secret z (using the underlying secret sharing scheme) and commits to each of them using the commitment protocol.

Step 2: For i = 1, …, n, the commitment to z_{i} is opened to P_{i}, and all players send their own share of (each coordinate of) z_{i} to P_{i}. We now do the following stages to verify that P_{i} agrees with all correct players on the values received from the dealer:

1. P_{i} compares what the dealer sent with the shares received from the players. If there is disagreement w.r.t. a qualified set, P_{i} asks the dealer to open the commitments to z_{i} publically. Otherwise P_{i} asks the dealer to make public the shares for which there was disagreement.

2. The dealer broadcasts the requested information. If this contradicts itself, or is incomplete, the dealer is deemed corrupt. Otherwise, if P_{i} finds that the public information contradicts his own, he accuses the dealer, who must then open the commitments to z_{i} publically. Again, the dealer is deemed corrupt, if the openings fail, oherwise the players take whatever is now public to be their share of z_{i}.

Step 3: At this point each P_{i} knows a correct share z_{i}, he knows all shares of (coordinates of) z_{i} distributed, and agrees with all correct players on these values. The only missing thing is that we don’t know if the set of z_{i}’s is consistently determining z. However, a set of z_{i}’s is consistent precisely if some set of linear combinations of them are all zero. The coefficients of these combinations can be computed from the span program matrix. Therefore, using the linearity property, the players compute the corresponding linear combinations of the commitments to the z_{i}’s, and the dealer has to open all of the resulting commitments as zero. If this fails, the dealer is deemed corrupt. Finally we compute a linear combination of commitments to a qualified set of z_{i}’s, which should reconstruct a commitment C to z. We check that Z and C contain the same value by computing a commitment containing the difference of values in C and Z, which the dealer must open to reveal 0.

It is straightforward to verify that this protocol has the properties required in Section 2. Details are left to the reader.

5.2.3 Muliplication Subprotocol Lemma 3 Suppose values s, s′ have been shared with sets of shares s, resp. s′, using span program matrix M, with root vector (1, 0, ...0). Consider the vector s∗s′. Then this is a set of shares of the value ss′ in a new span program based secret sharing scheme, with matrix M′ and root vector (1, 0, ..., 0), where M′ can be computed from the span program matrix M that we started from. Moreover, if M has the strong multiplication property, then any potential set of correct players is qualified w.r.t. M′.

Proof. Let v = (v_{1}, ..., v_{e}) be any e-vector over K. Define the (e^{2} + e)/2-vector ṽ by:

ṽ = (v_{1}v_{1}, v_{1}v_{2}, ..., v_{1}v_{e}, v_{2}v_{2}, v_{2}v_{3}, ..., v_{2}v_{e}, ..., v_{e}v_{e})

Also, for any two e-vectors a, b, let

a ⋄ b = (a_{1}b_{1}, a_{1}b_{2} + a_{2}b_{1}, .., a_{1}b_{e} + a_{e}b_{1},
a_{2}b_{2}, a_{2}b_{3} + a_{3}b_{2}, ..., a_{2}b_{e} + a_{e}b_{2}, ...., a_{e}b_{e})

It is now straightforward to check that

⟨v, a⟩ · ⟨v, b⟩ = ⟨ṽ, a ⋄ b⟩

Now, let v_{1}, ..., v_{d} be the rows of M. Define M′ by letting its rows be ṽ_{1}, ..., ṽ_{d}. The lemma now follows by direct inspection. △

We are now ready to give the multiplication protocol, for which we are given commitments A, B made by P_{i} to values a, b Step 1: P_{i} uses the commitment distribution protocol twice with inputs A, resp.

B, so that now each P_{j} is committed to shares a_{j}, b_{j} of a, b.

Step 2: P_{i} makes a vector of commitments to a_{j} ∗ b_{j}, for j = 1..n. These commitments are opened to P_{j}, i.e. all shares involved in committing to a_{j} ∗ b_{j} are sent to P_{j}, and P_{i} sends the values he claims for all these shares. If P_{j} finds that a qualified set of players disagrees with the values received from P_{i}, or if the commitments did not contain the right values (a_{j} ∗ b_{j}), P_{j} accuses the dealer and proves his case by opening publically his own commitments to a_{j}, b_{j}. P_{i} must now open the commitments to a_{j} ∗ b_{j} in public; if this is not correct, he is deemed corrupt.

Step 3: Let D be vector of all commitments made by P_{i} in step 2. D should contain a consistent set of shares in generated from span program matrix M′, by the above lemma. This can be checked by verifying that some fixed set of linear combinations of the entries in D all equal 0. The coefficients of these linear combinations can be computed from the matrix of M′. Hence P_{i} can prove that the shares committed to in D are consistent by opening a number of commitments to reveal 0. Finally we compute a linear combination of the commitments in D using the entries in the recombination vector of M as coefficients. The resulting commitment, C is the output of the protocol (and is guaranteed to contain ab).

This protocol has the required properties, since by the consistency check in step 3, P_{i} has distributed in D consistent shares of some secret s using matrix M′. But by step 2, P_{i} must in fact distribute a_{j} ∗ b_{j} to each correct P_{j}, or be disclosed as corrupt. And since the set of correct players is qualified in M′, we must have s = ab. It is also straightforward to check that if P_{i} is correct, C is a random commitment with the only constraint that it contains ab.

6 Cryptographic Multi-Party Computations

Let f be any Q2-monotone Boolean function. We will prove that in the cryptographic setting, one can perform general multiparty computations tolerating any single non-qualified (w.r.t. f) set of active corrupted players. This is what Hirt and Maurer [15] prove to be the tolerance against passive adversaries in the secure channels setting.

According to Section 3 and given the results in Section 4, it is sufficient to describe the necessary commitment scheme and the Commitment Distribution Protocol.

6.1 How to Do Commitments

We will use the cryptographic commitment schemes from [10], which are based on q-one-way group homomorphisms (q-OWGH). These commitments satisfy the requirements from Section 2.1, i.e. they are homomorphic and have a zero-knowledge multiplication subprotocol. The RSA, DL or Diffie-Hellman assumptions are sufficient for efficiently realizing these commitments. In some implementations, the prime q can be chosen independently of the security parameter for the commitment scheme.

We will assume that commitments are unconditionally binding, i.e. the value committed to is uniquely determined from the commitment. In [10], also commitments that are unconditionally hiding are proposed. We may also use that type of commitments to support our protocol, but this requires a somewhat different set-up phase and is ommitted here for lack of space.

Each of the n players in the multiparty computation protocol generates his own instance of the commitment scheme (but all for the same q) and all broadcast the “public key” of their instances: this amounts to fixing, for i = 1 … n, a (probabilistic) commitment function ϕ_{i},i.e., player i commits to a value a ∈ ZZ_{q} by broadcasting C ← ϕ(α, a), where α is a random string.

We note that a slight variation of the multiplication sub-protocol guaranteed by [10] can be used to show in zero-knowledge that one knows how to open a given commitment, or that two commitments contain the same value, even if the public keys involved differ.

Finally, these zero knowledge protocols require random challenges to be generated such that they are unpredictable by the prover. This can for instance be done by straight-forward multi-party coin-flipping based on the commitment schemes.

6.2 Commitment Distribution Protocol

We build a commitment distribution protocol generalizing Pedersen’s non-interactive verifiable secret sharing scheme [17]. A related construction for the threshold case was independently discovered in [13]. Our scheme works for any Q2-monotone function instead of “minority” only and is based on the existence of any q-homomorphic commitment scheme.

We will assume that each player initally publishes a public key for a (polynomially) secure public-key encryption system. Existence of such a system follows from any of the particular assumptions we can base our commitments on. In some cases, such as when commitments are based on Diffie-Hellman encryption, this public key can be the same as the one for commitments, i.e. ϕ_{i} can be used as encryption function when sending messages to player i. In such a case, the description below can be simplified considerably.

For technical reasons (i.e. to be able to prove security of our protocol by a simulation argument), we assume that whenever a player commits to a value or sends an encryption in the protocol below, he also proves in zero-knowledge that he knows the committed or encrypted value.

Let f(x_{1}, …, x_{n}) be Q2-monotone and say that (GF (q), M, a) is a monotone span program computing f. Wlog a = (10 ⋯ 0). As usual M has d rows and e columns. The (i, j)-th entry of M is represented by an integer m_{ij} with 0 ≤ m_{ij} ≤ q − 1. Suppose we are given a q-homomorphic commitment scheme. Let C denote the collection of all possible commitments. Then M induces a map M^{C} from C^{e} to C^{d} as follows. Let C = (C_{1}, …, C_{e}) ∈ C^{e}. For i = 1, …, d the i-th coordinate of M^{C}C is equal to ∏_{j=1}^{e} C_{j}^{m_{ij}}.

The Commitment Distribution Protocol is as follows, where C = ϕ_{i}(α, a) is the input to the protocol:

Distribution: Player i chooses ρ_{2}, …, ρ_{e} ∈ GF (q) at random, puts b ← (a, ρ_{2}, …, ρ_{e}), and computes (s_{1}, …, s_{d}) ← Mb. For j = 2 … e, he chooses α_{j} as a random string and puts C ← (C, C_{2}, …, C_{n}), where C_{j} ← ϕ_{i}(α_{j}, ρ_{j}) for j = 2, … n. Finally, for j = 1, …, d he computes some strings β_{j} satisfying that M^{C}C = (ϕ_{i}(β_{1}, s_{1}), …, ϕ_{i}(β_{d}, s_{d})). It follows by definition of the commitments in Section 2.1 (when viewed as cryptographic commitments) that computation of these β_{j} is feasible. For j = 1 … n, he puts s_{j} ← (·, …, s_{k}, ⋯, ·)_{k∈R_{j}} and t_{j} ← (·, …, β_{k}, …, ·)_{k∈R_{j}}, where R_{j} is the set of rows in M associated with player j as in Section 5.1. Finally, player i broadcasts C, and for j = 1 … n, he sends s_{j} and t_{j} privately to player j, using secure public key encryption.

Verification: Each player j verifies that M_{j}^{C}C = (·, …, ϕ_{i}(β_{k}, s_{k}), …, ·)_{k∈R_{j}}. If there is an inconsistency, broadcast a complaint. The dealer must then make public s_{j} and t_{j}, and open the encryption sent to P_{j} in the previous step. If this is correct and consistent, P_{j} takes s_{j} as his share, otherwise the dealer is deemed corrupt. Finally, P_{j} makes commitments to each value in s_{j} using his own function ϕ_{j} and new independently chosen random input. He then proves (in zeroknowledge) that these new commitments contain the same values as M_{j}^{C}C.

The analysis of this scheme is essentially the same as that of Pedersen’s, taken into account that we work with a secret sharing scheme based on span programs for a Q2-monotone function and abstract q-homomorphic commitments, instead of with Shamir’s secret sharing scheme and homomorphic commitments based on discrete logarithms.

Acknowledgements

We would like thank Anna Gál, Rosario Gennaro, Martin Hirt, Tal Rabin, and Markus Stadler for interesting discussions and comments. Michael Ben-Or inspired us by showing us an unpublished threshold-type multiplication subprotocol for the information-theoretic scenario.

References

[1] S. B. Akers: Logical Design with Three-Input Majority Gates, Computer Design, March/April/May/June 1963.

[2] L. Babai, A. Gál, J. Kollár, L. Rónyai, T. Szabó, A. Wigderson: Extremal Bipartite Graphs and Superpolynomial Lowerbounds for Monotone Span Programs, Proc. ACM STOC ’96, pp. 603–611.

[3] J. Benaloh, J. Leichter: Generalized Secret Sharing and Monotone Functions, Proc. of Crypto ’88, Springer Verlag LNCS series, pp. 25–35.

[4] M. Ben-Or, S. Goldwasser, A. Wigderson: Completeness theorems for Non-Cryptographic Fault-Tolerant Distributed Computation, Proc. ACM STOC ’88, pp. 1–10.

[5] E. F. Brickell: Some Ideal Secret Sharing Schemes, J. Combin. Maths. & Combin. Comp. 9 (1989), pp. 105–113.

[6] R. Canetti: Studies in Secure Multiparty Computation and Applications, Ph. D. thesis, Weizmann Institute of Science, 1995.

[7] R. Canetti, U. Feige, O. Goldreich, M. Naor: Adaptively Secure Multi-Party Computation, Proc. ACM STOC ’96, pp. 639–648.

[8] D. Chaum, C. Crépeau, I. Damgård: Multi-Party Unconditionally Secure Protocols, Proc. of ACM STOC ’88, pp. 11–19.

[9] B. Chor, S. Goldwasser, S. Micali, B. Awerbuch: Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults, Proc. IEEE FOCS ’85, pp. 383–395.

[10] R. Cramer, I. Damgård: Zero Knowledge for Finite Field Arithmetic or: Can Zero Knowledge be for Free?, manuscript, June 1997.

[11] P. Feldman, S. Micali: An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement, SIAM J. Comp. Vol. 26, No. 4, pp. 873–933, August 1997.

[12] R. Gennaro: Theory and Practice of Verifiable Secret Sharing, Ph.D. thesis, MIT, 1996.

[13] R. Gennaro, M. Rabin, T. Rabin, Simplified VSS and Fast-Track Multiparty Computations with Applications to Threshold Cryptography, submitted to STOC’98.

[14] O. Goldreich, S. Micali and A. Wigderson: How to Play Any Mental Game or a Completeness Theorem for Protocols with Honest Majority, Proc. of ACM STOC ’87, pp. 218–229.

[15] M. Hirt, U. Maurer: Complete Characterization of Adversaries Tolerable in General Multiparty Computations, Proc. PODC ’97.

[16] M. Karchmer, A. Wigderson: On Span Programs, Proc. of Structure in Complexity, 1993.

[17] T. P. Pedersen: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proc. CRYPTO ’91, Springer Verlag LNCS, vol. 576, pp. 129–140.

[18] P. Pudlák, J. Sgall: Algebraic Models of Computation and Interpolation for Algebraic Proof Systems Proc. Feasible Arithmetic and Proof Complexity, Springer Verlag LNCS series.

[19] T. Rabin: Robust Sharing of Secrets when the Dealer is Honest or Cheating, J. ACM, 41(6):1089-1109, November 1994.

[20] T. Rabin, M. Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest majority, Proc. ACM STOC ’89, pp. 73–85.

[21] A. Shamir: How to Share a Secret, Communications of the ACM 22 (1979) 612–613.

Appendix

Proof of Proposition 2. Write h = f(g_{1}, …, g_{n}). Think of the following secret sharing scheme for h. Let s be a secret to be distributed. Then first distribute s using the matrix F to get shares s_{1}, …, s_{n}. Second, for i = 1 … n, take the share s_{i} and distribute its coordinates one by one and independently using the matrix G_{i}. The matrix M to be defined hereafter captures exactly this linear map. With this image in mind, it is not so difficult to convince onseself that the multiplication property is also satisfied.

Let x_{il} denote the l-th literal of g_{i}, for i = 1 …, n, l = 1 … m_{i}. Let (·, …, ·, …, ·) be a vector whose first location we number 0 and subsequent locations (i, k) with 1 ≤ i ≤ n and 1 ≤ k ≤ rows(F_{i}) (hence there are 1 + rows(F) locations). The rows of M will be vectors whose locations are indexed as above. Next, let i, j, k be any integers satisfying 1 ≤ i ≤ n, 1 ≤ j ≤ rows(G_{i}), 1 ≤ k ≤ rows(F_{i}).

The rows of M will consist of vectors m_{ijk} to be defined hereafter. Consider (w_{ij}v_{ik}, w_{ij}), where v_{ik} is the k-th row of F_{i}, and (w_{ij}, w_{ij}) is the j-th row of G_{i} (i.e. w_{ij} is the first coordinate of that row and w_{ij} collects the remaining coordinates). The row m_{ijk} of M is constructed as follows. Place w_{ij}v_{ik} in the first location and w_{ij} in location (i, k). Fill up all other locations with 0. The dimensions of vectors placed in specific locations should be clear from the context. Note that the rows in M corresponding to the l-th literal x_{il} of function g_{i} are exactly those m_{ijk} where j is the index of a row in G_{i} associated with x_{il}.

Let A ⊂ {x_{11}, …, x_{1m_{1}}, …, x_{n1}, …, x_{nm_{n}}} be a collection of literals, and assume that the span of the rows in M associated with the literals in A contains (10 ⋯ 0). For fixed (i, k) define z_{ik} as the contribution (in the linear comination that yields (10 ⋯ 0)) of the rows m_{ijk} associated with the x_{il} ∈ A. Then z_{ik} is of the form (w_{i}v_{ik}, 0, …, w_{i}, 0, …) where w_{i} is in location (i, k), (w_{i}, w_{i}) ∈ Im G_{i}^{t} and v_{ik} is a multiple of the k-th row of F_{i}. By the choice of the locations we must have w_{i} = 0, since the sum over all z_{ik} is equal to (10 ⋯ 0) and the other contributions have 0 in location (i, k). Note that if z_{ik} ≠ 0, we must have g_{i}(A) = 1, since in this case the span of the rows in G_{i} corresponding to the x_{il} ∈ A contains (w_{i}, 0 …, 0) and w_{i} ≠ 0.

For each i define z_{i} as the sum over the contributing z_{ik}’s. Then z_{i} is of the form (v_{i}, 0, …) where v_{i} ∈ Im F_{i}. Note that the sum over the z_{i}’s is (10 ⋯ 0). Let B denote the collection of i such that z_{i} ≠ 0. For i ∈ B, there must exist a contributing z_{ik} ≠ 0. Then clearly we must have f(B) = 1. Similarly we conclude that g_{i}(A) = 1 when i ∈ B, by the remarks above. Hence (K, M, a) computes h.

As to the multiplication property, keep in mind the workings of the secret sharing scheme sketched at the beginning of this proof. Let (t_{1}, …, t_{n}) and (t′_{1}, …, t′_{n}) denote Mb and Mb′, respectively, for arbitrary b and b′. Denote the first coordinates of b and b′ by s and s′, respectively. Here, t_{i} and t′_{i} stand for the union of the shares (in s and s′ respectively) “given” to the literals x_{il} for l = 1 … m_{i}. For a proper fixed ordering of the coordinates of t_{i} and t′_{i}, we have

⟨ r_{0}, (⟨r′_{1}, t_{1} ∗ t_{1}⟩, …, ⟨r′_{n}, t_{n} ∗ t_{n}⟩) ⟩ = ss′,

where for i = 1 … n, r′_{i} denotes the repetition of r_{i} rows(F_{i}) times. The recombination vector r is now easily obtained from this expression.

Proof of Proposition 3 (second part). We have show that any Q2-monotone function can be computed by a formula with three-input majority gates (f_{2,3}-gates) and OR-gates (f_{1,2}-gates).

We first describe an induction step that works for any monotone f. Let M denote any collection of f’s qualified sets such that M’s monotone closure coincides with the collection of all qualified sets of f (in particular, M can consist of all minimal qualified sets). Define three smaller subsets M_{i} of M such that each member of M occurs in two of the M_{i}’s. For i = 1, 2, 3, let f_{i} be the monotone function corresponding to the monotone closure of M_{i}. Define Φ = f_{2,3}(f_{1}, f_{2}, f_{3}). We have Φ = f. Indeed, by construction f(A) = 1 implies Φ(A) = 1. If f(A) = 0, then clearly f_{i}(A) = 0, i = 1, 2, 3. So Φ^{∗}(A^{c}) = f_{2,3}^{∗}(f_{1}^{∗}(A^{c}), f_{2}^{∗}(A^{c}), f_{3}^{∗}(A^{c})) = f_{2,3}(1, 1, 1) = 1. Apply this inductively. Note that if any of the f_{2,3}-gates thus constructed is satisfied, the complete formula is satisfied. Eventually, there will be M_{i}’s with one or two members and the induction can no longer be applied.

Now we will apply the above to a Q2-monotone function f (if f ≡ x_{i} we are done). Let M consist of all minimal qualified sets of f and all complements of maximal non-qualified sets of f and carry out the above recursion. At any point in the recursion where we have (M_{1}, M_{2}, M_{3}) with, say wlog, M_{1} having one or two members, do the following. If M_{1} has one member, say A, let i ∈ A and put f_{2,3}(x_{i}, ·, ·). Else, say it contains B, B′, if neither B nor B′ is the complement of a max-nonterm of f, let i ∈ B and j ∈ B′, and put f_{2,3}(f_{1,2}(x_{i}, x_{j}), ·, ·). In the other cases, by Lemma 1, there is an i with i ∈ B ∩ B′. Then put f_{2,3} = (x_{i}, ·, ·). Now we have a formula Φ consisting of f_{2,3}- and f_{1,2}-gates, where clearly for all C, f(C) = 1 implies Φ(C) = 1. But does f(A) = 0 imply Φ(A) = 0? We may assume that A is maximal. By the way we treated inputs of the form A^{c} with f(A) = 0, the values produced by the f_{1,2}-gates “do not influence” the value of Φ(A^{c}). And since all other gates are self-dual, we have Φ^{∗}(A^{c}) = Φ(A^{c}) = 1. Hence, Φ(A) = 0. Note that if f is self-dual, the f_{2,3}-gates suffice and no f_{1,2}-gates are needed. In this case our proof is similar to a method given in [1].

Proof of Theorem 2. Similar argument as in the proof of Proposition 1 yields the first part of the first claim: let disjoint, non-qualified sets A, B, C contradict the claim, and let κ (with first coordinate 1) satisfy M_{B}κ = 0. Let r be the recombination vector for the complement of C (the coordinates corr. to C are 0). Then ⟨(Mκ ∗ r)_{A}, M_{A}b⟩ = s for all b, contradicting f(A) = 0 as before. Thus f is Q3.

Next, let f be Q3 and let Φ be a formula with 1/3-accepting gates computing f. Denote by Φ̂ the formula obtained from Φ by replacing each gate f_{t_{k},n_{k}} by f_{2t_{k}−1,n_{k}}. From the proof of Lemma 2, one easily sees that a single 1/3-accepting gate f_{t,n} has a monotone span program with strong multiplication, and that by extending the rows one can easily construct a monotone span program for f_{2t−1,n}. Let (K, M^{Φ}, a) and (K, M Φ̂, a), wlog a = (10 ⋯ 0), be the respective monotone span programs by applying Proposition 2.

By induction one can show that for all b, b′ there exists c such that M^{Φ}b∗M^{Φ}b′ = M Φ̂c and ss′ = t, where s, s′ and t′ are the respective secrets. Now let Φ(A) = 0. Then Φ^{∗}(A^{c}) = 1. But in each gate of Φ^{∗}, we have n_{k} − t_{k} + 1 ≥ 2t_{k} − 1 since 3t_{k} ≤ n + 2. Hence Φ̂(A^{c}) = 1 and a linear combination of the coordinates of M_{A^{c}}^{Φ}b ∗ M_{A^{c}}^{Φ}b′ yields ss′.

Proof of Proposition 6. First observe that M_{i}U_{j}^{t} = M_{i}(M_{j}R)^{t} = M_{i}RM_{j}^{t} = U_{i}M_{j}^{t}. Next, we argue that a non-qualified set gets no information about s before the reconstruction. Let the set A satisfy f(A) = 0, and let M_{A} denote the rows of M corresponding to the players i ∈ A. We show that M_{A}R, which is the information players P_{i} with i ∈ A get from the dealer, contains no information about s. Let X be any symmetric matrix satisfying the equation M_{A}X = M_{A}R, and say that X has s̃ ∈ K in its upper-left corner. From our assumption on A, there exists a vector μ = (μ_{1}, …, μ_{e}) ∈ KerM_{A} with μ_{1} = 1 (see Section 4.2). Let μ ⊗ μ denote the e by e matrix whose i-th column is μ_{i}μ. Note that it has 1 in its upper left corner and that it is symmetric. Then X + (s − s̃)μ ⊗ μ satisfies the equatione as well, and has s in its upper left corner and is symmetric. Hence, for each possible s̃, the number of different solutions X with s̃ in the upper left corner is the same.

Now we prove the claims from the reconstruction. First note that if c and c′ (both from K^{e}) have different first coordinates c and c′, then M_{i}c = M_{i}c′ for at most a non-qualified set of players i (call this set D). Indeed, we have M_{D}(c − c′) = 0. But c − c′ ≠ 0 implies that a ∉ Im M_{D}^{t}, and hence f(D) = 0. Next, it is important to note that for all i, j, M_{j}U_{i}^{t} = U_{j}M_{i}^{t} can be viewed as a collection of shares for player j in the coordinates of s_{i} (“shares of shares”). Thus, if a corrupted player i broadcasts any Ũ_{i} such that s̃_{i} ≠ s_{i}, the set of players j for which M_{j}Ũ_{i}^{t} = U_{j}M_{i}^{t} (the original U_{j}) is non-qualified. But since the corrupted players A control the Ũ_{j} with j ∈ A, the i-th row contains 1-entries corresponding to at most the union of two non- qualified sets. Then, since f is Q3, we must have f(B_{i}) = 1. Note that if player i is uncorrupted, we trivially have that f(B_{i}) = 0 and that s̃_{i} = s_{i}. Hence, bad shares s̃_{i} are detected, and there are always sufficient ones to reconstruct ^{16} the secret s (at least those corresponding to the players in A^{c}).

Proof of Theorem 3. The remarks about the modified secret sharing scheme assuming an honest dealer suffice up to Step 2. The set of values that bad players receive from correct ones in Step 3 could already be computed from the information that they got from the dealer earlier. Finally note that correct players will only receive incorrect values from bad players, and so will never accuse the dealer. At most they will complain about values received from bad players. This means that the dealer will only have to broadcast information sent to bad players, so that they learn nothing new from this phase. It is also clear that the good players all agree on the values sent by the dealer, in particular their shares consistently determine the secret s the dealer meant to share.

Proof of Theorem 4. By assumption the set A of corrupted players is nonqualified. The theorem is clearly true in case the protocol ends with the players using the default set of shares. Otherwise, only some non-qualified set B of players have complained. This means that the set C of non-complaining uncorrupted players must be qualified since A, B and C together form the complete player set (f is Q3).

Consider the matrix H whose (i, j)-entry is what the dealer claims is the correct check_{ij} (state of affairs as in Step 5). The correct players agree on the entries in those rows and columns of H (note that H is “matrix-valued”) that correspond to them, either because they agreed from the start, or because the dealer was forced to make the values public.

Consider an arbitrary player j ∈ C. From the dealer he has received U_{j}, and since j ∈ C, he has been able to verify that the j-th column of H is of form (M_{1}U_{j}^{t}, ..., M_{n}U_{j}^{t}), and that the j-th row of H is of form (U_{j}M_{1}^{t}, ..., U_{j}M_{n}^{t}).

Hence, for each j ∈ C, the j-th column of H forms consistent sets of shares, where the secrets are the elements in the first column of U_{j} (call these s_{j}). And those entries in the j-th column of H corresponding to the players in C are sufficient for reconstructing those secrets. Thus, there exists a vector λ_{C} (only depending on C) such that for each j ∈ C, ⟨λ_{C}, M_{C}U_{j}^{t}⟩ = U_{j}M_{C}^{t}λ_{C} = s_{j} ∈ K^{d_{j}}, where M_{C} denotes the superposition of those rows j of M with j ∈ C (note that M_{C}^{t}λ ∈ K^{e}).

Now observe that for each j ∈ C we have s_{j} = U_{j}M_{C}^{t}λ_{C} = M_{j}U_{C}^{t}λ_{C}, where U_{C} is the superposition of the U_{j} with j ∈ C. Hence, the s_{j} thus computed form a consistent set of shares for the players in C in the secret sharing scheme. To complete these to a fulll set of shares, note that for j ∉ C we can define s_{j} = M_{j}U_{C}^{t}λ_{C} as well (which can be computed from the entries (i, j) in H with i ∈ C and j ∉ C). Hence (s_{1}, …, s_{n}) is a collection of consistent shares in the secret sharing scheme.

16It is easy to show that the scheme from Section 4.2 already has the right error correction property if f is Q3. But there, the cost of recovery may be superpolynomial in the size of the span program (as opposed to our modified scheme here).

Note also that an uncorrupted player k not in C will be able to determine the correct share from the entries in his column: he agrees with the players in C on the entries in the columns corresponding to C and the rest of the entries must be consistent with this, either because the dealer made the entire column public without causing more complaints, or because some selected values were complained about and corrected by the dealer to player k’s satisfaction.

Recent BRICS Report Series Publications

RS-97-28 Ronald Cramer, Ivan B. Damgård, and Ueli Maurer. Span Programs and General Secure Multi-Party Computation. November 1997. 27 pp.

RS-97-27 Ronald Cramer and Ivan B. Damgård. Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free? November 1997. 33 pp.

RS-97-26 Luca Aceto and Anna Ingólfsdóttir. A Characterization of Finitary Bisimulation. October 1997. 9 pp. To appear in Information Processing Letters.

RS-97-25 David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, and Sven Skyum. Searching Constant Width Mazes Captures the AC^{0} Hierarchy. September 1997. 20 pp.

RS-97-24 Søren B. Lassen. Relational Reasoning about Contexts. September 1997. 45 pp. To appear as a chapter in the book Higher Order Operational Techniques in Semantics, eds. Andrew D. Gordon and Andrew M. Pitts, Cambridge University Press.

RS-97-23 Ulrich Kohlenbach. On the Arithmetical Content of Restricted Forms of Comprehension, Choice and General Uniform Boundedness. August 1997. 35 pp.

RS-97-22 Carsten Butz. Syntax and Semantics of the logic L_{ωω}^{λ}. July 1997. 14 pp.

RS-97-21 Steve Awodey and Carsten Butz. Topological Completeness for Higher-Order Logic. July 1997. 19 pp.

RS-97-20 Carsten Butz and Peter T. Johnstone. Classifying Toposes for First Order Theories. July 1997. 34 pp.

RS-97-19 Andrew D. Gordon, Paul D. Hankin, and Søren B. Lassen. Compilation and Equivalence of Imperative Objects. July 1997. iv+64 pp. Appears also as Technical Report 429, University of Cambridge Computer Laboratory, June 1997. To appear in Foundations of Software Technology and Theoretical Computer Science: 17th Conference, FCT&TCS ’97 Proceedings, LNCS,