We study a secret sharing problem with three secrets where the secrets are allowed to be related to each other, i.e., only certain combinations of the three secrets are permitted. The dealer produces three shares such that every pair of shares reveals a unique secret and reveals nothing about the other two secrets, other than what can be inferred from the revealed secret. For the case of binary secrets, we exactly determine the minimum amount of randomness required by the dealer, for each possible set of permitted combinations. Our characterization is based on new lower and upper bounds.
In the field of information-theoretic cryptography, randomness complexity is a key metric for protocols for private computation, that is, the number of random bits needed to realize the protocol. Although some general bounds are known, even for the relatively simple example of 1-private computation of n-party AND, the exact complexity is unknown. We study two settings. First, we consider the model of Goyal, Ishai, and Song (Crypto '22) where helper parties without any inputs are allowed to assist in the computation. In this setting, we show that two random bits always suffice to compute an arbitrary Boolean circuit C 1-privately: a single designated inputless helper flips the two bits and privately distributes the derived one-time bits to the other helper parties and the input parties as they are needed. We give an explicit construction using seven helper parties per AND gate and three helper parties per XOR gate (plus the single global randomness dealer). Moreover, two random bits are necessary already for the AND functionality (by a reduction to the standard no-helper model together with the lower bound of Kushilevitz, Ostrovsky, Prouff, Rosén, Thillard and Vergnaud (TCC '19), and therefore the worst-case helper-party randomness complexity is exactly 2 bits. Second, in the setting without helper parties, we improve the upper bound from Couteau and Rosén (Asiacrypt '22) on the (asymptotic) randomness complexity of n-party AND from 6 to 5 bits. That is, we give a 1-private protocol for computing the AND of n parties' inputs requiring 5 bits of randomness, for all n ≥ 6. Our construction, like that of Couteau and Rosén, uses a single party to flip the 5 bits and distribute the required derived values during the execution. Our approach to both problems is built around a more systematic exploration of techniques for recycling randomness across sub-computations. As part of resolving the second problem, we isolate an exact local-independence combinatorial object called a Sliding-Window Independence Generator, or a SWIG. A (k,m)-SWIG is a linear generator from a k-bit seed to m ≥ k output bits, where every cyclic length-k sliding window chosen from m output bits is perfectly uniform. We give an explicit (k,m)-SWIG for every k ≥ 1 and every m ≥ k and use a (5,n-1)-SWIG in our no-helper AND protocol.
A secret-sharing scheme realizes the forbidden graph access structure determined by a graph
G=(V,E)if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in
E(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph with
nvertices and at most
n1+βedges (resp. at least
(2n)−n1+βedges), for some
0≤β<1, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share size
O~(n1+β/2). Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is
O~(n1/4+β/4). We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size
Ω(n3/2); this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every
0≤β<1there exist a graph with at most
n1+βedges and a graph with at least
(2n)−n1+βedges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is
Ω(n1+β/2). Finally, we show that for every
0≤β<1there exist a graph with at most
n1+βedges and a graph with at least
(2n)−n1+βedges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is
Ω(n1/4+β/4). This shows that our constructions are optimal (up to poly-logarithmic factors).
In a t-out-of-n robust secret sharing scheme, a secret message is shared among n parties who can reconstruct the message by combining their shares. An adversary can adaptively corrupt up to t of the parties, get their shares, and modify them arbitrarily. The scheme should satisfy privacy, meaning that the adversary cannot learn anything about the shared message, and robustness, meaning that the adversary cannot cause the reconstruction procedure to output an incorrect message. Such schemes are only possible in the case of an honest majority, and here we focus on unconditional security in the maximal corruption setting where n = 2t+ 1. In this scenario, to share an m-bit message with a reconstruction failure probability of at most 2−k, a known lower-bound shows that the share size must be at least m + k bits. On the other hand, all prior constructions have share size that scales linearly with the number of parties n, and the prior state-of-the-art scheme due to Cevallos et al. (EUROCRYPT ’12) achieves m+ Õ(k + n). In this work, we construct the first robust secret sharing scheme in the maximal corruption setting with n = 2t+ 1, that avoids the linear dependence between share size and the number of
: A multi--secret sharing scheme is a protocol to share a number of (arbitrarily related) secrets among a set of participants in such a way that only qualified sets of participants can recover the secrets, whereas non-qualified sets of participants might have partial information about them. In this paper we analyze the amount of randomness needed by multi--secret sharing schemes. Given an m-tuple of access structures, we give a lower bound on the number of random bits needed by multi--secret sharing schemes; the lower bound is expressed in terms of a combinatorial parameter that depends only upon the access structures and not on the particular multi--secret sharing scheme used. Key Words: Data Security, Cryptography, Randomness, Secret Sharing Schemes. Category: E.3 1 Introduction There are many situations in cryptography in which it is important to be able to generate random numbers, random bit strings, etc. For example, cryptographic keys are to be generated at random from a speci...
In the problem of conditional disclosure of secrets (CDS), two parties, Alice and Bob, each has an input and shares a common secret. Their goal is to reveal the secret to a third party, Carol, as efficiently as possible, only if the inputs of Alice and Bob satisfy a certain functional relation
f. To prevent leakage of the secret to Carol when the input combination is unqualified, both Alice and Bob introduce noise. This work aims to determine the noise capacity, defined as the maximum number of secret bits that can be securely revealed to Carol, normalized by the total number of independent noise bits held jointly by Alice and Bob. Our contributions are twofold. First, we establish the necessary and sufficient conditions under which the CDS noise capacity attains its maximum value of 1. Second, in addition to the above best-case scenarios, we derive an upper bound on the linear noise capacity for any CDS instance. In particular, this upper bound is equal to
(ρ−1)(d−1)/(ρd−1), where
ρis the covering parameter of the graph representation of
f, and
dis the number of unqualified edges in residing unqualified path.