# Tag Info

8

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

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

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

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

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

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

4

The main misconception is, that Shamir's secret sharing is not a protocol. It states: If you have enough shares, then you can retrieve the information. And it is information theoretic. Waht does this mean? First off, there is no adversarial model in the sense of malicious or honest-but-curious adversary. It is out of scope of the protocol how and if ...

3

To answer your question, the cryptographic complexity will reduce by $2^{k-n}$ where $k$ is the key length and $n$ is the number of bits known. A slightly better scheme that doesn't use a cryptographic key sharing scheme can be as follows: Generate three random numbers $B_1$, $B_2$, $B_3$ with bit length equal to the size of your key $K_p$. Generate each ...

3

Just use Shamir's Secret sharing: wiki link It's designed by Adi Shamir, who is the "S" in RSA. It's fairly simple to use and there are no known weaknesses in it. While it doesn't split the data, splitting the key may work just as well (unless you absolutely must split the data.)

3

Start with “Shamir's Secret Sharing” concepts… Abstract. In this paper we show how to divide data D into n pieces in such a way that D is easily reconstructable from any k pieces, but even complete knowledge of k - 1 pieces reveals absolutely no information about D. This technique enables the construction of robust key management schemes for ...

3

I took a brief look at the code, but I fail to see how this transformation could introduce any additional secrecy. If the randomness used to define the polynomial is good, then Shamir's secret sharing provides information theoretic secrecy (no matter how the secret actually looks like). What Ricky points out in his answer seems reasonable, i.e., to provide ...

3

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

3

Well, first off, unless the updated shares hid a different secret, the problem is impossible (unless $k' = 0$, or you haven't distributed $k$ of the old shares). That's because, since at least $k$ people have the old shares, they can get together and ignore the new shares; instead, they use their old shares to construct the secret. If you need the new ...

2

Yes, that is possible -- that's exactly the problem that secure multiparty computation solves. You should start by reading standard references on secure multiparty computation. You might enjoy the following paper, and follow-on work: Secure Multiparty Computations on Bitcoin, Marcin Andrychowicz and Stefan Dziembowski and Daniel Malinowski and Łukasz ...

2

This is actually a fairly trivial case of secret sharing: In the first case, we select a random value $R$, we give $X$ the value $R \oplus M$, and we give both Y and Z the value $R$. Obviously, $X$ alone, nor $Y$ and $Z$ together cannot reconstruct $R$. In the second case, we select random values $R_1$, $R_2$ and $R_3$, we give: $R_1 \oplus M$ to $X$ ...

2

You can do it with two machines. https://www.iacr.org/archive/crypto2001/21390136.pdf (this paper is for DSA; it's easy to adapt for ECDSA). Here's an open-source JavaScript implementation of two-party ECDSA signing, using Bitcoin parameters: http://www.jpaulgossip.com/demo/split-key.html Unfortunately the protocol requires at least three rounds of ...

1

Reform the problem. Instead of each participant picking their givee (which they give to), have them select a giver (which they receive from). Each participant randomly generates a number (appropriately large) and anonymously submits it (e.g., via the tor network) to the site. This number represents them as giver. After all participants have entered, the ...

1

If you have $t-1$ shares of an $(t,n)$ system, you have a chance at learning of the roots of the system... as long as some of your shares have a 0 for the $y$ coordinate. You can't learn any other roots. Demonstration that the possession of a share with a $y$ coordinate of 0 gives you knowledge of a root (and forgive me if this is too obvious): A share ...

1

Just to be specific we are talking about information theoretically secure secret sharing, e.g. Shamir sharing. Lets say a secret $secret$ is shared in $n$ shares $S = \{s_1, \ldots, s_n\}$. Assume further party $P_i$ is given share $s_i$. If I understand your question correctly, you are asking if we give $P_i$ some share $r \ne s_i$ is there anyway for $P_i$ ...

1

Can you use threshold encryption and a mixnet? It might not be the fastest thing in the world but it uses well-understood components. Setup Every player generates an ElGamal keypair and proves knowledge of their secret key. The joint public key is the product of all public keys. (If you're worried about reset attacks, look up "Pedersen threshold key ...

1

Is /dev/urandom fine for my use-case or should I use /dev/random? Theoretically, there is no security difference as both are regarded to be cryptographically secure RNGs. Practically, you’ll want to use /dev/urandom as that is “non-blocking” since it re-uses it’s entropy-pool whenever it runs out of random data, while /dev/random may make your ...

1

The best way is to keep things simple. Once the key has been generated, keep it on the server and make sure only authenticated users can request the key from that location. Make all the clients request the key from the server.

1

Note that, despite your notation, the exponent does not need to be prime. Why is that? They probably do that to reduce the impact of malleability on the reconstruction process. Which attack does it prevent? It might prevent simple malleation when the secret is not easily guessable. Does it help when the secret has a short bit length? Yes.

1

As far as I know, you can not do multiplication with (m,m) shamir secret sharing. The typical method to do multiplication on shamir secret shares increases the degree of the sharing polynomial, which is why the parties run an additional protocol to reduce the degree. That is why the degree of the sharing polynomial must be less than $m/2$ if there are $m$ ...

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