BRICS RS-02-8 Cramer & Fehr: Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups BRICS

Basic Research in Computer Science

Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups

Ronald Cramer Serge Fehr BRICS Report Series RS-02-8 ISSN 0909-0878 February 2002 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2002, Ronald Cramer & Serge Fehr.

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/02/8/

Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups

Ronald Cramer^{∗}  Serge Fehr^{∗}

BRICS^{†}, March 20, 2002^{‡}

Abstract

A black-box secret sharing scheme for the threshold access structure T_{t,n} is one which works over any finite Abelian group G. Briefly, such a scheme differs from an ordinary linear secret sharing scheme (over, say, a given finite field) in that distribution matrix and reconstruction vectors are defined over ℤ and are designed independently of the group G from which the secret and the shares are sampled. This means that perfect completeness and perfect privacy are guaranteed regardless of which group G is chosen. We define the black-box secret sharing problem as the problem of devising, for an arbitrary given T_{t,n}, a scheme with minimal expansion factor, i.e., where the length of the full vector of shares divided by the number of players n is minimal.

Such schemes are relevant for instance in the context of distributed cryptosystems based on groups with secret or hard to compute group order. A recent example is secure general multi-party computation over black-box rings.

In 1994 Desmedt and Frankel have proposed an elegant approach to the black-box secret sharing problem based in part on polynomial interpolation over cyclotomic number fields. For arbitrary given T_{t,n} with 0 < t < n − 1, the expansion factor of their scheme is O(n). This is the best previous general approach to the problem.

Using low degree integral extensions of ℤ over which there exists a pair of sufficiently large Vandermonde matrices with co-prime determinants, we construct, for arbitrary given T_{t,n} with 0 < t < n − 1 , a black-box secret sharing scheme with expansion factor O(log n), which we show is minimal.

∗Email: {cramer,fehr}@brics.dk † Basic Research in Computer Science (www.brics.dk), funded by the Danish National Research Foundation.

‡This is the full version of an earlier abstract, February 2002.

Keywords: information theoretically secure secret sharing, distibuted cryptography, algebraic models of computation, integer span programs, Abelian groups, algebraic number theory.

1 Introduction

A black-box secret sharing scheme for the threshold access structure T_{t,n} is one which works over any finite Abelian group G. Briefly, such a scheme differs from an ordinary linear secret sharing scheme (over, say, a given finite field; see e.g. [Bla79, Sha79, Bri89, BI92, BL88, KW93, Gal95, Bei96, Dij97, CDM00]) in that distribution matrix and reconstruction vectors are defined over ℤ and are designed independently of the group G from which the secret and the shares may be sampled. In other words, the dealer computes the shares for the n players as ℤ-linear combinations of the secret group element of his interest and secret randomizing group elements, and reconstruction of the secret from the shares held by a large enough set of players is by taking ℤ-linear combinations over those shares. Note that each player may receive one or more group elements as his share in the secret. Perfect completeness and perfect privacy are guaranteed regardless of which group G is chosen. Here, perfect completeness means that the secret is uniquely determined by the joint shares of at least t + 1 players, and perfect privacy means that the joint shares of at most t players contain no Shannon information at all about the secret of interest. Note that these schemes are homomorphic in the sense that the sum of share vectors is a share vector for the sum of the corresponding secrets.

We define the black-box secret sharing problem as the problem of devising, for an arbitrary given T_{t,n}, a scheme with minimal expansion factor, i.e., where the length of the full vector of shares divided by the number of players n is minimized. Note the case t = n − 1 is easily solved by “additive n-out-of-n sharing,” which has expansion factor 1. The cases t = 0, n have no meaning for secret sharing. For the rest of this discussion we assume 0 < t < n − 1.

Black-box secret sharing schemes were first considered by Desmedt and Frankel [DF89] in the context of distributed cryptosystems based on groups with secret order. Shamir’s polynomial based secret sharing scheme over finite fields [Sha79] cannot immediately be adapted to the setting of black-box secret sharing. In [DF94], Desmedt and Frankel [DF94] showed a black-box secret sharing scheme that elegantly circumvents integer polynomial interpolation problems by passing to an integral extension ring of ℤ over which a sufficiently large invertible Vandermonde matrix exists. Their construction is then completed on account of the fact that (sufficiently many copies of) an arbitrary Abelian group can be viewed as a module over such an extension ring.

For a given commutative ring S with 1, the largest integer l such that there exists an invertible l×l Vandermonde matrix with entries in S is called the Lenstra constant l(S) of the ring S. Equivalently, l(S) is the maximal size of a subset E of S that is “exceptional” in that for all α, α′ ∈ E, α ≠ α′, it holds that α − α′ is a unit of S.

Given an integral extension ring S of degree m over ℤ, they construct a black-box secret sharing scheme with expansion factor m for a threshold access structure on at most l(S) − 1 players. For any prime p, Lenstra’s constant for the ring of integers of the pth cyclotomic number field is p. ^{1} Given an arbitrary T_{t,n} and choosing S as the ring of integers of the pth cyclotomic number field, where p is the smallest prime greater than n, they construct a black-box secret sharing scheme for T_{t,n} with expansion factor between n and 2n. This is the best previous general approach to the problem. Further progress on the black-box secret sharing problem via the approach of [DF94] depends on the problem of finding for each n an extension whose degree is substantially smaller than n and whose Lenstra constant is greater than n. To the best of our knowledge, this is an open problem of algebraic number theory (see also [DF94] and the references therein).

Except for some quite special cases, namely when t is constant or when t (resp. n−t) is small compared to n [DCB94, BBDW96] or the constant factor gain from [DKKK98], no substantial improvement on the general black-box secret sharing problem has been reported since.

Our result builds on [DF94] in that we also study the problem over certain integral extensions. However, we avoid dependence on Lenstra’s constant altogether. Namely, we exhibit low degree integral extensions of ℤ over which there exists a pair of sufficiently large Vandermonde matrices with co-prime determinants and show how this allows us to construct, for arbitrary given T_{t,n}, a black-box secret sharing scheme with expansion factor O(log n). Using a result of Karchmer and Wigderson [KW93], we show that this is minimal.

1It is not hard to find an exceptional set of size p in this ring. To see that the maximal size of such a set is p, let K be a number field of degree m, and let ℤ_{K} denote its ring of algebraic integers. For an arbitrary non-trivial ideal I of ℤ_{K}, it is easy to see that l(ℤ_{K}) ≤ |ℤ_{K}/I| (≤ 2^{m}). In the case where K is the pth cyclotomic number field, the integer prime p totally ramifies. Hence l(ℤ_{K}) ≤ |ℤ_{K}/P | = p, where P is the unique prime ideal of ℤ_{K} lying above p.

