Proposed SW-SSS

XOR. The dealer then pads that XOR with a vector of length m which contains a ‘1’

bit in the index of each chosen secret block and (m−1) ‘0’ bits elsewhere. The padded vector is called the coefficient of c_i. Suppose that c_i is constructed from t secret blocks bi0,· · · , bit−1. Let si =bi0 ⊕ · · · ⊕bit−1. ci has the following form:

c_i = (a₀, a₂,· · · , am−1

| {z }

m

, s_i

|{z}

|S|

m

) (7.1)

where ai = 1 if i∈ {i0,· · · , it−1} and ai = 0 elsewhere. The share size is |ci| = m+ ^|S|_m. The ideal property of a SSS is |c_i| = |S|. The revisited XOR network coding-based SSS achieves a better share size if |c_i| ≤ |S|. From this inequality, (m− ^|S|₂ )² ≤ ^|S|₄² − |S|.

Because|S|is large in a real system, ^|S|₄²− |S| ≈ ^|S|₄². Therefore, m≤ |S|. In other words, if the parameters are chosen such that m ≤ |S|, the scheme can reduce the share size.

Moreover, the coefficients are chosen such that the matrix consisting of the coefficients of any m shares has rank m. This condition is to ensure that m secret blocks can be reconstructed from any m shares. To reconstruct S, the dealer chooses any m shares to find m secret blocks, then, concatenates them together. To repair a corrupted share, the dealer requires m healthy shares to reconstitute using the XOR.

Example 7.2.1. Suppose thatS =b₀||b₁||b₂ and n= 4. The dealer creates the following four shares:

• c₀ = (1,1,1, b₀⊕b₁⊕b₂)

• c1 = (1,1,0, b0⊕b1)

• c₂ = (1,0,1, b₀⊕b₂)

• c₃ = (1,0,0, b₀)

The dealer sends {c₀,· · · , c₃} to the participants {P₀,· · · P₃}, respectively. To recon-structS, the dealer chooses m= 3 shares (supposec₀, c₂, c₃) and constructs the following equation system:







s₀ =b₀⊕b₁ ⊕b₂ s2 =b0⊕b2

s₃ =b₀

(7.2) Then,{b₀, b₁, b₂} are solved using the Gaussian elimination. Finally,S is reconstructed as S = b₀||b₁||b₂. Suppose that P₂ is corrupted, the dealer requires P₀,P₁ and P₃ to provides₀, s₁ and s₃. The dealer repairs s₂ bys₂ =s₀⊕s₁⊕s₃.

7.3 Proposed SW-SSS

In this scheme, a share c_i does not have the same form as in the revisited XOR network coding-based SSS (Equation 7.1). Instead,c_iis the index of the bin that the XOR belongs

7.3. PROPOSED SW-SSS

to. This scheme focuses on the share generation, secret reconstruction and share repair.

Checking a corrupted participant is beyond the scope of this proposed scheme because several existing schemes using the MAC or signature techniques can be used.

7.3.1 Share Generation

Each XOR is constructed from three different secret blocks. Fromm secret blocks, there are

m 3

XORs. However, onlyn out of m

3

XORs are required fornparticipants. The idea to choose these n XORs as the following remark:

Remark 1. The dealer chooses each XOR such that the index sequence of the three secret blocks is a permutation of the proper set {0,· · · , m−1} in an ascending order. Each XOR itself is also sorted in an ascending order. Namely, the dealer chooses n shares for n participants from the following XORs respectively, until the dealer has enough n XORs:

(b₀ ⊕b₁⊕b₂),(b₀⊕b₁⊕b₃),· · · ,(b₀⊕b₁⊕bm−1), (b₀ ⊕b₂⊕b₃),(b₀⊕b₂⊕b₄),· · · ,(b₀⊕b₂⊕bm−1),

· · ·

(b₁ ⊕b₂⊕b₃),(b₁⊕b₂⊕b₄),· · · ,(b₁⊕b₂⊕bm−1),

· · ·

Concretely, the dealer performs theShareGen algorithm which takes m, nand S as the inputs, and outputs n pairs of share c_i and its metadata d_i as follows:

• ShareGen(m, n, S)→ {(c0, d0),· · · ,(cn−1, dn−1)}

– Divide the secret intom blocks: S =b₀|| · · · ||bm−1. – Compute the size of a secret block: |b|=|S|/m.

– Set a value: count←0.

