Authors Andrej Bogdanov, Siyao Guo, Ilan Komargodski,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18
www.theoryofcomputing.org
Threshold Secret Sharing
Requires a Linear-Size Alphabet
Andrej Bogdanov∗ Siyao Guo† Ilan Komargodski‡
Received November 26, 2016; Revised May 3, 2019; Published September 7, 2020
Abstract. We prove that for every n and 1 < t < n any t-out-of-n threshold secret sharing
scheme for one-bit secrets requires share size log(t + 1). Our bound is tight when t =
n − 1 and n is a prime power. In 1990 Kilian and Nisan proved the incomparable bound
log(n − t + 2). Taken together, the two bounds imply that the share size of Shamir’s secret
sharing scheme (Comm. ACM 1979) is optimal up to an additive constant even for one-bit
secrets for the whole range of parameters 1 < t < n.
More generally, we show that for all 1 < s < r < n, any ramp secret sharing scheme with
secrecy threshold s and reconstruction threshold r requires share size log((r + 1)/(r − s)).
As part of our analysis we formulate a simple game-theoretic relaxation of secret sharing
for arbitrary access structures. We prove the optimality of our analysis for threshold secret
sharing with respect to this method and point out a general limitation.
ACM Classification: F.1.3
AMS Classification: 68Q17, 94A60
Key words and phrases: secret sharing, threshold, lower bound
A conference version of this paper appeared in the Proceedings of the The 14th Theory of Cryptography Conference (TCC),
2016-B.
∗ Supported by RGC GRF grants CUHK410113 and CUHK14208215.
† Part of the work done in the Chinese University of Hong Kong supported by RGC GRF grants CUHK410112 and
CUHK410113.
‡ Supported by an AFOSR grant FA9550-15-1-0262. Part of this work done while visiting CUHK, supported by RGC GRF
grant CUHK410113, and while being a Ph.D. student at the Weizmann Institute of Science, supported in part by a Levzion
fellowship, by a grant from the I-CORE Program of the Planning and Budgeting Committee, the Israel Science Foundation, BSF
and the Israeli Ministry of Science and Technology.
© 2020 Andrej Bogdanov, Siyao Guo, and Ilan Komargodski
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2020.v016a002
A NDREJ B OGDANOV, S IYAO G UO , AND I LAN KOMARGODSKI
1 Introduction
In 1979, Shamir [36] and Blakley [11] presented a method for sharing a piece of secret information
among n parties such that any 1 < t < n parties can recover the secret while any t − 1 parties learn nothing
about the secret. These methods are called (t, n)-threshold secret sharing schemes. This sharp threshold
between secrecy and reconstruction is fundamental in applications where a group of mutually suspicious
individuals with conflicting interests must cooperate. Indeed, threshold secret sharing schemes have found
many applications in cryptography and distributed computing; see the extensive survey of Beimel [3] and
the recent book of Cramer et al. [17].
Threshold secret sharing was generalized by Ito et al. [26] to allow more general structures of subsets
to learn the secret, while keeping the secret perfectly hidden from all other subsets. The collection of
qualified subsets is called an access structure.
A significant goal in secret sharing is to minimize the share size, namely, the amount of information
distributed to the parties. Despite the long history of the subject, there are significant gaps between lower
and upper bounds both for general access structures and for the special case of threshold structures.
Threshold access structures. For (t, n)-threshold access structures (denoted by THRtn ) and a 1-bit
secret, Shamir [36] gave a very elegant and efficient scheme: the dealer picks a random polynomial
of degree t − 1 conditioned on setting the free coefficient to be the secret, and gives the i-th party the
evaluation of the polynomial at the point i. The computation is done over a field F of size q > n.
The correctness follows because one can recover the unique polynomial from any t points (and thus
recover the secret). Security follows by a counting argument showing that given less than t points, all
possibilities for the free coefficient are equally likely. The share of each party is an element in the field F
that can be represented using log q ≈ log n bits. (All our logarithms are in base 2.) The efficiency of this
scheme makes it very attractive for applications.
A natural question to ask is whether log n-bit shares are necessary for sharing a 1-bit secret for
threshold access structures. Kilian and Nisan [28]1 showed that log n bits are necessary when t is not too
large. Specifically, they proved a log(n − t + 2) lower bound on share size for (t, n)-threshold schemes.
For large values of t, especially those close to n, their bound does not rule out schemes with shares much
shorter than log n bits. Their bound leaves open the possibility that, in particular, (n − 1, n)-threshold
schemes with two-bit shares exist.
Ramp schemes are a generalization of threshold schemes that allow for a gap between the secrecy
and reconstruction parameters. In an (s, r, n)-ramp scheme, we require that any subset of at least r parties
can recover the secret, while any subset of size at most s cannot learn anything about the secret.2 When
r = s + 1, an (s, r, n)-ramp scheme is exactly an (r, n)-threshold scheme. Ramp schemes, defined by
Blakley and Meadows [12], are useful for various applications (see, e. g., [24, 37, 16, 32]). If r − s is
large, they can sometimes be realized with shorter shares than standard threshold schemes (especially in
the case of a long secret).
1 Their result is unpublished and independently obtained (and generalized in various ways) by [15]. The original argument of
Kilian an Nisan appears in [15, Appendix A] and was referenced earlier in [4, 2, 5].
2 Another common definition (see [22, Definition 2.7] and [23, Example 2.11] for examples) for a ramp scheme is where the
information about the secret increases with the size of the set. We focus only on the definition in which sets of size below a
certain threshold have no information about the secret, while sets of size larger than some threshold can recover it.
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 2
T HRESHOLD S ECRET S HARING R EQUIRES A L INEAR -S IZE A LPHABET
Generalizing the lower bound of Kilian and Nisan, Cascudo et al. [15] showed that log((n − s +
1)/(r − s))-bit shares are necessary to realize an (s, r, n)-ramp scheme. When s = n − O(1), however,
their share size bound is a constant independent of n. Paterson and Stinson [34] showed that this bound is
tight for specific small values of s.
General access structures. For most access structures, the best known secret sharing schemes require
shares of size 2O(n) for sharing a 1-bit secret. Specifically, viewing the access structure as a Boolean
indicator function for qualified subsets, the schemes of [26, 10, 27] result with shares of size proportional
to the DNF/CNF size, monotone formula size, or monotone span program size of the function, respectively.
Thus, even for many access structures that can be described by a small monotone uniform circuit, the best
schemes have super-polynomial size shares.3 On the other hand, the best known lower bound on share
size for sharing an `-bit secret is Ω(` · n/ log n) bits, by Csirmaz [20] (improving on [14]).4
Bridging the exponential gap between the upper and the lower bounds is the major open problem
in the study of secret sharing schemes. While it is widely believed that the lower bound should be
exponential (see, e. g., [2, 3]), no major progress has been made in the last two decades. Moreover, even a
non-explicit linear lower bound is not known, that is, whether there exists an access structure that requires
linear size shares.
1.1 Our results
Share size lower bound. We close the gap in share size for threshold secret sharing up to a small
additive constant. We assume for simplicity that all parties are given equally long shares.
Theorem 1.1. For every n ∈ N and 1 < t < n, any (t, n)-threshold secret sharing scheme for a 1-bit
secret requires shares of at least log(t + 1) bits.
The assumption 1 < t < n is necessary, as (1, n)-threshold and (n, n)-threshold secret sharing schemes
with share size 1 do exist.
Our bound is tight when t = n − 1 and n is the power of a prime; see Section 5. By combining
Theorem 1.1 with the lower bound of Kilian and Nisan, we determine the share size of threshold schemes
up to a small additive constant. That is, we get that any such scheme requires shares of size
n+3
max{log(n − t + 2), log(t + 1)} ≥ log . (1.1)
2
Theorem 1.1 is a special case of the following theorem, which applies more generally to ramp
schemes.
Theorem 1.2. For every n ∈ N and 1 ≤ s < r < n, any (s, r, n)-ramp secret sharing scheme for a 1-bit
secret requires shares of at least log((r + 1)/(r − s)) bits.
3 One example is the directed connectivity access structure: the parties correspond to edge slots in the complete directed
graph and the qualified subsets are those edges that connect two distinguished nodes s and t.
4 In a follow-up work, Csirmaz [19] proved a lower bound of Ω(` · n2 / log n) for the total share size of all parties.
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 3
A NDREJ B OGDANOV, S IYAO G UO , AND I LAN KOMARGODSKI
By combining Theorem 1.2 with the lower bound of [15], we get that any (s, r, n)-ramp secret sharing
scheme must have share size at least
n−s+1 r+1 n+r−s+2
max log , log ≥ log . (1.2)
r−s r−s 2 · (r − s)
Proof technique and limitations. We prove our lower bounds by analyzing a new game-theoretic
relaxation of secret sharing. Here, we focus on threshold schemes, although our argument also applies to
ramp schemes.
Given an access structure A and a real-valued parameter θ > 0 we consider the following zero-sum
game G(A, θ ): Alice and Bob pick sets A and B in the access structure A, respectively, and the payoff is
(−θ )|A\B| , where A \ B denotes set difference. We say Alice wins if she has a strategy with non-negative
expected payoff, and Bob wins otherwise.
We show (in Lemma 3.1) that if Bob wins in the game G(A, 1/(q − 1)), then no secret sharing scheme
with share size log q exists. We prove Theorem 1.2 by constructing such a strategy for Bob.
On the negative side, we show that our analysis is optimal for threshold access structures, so the lower
bound in Theorem 1.1 is tight with respect to this method:
Theorem 1.3. For all 1 < t < n and 0 < θ ≤ 1/t, Alice wins in the game G(THRtn , θ ).
any total access structure A, this method cannot prove a lower bound exceeding
We also show that, for
log|min A| ≤ log bn/2c
n
= n − Ω(log n), where min A = {A ∈ A : ∀B ∈ A, B 6⊂ A} is the set of min-terms
in A.
Theorem 1.4. For every access structure A and every 0 < θ ≤ 1/(|min A| − 1) Alice wins in the game
G(A, θ ).
1.2 Related work
Known frameworks for proving lower bounds. The method of Csirmaz [20] is a general framework
for proving lower bounds on share size in various access structures. Csirmaz’s framework is a linear
programming relaxation whose variables are the entropies of the joint distributions of the shares (one for
each subset of the parties) and whose constraints are entropy inequalities. A solution to the dual linear
program yields an Ω(n/ log n) lower bound on the information ratio, namely the length of the largest
share divided by the length of the secret.
Csirmaz’s framework does not give any non-trivial lower bounds on share size for a 1-bit secret
over threshold access structures. The reason is that for sufficiently long secrets, the information ratio of
threshold schemes is 1 in Shamir’s construction (see Claim 5.1). Kilian and Nisan’s [28] proof is the only
known argument for threshold schemes. It does not appear to be useful for any other access structure,
including the (t, n)-threshold access structures with t being close to n.
Csirmaz [20] showed that his framework cannot be used to prove a super-linear lower bound on share
size for any access structure when the constraints are the Shannon inequalities from information theory.
This claim was strengthened by Beimel and Orlov [8], who showed that certain additional “non-Shannon
type” information inequalities do not help bypass the linear share size barrier (see [33] for a follow-up).
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 4
T HRESHOLD S ECRET S HARING R EQUIRES A L INEAR -S IZE A LPHABET
Linear schemes. A secret sharing scheme is linear if the reconstruction procedure is a linear function
of the shares (over a finite field). Many known schemes are linear (see [7, 9, 29, 38, 13, 31, 30] for
exceptions) and super-polynomial lower bounds for linear schemes were given in [1, 6, 25, 35] via their
equivalence to monotone span programs [27].
For linear (2, n)-threshold secret sharing schemes for a 1-bit secret, a log n lower bound on share size
was proven by Karchmer and Wigderson [27]. This was generalized by Cramer et al. [18] to a lower
bound as in Equation (1.1).5 For linear (s, r, n)-ramp secret sharing schemes, Cascudo et al. [15] obtained
a lower bound as in Equation (1.2). We emphasize that our lower bounds match the lower bounds of [15]
but are not restricted to linear (ramp) secret sharing schemes.
2 Access structures and secret sharing
Let P , {1, . . . , n} be a set of n parties. A collection of subsets A ⊆ 2P is upward-closed if for every
B ∈ A and C ⊇ B it holds that C ∈ A. The collection is downward-closed if for every B ∈ A and C ⊆ B it
holds that C ∈ A.
Definition 2.1. An access structure is a pair A = (S, R) where
(i) S and R are non-empty disjoint subsets of 2P ,
(ii) R is upward-closed and S is downward-closed.
Subsets in R are called qualified and subsets in S are called unqualified.
Remark 2.2. The condition that R 6= 0/ is equivalent to saying that P ∈ R, i. e., all parties together are
qualified (to unlock the secret). The condition S 6= 0/ is equivalent to saying that 0/ ∈ S, i. e., the secret is
not public (the empty set is not qualified).
The access structure is total if R and S form a partition of 2P . If A = (S, R) is total we write R ∈ A
for R ∈ R and S 6∈ A for S ∈ S.
In this paper we are primarily concerned with the following two types of access structures:
• The threshold access structure THRtn is a total access structure over n parties in which any t parties
can reconstruct and secrecy is guaranteed against any subset of t − 1 parties:
S = {S : |S| ≤ t − 1} , R = {R : |R| ≥ t}.
• More generally, in the ramp access structure RAMPns,r , any r parties can reconstruct and secrecy is
guaranteed against any s parties:
S = {S : |S| ≤ s} , R = {R : |R| ≥ r}.
5 Their proof is based on the duality of linear secret sharing schemes, by which the optimal share sizes of linear (s, r, n)-ramp
schemes and linear (n − r, n − s, n)-ramp schemes are equal.
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 5
A NDREJ B OGDANOV, S IYAO G UO , AND I LAN KOMARGODSKI
A secret sharing scheme involves a dealer who has a secret, a set of n parties, and an access structure
A = (S, R). A secret sharing scheme for A = (S, R) is a method by which the dealer distributes shares
to the parties such that any subset in R can reconstruct the secret from its shares, while any subset in S
cannot infer any information on the secret. We restrict our definition to 1-bit secrets.
Definition 2.3 (Secret sharing). A secret sharing scheme of a 1-bit secret for an access structure A = (S, R)
over n parties over share alphabet Σ is a pair (p0 , p1 ) of probability distributions over Σn with the following
properties:
Reconstruction: For every R ∈ R the marginal distributions6 of p0 and p1 on the set R are disjoint.
Secrecy: For every S ∈ S the marginal distributions of p0 and p1 on the set S are identical.
An implementation of a secret sharing scheme consists of a sharing algorithm that samples the shares
from the probability distribution p0 or p1 depending on the value of the secret and of a reconstruction
algorithm that recovers the secret from the joint values of the shares of any qualified subsets of parties. The
disjointness requirement ensures that recovery by qualified subsets of parties is possible with probability
1. The secrecy requirement ensures that unqualified subsets of parties can extract no information about
the secret. Thus, our definition is equivalent to the ones given, for example, in [2, Definition 3.6] and
in [3, Definitions 2 and 3].
An alternative formulation of secret sharing. Here is an equivalent formulation of secret sharing.
For x ∈ Znq , we use [x] to denote the set of positions with non-zero entries, i. e., [x] = {i : xi 6= 0}, and
[x]{ for the complement of this set, i. e., [x]{ = {i : xi = 0}. In this notation, [x − y] is the set of positions
where x and y differ and [x − y]{ is the set of positions where they agree.
A function φS : Znq → C is an S-junta if the value φS (x1 , . . . , xn ) is determined by the inputs xi : i ∈ S.
Lemma 2.4. A secret sharing scheme for a 1-bit secret for an access structure A = (S, R) over share
alphabet Zq exists if and only if there exists a function f : Znq → R that is not identically zero satisfying
the following conditions.
Reconstruction: For all x, y ∈ Znq such that [x − y]{ ∈ R, we have f (x) · f (y) ≥ 0.
Secrecy: For every S ∈ S and every S-junta φS : Znq → C, we have E[ f (x)φS (x)] = 0, where the expecta-
tion is over the uniform probability distribution of x ∈ Znq .
Proof. For a secret sharing scheme (p0 , p1 ) we set f (x) = p0 (x) − p1 (x). The functions p0 and p1 have
disjoint support (otherwise even reconstruction by all parties is impossible) so f cannot be identically zero.
The reconstruction implies that if [x−y]{ ∈ R, then at least one of p0 and p1 must assign zero probability to
both x and y, so f (x)· f (y) equals either p0 (x)· p0 (y) or (−p1 (x))·(−p1 (y)). In either case f (x)· f (y) ≥ 0.
For secrecy, since p0 and p1 have the same marginals on S ∈ S, E[p0 (x)φS (x)] = E[p1 (x)φS (x)] so
E[ f (x)φS (x)] = 0.
In the other direction, let p0 (x) = C · max{ f (x), 0} and let p1 (x) = C · max{− f (x), 0}, where 1/C =
(1/2) ∑x | f (x)|. We show reconstruction by contrapositive: If p0 and p1 did not have disjoint support
6 The marginal distribution of p over S is the function p : ZS → R given by p (z) =
S q S ∑x : xS =z p(x).
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 6
T HRESHOLD S ECRET S HARING R EQUIRES A L INEAR -S IZE A LPHABET
on some set R ∈ R, there would exist x, y ∈ Znq such that p0 (x) > 0, p1 (y) > 0, and R ⊆ [x − y]{ ∈ R
(by the monotonicity of R), implying f (x) > 0, f (y) < 0, and therefore f (x) · f (y) < 0. For secrecy, by
construction we have f = (p0 − p1 )/C, so E[p0 (x)φS (x)] = E[p1 (x)φS (x)] for every test function φS that
only depends on the positions in S ∈ S. Since no φS can distinguish between p0 and p1 on S, the statistical
distance between the marginal distribution of p0 and p1 on S is zero, so the two are identical.
By Lemma 2.4, ruling out the existence of a secret sharing scheme is equivalent to refuting the
solvability of a real-valued constraint satisfaction problem with quadratic constraints. The class of
refutations that we investigate are sum-of-squares inequalities of the form ∑i (∑x ρi (x) f (x))2 < 0, i. e.,
dual solutions to the canonical semidefinite relaxation of this problem.
Owing to the symmetries inherent in secret sharing, the sum-of-squares certificate of interest is a
positive linear combination of the squared magnitudes of the Fourier coefficients of f . Our lower bound
can be expressed as a dual certificate for a linear program with variables | fˆ(a)|2 , a ∈ Znq . This linear
program has the form of a zero-sum game, which we describe next.
3 A zero-sum game and proof of Theorem 1.2
Given an access structure A = (S, R) and a real parameter θ > 0 we define the following zero-sum game
G(A, θ ) between Alice and Bob. The actions are a set A 6∈ S for Alice and a set B ∈ R for Bob. Each
party chooses its action independently of the other. The payoff of the game is (−θ )|A\B| . We say that
Alice wins if she has a strategy with non-negative expected payoff (over her randomness) against all
strategies of Bob. Analogously, we say that Bob wins if he has a strategy with negative expected payoff.
By von Neumann’s minimax theorem the game has a unique winner.
Lemma 3.1. If there exists a secret sharing scheme for A with alphabet size q ∈ N, then Alice wins in
the game G(A, 1/(q − 1)).
Our proof of Lemma 3.1 uses Fourier analysis, which we briefly recall here. The characters of the
group Znq are the complex-valued functions χa : Znq → C, where a ranges over Znq , defined as χa (x) = ω ha,xi ,
ω = e2πi/q . The characters are an orthonormal basis with respect to the inner product h f , gi = Ex [ f (x) ·
g(x)] with x chosen uniformly from Znq . The characters inherit the group structure: χa · χb = χa+b and
χa−1 = χa = χ−a . Every function f : Znq → C can then be uniquely written as a linear combination
f = ∑ fˆ(a) · χa
a∈Znq
with the Fourier coefficients fˆ(a) given by fˆ(a) = h f , χa i = Ex [ f (x) · χa (x)].
Proof of Lemma 3.1. We show that Alice has a winning strategy. That is, we show that Alice has a
strategy such that for every possible action of Bob, the expected payoff of the game is non-negative.
We identify the alphabet with the elements of the group Zq . Let f : Znq → R be the function f (x) =
p0 (x) − p1 (x). Alice plays set A with probability proportional to
∑ | fˆ(a)|2 .
a : [a]=A
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 7
A NDREJ B OGDANOV, S IYAO G UO , AND I LAN KOMARGODSKI
By the secrecy part of Lemma 2.4, E[ f (x) · χa (x)] = 0 whenever [a] ∈ S, so Alice’s strategy is indeed
supported on sets outside S.
Now let B be an arbitrary set in R. By the reconstruction part of Lemma 2.4 and the fact that f is
real-valued, for every x ∈ Zqn and every z ∈ Zqn such that [z]{ = B, we have that
f (x) · f (x − z) = f (x) · f (x − z) ≥ 0. (3.1)
Let x be uniform in Znq and z be uniform in Znq conditioned on [z]{ = B. Averaging over this distribution,
we have
Ex,z [ f (x) · f (x − z)] = ∑ fˆ(a) · fˆ(b) · Ex,z [χa (x) · χb (x − z)]
a,b∈Znq
= ∑| fˆ(a)|2 · Ez [χa (z)]
a
= ∑| fˆ(a)|2 · ∏ Ez [ω ai zi ],
a i∈[a]
where the first equality follows by writing f (x) and f (x − z) using their Fourier representation and
using linearity of expectation, the second equality follows since x and z are independent and since
Ex [χa (x) · χb (x)] = 0 for a 6= b, and the last equality follows since z is chosen from a product distribution.
The expression E[ω ai zi ] evaluates to one when i is in B (since zi is fixed to zero). Otherwise, zi is
uniformly distributed over the set Zq \ {0} and
1 1 1
Ez [ω ai zi ] = ∑ ω ai zi
= ∑z ∈Z
ω ai zi
− 1 =− .
q − 1 z ∈Z \{0} q−1 i q q−1
i q
Therefore, ∏i∈[a] Ez [ω ai zi ] = (−1/(q − 1))|[a]\B| , and by Equation (3.1)
|[a]\B|
−1
∑| fˆ(a)|2 · q−1
≥ 0.
a
Grouping all elements a for which [a] = A, we get that
1 |A\B|
∑ ∑a : [a]=A | ˆ
f (a)|2
· − ≥0 for all B ∈ R.
A q−1
Therefore, Alice’s strategy has non-negative expected payoff with respect to every possible action of
Bob.
Proof of Theorem 1.2. It is sufficient to prove Theorem 1.2 in the case n = r + 1: If a secret sharing
scheme for RAMPns,r existed, then a secret sharing for RAMPr+1s,r over the same alphabet can be obtained
by discarding the remaining n − r − 1 parties and their shares.
We now give a winning strategy for Bob in the game G(RAMPr+1 s,r , θ ) for any θ > (r − s)/(s + 1). By
Lemma 3.1 it then follows that no secret sharing scheme over an alphabet of size (r + 1)/(r − s) exists.
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 8
T HRESHOLD S ECRET S HARING R EQUIRES A L INEAR -S IZE A LPHABET
Bob’s strategy is to uniformly choose a set B of size r (which is in R). Then for every set A 6∈ S, either
A ⊆ B and then |A \ B| = 0, or A 6⊆ B and then |A \ B| = 1 (since B includes all parties except one). Thus,
for every A 6∈ S, the expected payoff is
EB (−θ )|A\B| = 1 · PrB [A ⊆ B] − θ · PrB [A 6⊆ B]
r + 1 − |A| |A|
= 1· −θ ·
r+1 r+1
r−s s+1
≤ −θ · , (3.2)
r+1 r+1
where the inequality follows since |A| ≥ s + 1. If θ > (r − s)/(s + 1) this expression is less than zero,
i. e., Bob wins.
It is also possible to deduce Theorem 1.2 directly from Lemma 3.1 by showing the existence of
a winning strategy for Bob in the game G(RAMPns,r , θ ) whenever θ > (r − s)/(s + 1) (rather than for
G(RAMPr+1 s,r , θ ), as we did above). Let R be a random subset of r + 1 parties. Bob’s strategy has the
form B = B0 ∪ B1 , where B0 is a uniformly random subset of R of size r and B1 is a random subset of
R{ obtained by including each element independently with probability p = θ /(1 + θ ). The value of p
is chosen so that a random variable that equals 1 with probability p and −θ with probability 1 − p is
unbiased.
Let A, where |A| ≥ s + 1, be any action of Alice. For a fixed choice of R, if A \ R is nonempty, by our
choice of probability p the expected payoff is zero. Otherwise, A is a subset of R, and by Equation (3.2)
the expected payoff is at most −(s + 1) · θ + (r − s) < 0. Since the event A ⊆ R has positive probability,
the expected payoff is negative and Bob wins.
Extension to unequal shares. Theorem 1.1 requires that the shares given to all parties have the same
length. Its proof extends easily to yield the following generalization. For every n, every 1 < t < n, and
every (t, n)-threshold secret sharing scheme in which party i receives a log qi -bit share and q1 ≤ q2 ≤
· · · ≤ qn it must hold that
1 1
+···+ ≤ 1. (3.3)
q1 qt+1
In particular, inequality (3.3) implies that the average share size must be at least log (t + 1). Kilian and
Nisan [28] prove the same for (n − t + 1, n)-threshold access structures.
The proof of inequality (3.3) is a direct extension of the proof of Theorem 1.1. We describe the
differences and main steps. Given an access structure A = (S, R) and real positive numbers θ1 , . . . , θn , we
define the following zero-sum game G(A, θ1 , . . . , θn ) between Alice and Bob. The actions are a set A 6∈ S
for Alice and a set B ∈ R for Bob. The payoff of the game is ∏i∈A\B (−θi ). We can obtain the following
generalized version of Lemma 3.1.
Lemma 3.2. If there exists a secret sharing scheme for A with alphabet size qi ∈ N for the i-th party,
then Alice wins in the game G(A, 1/(q1 − 1), . . . , 1/(qn − 1)).
The generalized lemma can be proved via Fourier analysis over the product group Zq1 × · · · × Zqn .
We omit this proof.
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 9
A NDREJ B OGDANOV, S IYAO G UO , AND I LAN KOMARGODSKI
As in the proof of Theorem 1.1, it is sufficient to establish inequality (3.3) in the special case t = n − 1.
In this case, Bob plays set B = {1, . . . , n} \ {i} with probability proportional to 1 − 1/qi . It can be verified
that when ∑ni=1 1/qi > 1 this is a winning strategy for Bob. Specifically, for every set A 6∈ S, either
A ⊆ B and then |A \ B| = 0, or A 6⊆ B and then |A \ B| = 1 (since B includes all parties except one). Let
C = ∑ni=1 (1 − 1/qi ). Thus, for every A 6∈ S, the expected payoff is
EB ∏ −θi = PrB [A ⊆ B] · 1 − ∑ PrB [A \ B = {i}] · (−θi )
i∈A\B i∈A
1 − 1/qi 1 − 1/qi
=∑ ·1− ∑ · θi
i∈A
/
C i∈A C
1 − 1/qi 1/qi
=∑ −∑
i∈A
/
C i∈A C
|A|
= 1− .
C
By assumption |A| ≥ n − 1. So if ∑ni=1 1/qi > 1 this expression is less than zero, i. e., Bob wins.
4 Limitations of the game relaxation
In the case of threshold access structures Theorem 1.2 shows that Bob has a winning strategy in the game
G(THRtn , θ ) whenever θ > 1/t. We now prove Theorem 1.3, which states that our analysis is optimal:
There exists a winning strategy for Alice when θ ≤ 1/t.
We also prove Theorem 1.4: For every total access structure A over n parties, Alice has a winning
strategy in G(A, θ ) for every θ ≤ 1/(|A| − 1). As the proof of Theorem 1.4 is simpler, we present that
one first. We remark that Theorem 1.4 can be generalized to any access structure (S, R) by replacing A
with R in the proof.
Proof of Theorem 1.4. Alice’s strategy is uniformly random over all minterms A ∈ min A. Then, for
every B ∈ A and θ < 1, it holds that
EA [(−θ )|A\B| ] = EA [(−θ )|A\B| | A ⊆ B] · PrA [A ⊆ B]
+ EA [(−θ )|A\B| | A 6⊆ B] · PrA [A 6⊆ B]
≥ 1 · PrA [A ⊆ B] − θ · PrA [A 6⊆ B]
= (1 + θ ) · PrA [A ⊆ B] − θ
1
≥ (1 + θ ) · −θ.
|min A|
This is non-negative when θ ≤ 1/(|min A| − 1).
Proof of Theorem 1.3. Let a0 , . . . , an be the following sequence of integers:
a0 = · · · = at−1 = 0, at = 1, as = kt · as−1 + · · · + k0 · as−t−1
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 10
T HRESHOLD S ECRET S HARING R EQUIRES A L INEAR -S IZE A LPHABET
for t + 1 ≤ s ≤ n, where k j is the coefficient of x j in the formal expansion of (x + 1)t · (1/θ − x). By
expanding this expression according to the Binomial formula, we see that the numbers k0 , . . . , kt are
non-negative when θ ≤ 1/t because
t 1 j
kj = − ≥0
j θ t − j+1
for all 0 ≤ j ≤ t. Therefore as is also non-negative for all s.
Alice plays set A with probability proportional to the number a|A| . We will prove that this is a winning
strategy for Alice. When B = {1, . . . , n}, then EA [(−θ )|A\B| ] = 1 and Alice wins. Now let B ⊆ {1, . . . , n}
be any set such that t ≤ |B| < n. Let
(
1, if j ∈ B,
θj =
−θ , if j 6∈ B.
Then, EA [(−θ )|A\B| ] is proportional to
n
∑ a|A| ∏ θ j = ∑ as ws where ws = ∑ ∏ j∈A θ j .
A j∈A s=0 A : |A|=s
The number ws can be represented as the coefficient of zs in the formal expansion of g0 (z) = ∏nj=1 (1+θ j z).
Since exactly |B| of the θ j equal 1 and the other n − |B| equal −θ , it follows that
g0 (z) = (1 + z)|B| · (1 − θ z)n−|B| . (4.1)
The numbers a0 , . . . , an (as defined in the beginning of the proof) are defined by an order-t homogeneous
linear recurrence with constant coefficients whose characteristic equation is (x + 1)t · (1/θ − x) = 0. This
equation has roots −1 (with multiplicity t) and 1/θ (with multiplicity 1). Therefore,
t−1
as = C · θ −s + ∑ ci · si · (−1)s
i=0
where c0 , . . . , ct−1 and C are constants determined by the initial conditions on a0 , . . . , at . We can now
write
n n t−1 n
∑ as · ws = C · ∑ ws · θ −s + ∑ ci · ∑ ws · si · (−1)s .
s=0 s=0 i=0 s=0
As g0 is the generating function of the ws , g0 (z) = ∑ns=0 ws · zs . So, the term ∑ns=0 ws · θ −s equals
g0 (1/θ ) = 0. To finish the proof, we show that ∑ns=0 ws · si · (−1)s = 0 for all i ≤ t − 1. This implies that
Alice’s strategy has a 0 payoff, so she wins the game. Let gi (z) = z · g0i−1 (z) for 1 ≤ i ≤ t − 1 where g0i−1
is the derivative of gi−1 . On the one hand, since −1 is a root of g0 of multiplicity t, gi (−1) = 0 for all
i ≤ t − 1. On the other hand, gi (z) has the formal expansion ∑ns=0 ws · si · zs . Therefore, ∑ns=0 ws · si · (−1)s
must equal zero.
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 11
A NDREJ B OGDANOV, S IYAO G UO , AND I LAN KOMARGODSKI
5 On the tightness of Theorem 1.2
We show that Theorem 1.2 is tight when t = n − 1 and n is a prime power. This result is known (see, e. g.,
[17, Theorem 11.13]) and we give it here for completeness.
Claim 5.1. For every prime power n there exists a (n − 1)-out-of-n secret sharing scheme for blog nc-bit
secrets with dlog ne-bit shares.
Claim 5.1 follows by an optimization of Shamir’s secret sharing scheme, where we place the secret as
the coefficient of the highest-degree term (instead of as the constant term). We give the construction and
sketch the proof of correctness.
To share a secret s ∈ Fn , let p(x) = sxn−2 + r(x), where r is a random polynomial of degree n − 3 and
all algebra is over the finite field Fn . The shares are the n values p(x) as x ranges over Fn . Reconstruction
is immediate as the polynomial p can be interpolated from any n − 1 of its values.
For secrecy, we show for any s ∈ Fn and distinct x1 , . . . , xn−2 ∈ Fn , the vector (p(x1 ), . . . , p(xn−2 ))
is uniformly random in Fn−2 n . Since p(x) = sx
n−2 + r(x) it suffices to show that (r(x ), . . . , r(x
1 n−2 )) is
uniformly random. This is true because the evaluation map that takes the coefficients of r to its values
r(x1 ), . . . , r(xn−2 ) is a full-rank Vandermonde matrix.
6 Concluding remarks
Relation to the lower bound of Kilian and Nisan. By Theorem 1.3 our analysis of threshold secret
sharing is tight within the game-theoretic relaxation that we introduce here. As the lower bound of Kilian
and Nisan [28] is incomparable with ours, their analysis cannot be cast in terms of a winning strategy in
our game. The analysis of Kilian and Nisan relies on the collision probabilities Pr[XA = YA ], where X and
Y are independent samples of the distributions p0 and p1 , respectively, and XA ,YA are their projections on
A. In the Fourier basis these probabilities can be written as
Pr[XA = YA ] = ∑ p̂0 (a) · p̂1 (a).
a : [a]⊆A
Our game-theoretic formulation cannot express such quantities. It is, however, possible to unify our
analysis with that of Kilian and Nisan by a common linear program. One approach is to refine the
canonical linear programming formulation of the zero-sum game G(A, θ ), which has a variable v(A)
representing ∑[a]=A | fˆ(A)|2 for every subset A of [n]. In the refined formulation, each v(A) is split
into v00 (A) + 2v01 (A) + v11 (A), where vi j (A) represents the (real-valued) expression ∑[a]=A p̂i (a) · p̂ j (a).
These variables satisfy vii (A) ≥ 0 (non-negativity), v00 (A) = v01 (A) = v11 (A) for A ∈ S (secrecy), and
(
= 0, if B ∈ R and i j = 01,
∑ vi j (A)(−θ )|A\B| ≥ 0, otherwise. (reconstruction)
A
The last quantity represents the probability of the event {b : Xb = Yb } = B up to scaling, where X and Y
are independent samples of pi and p j , respectively.
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 12
T HRESHOLD S ECRET S HARING R EQUIRES A L INEAR -S IZE A LPHABET
This linear program captures both our proof technique and that of Kilian and Nisan and is therefore
infeasible with respect to THRtn when q < max{n − t + 2,t + 1}. Our computer experiments show that
this bound is tight for all n ≤ 7, so this particular formulation does not appear to be advantageous for
further improving the share size lower bounds on THRtn obtained in this paper.
Comparison with Csirmaz’s method. A common feature of Csirmaz’s method and ours is that the
secrecy and reconstruction axioms are formulated as linear constraints on functionals of random variables
determined by subsets of the shares. Csirmaz’s relevant functional is the Shannon entropy of the
corresponding subset. In contrast, under a suitable change of basis, our functionals capture the collision
(Rényi) entropies of shares of 0 and/or 1 restricted to the relevant subset of the parties.
Csirmaz’s method more generally gives a lower bound on the information ratio of schemes with
arbitrary secret alphabet, while our formulation only applies to binary secrets. In this setting the two
methods are incomparable. On the one hand, our main result shows that Csirmaz’s method is less powerful
than ours for threshold access structures. On the other hand, the alphabet size lower bound of 4 for the
tree access structure {01, 12, 03, 34, 05} obtained by Csirmaz and Tardos [21] cannot be matched by our
game analysis.
On general access structures. We do not know what is the best possible lower bound on share size
that our method can give among all access structures on n parties. Theorem 1.1 showsthat a lower bound
n
of log(n − 1) is attainable, while Theorem 1.4 shows that a lower bound of log bn/2c cannot be proved
by our method.
The best possible bound is the logarithm of
bn = min max q : Bob wins in G(A, 1/(q − 1)) ,
A
where the minimum is taken over all access structures A on n parties. As indirect evidence that log bn/2c
n
might be far from tight, we can prove that if the payoff function is replaced by (−θ )|A4B| , where
√ 4 is
symmetric set difference, then the quantity analogous to bn is at most cn + 1, where c = 1/ ln(1 + 2) ≈
1.135, when Bob plays tit-for-tat.
Claim 6.1. If A, B ⊆ [n] are independent and identically distributed then E[(−1/cn)|A4B| ] > 0.
Proof. We first show that Pr[|A4B| = s] ≤ ns Pr[A = B]. Let p be the probability mass function of the
sets.
Pr[|A4B| = s] = ∑ p(A)p(B) = ∑ p(A)p(A4S)
A,B : |A4B|=s A,S : |S|=s
s s
n
≤ ∑ p(A)2 · ∑ p(A4S)2 = p(A)2 ,
A,S : |S|=s A,S : |S|=s
s ∑A
where the inequality is Cauchy-Schwarz. The expectation of interest is then lower bounded by
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 13
A NDREJ B OGDANOV, S IYAO G UO , AND I LAN KOMARGODSKI
1 s
E (−1/cn)|A4B| ≥ Pr[A = B] − ∑
Pr[|A4B| = s]
s odd cn
1 s n
≥ Pr[A = B] − ∑ Pr[A = B]
s odd cn s
c−1 c−3 c−5
> Pr[A = B] · 1 − − − −···
1! 3! 5!
e1/c − e−1/c
= Pr[A = B] · 1 − ,
2
which is nonnegative by our choice of c.
Acknowledgments.
We thank Moni Naor for telling us about the work of Kilian and Nisan. We thank the anonymous
reviewers for their useful advice.
References
[1] L ÁSZLÓ BABAI , A NNA G ÁL , AND AVI W IGDERSON: Superpolynomial lower bounds for mono-
tone span programs. Combinatorica, 19(3):301–319, 1999. [doi:10.1007/s004930050058] 5
[2] A MOS B EIMEL: Secure Schemes for Secret Sharing and Key Distribution. Ph. D. thesis, Technion –
Israel Institute of Technology, 1996. Accessible in PS on the author’s home page and in PDF at
DPHU.org. 2, 3, 6, 16
[3] A MOS B EIMEL: Secret-sharing schemes: A survey. In Coding and Cryptology – 3rd Internat.
Workshop, IWCC’11, volume 6639, pp. 11–46. Springer, 2011. [doi:10.1007/978-3-642-20901-7_2]
2, 3, 6
[4] A MOS B EIMEL AND B ENNY C HOR: Universally ideal secret-sharing schemes. IEEE Trans. Inform.
Theory, 40(3):786–794, 1994. Preliminary version in CRYPTO’92. [doi:10.1109/18.335890] 2, 16
[5] A MOS B EIMEL AND M ATTHEW K. F RANKLIN: Weakly-private secret sharing schemes. In 4th
Theory of Cryptography Conf., TCC’07, volume 4392, pp. 253–272, 2007. [doi:10.1007/978-3-540-
70936-7_14] 2, 16
[6] A MOS B EIMEL , A NNA G ÁL , AND M IKE PATERSON: Lower bounds for monotone span
programs. Comput. Complexity, 6(1):29–45, 1996. Preliminary version in FOCS’95.
[doi:10.1007/BF01202040] 5
[7] A MOS B EIMEL AND Y UVAL I SHAI: On the power of nonlinear secrect-sharing. In Proc. 16th
IEEE Conf. on Computational Complexity (CCC’01), pp. 188–202. IEEE Comp. Soc., 2001.
[doi:10.1109/CCC.2001.933886] 5
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 14
T HRESHOLD S ECRET S HARING R EQUIRES A L INEAR -S IZE A LPHABET
[8] A MOS B EIMEL AND I LAN O RLOV: Secret sharing and non-Shannon information inequali-
ties. IEEE Trans. Inform. Theory, 57(9):5634–5649, 2011. Preliminary version in TCC’09.
[doi:10.1109/TIT.2011.2162183] 4
[9] A MOS B EIMEL AND E NAV W EINREB: Separating the power of monotone span programs over
different fields. SIAM J. Comput., 34(5):1196–1215, 2005. Preliminary version in FOCS’03.
[doi:10.1137/S0097539704444038] 5
[10] J OSH C OHEN B ENALOH AND J ERRY L EICHTER: Generalized secret sharing and monotone
functions. In Proc. of 8th Internat. Cryptology Conf. (CRYPTO’88), pp. 27–35. Springer, 1988.
[doi:10.1007/0-387-34799-2_3] 3
[11] G EORGE ROBERT B LAKLEY: Safeguarding cryptographic keys. In Proc. AFIPS Nat. Computer
Conf., volume 1, pp. 313–317. IEEE Comp. Soc., 1979. [doi:10.1109/AFIPS.1979.98] 2
[12] G EORGE ROBERT B LAKLEY AND C ATHERINE A. M EADOWS: Security of ramp schemes. In Proc.
of 4th Internat. Cryptology Conf. (CRYPTO’84), pp. 242–268. Springer, 1984. [doi:10.1007/3-540-
39568-7_20] 2
[13] A NDREJ B OGDANOV, Y UVAL I SHAI , E MANUELE V IOLA , AND C HRISTOPHER W ILLIAMSON:
Bounded indistinguishability and the complexity of recovering secrets. In Proc. of 36th Internat.
Cryptology Conf. (CRYPTO’16), pp. 593–618. Springer, 2016. [doi:10.1007/978-3-662-53015-
3_21] 5
[14] R ENATO M. C APOCELLI , A LFREDO D E S ANTIS , L UISA G ARGANO , AND U GO VACCARO: On
the size of shares for secret sharing schemes. J. Cryptology, 6(3):157–167, 1993. Preliminary
version in CRYPTO’91. [doi:10.1007/BF00198463] 3
[15] I GNACIO C ASCUDO P UEYO , RONALD C RAMER , AND C HAOPING X ING: Bounds on the threshold
gap in secret sharing and its applications. IEEE Trans. Inform. Theory, 59(9):5600–5612, 2013.
[doi:10.1109/TIT.2013.2264504] 2, 3, 4, 5, 16
[16] H AO C HEN AND RONALD C RAMER: Algebraic geometric secret sharing schemes and secure multi-
party computations over small fields. In Proc. of 26th Internat. Cryptology Conf. (CRYPTO’06), pp.
521–536. Springer, 2006. [doi:10.1007/11818175_31] 2
[17] RONALD C RAMER , I VAN B JERRE DAMGÅRD , AND J ESPER B UUS N IELSEN: Secure Multiparty
Computation and Secret Sharing. Cambridge Univ. Press, 2015. [doi:10.1017/CBO9781107337756]
2, 12
[18] RONALD C RAMER AND S ERGE F EHR: Optimal black-box secret sharing over arbitrary Abelian
groups. In Proc. 22nd Internat. Cryptology Conf. (CRYPTO’02), pp. 272–287. Springer, 2002.
[doi:10.1007/3-540-45708-9_18] 5
[19] L ÁSZLÓ C SIRMAZ: The dealer’s random bits in perfect secret sharing schemes. Studia Scientiarum
Mathematicarum Hungarica, 32(3–4):429–438, 1996. Available at Rényi Institute. 3
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 15
A NDREJ B OGDANOV, S IYAO G UO , AND I LAN KOMARGODSKI
[20] L ÁSZLÓ C SIRMAZ: The size of a share must be large. J. Cryptology, 10(4):223–231, 1997.
Preliminary version in EUROCRYPT’94. [doi:10.1007/s001459900029] 3, 4
[21] L ÁSZLÓ C SIRMAZ AND G ÁBOR TARDOS: Optimal information rate of secret sharing schemes on
trees. IEEE Trans. Inform. Theory, 59(4):2527–2530, 2013. [doi:10.1109/TIT.2012.2236958] 13
[22] O RIOL FARRÀS , T ORBEN B RANDT H ANSEN , TARIK K ACED , AND C ARLES PADRÓ: Optimal non-
perfect uniform secret sharing schemes. In Proc. of 34th Internat. Cryptology Conf. (CRYPTO’14),
pp. 217–234. Springer, 2014. [doi:10.1007/978-3-662-44381-1_13] 2
[23] O RIOL FARRÀS , S EBASTIÀ M ARTÍN M OLLEVÍ , AND C ARLES PADRÓ: A note on non-perfect
secret sharing. IACR Cryptology ePrint Archive, Report 2016/348, 2016. 2
[24] M ATTHEW K. F RANKLIN AND M OTI Y UNG: Communication complexity of secure com-
putation (extended abstract). In Proc. 24th STOC, pp. 699–710. ACM Press, 1992.
[doi:10.1145/129712.129780] 2
[25] A NNA G ÁL: A characterization of span program size and improved lower bounds for monotone
span programs. Comput. Complexity, 10(4):277–296, 2001. Preliminary version in STOC’98.
[doi:10.1007/s000370100001] 5
[26] M ITSURU I TO , A KIRA S AITO , AND TAKAO N ISHIZEKI: Multiple assignment scheme for sharing
secret. J. Cryptology, 6(1):15–20, 1993. [doi:10.1007/BF02620229] 2, 3
[27] M AURICIO K ARCHMER AND AVI W IGDERSON: On span programs. In Proc. 8th
Structure in Complexity Theory Conf. (SCT’93), pp. 102–111. IEEE Comp. Soc., 1993.
[doi:10.1109/SCT.1993.336536] 3, 5
[28] J OE K ILIAN AND N OAM N ISAN: Unpublished. Referenced in [4, 2, 5, 15], 1990. 2, 4, 9, 12
[29] I LAN KOMARGODSKI , M ONI NAOR , AND E YLON YOGEV: How to share a secret, in-
finitely. IEEE Trans. Inform. Theory, 64(6):4179–4190, 2018. Preliminary version in TCC’16.
[doi:10.1109/TIT.2017.2779121] 5
[30] T IANREN L IU AND V INOD VAIKUNTANATHAN: Breaking the circuit-size barrier in secret sharing.
In Proc. 50th STOC, pp. 699–708. ACM Press, 2018. [doi:10.1145/3188745.3188936] 5
[31] T IANREN L IU , V INOD VAIKUNTANATHAN , AND H OETECK W EE: Conditional disclosure of
secrets via non-linear reconstruction. In Proc. of 37th Internat. Cryptology Conf. (CRYPTO’17), pp.
758–790, 2017. [doi:10.1007/978-3-319-63688-7_25] 5
[32] K EITH M. M ARTIN , M AURA B. PATERSON , AND D OUGLAS R. S TINSON: Error decodable
secret sharing and one-round perfectly secure message transmission for general adversary structures.
Cryptography and Communications, 3(2):65–86, 2011. [doi:10.1007/s12095-010-0039-6] 2
[33] S EBASTIÀ M ARTÍN M OLLEVÍ , C ARLES PADRÓ , AND A N YANG: Secret sharing, rank inequalities,
and information inequalities. IEEE Trans. Inform. Theory, 62(1):599–609, 2016. Preliminary
version in CRYPTO’13. [doi:10.1109/TIT.2015.2500232] 4
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 16
T HRESHOLD S ECRET S HARING R EQUIRES A L INEAR -S IZE A LPHABET
[34] M AURA B. PATERSON AND D OUGLAS R. S TINSON: A simple combinatorial treatment of con-
structions and threshold gaps of ramp schemes. Cryptography and Communications, 5(4):229–240,
2013. [doi:10.1007/s12095-013-0082-1] 3
[35] T ONIANN P ITASSI AND ROBERT ROBERE: Lifting Nullstellensatz to monotone span programs over
any field. In Proc. 50th STOC, pp. 1207–1219. ACM Press, 2018. [doi:10.1145/3188745.3188914,
ECCC:TR17-165] 5
[36] A DI S HAMIR: How to share a secret. Comm. ACM, 22(11):612–613, 1979.
[doi:10.1145/359168.359176] 2
[37] D OUGLAS R. S TINSON AND RUIZHONG W EI: An application of ramp schemes to broadcast
encryption. Info. Processing Lett., 69(3):131–135, 1999. [doi:10.1016/S0020-0190(98)00204-X] 2
[38] V INOD VAIKUNTANATHAN AND P RASHANT NALINI VASUDEVAN: Secret sharing and statistical
zero knowledge. In Proc. 21st Internat. Conf. on Theory and Appl. of Cryptology and Inform.
Security (ASIACRYPT’15), pp. 656–680. Springer, 2015. [doi:10.1007/978-3-662-48797-6_27] 5
AUTHORS
Andrej Bogdanov
Associate professor
Department of Computer Science and Engineering
The Chinese University of Hong Kong
Hong Kong
andrejb cse cuhk edu hk
http://www.cse.cuhk.edu.hk/~andrejb/
Siyao Guo
Assistant professor
Department of Computer Science
NYU Shanghai
China
siyao guo nyu edu
https://sites.google.com/site/siyaoguo/
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 17
A NDREJ B OGDANOV, S IYAO G UO , AND I LAN KOMARGODSKI
Ilan Komargodski
Assistant professor and Scientist
Hebrew University of Jerusalem and NTT Research
Jerusalem, Israel and Palo Alto, CA, USA
ilan.komargodski mail huji ac il
http://ilan.tech.cornell.edu
ABOUT THE AUTHORS
A NDREJ B OGDANOV is an associate professor of Computer Science at the Chinese University
of Hong Kong. He is on short leave from the Iyengar Yoga Institute of Hong Kong after
a disastrous attempt at utthita pada sirsasana. He was advised by Luca Trevisan who
taught him the fine art of enjoying xiaolongbao.
S IYAO G UO is an assistant professor of Computer Science at NYU Shanghai. She received
her Ph. D. from the Chinese University of Hong Kong, advised by Andrej Bogdanov,
who taught her how to eat xiaolongbao properly.
I LAN KOMARGODSKI is an assistant professor of Computer Science at the Hebrew University
of Jerusalem and a Scientist at NTT Research. During his Ph. D. at the Weizmann Institute
of Science, advised by Moni Naor, he visited Andrej Bogdanov and Siyao Guo who
introduced to him xiaolongbao and other delicious treats like Fourier analysis.
T HEORY OF C OMPUTING, Volume 16 (2), 2020, pp. 1–18 18