# 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 ...

6

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 ...

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 ...

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 ...

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 ...

4

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 ...

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 ...

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

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

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 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 ... 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 ... 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 ... 1 Computers are unable to handle real numbers, especially irrational numbers. Computers can handle a fraction of the rational numbers (for being limited in size in a binary representation), and without some special tricks it can't handle the entire field$\mathbb{Q}$. So you're down to integer arithmetic anyway (if you consider floats: rounding and ... 1 As for your questions: In finite field arithmetic, negating x ($−x$) is really$0−x$, which is actually$0 \oplus x$(XOR), and it ends up being x itself, am I right? In any finite field,$-x$is defined to be$0-x$, and in a field of characteristic two (which you are working with), yes,$-x = x$Is there anything wrong with my approach to finding ... 1 The easy way to reconstruct the secret is using Neville's algorithm. Basically, let the array y contain n shares (assumed to be represented as the type gf_t here), let the array x contain the points at which the polynomial was evaluated to generate those shares, and let sub(), mul() and inv() be functions/macros that perform the appropriate finite field ... 1 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 ... 1 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 ...

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