3.3 Constructions
3.3.1 Benaloh-Leichter
The corresponding monotone access structure is given by
Γ(f)={{P1, P2},{P3, P4},{P1, P2, P3},{P1, P2, P4}, {P1, P3, P4},{P2, P3, P4},{P1, P2, P3, P4}},
where we use that party Pi owns variable xi fori= 1,2,3,4. This can also be represented by the collection of the minimal qualified sets,
Γ−(f)={{P1, P2},{P3, P4}}.
In the following we will show how to construct an ISP from an arbitrary monotone formula f. Since every monotone formula can be implemented by only using logicalAND- andOR-operators, it is sufficient to show how to construct a matrix representing the two operators given two matrices that express the two terms of the operator.
First we introduce some notation. Let M(u) ∈ Z1,1 be the matrix with a single entry that is one, i.e.
M(u)= (1)
We callM(u) and anyM(a)∈Zda×ea for 0≤da, eaa matrix for the convenience of consistency. Furthermore, if we have a matrix M(a) ∈ Zda×ea, then we define c(a)= (c(a)1 , . . . , c(a)d
a))T ∈Zea to represent the first column in M(a), and R(a) = [r(a)(i,j)] ∈ Z(da−1)×ea] to represent all but the first column in M(a). In the case whereda= 1, we letRa denote the “empty” matrix, where we by the
“empty” matrix mean the matrix with no entries. Also note, that the vector c(a) sometimes only represents a single entry, but we still denote it a column vector.
Given any monotone formulaf for a monotone access structure Γ, we con-struct the distribution matrixM by the following three rules.
• Each variablexi in the formulaf can be expressed byM(u).
• For any OR-term f =f(a)∨f(b), let M(a)∈Zda×ea and M(b) ∈Zdb×eb be the matrices that express the formulas f(a) and f(b), respectively. Then we can construct a matrix MOR ∈ Z(da+db−1)×(ea+eb) expressing f that is defined by letting the first column of MOR be the concatenation of the two column vectorsc(a)andc(b), then letting the followingda−1 columns be the columns of Ra expanded with eb succeeding zero entries, and the lastdb−1 columns be the columns of Rb expanded with ea leading zero entries. This is also visualized by,
MOR=
c(a)1 r(1,2)(a) . . . r(a)(1,e
a) 0 . . . 0
... ... . .. ... ... . .. ... c(a)da r(db,2) . . . r(d(a)
a,ea) 0 . . . 0 c(b)1 0 . . . 0 r(b)(1,2) . . . r(b)(1,e
b)
... ... . .. ... ... . .. ... c(b)d
b 0 . . . 0 r(b)(d
b,2) . . . r(b)(d
b,eb)
(3.2)
• For anyAND-termf =f(a)∧f(b), letM(a) ∈Zda×ea and M(b)∈Zdb×eb be the matrices that express the formulasf(a) and f(b), respectively. Then we can construct a matrix MAND ∈ Z(da+db)×(ea+eb) for the formula f. It is defined by letting the first column of MAND be the column vector c(a) expanded witheb succeeding zero entries, the next column to be the concatenation ofc(a)andc(b), the followingda−1 columns be the columns ofRaexpanded withebsucceeding zero entries, and the lastdb−1 columns be the columns ofRb expanded withealeading zero entries. This can also be visualized by,
MAND=
c(a)1 c(a)1 r(1,2)(a) . . . r(1,e(a)
a) 0 . . . 0
... ... ... . .. ... ... . .. ... c(a)d
a c(a)d
a r(db,2) . . . r(a)(d
a,ea) 0 . . . 0 0 c(b)1 0 . . . 0 r(b)(1,2) . . . r(1,e(b)
b)
... ... ... . .. ... ... . .. ... 0 c(b)d
b 0 . . . 0 r(d(b)
b,2) . . . r(d(b)
b,eb)
(3.3)
For the sake of clarity we provide a simple example here to demonstrate the procedure.
Example 3.3. Let
f = ((x1∧x2)∧(x3∨x4)).
Each variable inf can be expressed by the matrixM(u). If we letf =f(a)∧f(b) where f(a) = (x1∧x2) and f(b) = (x3 ∨x4), then we can express f(a) by the matrix
M(a)=
1 1 0 1
,
by using the AND-rule on x1 and x2, which both are expressed by M(u). Fur-thermore, we can expressf(b) by the matrix
M(b) = 1
1
,
by using the OR-rule on x3 and x4, which also are expressed by M(u). Then finally we can expressf by the matrix
M =
1 1 1 0 0 1 0 1 0 0 1 0
,
by using the AND-rule on f(a) and f(b) and their respectively matrix represen-tationsM(a) and M(b).
Note that each occurrence of a variable xi in the formula f is represented by a row in the resulting matrix. We say that a given row is owned by the variable that it represents or the party that owns the variable. Furthermore, note that a variable can own more than one row in the resulting matrix. This happens when a variable xi is represented more than once in the formula f.
Example 3.4. Consider the formula
f = (x1∧x2)∨(x1∧x3)∨(x2∧x3), which represents the threshold 2 out of 3 access structure, i.e.,
Γ−={{P1, P2},{P1, P3},{P2, P3}},
where party Pi owns variable xi for i= 1,2,3. Using the above construction, this will result in the following matrix of the ISP,
M =
1 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1
,
where row 1 and 3 is owned by partyP1 (variablex1), row 2 and 5 is owned by party P2 (variable x2), and finally row 4 and 6 is owned by partyP3 (variable x3).
In the following we show that (M, ψ,ε) defines an ISP, where M is the matrix defined above, ψ is the function that maps share components to the parties, and ε is the target vector. Note that ψ is easily defined from the monotone formula and the corresponding matrix M, it simply maps a row in the matrix to the party that owns it.
Example 3.5. Proceeding with Example 3.4 theψ function would be given by
row 1 2 3 4 5 6
ψ(·) P1 P2 P1 P3 P2 P3
We proceed to show that (M, ψ,ε) is an ISP for the given access structure Γ in the following two lemmas. Note, that in the first lemma we give the construction of the reconstruction vector and the following lemma give the construction of the sweeping vector.
Lemma 3.2. If A ∈ Γ, then there exits a reconstruction vector λA such that MATλA=ε.
Proof. We show how to construct the reconstruction vectorλA by induction in the number of variables in the formula f that represents the access structure Γ. IfM ∈Zd×e, then we construct the reconstruction vectorλ∈ZdforA∈Γ, such that MTλ =ε but λA{ = 0, i.e., we do not use rows of M that are not owned by some party inA.
In the base case,f =x, there is only one party, and the distribution matrix is M = (1), i.e., the party gets the secret s, so the reconstruction vector is λ= (1)T.
In the case of an OR-term, f = f(a) ∨f(b), then let M(a) and M(b) be the matrices that represent the the formulas f(a) and f(b), respectively. By
assumption we know that one of the matrices is able to reconstruct the secret.
Take the reconstruction vector belonging to the matrix able to to reconstruct the secret, e.g., λa = (λ1, . . . , λt)T. The new reconstruction vector for the OR-term is λOR = (λ1, . . . , λt,0, . . . ,0)T, i.e. we put zeros in the entries that represent the shares fromM(b).
In the case where there is anAND-term,f =f(a)∧f(b), then let the matrices M(a)andM(b)represent the formulasf(a)andf(b), respectively. By assumption each of the matricesM(a)and M(b) can reconstruct their part of the secret, let λa= (λa1, . . . , λat)T andλb = (λb1, . . . , λbv)T be the reconstruction vectors for M(a) andM(b). Then we claim that the reconstruction vector for theAND-term is
λAND= (λa1, . . . , λat,−λb1, . . . ,−λbv)T, because, if we define
λa0 = (λa1, . . . , λat,0, . . . ,0)T λb0 = (0, . . . ,0, λb1, . . . , λbv)T,
we know that ifM is the distribution matrix that represents the AND-term (see Equation 3.3), then
(M·ρ)T ·λa0 = s+ρ2 (M·ρ)T ·λb0 = ρ2, i.e., we have that
(M ·ρ)T ·λa0−(M·ρ)T ·λb0 = (M·ρ)T ·(λa0 −λb0)
= (M·ρ)T ·λAND
= s+ρ2−ρ2 =s, which concludes the proof.
Before we proceed with the following lemma we make some observations.
First of all, the ISP for the formula,
f =x1∨x2∨ · · · ∨xn,
does not have any sweeping vector, since there exist no unqualified non-empty subset of partiesA⊂ P.
Hence, the simplest case is for a formula on the form, f = (x1∨ · · · ∨xi)∧(xi+1∨ · · · ∨xj), which we will call the base case.
Lemma 3.3. For all A /∈ Γ there exists a sweeping vector κ = (κ1, . . . , κe)T such thatMA·κ=0 with κ1 = 1.
Proof. We show how to construct a sweeping vector κ by induction on the construction of the matrix from a formulaf that represents the access structure Γ. Note, that we only need to verify that the inner product of κ is zero with the rows from M that are owned by the parties inA.
By the above observation, we have that the base case is a formula of the form f = (x1∨ · · · ∨xi)∧(xi+1∨ · · · ∨xj), where there is only one AND-term.
The variables inf representing the parties in Acannot be on both sides of the AND-term. If a party Pi in A owns a variables on both sides of the AND-term, thenPiwould obviously be qualified to reconstruct the secret, which contradicts the assumption that A /∈ Γ. Note, that this also implies that the parties in A cannot own rows in both the upper and lower part of the matrix constructed in Equation (3.3). The sweeping vector can be constructed as follows, if the parties in A own rows is in the bottom of the matrix (Equation (3.3)), then κ= (1,0, . . . ,0)T would qualify as sweeping vector, whereas if the parties own rows in the top of the matrix (Equarion (3.3)), thenκ= (1,−1,0, . . . ,0)T would qualify as sweeping vector.
The induction step with anOR-term,f =f(a)∨f(b), where we have matrices M(a) and M(b) that represents the formulas f(a) and f(b), respectively. There are two cases to consider, first if both the formulas f(a) and f(b) contain at least one AND-term, then by the induction assumption there exists κa and κb such that (M(a))A·κa = 0 and (M(b))A ·κb = 0. In this case, we define κ= (1, κa2, . . . , κat, κb2, . . . , κbv)T, which from Equation (3.2) can be argued to work, because if we take the inner product with κ on an upper row owned by a party in A of the matrix (Equation (3.2)), then it will be 0 by definition of κa, and if take the inner product with κ on a lower row owned by a party in A of the matrix (Equation (3.2)), then it will be 0 by definition of κb. If only one of the formulas, f(a) orf(b), has an AND-term, sayf(a), then neither of the forbidden parties can have variables in f(b), since this would enable them to reconstruct the secret. That is, we need not to worry about the inner product of κ with the rows in the lower part of Equation (3.2). A similar argument holds if only f(b) containsAND-terms.
The induction step where we have an AND-term, f = f(a)∧f(b), and let M(a) and M(b) be the matrices that represent the formulas f(a) and f(b), respectively. Then the parties in A will either not be able to reconstruct the secret from f(a) or f(b). Observe from Equation (3.3) that if the par-ties from A /∈ Γ do not qualify reconstruct the secret from f(a), then by the induction assumption there exists κa such that (M(a))A·κa = 0, and we can use κ = (1,0, κa2, . . . , κat,0, . . . ,0)T as sweeping vector. However, if the parties in A can reconstruct the secret from f(a), then we use κ = (1,−1,0, . . . ,0,−κb2, . . . ,−κbv)T, where κb = (1, κb2, . . . , κbv)T is the sweeping vector for (M(b))A, which exists by assumption.
We summarize the above two lemmas in the following theorem.
Theorem 3.1. Given any monotone access structure Γ, then a LISS scheme for Γ can efficiently constructed.
We proceed to make some observations from the construction of the LISS schemeL= (M= (M, ψ,ε),Γ,R,K) that we will need later.
Given any LISS schemeL= (M= (M, ψ,ε),Γ,R,K) constructed as above, let f denote the monotone formula for Γ. Let depth(f) denote the greatest depth of the formula and op(f) the number of AND- and OR-operators inf. Remark 3.1. If we look at Equation (3.2) and (3.3), it follows that, ifmnzis the number of non-zero entries in a row in the matrixM, thenmnz≤depth(f) + 1.
Remark 3.2. Each non-zero entry in the matrix M is 1.
Remark 3.3. It follows from Equation (3.2) and (3.3), that if M ∈Zd×e then d≤op(f) + 1 and e≤op(f) + 1.
From Remark 3.1 and 3.2 it follows, that if we have distribution matrix M ∈Zd×e that represents a formula with depth at most depth(f), then we at most need d·depth(f) additions to calculate all the dshares component from Equation (3.1). Each share component is at most the addition of depth(f) integers of (l0+k)-bit, i.e., each share component is at mostl0+k+log(depth(f)) bits long.
Remark 3.3 gives that dis equal to the size of the formula that the matrix M represents.
In [86] Valiant shows the existence of a monotone formula for the majority function of size O n5.3
and of depth O(logn). A threshold-t function Tt,n can be constructed from the majority function, by fixing some of the inputs of the majority function. This construction implies that we need a majority function of size at most 2n to construct the threshold-t function Tt,n, i.e. [86]
gives the existence of a monotone formula for the threshold-t function Tt,n of sizeO n5.3
and of depth O(logn).
This result was improved by Hoory et al. in [62], where they give a monotone formula of size O
n1+
√ 2
and depth O(logn) for the majority function, and hence, for the threshold-tfunctionTt,n.
In the table below, we give the share size, computation time, and the number of random bits needed for constructing a threshold-t access structure, when based on the result of [62].
Complexity Share size (bits) O
n
√
2(l0+k+ log logn)
Computation time O n1+
√2logn(l0+k+ log logn)
Random bits O
n1+
√
2(l0+k)
Where we assume in the computation time, that it takesO(b) time to add two O(b) bit numbers.