There are several applications of black-box secret sharing schemes. For instance, the result of [DF94] is exploited in [DDFY94] to obtain an efficient and secure solution for sharing any function out of a certain abstract class of functions, including RSA. The interest in application of the result of [DF94] to practical distributed RSA-based protocols seems to have decreased somewhat due to recent developments, see for instance [Sho00] and the references therein. However, apart from the fact that optimal black-box secret sharing is perhaps interesting in its own right, we note that in [CFIK02] our black-box secret sharing scheme is applied in protocols for secure general multi-party computation over black-box rings. Also, optimal black-box secret sharing may very well be relevant to new distributed cryptographic schemes for instance based on class groups.

This paper is organized as follows. In Section 2 we give a formalization of the notion of black-box secret sharing, and show a natural correspondence between such schemes and integer span programs (ISPs). This generalizes the well-known correspondence between monotone span programs over finite fields [KW93] and linear secret sharing schemes over finite fields. In Section 3 we show lower bounds on the size of ISPs computing threshold access structures. Our main result is presented in Section 4, where we construct an ISP with minimal size for an arbitrary given threshold access structure. This leads to an optimal black-box secret sharing scheme for an arbitrary given threshold access structure.

2 Black-Box Secret Sharing

2.1 Definition

We give a formal definition that exactly captures the intuition behind blackbox secret sharing over Abelian groups.

Definition 1 A monotone access structure on {1, …, n} is a non-empty collection Γ of sets A ⊂ {1, …, n} such that ∅ ∉ Γ and such that for all A ∈ Γ and for all sets B with A ⊂ B ⊂ {1, …, n} it holds that B ∈ Γ.

Definition 2 Let t and n be integers with 0 < t < n. The threshold access structure T_{t,n} is the collection of sets A ⊂ {1, …, n} with |A| > t. ^{2}

Let Γ be a monotone access structure on {1, …, n}. Let M ∈ ℤ^{d,e} be an integer matrix, and let ψ : {1, …, d} → {1, …, n} be a surjective function.

2Note that some authors define T_{t,n} as consisting of all sets of size at least t. Our definition adheres to a convention in the multi-party computation literature.

We say that the jth row (j = 1 … d) of M is labelled by ψ(j) or that “ψ(j) owns the jth row.” For A ⊂ {1, …, n}, M_{A} denotes the restriction of M to the rows jointly owned by A. Write d_{A} for the number of rows in M_{A}. Similarly, for x ∈ ℤ^{d}, x_{A} ∈ ℤ^{d_{A}} denotes the restriction of x to the coordinates jointly owned by A. For each A ∈ Γ, let λ(A) ∈ ℤ^{d_{A}} be an integer (column-) vector. We call this the reconstruction vector for A. Collect all these vectors in a set R.

Definition 3 Let Γ be a monotone access structure on {1, …, n}, and let B = (M, ψ, R) be as defined above. B is called an integer Γ-scheme. Its expansion rate is defined as d/n, where d is the number of rows of M.

Let G be a finite Abelian group. We use additive notation for its group operation, and use 0_{G} to denote its neutral element. The group G is of course a ℤ-module (see e.g. [Lang]), by defining the map ℤ×G → G, (μ, g) ↦ μ·g, where 0·g = 0_{G}, μ·g = g+…+g (μ times) for μ > 0 and μ·g = −((−μ)·g) for μ < 0. ^{3} We also write μg or gμ instead of μ · g. Note that it is well-defined how an integer matrix acts on a vector of group elements.

Definition 4 Let Γ be a monotone access structure on {1, …, n} and let B = (M, ψ, R) be an integer Γ-scheme. Then B is a black-box secret sharing scheme for Γ if the following holds. Let G be an arbitrary finite Abelian group G, and let A ⊂ {1, …, n} be an arbitrary non-empty set. For arbitrarily distributed s ∈ G, let g = (g_{1}, …, g_{e})^{T} ∈ G^{e} be drawn uniformly at random, subject to g_{1} = s. Define s = Mg. Then:

• (Completeness) If A ∈ Γ, then s_{A}^{T} · λ(A) = s with probability 1, where λ(A) ∈ R is the reconstruction vector for A.

• (Privacy) If A ∉ Γ, then s_{A} contains no Shannon information on s.

Note that these schemes ^{4} are homomorphic in the sense that the sum s + s′ of two share vectors s and s′, is a share vector for the sum s + s′ of their corresponding secrets s and s′.

2.2 Monotone Span Programs over Rings

In this section we provide quite natural necessary and sufficient conditions under which an integer Γ-scheme is a black-box secret sharing scheme for Γ.

3If the group operation in G is efficient, multiplication by an integer can also be efficiently implemented using standard “double-and-add.”

4See [Kin00] for an equivalent definition.

To this end, we introduce the notion of monotone span programs over rings. This is a certain variation of monotone span programs over finite fields, introduced by Karchmer and Wigderson [KW93]. These are well-known to have a natural one-to-one correspondence with linear secret sharing schemes over finite fields (see e.g. [Gal95, Bei96]). Monotone span programs over ℤ (ISPs) will turn out to have a similar correspondence with black-box secret sharing schemes. We also show an efficient conversion of a monotone span program over an integral extension ring of ℤ to an ISP.

As an aside, monotone span programs over rings are the basis for multiparty computation over black-box rings, as studied in [CFIK02]. In particular, the techniques of [CDM00] for secure multiplication and VSS apply to this flavor of monotone span program as well.

Throughout this paper, S denotes a (not necessarily finite) commutative ring with 1. Let Γ be a monotone access structure on {1, …, n}, and let M ∈ S^{d,e} be a matrix whose d rows are labelled by a surjective function ψ : {1, …, d} → {1, …, n}.

Definition 5 ε = (1, 0, …, 0)^{T} ∈ S^{e} is called the target vector. M = (S, M, ψ, ε) is called a monotone span program (over the ring S). If S = ℤ, it is called an integer span program, or ISP, for short. We define size(M) = d, where d is the number of rows of M.

For N ∈ S^{a,b}, imN denotes its column space, i.e., the space of all vectors Nx ∈ S^{a}, where x ranges over S^{b}, and kerN denotes its null-space, i.e., the space of all vectors x ∈ S^{b} with Nx = 0 ∈ S^{a}.

Definition 6 As above, let Γ be a monotone access structure and let M = (S, M, ψ, ε) be a monotone span program over S. Then M is a monotone span program for Γ, if for all A ⊂ {1, …, n} the following holds.

