Hot answers tagged secret-sharing
9
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.
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
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 ...
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
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$
...
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 ...
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)$.
...
2
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 ...
2
Assuming each participant $i$ has a key-pair $(x_i,y_i)$ for an asymmetric encryption scheme (with $x_i$ being the private and $y_i$ the public key), you can divide your secret as
$$ S_i := \operatorname{Enc}(y_i, S).$$
Then each participant can retrieve the secret as
$$ S = \operatorname{Dec}(x_i, S_i).$$
Of course, simply giving each participant $S$ ...
2
It depends on the particular scheme. In a simple challenge-response scheme, the server sends a challenge, the client "encrypts" the challenge and the password to form a response, and then the client sends the response over the wire.
However, standard logins typically don't use challenge/response. The password is just sent to the server by the client. When ...
2
In general, an $(n,k,k')$ erasure code must have the property that any $k'$ out of $n$ symbols must be sufficient to recover the original $k$-symbol message.
An $(n,k')$ threshold secret sharing scheme, however, requires an additional property: knowing less than $k'$ shares out of $n$ must not be sufficient to recover any information about ...
2
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. ...
2
Yes and no.
A threshold cryptosystem means the decryption key can be split into $n$ shares such that only $t\leq n$ are required to recover it. That property in isolation is not useful for multiparty computation.
However when you combine a threshold cryptosystem with one that is at least partially homomorphic (meaning you can do some operation, like ...
2
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 ...
2
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$ ...
2
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 ...
2
The formula you are looking for is Lagrange Basis Polynomials. Essentially, each share consists of two values, an x coordinate and an y coordinate. The x coordinate might, depending on your specific needs, be implicitly determined by context, such as a preexisting identifier for the entity holding the share. The only requirement is that it is non-zero and ...
2
Suppose $s_0, s_1, s_2, \ldots, s_{k-1}$ are
elements from the finite field you are working in, where $s_0$ is the secret
to be shared, and the $s_i, i > 0$ are randomly chosen nonzero elements of
the field. Then, the polynomial used to construct the shares is
$$S(x) = s_0 + s_1x + s_2x^2+ \cdots + s_{k-1}x^{k-1}$$ and the shares
themselves are $y_i = ...
2
I don't think the approach you sketched helps very much. If the server is compromised, the attacker can pretty easily modify the server-side software to log and record all the cryptographic keys, and then you haven't gained anything. Therefore, I don't think the approach you sketch is likely to be a great way to spend your limited software development ...
Only top voted, non community-wiki answers of a minimum length are eligible
