# Tag Info

12

Splitting a key does not reduce the key strength at all. Simply generate two random 128-bit strings and give one to each party. Encrypt the data with the exclusive OR of the two random strings. Each string alone gives no information whatsoever about the final key, assuming your random number generator is sound. No party has any advantage.

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

8

Simplified SSLv3/TLS from this book Note, $R_{(Alice|Bob)}$ is a random nonce chosen by Alice or Bob respectively, and $\{S\}_{Bob}$ is encryption with Bob's public key. pre-master secret As stated in one of the answer you link to, "The point of a premaster secret is to provide greater consistency between TLS cipher suites." In the figure above, the ...

7

Just tell the whole secret to each person.

7

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

7

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

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

Suppose we have a $(k, n)$ threshold scheme meaning that there are $n$ shares of a secret distributed to different parties, and any $k$ shares can be used to re-create the secret. A new person joins the club and wants to have a share of the secret too. I contend that the secret must be available to a trusted party who can create the extra share. Because ...

6

I'd like to suggest a potentially interesting reformulation (or variant) of the problem as a form of secure multi-party computation: Given $k$, $n$ and $m$, is there a protocol by which $n$ participants $i \in \lbrace 1, \dotsc, n \rbrace$ may, without the help of a trusted external party, each compute a share $s_i$ such that there exists a ...

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

Well, no, in general, you won't be able to select arbitrary points $X, Y, Z$ and $Q$ that would work in a Shamir secret sharing scheme (unless $k\ge4$). Here's why; Shamir's scheme assumes that the points are on some polynomial of degree $k-1$ or less; for $k=2$, this means that the points all must be solutions of a linear equation $y = a_1 x + a_0$ for ...

5

On a general basis, no. If $t \lt n$, then the first $t$ values $x_1$ to $x_t$ are sufficient to rebuild the secret $S$, regardless of the values of $x_{t+1}$ to $x_n$. Therefore, those last values have no influence whatsoever on $S$. On the other hand, values $x_{n-t+1}$ to $x_n$ should be sufficient to also rebuild the secret, and since the last $t$ of ...

5

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

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

I assume you're referring to section 5 of the paper you linked to, which reads: 5 An instance using polynomials In this section, we describe an instance of the technique of Section 4 using Shamir's secret sharing scheme [25]. In this scheme, $\mathrm{hpwd}_a$ is shared by choosing a random polynomial $f_a \in \mathbb Z_q[x]$ of degree $m - 1$ ...

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

5

Any deterministic secret sharing scheme as in the question has the property that any participant can run the deterministic algorithm for a guess of the shared secret, and eliminate the guess if the share that the algorithm deterministically assigns him/her does not match his/her share. This implies that some information about the secret is leaked in his/her ...

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

You could view it as a form of One-Time-Pad encryption. In this view one of the two "messages" is the key and the other is the ciphertext (it does not matter which you think of as which as their roles are symmetric). It may, however, be more natural to think of as a simple secret sharing scheme. Roughly speaking a secret sharing scheme is a scheme where a ...

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

A trivial example showing that this is possible, at least in some cases, is the $n$-out-of-$n$ secret sharing scheme based on modular addition. Let $s \in \mathbb Z / m \mathbb Z$ be the secret, and construct $n$ shares of it by picking $x_1, \dotsc, x_{n-1}$ randomly from $\mathbb Z / m \mathbb Z$ and letting $x_n = s - (x_1 + \dotsm + x_{n-1}) \mod m$. ...

4

The usual method of "splitting a key" $K$ into two keys $K_0$ and $K_1$ given to two parties, for the purpose described, is as follows: generate $K_1$ randomly, of the same size as $K$; set $K_0 = K \oplus K_1$. "Joining" $K_0$ and $K_1$ into $K$ is simply $K = K_0 \oplus K_1$. This construct is such that each of the two parties gain absolutely no ...

4

Actually, this appears to be quite straight-forward. I'll give you an example of this using Shamir's original method: in Shamir's method, the trusted party which generates the shares picks a random polynomial, with the secret as the constant element, and then evaluates that polynomial over various nonzero element, and distributes the pairs $(e, P(e))$ as ...

4

With Shamir's secret sharing for the case of $k$ out of $n$, you construct a random polynomial of degree $k-1$, because $l$ points uniquely identify a polynomial of degree $k-1$. The usual way to construct said polynomial is to uniformly choose coefficients $a_1$ through $a_{k-1}$ and setting $a_0=s$. There is an alternative to that, where you choose $k-1$ ...

4

Well, Shamir Secret Sharing is done using a field $GF(p^k)$, for some prime $p$ and some integer $k$. A share consists of two integers $(x, y)$, where $0 \le x, y < p^k$. So, the obvious way to express a single share $(x, y)$ as a single value would be to use the value $x p^k + y$ (using integer arithmetic, not field operations); each potential 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 ...

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