• If A ∈ Γ, then ε ∈ imM_{A}^{T}.

• If A ∉ Γ, then there exists κ = (κ_{1}, …, κ_{e})^{T} ∈ kerM_{A} with κ_{1} = 1.

We also say that M computes Γ.

If S is a field, our definition is equivalent to the computational model of monotone span programs over fields [KW93]. Indeed, this model is characterized by the condition that A ∈ Γ if and only if ε ∈ imM_{A}^{T}. The equivalence follows from the remark below.

Remark 1 By basic linear algebra, if S is a field, then ε ∉ imM_{A}^{T} implies that there exists κ ∈ kerM_{A} with κ_{1} = 1. If S is not a field this does not necessarily hold. ^{5} The implication in the other direction trivially holds regardless of S.

Using (generally inefficient) representations of monotone access structures as monotone Boolean formulas and using induction in a similar style as in e.g. [BL88], it is straightforward to verify that for all Γ and for all S, there is a monotone span program over S that computes Γ.

Definition 7 For any Γ and for any S, msp_{S}(Γ) denotes the minimal size of a monotone span program over S computing Γ. If S = ℤ, we write isp(Γ).

Define a non-degenerate monotone span program as one for which the rows of M span the target-vector. As opposed to the case of fields, a nondegenerate monotone span program over a ring need not compute any monotone access structure. This is of no concern here, though.

The following proposition characterizes black-box secret sharing schemes in terms of ISPs.

Proposition 1 Let Γ be a monotone access structure on {1, …, n}, and let B = (M, ψ, R) be an integer Γ-scheme. Then B is a black-box secret sharing scheme for Γ if and only if M = (ℤ, M, ψ, ε) is an ISP for Γ and for all A ∈ Γ, its reconstruction vector λ(A) ∈ R satisfies M_{A}^{T} λ(A) = ε.

Proof. The argument that the stated ISP is sufficient for black-box secret sharing is quite similar to the well-known case of linear secret sharing over finite fields. The other direction of the implication follows in essence from Lemma 1 below. We include full details for convenience.

Consider the ISP from the statement of the proposition, together with the assumption on the reconstruction vectors. Consider an arbitrary set A ⊂ {1, …, n} and an arbitrary finite Abelian group G. Define s = Mg for arbitrary g = (s, g_{2}, …, g_{e})^{T} ∈ G^{e}. Suppose A ∈ Γ, and let λ(A) ∈ R be its reconstruction vector. It follows that s_{A}^{T}λ(A) = (M_{A}g)^{T} λ(A) = g^{T} (M_{A}^{T} λ(A)) = g^{T} ε = s. Thus the completeness condition from Definition 4 is satisfied. If A ∉ Γ, then there exists κ ∈ ℤ^{e} with M_{A}κ = 0 ∈ ℤ^{d_{A}} and κ_{1} = 1, by Definition 6. For arbitrary s′ ∈ G, define s′ = s + M(g + (s′ − s)κ) ∈ G^{d_{A}}. The secret defined by s′ equals s′, while on the other hand s′_{A} = s_{A}. This implies perfect privacy: the assignment g′ = g + (s′ − s)κ provides a bijection between the set of possible vectors of “coins” consistent with s_{A} and s, and the set of those consistent with s_{A} and s′. Therefore, the privacy condition from Definition 4 is also satisfied.

5Consider for example the integer matrix M = (2 0).

In the other direction of the proposition, we start with a black-box secret sharing scheme for Γ according to Definition 4. Consider an arbitrary set A ⊂ {1, …, n}. Suppose A ∈ Γ, and let λ(A) ∈ R be its reconstruction vector. For an arbitrary prime p, set G = ℤ_{p}. By the completeness condition from Definition 4, it follows that (1, 0, …, 0)^{T} ≡ (M_{A}I_{e})^{T} λ(A) ≡ M_{A}^{T} λ(A) mod p, where I_{e} ∈ ℤ_{p}^{e,e} is the identity matrix. This holds for all primes p. Hence, M_{A}^{T} λ(A) = (1, 0, …, 0)^{T} = ε. Therefore, the condition on the sets A ∈ Γ in Definition 6 and the condition on the reconstruction vectors R from the statement of the proposition are satisfied.

To conclude the proof we show that the privacy condition from Definition 4 implies the condition on the sets A ∉ Γ from Definition 6. The following formulation is equivalent. Let y ∈ ℤ^{d_{A}} denote the left-most column of M_{A}, and let N_{A} ∈ ℤ^{d_{A},e−1} denote the remaining e−1 columns. Then it is to be shown that the linear systems of equations N_{A}x = y is solvable over ℤ.

By Lemma 1 below, it is sufficient to show that this holds modulo m, for all m ∈ ℤ, m ≠ 0. With notation as in Definition 4 and considering G = ℤ_{m}, it follows from the privacy condition that there exists g′ ∈ ℤ_{m}^{e} such that g′_{1} ≡ s − 1 and s_{A} ≡ M_{A}g′. Setting κ ≡ g − g′ ∈ ℤ_{m}^{e}, we have M_{A}κ ≡ 0 with κ_{1} ≡ 1. In other words, N_{A}x = y is solvable over ℤ_{m} for all integers m ≠ 0. △

We note that [Kin00] also discusses a characterization. Although there are some similarities in the technical analysis, the conditions stated there are still in terms of the black-box secret sharing scheme, rather than by providing simple algebraic conditions on the matrix M as we do. Therefore, we feel that our approach based on integer span programs is perhaps more useful and insightful, especially since monotone span programs over finite fields have since long been known to be equivalent to linear secret sharing schemes over finite fields.

Lemma 1 Let N ∈ ℤ^{a,b} and y ∈ ℤ^{a}. Then the linear system of equations Nx = y is solvable over ℤ if and only if it is solvable over ℤ_{m} for all integers m ≠ 0.

Proof. The forward direction of the proposition is trivial. In the other direction, consider the ℤ-module H generated by the columns of N. By basic theory of ℤ-modules (see e.g. [Lang]), there exists a ℤ-basis B = (b_{1}, …, b_{a}) of ℤ^{a}, and non-zero integers a_{1}, …, a_{l} such that B_{H} = (a_{1}b_{1}, …, a_{l}b_{l}) is a ℤ-basis of H. Let L denote the ℤ-module with basis B_{L} = (b_{1}, …, b_{l}). Note that H ⊂ L. Let p be an arbitrary prime, and let \overline{(·)} denote reduction modulo p. Since the determinant of B is ±1, \overline{B} (resp. \overline{B}_{L}) provides a basis for the vector-space 𝔽_{p}^{a} (resp. the vector-space \overline{L}). Note that \overline{B}_{L} ⊂ \overline{B}.