– For∀j ∈ {0,· · · , m−3},∀t ∈ {j+ 1,· · · , m−2}and ∀z ∈ {t+ 1,· · · , m−1}:

∗ Compute a XOR for each share: s_i ←b_j ⊕b_t⊕b_z.

∗ Find the number of ‘1’ bits in s_i: d_i ← s_i.count(⁰1⁰). This is also the metadata of the share c_i.

∗ Find the share c_i ←FindShare(|b|, s_i, d_i).

∗ Increase count by 1: count=count+ 1

∗ Check if (count==n−1), then return {(c₀, d₀),· · · ,(cn−1, dn−1)}

• FindShare(|b|, si, di) → ci: this is the sub-algorithm which is used in the ShareGen algorithm:

– Construct a set M_i which consists of all permutations of each XOR, given |b|

and di. The elements in Mi are sorted in an ascending order.

7.3. PROPOSED SW-SSS

– Find the corresponding index of si in Mi: ci ← index(Mi, si). This is the share.

We can observe that the share is nots_i but the index ofs_i in the set M_i. The number of elements inM_i is |M_i|=

|b|

di

. The number of bits for representing a share is at most log₂|M_i|. The bandwidth and the storage cost can be reduced because the size of an index is less than the size of a XOR. Thank for the SWC. TheShareGen algorithm finally returns (c0, d0),· · · ,(cn−1, dn−1). The dealer distributes {ci, di} to the participant Pi. Example 7.3.1. Suppose that S = 10100111001110110001. S is divided into m = 5 blocks: b₀ = 1010, b₁ = 0111, b₂ = 0011, b₃ = 1011 and b₄ = 0001 (|S| = 20, |b_i| = 4).

Suppose that n= 8, the shares are {c₀,· · · , c₇}.

To construct c0, s0 = b0 ⊕b1 ⊕b2 = 1110 is used. Because the number of ‘1’ bits in s₀ is 3, d₀ = 3. Because d₀ = 3 and |b_i| = 4, M₀ = {0111,1011,1101,1110}. The elements in M₀ are sorted in an ascending order and are indexed as {0,· · · ,3}. Because

|M₀|= 4

3

= 4, at most log₂4 = 2 bits are required to represent c₀ instead of 4 bits of s₀. Because the index of s₀ in M₀ is 3, c₀ = 3_decimal = 11_binary. {c₀, d₀} are sent to the participant P0. Similarly, {c1,· · ·c7}are computed as follows.

i s_i d_i M_i c_i

0 b₀⊕b₁⊕b₂ = 1110 3 {0111,1011,1101,1110} 3_decimal = 11_binary 1 b₀⊕b₁⊕b₃ = 0110 2 {0011,0101,0110,1001,1010,1100} 2_decimal = 10_binary 2 b₀⊕b₁⊕b₄ = 1100 2 {0011,0101,0110,1001,1010,1100} 5_decimal = 101_binary 3 b₀⊕b₂⊕b₃ = 0010 1 {0001,0010,0100,1000} 1_decimal = 1_binary 4 b₀⊕b₂⊕b₄ = 1000 1 {0001,0010,0100,1000} 3_decimal = 11_binary

5 b₀⊕b₃⊕b₄ = 0000 0 {} 0_decimal = 0_binary

6 b₁⊕b₂⊕b₃ = 1111 4 {1111} 0_decimal = 0_binary 7 b₁⊕b₂⊕b₄ = 0101 2 {0011,0101,0110,1001,1010,1100} 1_decimal = 1_binary.

{c_i, d_i} are then sent toP_i where i∈ {0,· · ·7}.

7.3.2 Secret Reconstruction

To reconstruct S, the dealer requires m participants to provide their shares (suppose c_k0, · · ·, c_km−1). These shares are chosen such that the binary matrix consisting of the coefficient vectors of the XORs has full rank. Concretely, the dealer performs the secret reconstruction Reconst algorithm which takes m pairs of (c_ki, d_ki) as the inputs, and outputsm secret blocks {b₀,· · · , bm−1}as follows:

• Reconst((c_k0, d_k0),· · · ,(c_km−1, d_km−1))→ {b₀,· · · , bm−1}:

– For∀i∈ {0,· · · , m−1}:

∗ Find the XOR for c_ki: s_ki ←FindXOR(|b|, d_ki, c_ki).

7.3. PROPOSED SW-SSS

