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

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

10

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

8

Just tell the whole secret to each person.

8

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

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

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

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

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

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

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

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

6

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

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

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

I believe there is strong enough precedence for using the term threshold decryption for the second. The abstract of this paper states: A threshold decryption scheme is a multi-party public key cryptosystem that allows any sufficiently large subset of participants to decrypt a ciphertext, but disallows the decryption otherwise. Sounds to me like what ...

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

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

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

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

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

Assuming that $p$ is prime, then you are in a cyclic group. Consequently, this is identical to considering the shares $s_i$ as "exponents" of a generator $g$ of $Z_p^*$. Now we can write: $s_1 = g^{s'_1}, \ldots,s_{k}=g^{s'_{k}}$ and $s=\prod_{i=1}^{k} s_i$ Or we can view this as: $s = g^{\sum_{i=1}^{k} s'_i}$. Consequently it looks like a perfect (= ...

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

In a short paper "On sharing secrets and Reed-Solomon codes," Communications of the ACM, vol. 24, pp. 583-584, September 1981, Bob McEliece and I described a secret-sharing system that uses no randomness (cf. the second paragraph of the paper). This is most useful for very large secrets (lots of bits) since it divides the secret into $k$ parts, and then ...

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