It follows from the assumptions that \overline{y} ∈ \overline{H} ⊂ \overline{L}. Let (y_{1}, …, y_{a}) ∈ ℤ^{a} denote the coordinates of y wrt. B. Since the latter observation holds for all primes p, it follows that y_{l+1} = … = y_{a} = 0. Hence, y ∈ L. Now set m̂ = ∏_{i=1}^{l} a_{i}. By the assumptions, there exists cm̂ ∈ ℤ^{a} such that y + m̂ · cm̂ ∈ H. Therefore, m̂ · cm̂ ∈ L, and by the definition of L, cm̂ ∈ L. By the choice of m̂, it follows that m̂ · cm̂ ∈ H. We conclude that y ∈ H, as desired. △

Remark 2 Let M = (S, M, ψ, ε) compute Γ. If S is a field or a principal ideal domain (such as ℤ), then we may assume without loss of generality that e ≤ d, i.e., there are at most as many columns in M as there are rows.

This is easily shown using elementary linear algebra, and using the basic properties of modules over principal ideal domains (see e.g. [Lang] and the proof of Lemma 1). Briefly, since M is non-degenerate, the last statement in Remark 1 implies that the space generated by the 2nd up to the eth column of M does not contain even a non-zero multiple of the first column. Without changing the access structure that is computed, we can always replace the 2nd up to the eth column of M by any set of vectors that generates the same space. If S is a field or a principal ideal domain, this space has a basis of cardinality at most d − 1.

Remark 3 We may now identify a black-box secret sharing scheme for Γ with an ISP M = (ℤ, M, ψ, ε) for Γ. A reconstruction vector for A ∈ Γ is simply any vector λ(A) ∈ ℤ^{d_{A}} such that M_{A}^{T} λ(A) = ε. Note that the expansion rate of the corresponding black-box secret sharing scheme is equal to size(M)/n. By Remark 2 it uses at most size(M) random group elements.

We now state some lemmas that are useful in the sequel.

Definition 8 The dual Γ^{∗} of a monotone access structure Γ on {1, …, n} is the collection of sets A ⊂ {1, …, n} such that A^{c} ∉ Γ.

Note that Γ^{∗} is a monotone access structure on {1, …, n}, that (Γ^{∗})^{∗} = Γ and that (T_{t,n})^{∗} = T_{n−t−1,n}. The lemma below generalizes a similar property shown in [KW93] for the case of fields.

Lemma 2 msp_{S}(Γ) = msp_{S}(Γ^{∗}), for all S and Γ.

Proof. Let M = (S, M, ψ, ε) be a monotone span program for Γ. Select an arbitrary generating set of vectors b_{1}, …, b_{l} for kerM^{T}, and choose λ with M^{T} λ = ε. Let M^{∗} be the matrix defined by the l + 1 columns (λ, b_{1}, b_{2}, …, b_{l}), and use ψ to label M^{∗} as well. Define M^{∗} = (S, M^{∗}, ψ, ε^{∗}), where ε^{∗} = (1, 0, …, 0)^{T} ∈ S^{l+1}. Note that size(M^{∗}) = size(M). We claim that M^{∗} computes Γ^{∗}. This is easy to verify.

If A^{c} ∉ Γ, then by Definition 6, there exists κ ∈ S^{l+1} such that M_{A^{c}}κ = 0 and κ_{1} = 1. Define λ^{∗} = M_{A}κ. Then (M^{∗})_{A}^{T}λ^{∗} = ((M^{∗})^{T} · M)κ = ε^{∗}. On the other hand, if A^{c} ∈ Γ, then there exists λ̂ ∈ S^{d} such that M^{T} λ̂ = ε and λ̂_{A} = 0. By definition of M^{∗}, there exists κ ∈ S^{l+1} such that M^{∗}κ = λ̂ and κ_{1} = 1. Hence, M_{A}^{∗}κ = λ̂_{A} = 0 and κ_{1} = 1. This concludes the proof. △

The lemma below holds in a more general setting, but we tailor it to ours.

Lemma 3 Let f(X) ∈ ℤ[X] be a monic, irreducible polynomial. Write m = deg(f). Consider the ring S = ℤ[X]/(f(X)). Suppose M = (S, M, ψ, ε) is a monotone span program over S for a monotone access structure Γ. Then there exists an ISP M̂ = (ℤ, M̂, ψ̂, ε̂) for Γ with size(M̂) = m · size(M).

Proof. The proof is based on a standard algebraic technique for representing a linear map defined over an extension ring in terms of a linear map defined over the ground ring. This technique is also used in [KW93] for monotone span programs over extension fields. Since our definition of monotone span programs over rings differs slightly from the definitions in [KW93], we explain it in detail.

Note that S is a commutative ring with 1 and that it has no zero divisors, but that it is not a field. Fix w ∈ S such that f(w) = 0 (such as w = \overline{X}, the class of X modulo f(X)). Then for each x ∈ S, there exists x⃗ = (x_{0}, …, x_{m−1}) ∈ ℤ^{m} such that x = x_{0} · 1 + x_{1} · w + ⋯ + x_{m−1} · w^{m−1}. This vector, which we will view as a row-vector, is unique. In other words, W = {1, w, …, w^{m−1}} is a ℤ-basis for S. As before, write d (resp. e) for the number of rows (resp. columns) of M. Fix an arbitrary set B ∈ Γ and write d_{B} for the number of rows of M_{B}. Let λ = (λ_{1}, …, λ_{d_{B}})^{T} ∈ S^{d_{B}} be such that M_{B}^{T}λ = ε ∈ S^{e}. Let λ⃗_{i} ∈ ℤ^{m} denote the coordinates of λ_{i} ∈ S wrt. W, i = 1 … d_{B}. Also fix an arbitrary set A ∉ Γ, and write d_{A} for the number of rows of M_{A}. Let κ = (κ_{1}, κ_{2}, …, κ_{e})^{T} ∈ S^{e} be such that κ_{1} = 1 and M_{A}κ = 0 ∈ S^{d_{A}}, and let κ⃗_{i} ∈ ℤ^{m} denote the coordinates of κ_{i} wrt. W, i = 1 … e.

Define the monotone span program \overline{M} = (S, \overline{M}, ψ̂, ε) as follows. To define \overline{M}, replace each row r of the matrix M by the matrix consisting of the m rows 1 · r, w · r, …, w^{m−1} · r, where the labeling ψ is extended to ψ̂ so that these m rows of \overline{M} have the same label as r in M. Note that \overline{M} ∈ S^{md,e}. To verify that \overline{M} = (S, \overline{M}, ψ̂, ε) is a monotone span program for Γ as well, note that

