# Tag Info

10

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.

7

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

6

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

5

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

5

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

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

4

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

4

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

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

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

4

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

4

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

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

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

4

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

3

As poncho and Maeher have noted, this isn't possible with straightforward Shamir's secret sharing. In fact, it's pretty obvious, once you think about it, that there's no way to choose more than $k$ shares independently in advance and get a consistent secret out of them with any unconditionally secure $k$-out-of-$n$ threshold secret sharing scheme, even if ...

3

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

3

One simple way would be to use Trivial secret sharing: Split DOCUMENT in half into DOCUMENT1 and DOCUMENT2. Choose BITS1 and BITS2 uniformly and independently at random from binary strings of length equal to the lengths of DOCUMENT1 and DOCUMENT2, respectively. Give BITS2 and (BITS1 xor DOCUMENT1) to not-quite-trusted 3rd party A, and BITS1 and (BITS2 xor ...

3

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

3

You seem to be assuming that you will take the key, and give half the key bits to each party. While this can be made to work, there are cleverer ways to do this: You can pick an N bit random number (where N is the length of the key), and give one side that random number, and the other that random number xor'ed with the key. That way, neither side has any ...

3

The index $i$ is running through the $n$ possible participants (1=Alice, 2=Bob, 3=Charlie, 4=Dave, and 5=Eve). Now to be able to easily refer to the $t$ out of $n$ persons — required by the threshold scheme — the index $i_j$ is used: $i_1$ is the first of the $t$ people taking part to the decryption, $i_2$ is the second, ..., $i_t$ is the $t$-th. ...

3

The answer is definitely yes. You should be able to do what you are looking for. The computation is very simplistic, so using existing MPC protocols will be efficient. Many of the existing protocols are able to evaluate a few blocks of AES using MPC per second, so this computation will be no problem. Typically MPC works by translating your function into a ...

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

It depends on what you mean by interaction. Some protocols for secure multiparty computation, e.g. those based on Shamir secret sharings and the GMW protocol, require the servers to communicate a lot during the computation. In other protocols, such as those based on Yao's garbled circuits (e.g. Fairplay MP), the interaction between servers is reduced in ...

3

The security concern is that the result of that operation will be guessable without the secret number, since the later part of that answer explains why it also applies to SHA-256. (Also, $\:$ SHA256(A+"") = SHA256(A)$\:$.) The random number should be long enough to make brute-force highly infeasible. If it is and you publish HMAC(A,"") and present them ...

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

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

3

It is informationally secure (assuming $p$ is prime). In general, we can create an $(n,n)$ secret sharing method (that is, one that generates $n$ shares, and which requires all $n$ shares to reconstruct the secret) by taking any group $G$ with group operation $*$, mapping the shared secret into a group member $s$, selecting $n-1$ random (uniformly ...

2

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

2

Not enough information was provided in the question, so I'm going to assume something to fill in the hole. Let me know if this is not what you envisioned. Assumption: The party trying to detect the cheater knows the original polynomial used to share the secret. In the initialization phase, each party $p_i$ is given a pair $x_i, y_i$ where $y_i = f(x_i)$. ...

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