20

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


12

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


12

Here is an active attack on the privacy of out-of-the-box SSS. For this attack, we'll assume that the attacker (without a valid share) is allowed to participate (with $T-1$ friends with honest key shares), jointly use the protocol to recover a 'shared secret' (which might not be the real shared secret); we'll assume that this shared secret recovery process ...


10

Shamir's (m,n) secret sharing scheme has a secret $s_0$ which is represented as an element of a finite field $\mathbb F_q$ of $q$ elements. There are also $m-1$ other "randomly chosen" elements $s_1, s_2, \ldots, s_{m-1}$ that the designer uses. The scheme creates a polynomial $$S(x) = s_0 + s_1x + \cdots + s_{m-1}x^{m-1}$$ and evaluates $S(x)$ at $n$ ...


10

As you note, Shamir's threshold secret sharing is perfectly secure (or information theoretically secure), yet does leak some information about the size of the secret (same thing with one-time pad). If you are worried about leaking some information about the size of the secret, then padding could be used to lower the information leakage (instead of knowing ...


10

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


10

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


10

In RSA, assuming knowledge of the public key but not the private key, analyzing any number of triplets of matching message, encrypted message, and signature $(m,M,sg)$, does not help (as far as we know) towards recovering the private key $s$ (nor an equivalent). That's regardless of the sensible padding or RSA variant used (as long as neither the padding nor ...


10

let's say have used a 64-bit secret key to encrypt a file and then we split the key into 2 pieces of 32-bit That right there is your misunderstanding. Shamir secret sharing does not split a secret into pieces that are smaller than the original secret. Instead, it splits the secret into pieces that are the same size as the original secret. A simple ...


8

There is no reason in Shamir's scheme for the finite field $\mathbb F$ to have a prime number $p$ of elements; the field can have $p^m$ elements for suitable prime $p$ and integer $m \geq 1$. So, using $F_{2^8}$, the field with $2^8$ elements is perfectly all right. However, choosing $m = 1$ has the advantage that calculations in $\mathbb F_p$ can be done ...


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


8

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


8

This cannot be achieved information-theoretically. This is typically the task that requires multiparty computation protocol to be achieved. In particular, the common method for what you want is called "secure multiplication protocol", and is in general constructed from an additively homomorphic encryption scheme (over the ring $R$), or from oblivious ...


8

With Shamir's Secret Sharing you can add as many shares as you want, as long as the threshold and the secret is unchanged. You can see that neither the generation of the polynomial that produces the shares nor the reconstruction of the secret by polynomial interpolation require the parameter $N$ (number of shares), but only the threshold $k$. Of course ...


8

Yes. It is possible to construct secret sharing schemes for general (monotone) access structures. You can read about the first construction in the paper called Secret Sharing Scheme Realizing General Access Structure. I also suggest reading this survey by Amos Beimel.


8

The proposed sharing scheme does allow reconstruction of key $K$ from any two of the three shares $K_A$, $K_B$, $K_C=(X_A,X_B)$, because: $K=K_A+K_B$ from $K_A$ and $K_B$ $K=K_A\oplus X_A$ from $K_A$ and $K_C$ $K=K_B\oplus X_B$ from $K_B$ and $K_C$ Problem is, the scheme leaks information about key $K$: always less than 1 bit worth to participants $A$ and $...


8

The maximum number of shares in Shamir's secret sharing is limited by the size of the underlying finite field. In particular, the maximum is one less than the number of elements in the field, since each share must be associated with a distinct element of the field, and one of the elements (usually the zero element) must be reserved for the secret being ...


7

It has to do with which modulus you use. You did all your arithmetic modulo 11. However, when using Feldman's VSS, you gotta use two different moduli (using each one in the appropriate spot). In your example, you shouldn't do all arithmetic modulo 11. Instead, you should be doing some arithmetic modulo 11, and some arithmetic modulo 5 (the order of $g$ ...


7

Shamir's secret sharing scheme provides only confidentiality against shareholders who want to try to learn the secret. It does not prevent denial-of-service attacks (or attacks on integrity), where a malicious shareholder submits a bogus share to try to cause the reconstruction of the shares to fail. If you want security against that sort of attack, don't ...


7

Shamir's secret sharing works in any finite field. A field is a mathematical structure that follows the usual laws of addition and multiplication. A finite field is a field with a finite number of elements, unlike for example the real numbers, which have an infinite number of elements. Fields exist for all prime powers pk where p is a prime and k a positive ...


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

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


7

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


7

Your understanding is correct. The SPDZ protocol can be used for any number of two or more parties. In fact, this is one of the strengths of the SPDZ protocol. Namely, many recent secure computation protocols such as the various versions of the Yao protocol or the TinyOT protocol are limited to two parties. So it may sometimes be overemphasized that SPDZ ...


7

Here's one more way in which a dishonest participant can mess with Shamir's secret sharing: Let's briefly review how secret reconstruction in Shamir's $(k,n)$ secret sharing works. Given the $x$-coordinates of $k$ participants $(x_1, x_2, \dots, x_k)$, one way to reconstruct the secret is to compute the Lagrange basis polynomials: $$\ell_j(x) = \prod_{1 \...


7

Is there an algorithm that can realistically generate keys for value of k between 1,000 and 1,000,000? How about Shamir's Secret Sharing method? For $k = 1000000$, generating a share would take a million field operations (multiplications and addition); this can be done in a few milliseconds per core (depending somewhat on the field you pick; there are CPU ...


7

Each person might be allotted more than one share of the secret. Let $G$, $C$ and $D$ denote the number of shares allotted to a General, a Colonel, and a Desk Clerk respectively, and let $T$ denote the Threshold of the secret sharing scheme. Then, we have that \begin{align} T &\leq 5G,\\ T &\leq 4C + 3D,\\ T &\leq 3G + 3D. \end{align} Can you ...


7

This problem is known as conditional disclosure of secret in cryptography. There have been many nice recent works on the subject, I suggest having a quick look at this one for example. In you exact scenario, can $r$ be of length $2n$? If so, here is a simple solution: call $(r_0,r_1)$ the left and right parts of $r$, each of length $n$. Alice sends $s + ...


7

This $(k,n)$ scheme works, but isn't very interesting. Effectively, it is: For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set. For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $\binom{3}{2} = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 ...


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