Tag Info

Hot answers tagged

11

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


8

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

The point is that the dealer generating the update needn't know what the shared secret is. If we had a dealer that remembered what the shared secret was (or we asked enough people to contribute their shares so that the dealer could reconstruct it), then yes, the dealer could generate new shares. However, this would require is a dealer that did know the ...


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


7

Full disclosure: In 2007 I founded an association aiming at voting transparency. I'm proud that my efforts may have had some role, however small, in the fact that the number of French cities using electronic voting machines for political elections, then growing, has been declining since then. The book defining the protocol of the question is made freely ...


6

Some additional points on poncho's excellent answer: If the attacker can eventually steal all shares ever distributed, then nothing can provide secrecy. So we have to assume some constraint on how many shares can be compromised, or the rate of compromise. The solution outlined in the article has the property that, once new shares are distributed (and none ...


6

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


6

We simply have to trust this party because this scheme requires a trusted dealer (a party that distributes the shares to the secret to the participants - this can be you or some other party - but if its you you should trust yourself). We can use verifiable secret sharing, that allows the parties to check whether the shares they have obtained are consistent, ...


6

What you describe is known as Threshold-secret-sharing, for which a good candidate is the threshold version of shamir-secret-sharing. In particular, for your use case I would recommend implementing an "n-1 out of n threshold sharing scheme". Shamir Secret Sharing $(n,k)$-threshold scheme. Shamir's $k$ of $n$ threshold sharing scheme is based on the ...


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

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


5

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


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

For information theoretic security in Shamir's [m,m] secret sharing scheme, do i need both authentic and confidential channels? Regular shamir secret sharing provides no protection against modified shares. So we typically assume an honest dealer with authentic and confidential channels. That means the adversary cannot change the message in transit. If a ...


5

The purpose of the reconstruction of the polynomial $P(x)$, is just to calculate the value of $P(0)$, which equals the shared secret value. If Lagrange polynomials are used, a trivial optimization which cuts the number of multiplication nearly in half is $$P(0) = (\prod_{i=0}^{n-1}{-x_i})\sum_{i=0}^{n-1}{{\frac{y_i}{-x_i (\prod_{j=0,j\neq ...


5

Shamir Secret Sharing (SSS) is based on constructing a polynomial of degree $t-1$, whose independent term is the secret $S$. Each share is actually a point of the polynomial. The security of SSS is based on the fact that, when one wants to interpolate a polynomial of degree $t-1$, one needs at least $t$ points of the polynomial. It can be seen graphically ...


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

The main misconception is, that Shamir's secret sharing is not a protocol. It states: If you have enough shares, then you can retrieve the information. And it is information theoretic. Waht does this mean? First off, there is no adversarial model in the sense of malicious or honest-but-curious adversary. It is out of scope of the protocol how and if ...


4

Actually, you can do Shamir Secret Sharing over any finite field $GF(p^k)$, for any prime $p$ and any integer $k$. If $k=1$, you have the $GF(p)$ field you mentioned; however it works on extension fields as well. We often pick $p=2$ and $k$ a multiple of 8; this makes everything nice even number of bytes (at the cost of doing our calculations in $GF(2^k)$). ...


4

Is the Kurihara algorithm really what it purports to be (dramatically faster but equally secure replacement for Shamir Secret Sharing)? The algorithm being referred to is in this paper, and I believe that the speed benefits are at best marginal, if not nonexistent. As for the speed benefits being marginal, well, normally we use secret sharing as a part ...


4

Take a linear polynomial: $y=mx+b$. If I tell you that the point $(1,5)$ is on the line, can you tell me $m$ and $b$? No, because in fact there are infinitely many lines that pass through the point $(1,5)$. It takes 2 points to uniquely identify a line. In general it takes $t$ points to uniquely identify a degree $t-1$ polynomial. Furthermore, given $t-1$ ...


4

Shamir's $(t,n)$ secret sharing scheme involves picking a random polynomial $p$ (over a finite field) of degree $t-1$, such that $p(0) = s$ is the secret value to be shared (this is easy to do, since $p(0)$ is just the constant term of the polynomial), and then evaluating the polynomial at $n$ distinct non-zero points $x_1, \dotsc, x_n$ to construct $n$ ...


3

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


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

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


3

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


3

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


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 took a brief look at the code, but I fail to see how this transformation could introduce any additional secrecy. If the randomness used to define the polynomial is good, then Shamir's secret sharing provides information theoretic secrecy (no matter how the secret actually looks like). What Ricky points out in his answer seems reasonable, i.e., to provide ...



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