# 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

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

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

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

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

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

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

4

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

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

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

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

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 would appear that (for example) Shamir's original threshold secret sharing scheme would meet the requirements of 'post-quantum' (that is, remain secure even if that attacker has access to a Quantum computer). Let us assume that the shares were generated using a truly random stream; in that case, someone with $N-1$ shares (where $N$ is the threshold) does ...

3

I am not quite sure why you are looking for the kind you have mentioned in your question. But good old Shamir's polynomial secret sharing over finite fields, look here, provides information theoretic secrecy, i.e., even a quantum computer will not help you to break the secrecy.

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

2

The primary secret sharing methods in use for multiparty computation today are Shamir's and additive. I'm going to assume that you understand both. Additive No. When you go to reconstruct, you would have (simplified for 2 parties) $a_1b_1+a_2b_2\neq(a_1+a_2)(b_1+b_2)$. To prove it in the general case you would have to extend that analysis to $n$ parties. ...

2

This answer attempts to solve the original question, which gave a specific example - it certainly won't solve the generalised case now given! Create a threshold sharing scheme with $4$ shares (call them $1,2,3,4$) and a threshold of $3$ required for secret retrieval. Then, issue shares such that: \begin{array}{cl} A & 1,4 \\ B & 2 \\ C & ...

2

Your protocol is good (assuming an honest-but-curious adversary model). As DrLecter pointed out, each party will need to publish their sum of shares. To recover the answer, each party then simply xors all published values.

2

Shamir's secret sharing is based on mathematical splitting but not string splitting (as in programming languages) . So a key share cannot be considered same as partial key . Also the security is information-theoretic but not computational meaning no amount of computational power can reveal the complete secret if less than threshold secret shares are ...

2

Well, the first thing comes to mind is "what if your 'read-only location' isn't quite as read-only as you had hoped; if someone could modify your $f(i) \oplus k_i$ share, could they modify the reconstructed shared secret in a controlled way. In your first example, I believe they could. Let us assume that we are doing Shamir's Secret Sharing over the field ...

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

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

1

I'm not quite sure if I understand you correctly. As far as I understand it, you want to produce a threshold signature on the hash value of an X.509 certificate. It is not sure if you require a distribute key generation of the private key, or you are in possession of the signing key and distribute shares of the key to all stakeholders. 1) Actually, in ...

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