# Tag Info

8

In Shamir's scheme is a secret sharing scheme, that is, someone that has fewer shares than is required get no information about the secret. For example, if we have a system where we require 3 shares to reveal the shared secret, then someone with 2 shares cannot be able to reconstruct it. This is true if we make the shared secret the zero-th coefficient; ...

7

It's simply not secure. Sure, it "works", in the sense that you can generate shares and reconstruct the secret from a sufficient number of them, but the essential security property of Shamir's secret sharing — namely, that knowing less than the required threshold number of shares reveals no information about the secret — does not hold. Since ...

7

No, the Runge phenomenon is known not to affect Shamir's scheme. Remember, the point of Shamir's scheme is not actually to form an approximation over an interval; instead, it's to encode a secret in a randomly chosen polynomial, and then divide up clues to that polynomial so that, with enough clues (shares), someone can reconstruct the entire polynomial ...

6

We simply have to trust this party because this scheme requires a trusted setup. We can use verifiable secret sharing, that allows the parties to check whether the shares they have obtained are consistent. If we do not want to have a trusted dealer who sets up the shares at all, we have to switch to dealer-free secret sharing schemes. See for instance, ...

5

The process is pretty simple. As you say, each party multiplies their two shares. They then use Shamir secret sharing to share the resulting value with the other parties. Once they have received a "subshare" from each other party, each party simply runs Lagrangian interpolation on the subshares they received (plus their own subshare). The result is a share ...

5

Here's an easy way to do it: Take your secret $S$, and select a random value $R$ of the same size, and compute $T = S \oplus R$ Give the accountant the value $R$ Use a $(k-1, n-1)$ secret sharing method to share $T$ to the other parties. The accountant plus any set of $k-1$ other parties can reconstruct the secret. And, any smaller subset cannot get any ...

5

In the scenario you describe, any of the non-cheating participants can contact each of the others and arrange to swap shares and reconstruct the secret. (Equivalently, all the participants can agree to publish their shares, at which point any of them can pair their share with each of the others.) If there's only one cheater, the participant who does this ...

4

The simplest answer is probably to give an example of information leaked when using Shamir's secret sharing over the integers. Assume that we construct a low degree example, defining $q$ to be a linear polynomial with $q(0)=D$ and $q(1)=a_1$. By interpolation you find that: $$q(x)=(a_1-D)x+D.$$ Assume that you are given the share corresponding to ...

4

A simple partial explanation addressing your "random value added", too long for a comment. This works well for the trivial case of two shares: Given a secret $x$, split it into $r$ and $x-r$, where $r$ is a random number. Having both shares, you can get the secret by as their sum. Having only one share, you can do nothing at all, assuming there are no ...

3