\overline{M}_{B}^{T}(λ⃗_{1}, …, λ⃗_{d_{B}})^{T} = ε ∈ S^{e} and \overline{M}_{A}κ = 0 ∈ S^{md_{A}}.

We define the ISP M̂ = (ℤ, M̂, ψ̂, ε̂) as follows. First, define a new target vector ε̂ = (1, 0 …, 0)^{T} ∈ ℤ^{me}. Next, construct, M̂ ∈ ℤ^{md,me} from \overline{M}, by replacing each entry x in \overline{M} by the row-vector x⃗ ∈ ℤ^{m}, its coordinate vector wrt. W. Note that

M̂_{B}^{T}(λ⃗_{1}, …, λ⃗_{d_{B}})^{T} = ε̂ ∈ ℤ^{me}.

Consider arbitrary u, v ∈ S, and let u⃗, v⃗ ∈ ℤ^{m} be their respective coordinate vectors wrt. W. It is straightforward that there exist V_{0}, …, V_{m−1} ∈ ℤ^{m,m}, only depending on W, such that, for i = 0 … m − 1, u⃗V_{i}v^{T} ∈ ℤ is the ith coordinate of u · v ∈ S, when written in coordinates wrt. W. By the particular choice of W we must have V_{0}(1, 0, …, 0)^{T} = (1, 0, …, 0)^{T}. Then

M̂_{A}(1, 0, …, 0, y⃗_{2}, …, y⃗_{e})^{T} = 0 ∈ ℤ^{md_{A}},

where, for i = 2 … e,

y⃗_{i} = κ⃗_{i}V_{0}^{T} ∈ ℤ^{m}.

Hence, M̂ = (ℤ, M̂, ψ̂, ε̂) is an ISP for Γ. As an aside, note that we may delete the 2nd up to mth leftmost colums of M̂ and the corresponding coordinates of ε̂ without penalty. Hence, 1 + m(e − 1) columns suffice, rather than me. △

3 Lower Bounds for the Threshold Case

In this section we prove ^{6}

Proposition 2 For all integers t, n with 0 < t < n − 1, it holds that isp(T_{t,n}) = Ω(n · log n). Consequently, the expansion factor of a black-box secret sharing scheme for T_{t,n} with 0 < t < n − 1 is Ω(log n).

6Note that isp(T_{n−1,n}) = n: the case t = n − 1 is solved by simple additive “n-out-of-n secret sharing.”

Proposition 2 follows quite directly from the bound shown in Theorem 1 for binary monotone span programs, as proved in [KW93]. Before we give the details of the proof of Proposition 2, we include a proof of their bound for convenience. Note that we have made constants for their asymptotic bound explicit.

Throughout this section, K denotes a field. Let M = (K, M, ψ, ε) be a non-degenerate monotone span program. The access structure of M, denoted Γ(M), is the collection of sets A such that ε ∈ imM_{A}^{T}. Note that by Remark 1 this is consistent with our Definition 6. We write msp_{2}(Γ) instead of msp_{𝔽_{2}}(Γ).

Proposition 3 [KW93] msp_{2}(T_{1,n}) ≥ n · log n.

Proof. Consider a monotone span program M = (𝔽_{2}, M, ψ, ε) such that Γ(M) = T_{1,n}. Define e as the number of columns of M, d as its number of rows, and d_{i} as the number of rows of M_{i} for i = 1 … n, where we write M_{i} instead of M_{{i}} and d_{i} instead of d_{{i}}. Without loss of generality, assume that the rows of each M_{i} are linearly independent over 𝔽_{2}. Let H_{1} collect the vectors in 𝔽_{2}^{e} with first coordinate equal to 1. Since {i} ∉ T_{1,n}, Remark 1 implies that |kerM_{i}∩H_{1}| ≠ ∅. By assumption on M_{i}, |kerM_{i}∩H_{1}| = 2^{e−1−d_{i}} for i = 1 … n. On the other hand, {i, j} ∈ T_{1,n}. Hence, by Remark 1, we have kerM_{i} ∩ kerM_{j} ∩ H_{1} = ∅, for all i, j with 1 ≤ i < j ≤ n. By counting and normalizing, 2^{−d_{1}} + ⋯ + 2^{−d_{n}} ≤ 1. By the Log Sum Inequality (see e.g. [CT]), d = d_{1} + ⋯ + d_{n} ≥ n log n. △

Theorem 1 [KW93] n · (⌊log n⌋ + 1) ≥ msp_{2}(T_{t,n}) ≥ \frac{n+3}{2} · log \frac{n+3}{2}, for all t, n with 0 < t < n − 1.

Proof. The upper bound, which is not needed for our purposes, follows by considering an appropriate Vandermonde matrix over the field 𝔽_{2^{u}}, where u = (⌊log n⌋ + 1). This is turned into a binary monotone span program for T_{t,n} using a similar conversion technique as in Lemma 3. As to the lower bound, note that we may assume t ≥ (n − 1)/2, since msp_{2}(T_{t,n}) = msp_{2}(T_{n−t−1,n}) by Lemma 2.

Then msp_{2}(T_{t,n}) ≥ msp_{2}(T_{t,t+2}) = msp_{2}(T_{1,t+2}) ≥

(t + 2) log(t + 2) ≥ \frac{n + 3}{2} · log \frac{n + 3}{2}.

The first inequality follows by “deleting sufficiently many blocks M_{{i}} from a monotone span program,” the equality is implied by Lemma 2, the second to last inequality follows from Proposition 3, and the last one by the assumption on t △

For the proof of Proposition 2, let an ISP for T_{t,n} be given, and consider the ISP matrix, but with all entries reduced modulo 2. By our ISP definition and by arguing the cases A ∉ T_{t,n} using Remark 1, it follows that a binary monotone span program for T_{t,n} is obtained in this way. The argument is concluded by applying Theorem 1. ^{7} The statement about black-box secret sharing follows from Proposition 1. This can also be seen without reference to Proposition 1, by essentially the same argument as above. Namely, setting G = ℤ_{2} in Definition 4, we clearly obtain a linear secret sharing scheme over 𝔽_{2}. As mentioned earlier, linear secret sharing schemes over a field K are known to be essentially equivalent to monotone span programs over K.

4 Optimal Black-Box Threshold Secret Sharing

Theorem 2 For all t, n with 0 < t < n − 1, isp(T_{t,n}) = Θ(n · log n). Consequently, there exists a black-box secret sharing scheme for T_{t,n} with expansion factor O(log n), which is minimal.

