Tag Info

Hot answers tagged

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

We simply have to trust this party because this scheme requires a trusted dealer (a party that distributes the shares to the secret to the participants - this can be you or some other party - but if its you you should trust yourself). We can use verifiable secret sharing, that allows the parties to check whether the shares they have obtained are consistent, ...


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

The process is pretty simple. As you say, each party multiplies their two shares. They then use Shamir secret sharing to share the resulting value with the other parties. Once they have received a "subshare" from each other party, each party simply runs Lagrangian interpolation on the subshares they received (plus their own subshare). The result is a share ...


5

Here's an easy way to do it: Take your secret $S$, and select a random value $R$ of the same size, and compute $T = S \oplus R$ Give the accountant the value $R$ Use a $(k-1, n-1)$ secret sharing method to share $T$ to the other parties. The accountant plus any set of $k-1$ other parties can reconstruct the secret. And, any smaller subset cannot get any ...


5

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


5

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


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

The purpose of the reconstruction of the polynomial $P(x)$, is just to calculate the value of $P(0)$, which equals the shared secret value. If Lagrange polynomials are used, a trivial optimization which cuts the number of multiplication nearly in half is $$P(0) = (\prod_{i=0}^{n-1}{-x_i})\sum_{i=0}^{n-1}{{\frac{y_i}{-x_i (\prod_{j=0,j\neq ...


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

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

First note that using MPC we can compute addition, subtraction, multiplication and division (multiplication by the inverse) on shares. It turns out there are also secure protocols out there for doing comparison (see http://viff.dk and their references). So we could simply do something like this: while k >= m: k = k-m $m$ could be public or secret ...


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

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

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

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


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

You really only need to do step 1. If each party has shares of x and y (say $x_i,y_i$) then $z_i=x_i+y_i$ is a valid sharing of $z=x+y$. What you are doing is used to multiply shares. Multiply, share the shares, reconstruct. In that case everything you said is correct. The reason this is needed in multiplication of shares and not addition can be seen by ...


2

I think there's a better way to do this, and I'm not sure the existing answers check all your boxes. I suggest using secret splitting together with asymmetric keys so that: Nobody but you can write data. Shareholders can come together to read data. Each shareholder can individually verify, but not read data. You can read and write data at any time. ...


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

If you don't update the shares, then any $T$ share holders will be able to reconstruct only the original secret $S_{\scriptstyle{\text{old}}}$, and not the updated version $S_{\scriptstyle{\text{new}}}$. Instead of providing all the $N$ share holders with new shares to use in the reconstruction process you could consider informing all $N$ to simply XOR ...


2

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


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

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

The reason that a field must be used in Shamir's reconstruction scheme is that the calculations used in the reconstruction need to divide one "number" by another, and division is not defined in $\mathbb Z$, the set of integers: $\frac{m}{n}$ is not necessarily a member of $\mathbb Z$. So, why not use $\mathbb R$, or $\mathbb Q$ which can be "implemented" in ...


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

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



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