# Tag Info

12

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

8

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

8

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

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

7

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

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

7

I assume that your question relates to sharing a secret specifically of this form. Furthermore, you want to guarantee this even if the dealer is not trusted and may try to share a secret of a different form. Otherwise, you could just use any secret sharing (or verifiable secret sharing) scheme. However, note that $s$ as you wrote actually does not have any ...

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

6

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

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

Let us first consider the problem without involving Shamir secret-sharing at all. Suppose that $n = 140$ and that the secret $\sigma$ is a 140-byte Twitter message. The space is thus restricted considerably, from all possible $256$ byte values to the printable characters permitted to be used in Twitter messages, and the distribution in this restricted space ...

6

Yes, preprocessing Beaver triples in an offline phase leads to a faster online phase. The online phase of an AND gate requires just two openings plus local computations. But there are other advantages as well. Define a "linear representation" $[x]$ to be any way of representing/distributing a value $x$ among parties such that the following properties hold: ...

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

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

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

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 i}^{n-1}{(x_i-... 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 ... 5 Yes. If all of the shares you have are valid, you can tell when you have reached the threshold. Reconstructing the secret from t+1 shares will yield the same result as reconstructing the secret from t+2 shares. Reconstructing it from t-1 will however (always) yield a completely different result. Reconstructing the secret from t-2 or fewer shares will ... 5 Is the running times of corresponding steps true? No. Step 3 of the dealer has to be executed n times (once for each party) with each execution taking O(t) time. So it must be O(t\cdot n). Step 4 of the dealer needs O(n) to distribute each share to every party. I count O(t\cdot n) as the overall time complexity for the dealer. Of course, you ... 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

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

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

4

What you're looking for is called packed secret sharing. It was introduced by Franklin & Yung in: Franklin, M. and Yung, M., Communication complexity of secure computation.. STOC 1992. If you have a polynomial of degree $< d$, with at most $t$ corrupt parties, then you can use a single polynomial to hide $d - t$ secrets. It's not hard to see that ...

4

Optimality is actually not a well-defined term for secret sharing, and can refer to a number of different issues. First, one issue that is often considered is the size of the share that each party holds in the scheme. If the size of a party's share equals the size of the secret itself, then the secret sharing scheme is called ideal. (Formally, we don't talk ...

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

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