Hot answers tagged secret-sharing
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
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
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
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 ...
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$ ...
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
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
Have you considered using Shamir's Secret Sharing algorithm?
First, Bob encrypts the message with a symmetric algorithm. Then, he divides the secret key into four parts using SSA such that it requires three parts to decrypt (a $(3,4)$ threshold). Bob then distributes one part each to Alice and Mark, and two parts to Jim.
When Alice wants to decrypt, ...
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
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
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
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
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 ...
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 = ...
1
The easy way to reconstruct the secret is using Neville's algorithm.
Basically, let the array y contain n shares (assumed to be represented as the type gf_t here), let the array x contain the points at which the polynomial was evaluated to generate those shares, and let sub(), mul() and inv() be functions/macros that perform the appropriate finite field ...
1
All too often I describe some process saying that "he" did something to "his" message,
and it makes sense in my own head, but no one else can figure out which of the several people involved that those pronouns refer to.
Or worse -- sometimes I say that "the message is encrypted", but I don't say who does it and with which key.
That's why all the good ...
1
Yes. Threshold cryptosystems come under the secure multiparty computation branch of cryptography.
Essentially, threshold cryptosystems require multiple parties to cooperate in order to decrypt a ciphertext.
Secure multiparty computation is a field of study involving cryptosystems that require more than one party to compute an operation. As such, threshold ...
1
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 ...
1
The best answer is to use verifiable secret sharing (VSS), as I describe here: http://crypto.stackexchange.com/a/6618/351
VSS gives the best parameters and best solution to this problem. If you have a $k$-out-of-$n$ secret sharing scheme, VSS can detect any cheater and enable you to reconstruct the secret as long as you have at least $k$ good shares (even ...
1
The Lagrange interpolation polynomial $L(x)$ is evaluated at $x=0$ to get the secret (the constant term). It can just as easily be evaluated at any $x$ to get another share. This requires that the threshold $k$ number of shares are present, just as they would be required to evaluate $L(0)$ to get the secret.
This approach does not require one to store the ...
Only top voted, non community-wiki answers of a minimum length are eligible