Proof. By Proposition 1 it is sufficient to focus on the claim about the ISPs. The lower bound follows from Proposition 2. For the upper bound, consider a ring S = ℤ[X]/(f(X)), where f(X) ∈ ℤ[X] is a monic, irreducible polynomial. Write m = deg(f), the degree of S over ℤ.

On account of Lemma 3, it is sufficient to exhibit a ring S together with a monotone span program M over S for T_{t,n} such that the degree of S over ℤ is O(log n) and size(M) = O(n).

The proof is organized as follows. We first identify a certain technical property of a ring S that facilitates the construction of a monotone span program over S for T_{t,n}, with size O(n). We finalize the proof by constructing a ring S that enjoys this technical property, and that has degree O(log n) over ℤ.

For x_{1}, …, x_{n} ∈ S, define

Δ(x_{1}, …, x_{n}) = ∏_{i=1}^{n} x_{i} · ∏_{1≤j<i≤n}(x_{i} − x_{j}).

7See [Kin00, Kin01] for lower bounds on the randomness required in black-box secret sharing schemes.

Assume, for the moment, that there exist α_{1}, …, α_{n} ∈ S and r_{0}, r_{1} ∈ S such that

r_{0} · Δ(1, …, n)^{2} + r_{1} · Δ(α_{1}, …, α_{n})^{2} = 1.

This assumption implies the existence of a monotone span program over S for T_{t,n} with size 2n, as we now show. Write Δ_{0} = Δ(1, …, n) ∈ S and Δ_{1} = Δ(α_{1}, …, α_{n}) ∈ S. Let N_{0} ∈ S^{n,t+1} (resp. N_{1} ∈ S^{n,t+1}) be the matrix whose i-th row is (Δ_{0}, i, i^{2}, …, i^{t}) (resp. (Δ_{1}, α_{i}, α_{i}^{2}, …, α_{i}^{t})), i = 1 … n. In both cases, the ith row is labelled by i. When studied as possible monotone span programs over S for T_{t,n}, N_{0} (resp. N_{1}) satisfies Definition 6 for the sets A ∉ T_{t,n}. On the other hand, in both cases, the rows owned by a set A ∈ T_{t,n} do not necessarily span the target vector (1, 0, …, 0) ∈ S^{t+1}. However, these rows do span ^{8} the vector (Δ_{0}^{2}, 0, …, 0) ∈ S^{t+1} (resp. (Δ_{1}^{2}, 0, …, 0) ∈ S^{t+1}). Both properties stated can be verified immediately, for instance using the well-known expression for a Vandermonde determinant in combination with Cramér’s rule (see e.g. [Lang]); passing to the fraction field K of S (note that S has no zero-divisors), this rule implies that a c × c linear system of equations Nx = y over the ring S, has a solution at least in case where y ∈ det(N) · S^{c}. Another way is by using Lagrange Interpolation over K, and clearing denominators.

Define a new monotone span program matrix M ∈ S^{2n,2t+1} consisting of all pairs of rows

(Δ_{0}, i, i^{2}, …, i^{t}, 0, …, 0), and (Δ_{1}, 0, …, 0, α_{i}, α_{i}^{2}, …, α_{i}^{t}),

for i = 1 … n. The shown padding consists of t zeroes in both cases, and each of the rows in a pair is labelled by i. Define ε = (1, 0, …, 0)^{T} ∈ S^{2t+1}. The sets A ∉ T_{t,n} clearly satisfy Definition 6, and this time the rows owned by sets A ∈ T_{t,n} span the target vector: they span in particular all vectors of the form (r · Δ_{0}^{2} + s · Δ_{1}^{2}, 0, …, 0), with r, s ∈ S. By setting r = r_{0} and s = r_{1}, these include the target vector ε.

To conclude, we exhibit a ring S with degree O(log n) over the integers and α_{1}, …, α_{n}, r_{0}, r_{1} ∈ S with r_{0} · Δ_{0}^{2} + r_{1} · Δ_{1}^{2} = 1, where Δ_{0} = Δ(1, …, n) and Δ_{1} = Δ(α_{1}, …, α_{n}).

These conditions are reformulated as follows. Let Π_{n} denote the set of integer primes p with 2 ≤ p ≤ n and define Q_{n} = ∏_{p∈Π_{n}} p ∈ ℤ. Then we are looking for a ring S with degree O(log n) over the integers and α_{1}, …, α_{n} ∈ S such that

\overline{Δ}_{1} ∈ (S/(Q_{n}))^{∗},

8A similar property was first noticed and exploited in [FGKY97a, FGKY97b] and later in [Sho00].

i.e., the residue-class of Δ_{1} in the ring S/(Q_{n}) is a unit.

Indeed, if \overline{Δ}_{1} ∈ (S/(Q_{n}))^{∗}, then \overline{Δ}_{1} ∈ (S/(Q_{n}^{k}))^{∗} as well, for any positive integer k. To verify this by induction, suppose that Δ_{1} · v = 1 + w · Q_{n}^{i} for some v, w ∈ S and i ≥ 1: then Δ_{1} · (v − vw · Q_{n}^{i}) = 1 − w^{2} · Q_{n}^{2i} and 2i ≥ i + 1. As a consequence, \overline{Δ}_{1} ∈ (S/(Δ_{0}^{2}))^{∗}. Namely, as an integer, Δ_{0}^{2} factors completely over the primes p ∈ Π_{n}. Then choose k_{∗} large enough such that Δ_{0}^{2} divides Q_{n}^{k_{∗}}, and apply the previous observation. It follows that \overline{Δ}_{1}^{2} ∈ (S/(Δ_{0}^{2}))^{∗} as well, or equivalently, there exist r_{0}, r_{1} ∈ S such that r_{0} · Δ_{0}^{2} + r_{1} · Δ_{1}^{2} = 1.

Set m = ⌊log n⌋ + 1. Let f̂(X) ∈ ℤ[X] be any monic, irreducible polynomial of degree m such that for all p ∈ Π_{n}, f̂_{p}(X) (the polynomial f̂(X) with its coefficients reduced modulo p) is irreducible in 𝔽_{p}[X].

One way of constructing such a polynomial is as follows. For all p ∈ Π_{n}, select a monic, irreducible polynomial f̂_{p}(X) ∈ 𝔽_{p}[X] of degree m. By the theory of finite fields, this is always possible. Applying the Chinese Remainder Theorem to each of the coefficients separately, select an arbitrary lift to a monic polynomial f̂(X) ∈ ℤ[X] of degree m such that f̂(X) ≡ f̂_{p}(X) mod p. Note that the monic polynomial f̂(X) is irreducible in ℤ[X]: if not, reduction modulo p with p ∈ Π_{n}, gives a non-trivial factorization of f̂_{p}(X) in 𝔽_{p}[X].