First note that using MPC we can compute addition, subtraction, multiplication and division (multiplication by the inverse) on shares. It turns out there are also secure protocols out there for doing comparison (see http://viff.dk and their references). So we could simply do something like this: while k >= m: k = k-m $m$ could be public or secret ...

3

I will make a start by observing that not every monotone access structure can be realized by means of $(t,n)$ threshold secret sharing (here we require $t$ out of the $n$ shares need to be available for reconstruction). First let us define a monotone access structure. Let $P$ be a set of participants. An access structure $\Gamma$ is a collection of ...

3

I now see your problem; it's more fundamental than what my previous answer assumed. You state: Now the same method should work for finite field GF(2^8) as long as the arithmetic are replaced with finite field arithmetic. However this is not the case where you interpret "should work" as "coming up with the exact same answer". Actually, that's not the ...

3

Shamir's secret-sharing scheme has $n$ shares of a secret. The shares are of the form $(x_0,f(x_0)), (x_1,f(x_1)), \ldots , (x_{n-1},f(x_{n-1}))$ where the $x_i$ are $n$ distinct nonzero elements of a finite field $\mathbb F$, and $f(x)$ is a polynomial of degree $k-1$ with coefficients in $\mathbb F$. One coefficient, say $f_0$, of $f(x)$ is the secret ...

2

The formula you are looking for is Lagrange Basis Polynomials. Essentially, each share consists of two values, an x coordinate and an y coordinate. The x coordinate might, depending on your specific needs, be implicitly determined by context, such as a preexisting identifier for the entity holding the share. The only requirement is that it is non-zero and ...

2

You really only need to do step 1. If each party has shares of x and y (say $x_i,y_i$) then $z_i=x_i+y_i$ is a valid sharing of $z=x+y$. What you are doing is used to multiply shares. Multiply, share the shares, reconstruct. In that case everything you said is correct. The reason this is needed in multiplication of shares and not addition can be seen by ...

2

I think there's a better way to do this, and I'm not sure the existing answers check all your boxes. I suggest using secret splitting together with asymmetric keys so that: Nobody but you can write data. Shareholders can come together to read data. Each shareholder can individually verify, but not read data. You can read and write data at any time. ...

2

If you don't update the shares, then any $T$ share holders will be able to reconstruct only the original secret $S_{\scriptstyle{\text{old}}}$, and not the updated version $S_{\scriptstyle{\text{new}}}$. Instead of providing all the $N$ share holders with new shares to use in the reconstruction process you could consider informing all $N$ to simply XOR ...

2

The best answer is to use verifiable secret sharing (VSS), as I describe here: http://crypto.stackexchange.com/a/6618/351 VSS gives the best parameters and best solution to this problem. If you have a $k$-out-of-$n$ secret sharing scheme, VSS can detect any cheater and enable you to reconstruct the secret as long as you have at least $k$ good shares (even ...

2

Not enough information was provided in the question, so I'm going to assume something to fill in the hole. Let me know if this is not what you envisioned. Assumption: The party trying to detect the cheater knows the original polynomial used to share the secret. In the initialization phase, each party $p_i$ is given a pair $x_i, y_i$ where $y_i = f(x_i)$. ...

2

Suppose $s_0, s_1, s_2, \ldots, s_{k-1}$ are elements from the finite field you are working in, where $s_0$ is the secret to be shared, and the $s_i, i > 0$ are randomly chosen nonzero elements of the field. Then, the polynomial used to construct the shares is $$S(x) = s_0 + s_1x + s_2x^2+ \cdots + s_{k-1}x^{k-1}$$ and the shares themselves are $y_i = ... 2 The reason that a field must be used in Shamir's reconstruction scheme is that the calculations used in the reconstruction need to divide one "number" by another, and division is not defined in$\mathbb Z$, the set of integers:$\frac{m}{n}$is not necessarily a member of$\mathbb Z$. So, why not use$\mathbb R$, or$\mathbb Q$which can be "implemented" in ... 2 Shamir's secret sharing is based on mathematical splitting but not string splitting (as in programming languages) . So a key share cannot be considered same as partial key . Also the security is information-theoretic but not computational meaning no amount of computational power can reveal the complete secret if less than threshold secret shares are ... 2 With SSS you are sharing field elements, so if the secret to be shared is larger than one field element, you are going to have to break up the secret somehow and share the parts. I am not aware of any standard method that allows you to make the sharings dependent on one another. Probably the best way is to encrypt the secret with a key and then share the key ... 2 Well, the first thing comes to mind is "what if your 'read-only location' isn't quite as read-only as you had hoped; if someone could modify your$f(i) \oplus k_i$share, could they modify the reconstructed shared secret in a controlled way. In your first example, I believe they could. Let us assume that we are doing Shamir's Secret Sharing over the field ... 2 This is actually a fairly trivial case of secret sharing: In the first case, we select a random value$R$, we give$X$the value$R \oplus M$, and we give both Y and Z the value$R$. Obviously,$X$alone, nor$Y$and$Z$together cannot reconstruct$R$. In the second case, we select random values$R_1$,$R_2$and$R_3$, we give:$R_1 \oplus M$to$X$... 1 The values$b_i = \prod\limits_{j \in B, j \neq i}\frac{j}{(j-i)}$are the evaluations of the so called Lagrange basis polynomials at point$0$. These terms are often also called Lagrange coefficients and can be computed by any participant and$B$is the index set of the participants. The formula$a_0^{(i)}G = \sum_{j \in B}b_j f_i(j)G$is just a ... 1 In general, you cannot encode information such that "any variance at all in the inputs causes the decoded secret to be completely useless." That's because there's a generic attack that can be used to reconstruct the secret with a high probability, given almost enough enough information to uniquely determine it, as long as the correct secret can somehow be ... 1 As pointed out in the comments, this is a poor choice since it does not maintain the security level of the secret sharing on which it is based. For just one person, you can use Shamir except instead of storing the secret as point$f(0)$use the point$f(t)$, where you give$t$to the required person. So, set up the scheme as$(k-1,n-1)$for the other ... 1 This answer attempts to solve the original question, which gave a specific example - it certainly won't solve the generalised case now given! Create a threshold sharing scheme with$4$shares (call them$1,2,3,4$) and a threshold of$3$required for secret retrieval. Then, issue shares such that:$$\begin{array}{cl} A & 1,4 \\ B & 2 \\ C & ... 1 As long as computers have a finite amount of RAM, then they cannot handle infinite amounts of data. Shamir's secret sharing is "perfect" in the following sense: it does not leak any extra information. When a threshold$t$is used, an attacker obtaining$t-1\$ shares learns nothing that he did not already know. But we assume that "what the attacker already ...

Only top voted, non community-wiki answers of a minimum length are eligible