# Tag Info

## Hot answers tagged secret-sharing

7

I assume that your question relates to sharing a secret specifically of this form. Furthermore, you want to guarantee this even if the dealer is not trusted and may try to share a secret of a different form. Otherwise, you could just use any secret sharing (or verifiable secret sharing) scheme. However, note that $s$ as you wrote actually does not have any ...

7

This cannot be achieved information-theoretically. This is typically the task that requires multiparty computation protocol to be achieved. In particular, the common method for what you want is called "secure multiplication protocol", and is in general constructed from an additively homomorphic encryption scheme (over the ring $R$), or from oblivious ...

7

With Shamir's Secret Sharing you can add as many shares as you want, as long as the threshold and the secret is unchanged. You can see that neither the generation of the polynomial that produces the shares nor the reconstruction of the secret by polynomial interpolation require the parameter $N$ (number of shares), but only the threshold $k$. Of course ...

6

Yes, preprocessing Beaver triples in an offline phase leads to a faster online phase. The online phase of an AND gate requires just two openings plus local computations. But there are other advantages as well. Define a "linear representation" $[x]$ to be any way of representing/distributing a value $x$ among parties such that the following properties hold: ...

6

I believe there is strong enough precedence for using the term threshold decryption for the second. The abstract of this paper states: A threshold decryption scheme is a multi-party public key cryptosystem that allows any sufficiently large subset of participants to decrypt a ciphertext, but disallows the decryption otherwise. Sounds to me like what ...

6

Let us first consider the problem without involving Shamir secret-sharing at all. Suppose that $n = 140$ and that the secret $\sigma$ is a 140-byte Twitter message. The space is thus restricted considerably, from all possible $256$ byte values to the printable characters permitted to be used in Twitter messages, and the distribution in this restricted space ...

5

You are right that if it costs Alice & Bob effort $N$ to agree on a key in this way, then it costs Eve only effort $N^2$ to find it. So the protocol is not secure in the standard sense, and probably not very useful. (Maybe in some highly constrained situation with very short-lived keys?) More generally, this purports to be a key agreement protocol whose ...

5

Shamir Secret Sharing (SSS) is based on constructing a polynomial of degree $t-1$, whose independent term is the secret $S$. Each share is actually a point of the polynomial. The security of SSS is based on the fact that, when one wants to interpolate a polynomial of degree $t-1$, one needs at least $t$ points of the polynomial. It can be seen graphically ...

5

You could view it as a form of One-Time-Pad encryption. In this view one of the two "messages" is the key and the other is the ciphertext (it does not matter which you think of as which as their roles are symmetric). It may, however, be more natural to think of as a simple secret sharing scheme. Roughly speaking a secret sharing scheme is a scheme where a ...

4

Is the Kurihara algorithm really what it purports to be (dramatically faster but equally secure replacement for Shamir Secret Sharing)? The algorithm being referred to is in this paper, and I believe that the speed benefits are at best marginal, if not nonexistent. As for the speed benefits being marginal, well, normally we use secret sharing as a part of ...

4

Take a linear polynomial: $y=mx+b$. If I tell you that the point $(1,5)$ is on the line, can you tell me $m$ and $b$? No, because in fact there are infinitely many lines that pass through the point $(1,5)$. It takes 2 points to uniquely identify a line. In general it takes $t$ points to uniquely identify a degree $t-1$ polynomial. Furthermore, given $t-1$ ...

4

Shamir's $(t,n)$ secret sharing scheme involves picking a random polynomial $p$ (over a finite field) of degree $t-1$, such that $p(0) = s$ is the secret value to be shared (this is easy to do, since $p(0)$ is just the constant term of the polynomial), and then evaluating the polynomial at $n$ distinct non-zero points $x_1, \dotsc, x_n$ to construct $n$ ...

4

I don't believe that, in the example you gave, you can reconstruct the secret using two shares. $d + \alpha m_0$ is in the range $[0, 2431)$; using the two shares $1 \bmod 11$ and $3 \bmod 19$, you can determine that it is one of $155, 364, 573, 782, 991, 1200, 1409, 1618, 1827, 2036, 2245$, however you have no further information about which it might be. ...

4

Optimality is actually not a well-defined term for secret sharing, and can refer to a number of different issues. First, one issue that is often considered is the size of the share that each party holds in the scheme. If the size of a party's share equals the size of the secret itself, then the secret sharing scheme is called ideal. (Formally, we don't talk ...

3

