Linear Integer Secret Sharing

Assume that there are n parties that are denoted by P₁, . . . , P_n. Let P = {P₁, . . . , P_n}be the set of all the parties, and let the power set ofP be denoted byP(P). In the context of secret sharing, a secretsis shared among the parties inP. A setAinP(P) is denotedqualified if the parties in the setAare allowed to reconstruct the secrets. Furthermore, a setB inP(P) is denotedforbidden if the parties in the set B should not be able to obtain any information about the secret s.

If Γ is the collection of all qualified subsets of parties in P and Γ is a monotone access structure, then the corresponding adversary structure, ∆, is the collection of all the forbidden sets. Note that, ∆ is monotone as required by an adversary structure, and that Γ∪∆ =P(P) and Γ∩∆ =∅.

Note 3.1. In the context of secret sharing the collection of qualified subsets Γ needs to be monotone. Otherwise there would exist A ∈ Γ and a B /∈ Γ such that A ⊂B. This implies that the parties inA should be able to reconstruct the secret, while the parties inB should not.

In alinear integer secret sharing(LISS) scheme a dealerDcan share a secret s from a publically know interval [−2^l..2^l] over any monotone access structure Γ between the parties inP such that only qualified subsets can reconstruct the secret while other subsets do not gain any information about the secret. More precisely:

Definition 3.1. A LISS scheme is correct, if the secret can be reconstructed from shares of any qualified set inA∈Γ, by taking an integer linear combination of the shares with coefficient that depends only on the index set A.

Definition 3.2. A LISS scheme is private, if for any forbidden set B ∈ ∆, any two secret s, s⁰ ∈ [−2^l..2^l], and independent random coins r and r⁰, the

1Note that in a later paper [34], Cramer, Fehr and Stam propose a construction that they conjecture to be more efficient than [32], but so far, the asymptotic efficiency of the scheme remains unproved.

statistical distance between the distributions of the shares {s_i(s, r, k) |i ∈ B}

and{s_i(s⁰, r⁰, k)|i∈B} is negligible in the security parameter k.

Formally, a LISS scheme is described as follows. Let [−2^l..2^l] be the set of secrets, then each party j is associated a positive integer d_j = |ψ⁻¹(j)| for 1≤j≤n, such that the set of possible shares for partyj, is a subsetS_j ⊆Z^dj of theZ-moduleZ^dj. Each possible share for partyjis in the subsetS_j. Theshare size of party j is defined to be the number of bits used to uniquely represent the share from S_j. Note, that d = Pn

j=1dj, where d is the number of share components. Then letS =S₁× · · · × S_n⊆Z^dthat defines the subset of possible shares for the parties. Define theexpansion rate to be µ=d/n, wheredis the number of share components and n is the number of parties. Note, that for a given distribution of a secret, the shares of the shareholders can be considered as an element in the subsetS. If we usembits to uniquely represent the shares inS, then we define theaverage share size to bem/µ, i.e., the number of share bits each party will get on average.

To realize a LISS scheme, we need the following tools. A labeled ma-trix consists of a d× e matrix M and a corresponding surjective function ψ : {1, . . . , d} → {1, . . . , n}. We say that the i-th row is labeled by ψ(i) or owned by partyP_ψ(i). For any subset A⊂ P, we letMA denote the restriction of M to the rows jointly owned by the parties in A. We denote d_A for the number of rows in M_A. For any d-vector x, we similarly denote x_A to be the restriction of entries jointly owned by the parties in A. For any two vectors a andb, let ha,bi denote the inner product.

Definition 3.3. M = (M, ψ,ε) is called an Integer Span Program (ISP), if M ∈ Z^d×e and the d rows of M are labelled by a surjective function ψ : {1, . . . , d} → {1, . . . , n}. Finally, ε = (1,0, . . . ,0)^T ∈ Z^e is called the target vector. We define size(M) =d, where dis the number of rows ofM.

