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

6

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

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

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

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

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

The answer is definitely yes. You should be able to do what you are looking for. The computation is very simplistic, so using existing MPC protocols will be efficient. Many of the existing protocols are able to evaluate a few blocks of AES using MPC per second, so this computation will be no problem. Typically MPC works by translating your function into a ...

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

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

3

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

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

All too often I describe some process saying that "he" did something to "his" message, and it makes sense in my own head, but no one else can figure out which of the several people involved that those pronouns refer to. Or worse -- sometimes I say that "the message is encrypted", but I don't say who does it and with which key. That's why all the good ...

2

Have you considered using Shamir's Secret Sharing algorithm? First, Bob encrypts the message with a symmetric algorithm. Then, he divides the secret key into four parts using SSA such that it requires three parts to decrypt (a $(3,4)$ threshold). Bob then distributes one part each to Alice and Mark, and two parts to Jim. When Alice wants to decrypt, ...

2

Well, Shamir Secret Sharing is done using a field $GF(p^k)$, for some prime $p$ and some integer $k$. A share consists of two integers $(x, y)$, where $0 \le x, y < p^k$. So, the obvious way to express a single share $(x, y)$ as a single value would be to use the value $x p^k + y$ (using integer arithmetic, not field operations); each potential share ...

2

It has to do with which modulus you use. You did all your arithmetic modulo 11. However, when using Feldman's VSS, you gotta use two different moduli (using each one in the appropriate spot). In your example, you shouldn't do all arithmetic modulo 11. Instead, you should be doing some arithmetic modulo 11, and some arithmetic modulo 5 (the order of $g$ ...

2

All of this arithmetic must be done modulo $p$ (for some prime $p$ that is large enough so that it'll be larger than any conceivable $K$ you might ever want to use). You need to pick $p$ in advance. Once you've picked $p$, then you choose $a$ and $b$ uniformly at random from the set of integers modulo $p$, i.e., uniformly at random from the set ...

2

I don't think the approach you sketched helps very much. If the server is compromised, the attacker can pretty easily modify the server-side software to log and record all the cryptographic keys, and then you haven't gained anything. Therefore, I don't think the approach you sketch is likely to be a great way to spend your limited software development ...

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 question makes no sense to me. You probably will need to edit it. It makes no sense to ask for the users to "agree" on anything, since the other$n$parties have absolutely no information about$D$other than what is provided by$u$. So, your requirements don't make any sense to me. If the output of the protocol depends only upon$D$, and if one ... 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 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 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 ...

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