## 4 Basic Data Striping Schemes in Cloud-Based Systems
### Sharing Methods
#### 4.1.1 Perfect Secret Sharing Scheme (PSS)  
[PERSON] (1979) provides a good example of a perfect secret sharing [15]. It requires two conditions to be perfect: if, and only if, \(t-1\) shares provide absolutely no information regarding the hidden secret, and when the ratio of the length of the secret to the length of each of the shares (known as the information rate) is equivalent to 1. [PERSON]'s PSS relies on the idea that on the principle that you can define a straight line with two points, three points for a quadratic equation, and so on, to give \(t\) points to define a polynomial of degree \(t-1\). Hence, a method for \(t\)-out-of-\(n\) secret sharing can thus use a polynomial with a \(t-1\) degree using a secret for the first coefficient, and then random values for the remaining coefficients. Next, find \(n\) points on the curve and give one to each of the players. As a result, when at least \(t\) out of the \(n\) players reveal their points, there is sufficient information to fit a \((t-1)\)th degree polynomial to them, in which the first coefficient is the secret. To illustrate this construction technique, consider a concrete example. Assume that a secret value is split into five parts, three of which are needed to reconstruct the original data (_i.e._, \(n=5\), \(t=3\)). The first step is to create a second degree polynomial:  
\[y=\mathtt{a}_{0}\times x^{0}+\mathtt{a}_{1}\times x^{1}+\mathtt{a}_{2}\times x ^{2}\]  
The second step is to assign the secret value to the first coefficient (_i.e._, \(\mathtt{a}_{0}\)) and choose random values for the remaining coefficients (_i.e._, \(\mathtt{a}_{1}\) and \(\mathtt{a}_{2}\)). Suppose that the secret value is: 42, \(\mathtt{a}_{1}=1\) and \(\mathtt{a}_{2}=2\), then the polynomial becomes:  
\[y=42+x+2\times x^{2}\]  
The third step is to calculate any five \((x,y)\) pairs, for instance:  
\[ \begin{array}{llll}\underline{\mathbf{x}}&&\underline{\mathbf{v}}\\ \hline 1&42+1+2\times 1&45\\ 2&42+2+2\times 4&52\\ 3&42+3+2\times 9&63\\ 4&42+4+2\times 16&78\\ 5&42+5+2\times 25&97\end{array} \]  
Finally, distribute one pair to each player, e.g., Player1 receives (1, 45), Player2 receives (2, 52), and so on. No player can thus tell anything about the original secret, unless at least three players exchange their information and yield equations like:  
\[45=\mathtt{a}_{0}+\mathtt{a}_{1}\times 1+\mathtt{a}_{2}\times 1 ^{2}\] \[52=\mathtt{a}_{0}+\mathtt{a}_{1}\times 2+\mathtt{a}_{2}\times 2^{2}\] \[63=\mathtt{a}_{0}+\mathtt{a}_{1}\times 3+\mathtt{a}_{2}\times 3 ^{2}\]  
Hence, the three players together can work out that the secret value \(\mathtt{a}_{0}\) is 42. This method works fine, but from security point of view a player can still obtain more information about the secret with every pair on the polynomial that they find. For example, player [PERSON] finds two pairs (2, 52) and (4, 78). Although these are not enough to reveal the secret value, [PERSON] could combine them together and get:  
\[76=\mathtt{a}_{0}+\mathtt{a}_{1}\times 4+\mathtt{a}_{2}\times 4 ^{2}\] \[52=\mathtt{a}_{0}+\mathtt{a}_{1}\times 2+\mathtt{a}_{2}\times 2 ^{2}\]  
Therefore, [PERSON] can work out that:  
\[\mathtt{a}_{0}=26+8\times\mathtt{a}_{2}\]  
So, [PERSON] starts to replace \(\mathtt{a}_{2}\) with 0, 1, 2, 3... to find all possible values of \(\mathtt{a}_{0}\). This problem can be fixed by using finite field arithmetic in a field of size \(r\) where:  
\(r>\mathtt{a}_{i}\), \(r>N\), \(r=p^{k}\), \(p\in\mathrm{P}\) where \(\mathrm{P}\) is the set of primes and \(k\) is a positive integer. Then, calculate the pairs as:  
\[y=\mathrm{f}(x)\bmod(p)\]For example, consider the example of \(p=61\): \begin{tabular}{l l l l} \(\underline{x}\) & \(\underline{p}\) & & \(\underline{v}\) \\
1 & 61 & (42 + 1 + 2 \(\times\) 1) \% 61 & 45 \\
2 & 61 & (42 + 2 + 2 \(\times\) 4) \% 61 & 52 \\
3 & 61 & (42 + 3 + 2 \(\times\) 9) \% 61 & 2 \\
4 & 61 & (42 + 4 + 2 \(\times\) 16) \% 61 & 17 \\
5 & 61 & (42 + 5 + 2 \(\times\) 25) \% 61 & 36 \\ \end{tabular}