Definition 3.4. Let Γ be a monotone access structure and let M= (M, ψ,ε) be a integer span program. Then M is an ISP for Γ, if for all A ⊆ P the following holds.

- If A∈Γ there exists a reconstruction vectorλ∈Z^d such thatM_A^Tλ=ε.

- If A /∈Γ there exists a sweeping vector κ∈Z^e such that MAκ= 0 and hκ,εi= 1.

In other words, the rows owned by a qualified set must include the target vector in their span, while for a forbidden set, there must exist a sweeping vector, which is orthogonal to all rows of the set, but has inner product 1 with the target vector. We also say thatM computes Γ.

We define κmax = max{|a| | ais an entry in some sweeping vector}. Let l0 =l+dlog₂(κmax(e−1))e+ 1. The size of Mis defined to be d.

Note 3.2. In the case of a span program, which works over a field, the explicit requirement of a sweeping vector is not necessary. This is because the following holds for fields,ε∈im(M_A^T) if and only if there exists a sweeping vector. When working with the integers then only the “only if” implication is guaranteed.

To share a secret s ∈ [−2^l..2^l], we use a distribution vector ρ, which is a uniformly random vector in [−2^l0+k..2^l0+k]^e with the restriction thathρ,εi=s and wherekis the statistical security parameter. Theshare vector is computed by

s= (s₁, . . . , s_d)^T =Mρ, (3.1) where the share component s_i is given to partyP_ψ(i) for 1 ≤i≤d. The share of party P_j is the subset of share componentss_{Pj}.

Now, the first requirement in Definition 3.4 obviously makes the scheme correct, in that a qualified set A can compute the secret by taking a linear combination of their values, since there existsλ_A∈Z^dA such that M_A^T ·λ_A=ε which gives

s^T_A·λA= (MA·ρ)^T ·λA=ρ^T ·(M_A^T ·λA) =ρ^T ·ε=s

The Lemma below shows that the second requirement in Definition 3.4 is sufficient to make the scheme private.

Lemma 3.1. Ifs∈[−2^l..2^l]is the secret to be shared andρis chosen uniformly at random from [−2^l0+k..2^l0+k]^e with the restriction that hρ,εi = s, then the LISS scheme derived from Mis private.

Proof. We have chosen ρ = (s, ρ2, . . . , ρe)^T, with ρi ∈ [−2^l0+k..2^l0+k] as uni-formly random numbers for 2≤i≤e, and the secret s∈[−2^l..2^l].

Lets⁰ ∈[−2^l..2^l] be arbitrary. We first observe, that s_A=M_Aρ are shares that a subset Acan see. If A /∈Γ, then we by definition know that there exists a sweeping vector κsuch thatM_Aκ=0∈Z^dA.

Defines⁰ =M(ρ+ (s⁰−s)κ). We note thats⁰_A=s_A, i.e., the parties in A see the same shares, but the secret s⁰ was shared instead ofs. Define ρto be good if ρ⁰ = ρ+ (s⁰−s)κ has entries in the specified range. Then the above implies that if we restrict the distribution of A’s shares ofsto the cases where ρ is good, the resulting distribution equals the one generated from s⁰ and ρ⁰.

It follows that the statistical distance between the distributions ofA’s shares of s and s⁰ is at most twice the probability that ρ is not good, which we can estimate by the union bound as e−1 times the probability that a single entry is out of range. So since|s⁰−s| ≤2^l, the distance is at most

2·2^lκ_max(e−1)

2^l0+k ≤2^−k, which is negligible in the security parameter k.

A description of a LISS scheme is given by L = (M= (M, ψ,ε),Γ,R,K), where M is an ISP for Γ, for each A ∈ Γ there is a reconstruction vector λ^(A) ∈ R, and for each set B ⊆ P with B /∈ Γ there is a sweeping vector κ^(B) ∈ K. In the following sections and chapters we will only refer to the ISP as the LISS scheme for some access structure Γ, where we implicitly assume that there is a full description of a LISS scheme as given above.