∗ Find the indices of three operands ofski: (jki, tki, zki)←LocateIndices(m, ki).

∗ Construct a vectorv_ki which consists of (m+ 1) elements: mfirst elements are the binary coefficients of msecret blocks and the finally element iss_ki. Namely,v_ki = [e₀, e₁,· · · , em−1, s_ki] wheree_x ∈ {0,1}forx= 0,· · · , m−1.

e_x = 1 when x is the index of each operand ins_ki (j_ki,t_ki and z_ki). e_x = 0 elsewhere.

∗ Construct a matrix Q in which each vector v_ki is a row of the matrix Q:

Q←[vk0, vk1,· · · , vkm−1]^T.

∗ Execute the Gaussian elimination on Q to obtain a matrix Q⁰.

∗ Filter m unknowns {b₀,· · ·, bm−1} fromQ⁰.

∗ Reconstruct the secret by concatenating all the secret blocks: S=b₀ || · · ·

|| bm−1.

• FindXOR(|b|, dki, cki) → ski: this is the sub-algorithm which is used in the Reconst algorithm:

– Lists all permutations given |b| and d_ki.

– Find the XOR s_ki by picking the c_ki-th element in the set M_ki.

• LocateIndices(m, k_i) → {j_ki, t_ki, z_ki}: this is sub-algorithm which is used in the Reconst algorithm:

– Set a value: count← −1.

– For∀j ∈ {0,· · · , m−3},∀t ∈ {j + 1,· · · , m−2}, ∀z ∈ {t+ 1,· · · , m−1}:

∗ Increase count by 1: count=count+ 1.

∗ Check if (count==k_i), then set:

· j_ki ←j

· t_ki ←t

· z_ki ←z

Example 7.3.2. This example follows Example 7.3.1. Suppose that {c₁, c₃, c₅, c₆, c₇} are chosen to reconstruct S because the matrix consisting of the coefficient vectors of {s₁, s₃, s₅, s₆, s₇}has full rank. Because|b|= 4 andd₁ = 2,M₁ ={0011, 0101, 0110, 1001, 1010, 1100}. Because the element whose index in M₁ is c₁ = 10_binary = 2_decimal is 0110, s₁ = 0110. Similarly, s₃ = 0010,s₅ = 0000,s₆ = 1111 and s₇ = 0101. A vectorv_ki is then constructed for eachc_ki. Becauses₁ =b₀⊕b₁⊕b₃ = 0110, (j₁, t₁, z₁) = (0,1,3). Therefore, v₁ = [1,1,0,1,0,0110]. Similarly, v₃ = [1,0,1,1,0,0010], v₅ = [1,0,0,1,1,0000], v₆ = [0,1,1,1,0,1111] and v₇ = [0,1,1,0,1,0101]. The matrix Q is constructed as follows:

Q=











 v1

v₃ v₅ v6

v₇













=













1,1,0,1,0, 1,0,1,1,0, 1,0,0,1,1, 0,1,1,1,0, 0,1,1,0,1,

0110 0010 0000 1111 0101













(7.3)

7.3. PROPOSED SW-SSS

We apply Gauss-elimination onQ to obtain Q⁰:

Q⁰ =













1,0,0,0,0, 0,1,0,0,0, 0,0,1,0,0, 0,0,0,1,0, 0,0,0,0,1,

1010 0111 0011 1011 0001













(7.4)

From Q⁰, the secret blocks are obtained as: b₀ = 1010, b₁ = 0111, b₂ = 0011, b₃ = 1011 and b₄ = 0001. Finally,S is reconstructed as S=b₀|| · · · ||b₄.

7.3.3 Share Repair

Suppose that the participant P_corr is corrupted. The dealer finds only three shares which belongs to three participants to repair P_corr. The idea to find these three shares is given in the following remark:

Remark 2. Let s_corr denote the XOR used to construct the share c_corr in P_corr. s_corr = b_jcorr ⊕b_tcorr ⊕b_zcorr. We choose two integers α, β ∈ {0,· · ·, m −1} such that α, β 6=

jcorr, tcorr, zcorr. The idea to find three shares to repair Pcorr is that:

b_jcorr ⊕b_tcorr ⊕b_zcorr = (b_jcorr ⊕b_tcorr ⊕b_α)

⊕ (b_jcorr ⊕b_zcorr⊕b_β)

