# Tag Info

6

In Shamir's secret-sharing scheme, the secret and the shares of the secret all are elements of a finite field, and so necessarily have the same size. In the Reed-Solomon code based variant of Shamir's secret-sharing scheme proposed by the late Bob McEliece and myself (R.J. McEliece and D.V. Sarwate, "On sharing secrets and Reed-Solomon codes", Communications ...

6

If you reuse the same multiplication triples, then you leak information about the secret shared values that you multiply. Let's recall how the multiplication works in Beaver's protocol for secure evaluation of arithmetic circuits. Protocols like the ones from the SPDZ family follow Beaver's blueprint and "just" add some additional magic on top for getting ...

5

Except for the extensibility (being able to latter add a third user), the trivial scheme with XOR works just as well as Shamir; the trivial scheme retains the following properties: The length of each share is still as long as the original secret (in fact, you don't need to bother assigning share identifiers, which you have to with Shamir's scheme) It is ...

4

You've described an $n$-of-$n$ threshold encryption scheme by nesting: there are $n$ shares of a secret key, and it takes all $n$ of them (in the right order, so I hope you labeled them) to recover the plaintext. Similarly, there's a simple $1$-of-$n$ threshold encryption scheme by concatenation, which is what, e.g., OpenPGP uses for multiple-recipient ...

4

As SEJPM notes in the comments above, an information-theoretically secure threshold secret sharing scheme (such as Shamir's secret sharing) has two properties that it needs to satisfy: any subset of at least $t$ shares must allow the secret to be unambiguously reconstructed, and no set of $t-1$ or fewer shares may reveal any information about the secret (...

3

A permutation on a set is a bijection from the set to itself; thus $\sigma$ is a (bijective) map from $P$ to itself, not from $p(P)$ to itself (though it does induce a map from $p(P)$ to itself in a natural manner). Also, if $f$ is a map from $A$ to $B$ and $X$ is a subset of $A$, then $f(X) = \{f(x), x \in X\}$. This is completely standard notation. For a ...

3

Secure computation over incomplete networks has been the subject of several works in the past. However, as far as I am aware of, none of these works uses the model of rational cryptography, where the agents are modeled in a game-theoretic way as rational players rather than computationally-bounded machines. The most classical setting of secure computation ...

3

To share a vector using Shamir's secret sharing, you can just share each element of the vector independently. It really is that simple. To save some space, you can assign all the shareholders a distinct fixed non-zero $x$ coordinate and reuse those same $x$ coordinates for all elements of the vector being shared. The $x$ coordinates only need to be ...

2

More generally, is it possible to construct a $(k,n)$ threshold secret sharing scheme (i.e. let than k shares leaks no statistical information about the secret) such that possession of the secret along with fewer than $\left\lfloor \frac{k-1}{2} \right\rfloor$ is enough to reconstruct the entire key (i.e. the entire polynomial)? Well, if that's the problem ...

2

So, if you have a $(k,n)$ threshold scheme, this means that your polynomial is of degree $k - 1$. That means you need $k$ points to interpolate the polynomial. The secret is just another data point. So, to reconstruct the very same polynomial used initially, possession of the secret should not help. You'd still need enough $(x,y)$ pairs to get back to the ...

2

As already pointed out in the comments there is nothing special about a vector, right? So you could just transform it to some binary representation and use Shamir secret sharing to distribute the shares among the shareholders. If you say each component of your vector is viewed as a secret you could use multiple applications of the secret sharing protocol. ...

2

You have four equations and two unknowns. Any two of those equations should therefore be solvable, and all pairs that don't include the cheater should yield the same solution. (You don't actually need to solve all six possible pairs of equations if you know there's at most one cheater. It's sufficient to e.g. just solve equations 1 & 2, and check ...

2

This is "half an answer" while I think about the other half :) EDIT: other half added below. The mathematical model that I find most useful for all discrete logarithm based cryptography is that of a vector space over a finite field. In many ways, the multiplicative-group implementation and the elliptic curve implementation are isomorphic, although it can ...

2

Aren't they delievering by the network the same as the encypted messages? No. At least not in the plain. What doing it end-to-end encrypted? Try to search for the key agreement protocol (e. g. Diffie-Hellman ) and asymmetric encryption (e.g. RSA ). The "asymmetric" encryption allows sending encrypted and signed messages without sharing the private (...

2

I really don't understand what each participant hold and how to recover the secret s in this complicated scenario. Part of the issue you're running into is that the method to implement the original scheme is not uniquely defined, and so what the various parties hold (and how they would recover the secret) would vary based on things not specified in the ...

2

Here's one way to approach the question: if we have a $(n, t)$ Shamir secret sharing system, and we have $t-1$ shares $(x_0, y_0), (x_1, y_1), …, (x_{t-2}, y_{t-2})$, then all we can deduce that the secret polynomial is of the form: $$P(x) + c \prod_{i=0}^{t-2}(x - x_i)$$ where $P(x)$ is a computable polynomial (exactly what that polynomial is depends on ...

1

GMW protocol says that A and B can locally compute $c_i = a_i \oplus b_i$ and the result should be same for both. I highlighted the part that is incorrect. They started with secret shares of $a=0$ and secret shares of $b=1$. Now they have secret shares of the XOR $c= a \oplus b =1$. Only if the secret value $c$ is zero will their shares be the same (and ...

1

My question is: since $s$ is an element in $Z_q$, shouldn't $b_js_j$ be also calculated $\mod q$? Doesn't really matter - the results come out the same either way. We know that the order of $C1$ is $q$, and so we have $x C1 = (x+q)C1$ for any $x$. Hence, we have $b_js_j C1 = (b_js_j \bmod q) C1$ In practice, we generally want to reduce $b_js_j$ mod $q$ ...

1

Yes, there is. And it generalizes easily to requiring any $k$ out of $n$ keys, not just 3 out of 5: Generate a random key for some symmetric encryption scheme (say, AES-SIV). Encrypt your data with that random key. Use a threshold secret sharing scheme such as Shamir's secret sharing to split the random key into $n$ shares, such that any $k$ of them are ...

1

But for another three share holders is can't reconstruction secrete. Sure they can. In the field $GF(17)$, we have: $$\frac{43}{3} = \frac{9}{3} = 3$$ because $43 = 9 \pmod {17}$, and $3$ is the value that, when multiplied by 3, gives us 9 modulo 17. And, we have: $$\frac{23}{2} = \frac{6}{2} = 3$$ beause $23 = 6 \pmod {17}$, and $3$ is the value that,...

1

It is correct to me. Polynomial is not evaluated in the elliptic curve group $G$, but in $F_q$ (where $q$ is the order of $G$), which is a field because $q$ is a prime number. To be clearer, I add brackets to the equation you gave: $$X_i = \prod_{j=0}^{t-1} (C_j)^{{i}^j} = \prod_{j=0}^{t-1} (g^{\alpha_j})^{ i^j}= (g)^{ \sum^{t-1}_{j=0} \alpha_j i^j}$$ You ...

1

Does the "collusion" mean any possibility that t shares in the servers are somehow assembled? It refers to the possibility that t or more server admins/owners collude to pool their shares to break protocol. Regarding the follow-up questions: non-collusion is in this context in regards to server operators being malicious. Malicious clients are considered a ...

1

1

Here is one possible approach: The dealer generates a group suitable for a Pedersen commitment scheme (namely, an Elliptic Curve with prime order $p$, and two elements $G, H$ where no one knows the discrete log of $H$ with respect to $G$) - we can do this in a multiplicative group; I just find the additive notation a bit easier in this case, as the notation ...

1

Defining $l_{i} = \prod_{m=1, m \neq i}^{t+1}{ \frac{m}{i - m}}$ works perfectly fine. I have done a port of rust-threshold-secret-sharing using curve25519-dalek with positive results.

1

Use a trusted messenger. If possible, transfer the OTP yourself. Sending OTP keys over the Internet is usually not a very good idea because "the distribution itself won't deliver perfect security" and one must worry about "integrity and authenticity", as Maarten Bodewes has said. Moreover, it is reasonable to assume that using a OTP might attract some ...

1

Transposition and substitution are heavily used in today's block ciphers. S-box means substitution box, and P-boxes transpose bits. When you say transposition cipher you are referring to classical cryptography. The heyday of the transposition cipher was before the end of World War I. The ADFGX and the ADFGVX were fractionated transposition ciphers used by ...

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