Set S = ℤ[X]/(f̂(X)). By definition of f̂(X), it follows that S/(p) is a finite field, for all p ∈ Π_{n}. Indeed, for all p ∈ Π_{n},

S/(p) ≃ ℤ[X]/(p, f̂(X)) ≃ 𝔽_{p}[X]/(f̂_{p}(X)) ≃ 𝔽_{p^{m}}.

Note that all ideals (p) of S with p ∈ Π_{n} are distinct and maximal. It follows, using the Chinese Remainder Theorem for general rings, that

S/(Q_{n}) ≃ ∏_{p∈Π_{n}} 𝔽_{p^{m}}.

For all p ∈ Π_{n} we have |𝔽_{p^{m}}^{∗}| = p^{m} − 1 ≥ 2^{m} − 1 ≥ n. Therefore, for each p ∈ Π_{n}, distinct non-zero

β_{1}^{(p)}, …, β_{n}^{(p)} ∈ 𝔽_{p^{m}}

can be selected. Finally, select arbitrary α_{1}, …, α_{n} ∈ S such that, for i = 1 … n,

S/(Q_{n}) ∋ \overline{α}_{i} ⟷ (β_{i}^{(p)})_{p∈Π_{n}} ∈ ∏_{p∈Π_{n}} 𝔽_{p^{m}},

where the correspondence is via the (implicit) isomorphism. By construction, for all i, j with 1 ≤ i, j ≤ n and i ≠ j, it holds that \overline{α}_{i} ∈ (S/(Q_{n}))^{∗} and \overline{α}_{i} − \overline{α}_{j} ∈ (S/(Q_{n}))^{∗}. Hence, \overline{Δ}_{1} ∈ (S/(Q_{n}))^{∗}, as desired. △

Corollary 1 For all t, n with 1 ≤ t < n − 1, there exists an ISP of size n · (⌊log n⌋ + 2) for T_{t,n}.

Proof. Let α_{1}, …, α_{n}, r_{0}, r_{1} ∈ S be as constructed at the end of the proof of Theorem 2, and consider the matrices N_{0} and N_{1} defined earlier in the proof. Instead of applying Lemma 3 to the matrix M constructed from them, apply it directly to N_{1}. This leads to an ISP matrix N̂_{1} with n · (⌊log n⌋ + 1) rows and 1 + t(⌊log n⌋ + 1) columns (take into account the final remark of the proof of Lemma 3). Clearly, the sets A ∉ T_{t,n} satisfy Definition 6. For the sets A ∈ T_{t,n}, the rows owned by A span δ_{1} · ε̂, where δ_{1} ∈ ℤ is the left-most coordinate of r_{1}·Δ_{1}^{2}; before the “pruning” indicated at the end of the proof of Lemma 3, these rows spanned all possible S-multiples of Δ_{1}^{2} ·ε ∈ S^{t+1} but written in integer coordinates, and after that, all except the left-most among the m left-most coordinates have been removed.

As for the ISP matrix N_{0}, note that it has the properties stated in the proof also when studied over ℤ rather than S. Hence, the sets A ∉ T_{t,n} also satisfy Definition 6 over ℤ. For the sets A ∈ T_{t,n}, the rows owned by them clearly span (δ_{0}, 0, …, 0) ∈ ℤ^{t+1}, where δ_{0} ∈ ℤ is the left-most coordinate of r_{0} · Δ_{0}^{2}; Δ_{0} is an integer, so δ_{0} is simply the left-most coordinate of r_{0}, multiplied by Δ_{0}^{2}. Since δ_{0} + δ_{1} = 1, this leads directly to an ISP for T_{t,n}, where the ISP matrix has n·(⌊log n⌋+2) rows and t(⌊log n⌋+2)+1 columns.

△

5 Implementation and Concluding Remarks

We stress that in this paper we are primarily interested in the asymptotically optimal result from Theorem 2. Several choices in its proof have been made to simplify the mathematical exposition, while suppressing computational aspects.

There are a number of possible practical implementations of black-box secret sharing based on our result. We do not optimize its performance here, but merely indicate below that straightforward implementations run in time polynomial in n.

Note that the scheme consumes O(n log n) random coins (group elements) and that the expansion factor is O(log n) in any case, i.e., each player receives O(log n) groups elements as his share in a secret group element. For an implementation, it is important to limit the necessary computational resources for dealer and players.

One implementation is based on the well-known fact that for any finite Abelian group G, G^{m} can be viewed as a module over the ring S (see also [DF94]). The multiplication of an element of S by an element of G^{m} can be performed having only black-box access to the group operation of G. This way, the monotone span program over S acts directly on vectors of elements of G^{m}. This leads in a straightforward fashion to an attractive implementation of black-box secret sharing where the actual ISP it is based upon can be left implicit. See for instance [DF94] for the computational details of this general procedure, taking into account the remarks below.

By the constructive method from the proof of Theorem 2, we may assume without loss of generality that the coefficients of the polynomial f(X) have bit length smaller than log Q_{n} ≤ log(n!) = O(n log n) bits. Recall that its degree m is ⌊log n⌋ + 1. For given threshold parameters t, n, it can be fixed once and for all. One simple possible choice for the α_{i}’s is to identify them with distinct, non-zero integer polynomials of degree at most ⌊log n⌋, such that each of the coefficients is either 0 or 1. For instance, α_{i} can point to i by basing it on the bit representation of i. Δ_{0}^{2} is simply represented by an integer with bit length O(n^{2} · log n). The value Δ_{1}^{2} is the product of O(n^{2}) elements of S, each of which has integer coordinates −1, 0 or 1. The values r_{0} and r_{1} can be obtained by computing the inverse \overline{u} of \overline{Δ}_{1}^{2} ∈ S/(Δ_{0}^{2}), for instance by solving a linear system of equations over ℤ_{Δ_{0}^{2}}, and by computing u·Δ_{1}^{2} ∈ S. The reconstruction vectors are computed from r_{0}, r_{1} and obvious “interpolation coefficients” obtained from the α_{i}’s.

Finally, the discussion above may seem to suggest that the notion of black-box secret sharing can be generalized by replacing ℤ with an extension ring in Definitions 3 and 4. However, using a conversion as in Lemma 3 this boils down to the definition we have given. Moreover, we feel that conceptual simplicity is better served by our current definition.

6 Acknowledgments

We thank Ivan Damgaard for many helpful suggestions and discussions. Also thanks to Yvo Desmedt, Yair Frankel, Anna Gál and Yuval Ishai for comments.

