19

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


18

It's impossible. In order to be perfectly hiding, it must be the case that two different messages can produce the same commitment string. But then that commitment can be opened in two ways (by an unbounded committer), so the scheme is not perfectly binding.


12

Here is an active attack on the privacy of out-of-the-box SSS. For this attack, we'll assume that the attacker (without a valid share) is allowed to participate (with $T-1$ friends with honest key shares), jointly use the protocol to recover a 'shared secret' (which might not be the real shared secret); we'll assume that this shared secret recovery process ...


8

In RSA as usually practiced (encryption or signature per PKCS#1, signature per X9.31, ISO/IEC 9796-2, FIPS 186), it is NOT necessary, or even common, to require $n=p⋅q$ with $p=2⋅p′+1$ and $q=2⋅q′+1$ with $p'$ and $q'$ huge primes, as stated in the question. IF that's done, it ensures that: any small odd $e>2$ (including the common $e=3$ and $e=65537$) ...


7

Full disclosure: In 2007 I founded an association aiming at voting transparency. I'm proud that my efforts may have had some role, however small, in the fact that the number of French cities using electronic voting machines for political elections, then growing, has been declining since then. The book defining the protocol of the question is made freely ...


7

Actually, there are also other reasons why one wants to use safe primes in the RSA setting (when working with hidden order groups in cryptographic protocols). When choosing the RSA modulus $n=pq$ to be the product of safe primes $p=2p'+1$ and $q=2q'+1$, then we also have the following: The subgroup of $Z_n^*$ of qadratic residues is cyclic and has order $...


7

Safe primes (that are two times a prime plus one) and strong primes were at some point in time considered sensible. One reason was that safe primes ensures that Pollard's $p-1$ factoring algorithm stops working. However, safe primes are not enough. There are other related factoring algorithms, such as the $p+1$ method, and strong primes also stop them. The ...


7

Here's one more way in which a dishonest participant can mess with Shamir's secret sharing: Let's briefly review how secret reconstruction in Shamir's $(k,n)$ secret sharing works. Given the $x$-coordinates of $k$ participants $(x_1, x_2, \dots, x_k)$, one way to reconstruct the secret is to compute the Lagrange basis polynomials: $$\ell_j(x) = \prod_{1 \...


7

This $(k,n)$ scheme works, but isn't very interesting. Effectively, it is: For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set. For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $\binom{3}{2} = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 ...


6

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


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

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


6

I know that this is technically okay, since it is still GF(p^k), but why is this preferable to just using a prime field? They have equivalent security; however the nice thing about $GF(2^8)$ is that everything ends up to be an integral number of byte. We could use (say) $GF(257)$, however when the shares will end up being slightly larger than 1 byte, and ...


6

Let's recall Shamir's Secret Sharing. We work in a finite field $\mathbb{F}_q$ of cardinal $q$. The secret to share is $s$; we want $n$ shares with a threshold $t$. We suppose that $n < q$ (otherwise, the scheme does not work). We conventionally name $n$ non-zero values of $\mathbb{F}_q$: $x_1$, $x_2$... $x_n$. Exactly how we choose them is unimportant, ...


5

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


5

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.


5

A threshold, additively homomorphic cryptosystems (such as the threshold variant of paillier) would work just fine for this sort of system. Each voter would need to prove that their vote was in the set $\{-1,0,1\}$ instead of the typical $\{0,1\}$. All of this could be done using the thep library. There is a page on dealing with negative numbers. An ...


5

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


5

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


5

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


5

Yes. If all of the shares you have are valid, you can tell when you have reached the threshold. Reconstructing the secret from $t+1$ shares will yield the same result as reconstructing the secret from $t+2$ shares. Reconstructing it from $t-1$ will however (always) yield a completely different result. Reconstructing the secret from $t-2$ or fewer shares will ...


5

Another way to look at it informally is this; If it is perfectly hiding, then you cannot tell what made the final value. It could equally be any combination. If it is perfectly binding, then there is only one combination that produces the final value, essentially binding the final value to that one combination. Let's say we are talking about addition, and ...


5

In your example, let's assume the secret sharing scheme is a $(k,n)$-threshold sharing scheme with $k = \frac{n + 1}{2}$, as you say only an 'honest majority' can construct the secret. If then $n$ protocol-following parties release their information to the group, an adversarial participant can then construct the whole secret, as they have a share, without ...


4

The security of pairing-based cryptography relies on the security of the elliptic curve (which is linked to the size of underlying finite field, or "base field") and of the finite extension field being used. The "Dlog security" column in the linked page is the size of the finite extension field. Its security used to be comparable to the corresponding RSA ...


4

The way to prove this is to follow the same proof that Shamir's secret sharing is perfectly secret. Specifically, given any two points all secrets are possible since there is a polynomial going through every possible secret and the two given points. Since the polynomial is random, all of these polynomials have the same probability. The same thing is ...


3

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


3

Threshold (robust) m-of-n variant of Schnorr signature scheme is known: Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates Major hints on intended usage are from Ripple page mentioned. Points 4 and 3 are explicit: produce a signature, in a theshold m-of-n way. This could ...


3

I assume you say on the threshold encryption scheme, in which a dealer generates $(PK,SK_1,\dots,SK_n)$ and distributes the secret keys to users indexed by $1,\dots,n$, and if a combiner obtains $t$ partially-decrypted ciphertexts, it can retrieve a plaintext. Dodis and Katz showed a generic construction of CCA-secure threshold encryption scheme from a ...


3

To be a little more formal, consider the notation provided by Iftach. Assume a commitment scheme $(S,R)$ is statistically hiding. This means that a computationally unbounded $R$ is unable to get any information about $m$ from the commitment $c$. Since the process of computing a commitment is known to both parties, this means that there must exist $(m,d)\...


3

Apart from the slightly unusual nomenclature, this is Shamir's secret-sharing scheme with $n=6$ and $k=3$ (i.e., the secret is shared into six pieces, any three of which can be combined to retrieve the secret). In this case, the pieces are as follows: $$\begin{align}(x_0, y_0) &= (10, 25) \\ (x_1, y_1) &= (20, 405) \\ (x_2, y_2) &= (30, 272) \\ ...


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