29

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.


20

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


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


10

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


8

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


8

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


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

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

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

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

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


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

This answer is assuming you are not removing the private key $a$ from the computation of $S$, and instead actually meant what is said in the title of the question: $S = r + a H(A, M)$ Removing $a$ from the computation would be terrible. The first issue that comes to mind is malleability, on top of collision resistance. The signature process for EdDSA ...


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


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

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

would using S = r + H(A, M) be a secure variant? Actually, it would become trivial to generate a signature for an abitrary message with just the public key. The verification check would be: $$2^h s G = 2^h R + 2^h H(A, M) A$$ where $h$ is the curve cofactor, $G$ is the curve generator, $A$ is the public key, $M$ is the message and $(R, s)$ is the signature. ...


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

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

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

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


3

I just saw this question now. There is no reference implementation of the 2-party threshold ECDSA protocol since this was joint work with Unbound Tech (previously Dyadic Security), and they did the implementation. In general, I am a strong proponent of open source, and all pure academic work that I do is published with open source code (see https://github....


3

The purpose of a BFT is to achieve Byzantine Fault Tolerance rather than to be cryptographically secure. In fact, some BFT papers have no cryptography in them at all. You could devise a secure voting scheme but that doesn't automatically make it tolerant to byzantine failures. Generally these algorithms seek to achieve liveness (eventual consistency of the ...


3

This is a somewhat standard method for generalizing results based on threshold adversaries. Let $n$ be the number of parties and let $\mathcal{C} \subseteq 2^{[n]}$ denote the family of subsets that the adversary can corrupt. For example, in the case of honest majority, $\mathcal{C} = \{ C \subseteq [n] : |C| < n/2 \}$. $\mathcal{C}$ has the Q2 property ...


3

As has been commented, Asmuth-Bloom is does not always give a perfect scheme. The original paper gives a condition on the primes to maximise "sharpness", which is what they call their measure of closeness to perfection. A recent paper at Asiacrypt 2018 gives fairly detailed analysis of the differences, and they also construct a new scheme using similar ...


3

Everything you write looks correct. However, you may be expecting the distributed decryption protocol to have a security property that it does not (and was not intended to, and really cannot in your example) have. Specifically, the Mukherjee-Wichs paper you linked defines security to say (roughly) that, given the evaluated ciphertext, its underlying ...


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