References

[Bei96] A. Beimel. Secure schemes for secret sharing and key distribution. Ph.D.-thesis, Technion, Haifa, June 1996.

[BL88] J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In: Proc. CRYPTO ’88, Springer LNCS, vol. 765, pp. 274–285, 1988.

[BI92] M. Bertilsson, I. Ingemarsson. A construction of practical secret sharing schemes using linear block codes. In Proc. AUSCRYPT ’92, Springer LNCS, vol. 718, pp. 67-79, 1993.

[BBDW96] S. Blackburn, M. Burmester, Y. Desmedt, and P. Wild. Efficient multiplicative sharing scheme. In: Proc. EUROCRYPT ’96, Springer LNCS, vol. 1070, pp. 107–118, 1996.

[Bla79] G. R. Blakley. Safeguarding cryptographic keys. In: Proc. National Computer Conference ’79, AFIPS Proceedings, vol. 48, pp. 313-317, 1979.

[Bri89] E. F. Brickell. Some ideal secret sharing schemes. In: J. Combin. Maths. & Combin. Comp. vol. 9, pp. 105–113, 1989.

[CT] T. Cover and J. Thomas. Elements of information theory. Wiley Series in Telecommunications, 1991.

[CDM00] R. Cramer, I. Damgaard, and U. Maurer. Efficient general secure multi-party computation from any linear secret-sharing scheme. In: Proc. EUROCRYPT ’00, Springer LNCS, vol. 1807, pp. 316–334, 2000.

[CFIK02] R. Cramer, S. Fehr, Y. Ishai, and E. Kushilevitz. Efficient multiparty computation over rings. Manuscript, February 2002.

[DF89] Y. Desmedt and Y. Frankel. Theshold cryptosystem. In: Proc. CRYPTO ’89, Springer LNCS, vol. 435, pp. 307–315, 1990.

[DF94] Y. Desmedt and Y. Frankel. Homomorphic zero-knowledge threshold schemes over any finite Abelian group. In: SIAM Journal on Discrete Mathematics, 7(4), pp. 667–679, 1994.

[DDFY94] Y. Desmedt, A. De Santis, Y. Frankel, and M. Yung. How to share a function securely. In: Proc. STOC ’94, ACM Press, pp. 22–33, 1994.

[DCB94] Y. Desmedt, G. Di Crescenzo, and M. Burmester. Multiplicative non-abelian sharing schemes and their application to threshold cryptography. In: Proc. ASIACRYPT ’94, Springer LNCS, vol. 917, pp. 21–31, 1995.

[DKKK98] Y. Desmedt, B. King, W. Kishimoto, and K. Kurosawa. A comment on the efficiency of secret sharing scheme over any finite Abelian group. In: Proc. ACISP ’98, Springer LNCS, vol. 1438, pp. 391–402, 1998.

[Dij97] M. van Dijk. Secret key sharing and secret key generation. Ph. D. Thesis, Eindhoven University of Technology, 1997.

[FGKY97a] Y. Frankel, P. Gemmell, P. MacKenzie, and M. Yung. Optimal resilience proactive public-key cryptosystems. In: Proc. FOCS ’97, IEEE Press, pp. 384–393, 1997.

[FGKY97b] Y. Frankel, P. Gemmell, P. MacKenzie, and M. Yung. Proactive RSA. In: Proc. CRYPTO ’97, Springer LNCS, vol. 1294, pp. 440–454, 1997.

[Gal95] A. Gál. Combinatorial methods in boolean function complexity. Ph.D.-thesis, University of Chicago, 1995.

[KW93] M. Karchmer and A. Wigderson. On span programs. In: Proc. Structures in Complexity Theory ’93, IEEE Computer Society Press, pp. 102–111, 1993.

[Kin00] B. King. Some results in linear secret sharing. Ph.D.-thesis, University of Wisconsin-Milwaukee, 2001.

[Kin01] B. King. Randomness required for linear threshold sharing schemes defined over any finite abelian group. In: Proc. ACISP ’01, Springer LNCS, vol. 2119, pp. 376–391, 2001.

[Lang] S. Lang. Algebra. Addison-Wesley Publishing Co., 2nd edition, 1984.

[Sha79] A. Shamir. How to share a secret. In: Communications of the ACM, (22) pp. 612–613, 1979.

[Sho00] V. Shoup. Practical threshold signatures. In: Proc. EURO-CRYPT ’00, Springer LNCS, vol. 1807, pp. 207–220, 2000.

Recent BRICS Report Series Publications

RS-02-8 Ronald Cramer and Serge Fehr. Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups. February 2002. 19 pp.

RS-02-7 Anna Ingólfsdóttir, Anders Lyhne Christensen, Jens Alsted Hansen, Jacob Johnsen, John Knudsen, and Jacob Illum Rasmussen. A Formalization of Linkage Analysis. February 2002. vi+109 pp.

RS-02-6 Luca Aceto, Zoltán Ésik, and Anna Ingólfsdóttir. Equational Axioms for Probabilistic Bisimilarity (Preliminary Report). February 2002. 22 pp.

RS-02-5 Federico Crazzolara and Glynn Winskel. Composing Strand Spaces. February 2002. 30 pp.

RS-02-4 Olivier Danvy and Lasse R. Nielsen. Syntactic Theories in Practice. January 2002. 34 pp. This revised report supersedes the earlier BRICS report RS-01-31.

RS-02-3 Olivier Danvy and Lasse R. Nielsen. On One-Pass CPS Transformations. January 2002. 18 pp.

RS-02-2 Lasse R. Nielsen. A Simple Correctness Proof of the Direct-Style Transformation. January 2002.

RS-02-1 Claus Brabrand, Anders Møller, and Michael I. Schwartzbach. The <bigwig> Project. January 2002. 36 pp. This revised report supersedes the earlier BRICS report RS-00-42.

RS-01-55 Daniel Damian and Olivier Danvy. A Simple CPS Transformation of Control-Flow Information. December 2001. 18 pp.

RS-01-54 Daniel Damian and Olivier Danvy. Syntactic Accidents in Program Analysis: On the Impact of the CPS Transformation. December 2001. 41 pp. To appear in the Journal of Functional Programming. This report supersedes the earlier BRICS report RS-00-15.

RS-01-53 Zoltán Ésik and Masami Ito. Temporal Logic with Cyclic Counting and the Degree of Aperiodicity of Finite Automata. December 2001. 31 pp.

RS-01-52 Jens Groth. Extracting Witnesses from Proofs of Knowledge in the Random Oracle Model. December 2001. 23 pp.