⊕ (b_jcorr ⊕b_α⊕b_β)

The three shares which will be used to repair P_corr is the shares that are constructed from the XORs: (b_jcorr ⊕b_tcorr ⊕b_α), (b_jcorr ⊕b_zcorr ⊕b_β) and (b_jcorr ⊕b_α⊕b_β).

Concretely, the dealer performs the ShareRepair algorithm which takes Pcorr as the inputs, and outputs the sharec_corr and the metadata d_corr of P_corr as follows.

• ShareRepair(P_corr)→ {c_corr, d_corr}:

– Find indices of the XOR (b_jcorr ⊕b_tcorr ⊕b_zcorr):

(j_corr, t_corr, z_corr)←LocateIndices(m, corr).

– Choose α, β ∈ {0,· · · , m−1} such thatα, β 6=j_corr, t_corr, z_corr.

– Sort{j_corr, t_corr, α},{j_corr, z_corr, β}and{j_corr, α, β}in an ascending orders. Let {jr1, tr1, zr1}, {jr2, tr2, zr2} and {tr3, tr3, zr3} denote the results of these sorts, respectively.

– Find three participants used for the repair:

∗ Pr1 ←LocateParticipant(jr1, tr1, zr1).

∗ P_r2 ←LocateParticipant(j_r2, t_r2, z_r2).

∗ P_r3 ←LocateParticipant(j_r3, t_r3, z_r3).

7.3. PROPOSED SW-SSS

– Require Pr1,Pr2 and Pr3 to provide {cr1, dr1}, {cr2, dr2} and {cr3, dr3}, respec-tively.

– Find the XORs (s_r1, s_r2 ands_r3) by picking thec_r1-th, c_r2-th andc_r3-th element in the set M_r1, M_r2 and M_r3, respectively:

∗ s_r1 ←FindXOR(|b|, d_r1, c_r1).

∗ sr2 ←FindXOR(|b|, dr2, cr2).

∗ s_r3 ←FindXOR(|b|, d_r3, c_r3)

– Recover s_corr as: s_corr ←s_r1 ⊕s_r2 ⊕s_r3.

– Find the metadata d_corr by counting the number of ‘1’ bits in s_corr.

– Compute the share c_corr using the FindSharesub-algorithm like the share gen-eration algorithm.

• LocateParticipant(jri, tri, zri) → Pri: this is the sub-algorithm which is used in the ShareRepair algorithm:

– Set a value: count=−1.

– For∀j ∈ {0,· · · , m−3},∀t ∈ {j + 1,· · · , m−2}, ∀z ∈ {t+ 1,· · · , m−1}:

∗ Increase count by 1: count=count+ 1.

∗ Check if: (j ==jri) and (t ==tri) and (z == zri), then return count.

Example 7.3.3. This example follows Example 7.3.1 and Example 7.3.2. Suppose that P₄ is corrupted. {j_corr, t_corr, z_corr}= {0,2,4}because P₄ usesb₀⊕b₂⊕b₄ to construct its share. Choose α= 1 and β= 3 because 1,36= 0,2,4.

b0⊕b2⊕b4 = (b0⊕b2⊕b1)

⊕ (b₀⊕b₄⊕b₃)

⊕ (b₀⊕b₁⊕b₃)

Let{j_r1, t_r1, z_r1} ={0,1,2}, {j_r2, t_r2, z_r2}= {0,3,4} and {j_r3, t_r3, z_r3} ={0,1,3}. The participants are chosen for repairing P4 as follows:

• Given {j_r1,t_r1, z_r1} ={0,1,2}, P₀ is chosen becauseP₀ uses (b₀⊕b₁⊕b₂).

• Given {j_r2, t_r2, z_r2}={0,3,4}, P₅ is chosen because P₅ uses (b₀⊕b₃⊕b₄).

• Given {j_r3, t_r3, z_r3}={0,1,3}, P₁ is chosen because P₁ uses (b₀⊕b₁⊕b₃).

The participantsP₀,P₅ and P₁ are then required to provide (c₀, d₀),(c₅, d₅) and (c₁, d₁) to the dealer. The XORs used for the repair are found as follows:

• Given (c₀, d₀) = (11,3), the dealer finds s₀ = 1110.

• Given (c₅, d₅) = (0,0), the dealer finds s₅ = 0000.

ドキュメント内 JAIST Repository https://dspace.jaist.ac.jp/ (ページ 153-159)