There is one theoretical difference between Shamir's scheme and Asmuth and Bloom's scheme. Shamir can be done in an informationally secure manner; specifically, if the nonconstant polynomial coefficients were chosen in a random manner (that is, from a uniform probability distribution that's uncorrelated to anything else the attacker can see), then someone ...

3

My question is whether one can start with both a secret and a string - representing ultimately a share in the end state - and work his way into finding the rest of the shares? With $t-1$ shares and the secret, you can uniquely reconstruct the polynomial (and with that, generate all the rest of the shares, assuming you know their $x$ coordinates). With ...

3

Shamir secret sharing is information theoretically secure. This holds as long as the attacker knows fewer than $t$ shares. So, even with $t-1$ shares, the attacker still knows nothing about the secret. So a brute force attack given $t-1$ shares is impossible, even an attacker with infinite computing resources could not brute force the secret. Using a ...

3

there are some special constructions that could be used. for example see this paper of florain kerschbaum (freely available version). also, you can use some secure DFA evaluation protocols, as any regex can be represented as a DFA. what you have proposed is not secure and the servers can learn lots of information.

3

This is because $t$ shares uniquely defines the polynomial of degree $t-1$. $t-1$ shares still leaves $k$ possible and equally likely polynomials, for $k$ the size of the field, so the secret is information theoretically hidden. Think of a degree 1 polynomial, essentially a line. If you know just one point on the line, you cannot say anything about the ...

2

An easier way of explaining it is here: http://www.demoivre.org/courses/CIS628/chapter15.pdf So for a point $(x_0,y_0,z_0)$ we set $x_0$ as the secret and then randomly choose $y_0$ and $z_0\pmod{P}$. Now we generate our plane to distribute to the participants: we pick two random integers $a$ and $b$, then we set $$C = z_0 - ax_0 -by_0 \pmod{P}$$ we now ...

2

The coefficients must be uniformly chosen. If you do not choose your coefficients uniformly, then by Kerckhoff's principle, the attacker knows this, and that makes it easier than normal to reconstruct the polynomial, and thus to obtain the secret.

2

This is string notation: $J_i^0=0^{i-1}10^{k-i}$ means i-1 consecutive 0's followed by a 1 (we don't write $1^1$) which is then followed by k-i consecutive 0's. So $0^{3}10^{4}$ is $00010000$. As for $S^t[i,x]=\langle J_i^t,x\rangle$, with $t\in \{0,1\}$ this is an inner product of $J_i^t$ with $x=(x_1,\ldots,x_k) \in \{0,1\}^k$ so in general $S^t[i,x]=x_i$ ...

2

If I understand the question right, what you are looking for is a fair secret sharing protocol. Most secret sharing protocols are unfair. For example, in 3-out-of-4 secret sharing with 2 dishonest parties, once one honest party broadcasts their share, the two dishonest parties can privately collude to reconstruct the secret. Then if they refuse to ...

2

First, you should always use HMAC with the secret data as the key and the (possibly) public data as the message. The proof of its security relies on that. So rather than concatenating the static key to the message, you might want to consider concatenating it to the secret key. Second, the extra hash doesn't add any security. Anyone who knows the secret key ...

2

The dealer is one of n participants or it should be from outside? The dealer, knows the secret as he's the one who shared it. Thereby it makes no sense to give him a share as well, unless you have a such a scheme that requires all partys to collaborate to recover the image, but then the question becomes: "Why bother secret sharing at all if the dealer ...

2

I too had to go through this decision some time back and did a comparative study of both schemes. Shamir's scheme is used for the majority of works in the area of threshold secret sharing. This is because of the foremost reason of the number of primes required in both the schemes. Asmuth-Bloom's scheme require $n+1$ ($n$ being the number of shares) prime ...

2

Shamir's scheme is the most widely used scheme in such things as multi-party computation, threshold cryptography and oblivious transfer. Honestly I don't really know of any real everyday use of secret sharing based on CRT. As Artjom said Asmuth and Bloom's scheme takes some time to setup. The dealer must choose pairwise relatively prime integers $m_0 < ... 2 Yes we can do better. Secure approaches exist. We implemented regular expression matching in the ShareMonad, which is secure in the semi-honest setting. IIRC, the paper touches on our DFA construction and selected algorithm - which is the hardest part really. Once you know the algorithm it's just a matter of turning the crank. 1 You can use a variant of the standard "degree reduction" trick from secret-sharing-based MPC protocols, but use it to increase the degree instead. You start out with a$(k,n)$-sharing of a value$s$. Denote the collective object by$[s]_k$, meaning that party$i$has private value$p(i)$where$\deg(p) < k$and$p(0) = s\$. Just so we're on the same page: ...

1

Yes, your scheme is trivially correct and secure. This follows from the fact that: Shamir's secret sharing is correct: any group of participants with at least the threshold number of shares can reliably reconstruct the secret; and Shamir's secret sharing is perfectly secure: no group of participants with less than the threshold number of shares can learn ...

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