29 votes
Accepted

Why can't the commitment schemes have both information theoretic hiding and binding properties?

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 ...
user avatar
12 votes
Accepted

Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box?

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 ...
user avatar
  • 134k
10 votes

Why can't the commitment schemes have both information theoretic hiding and binding properties?

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 ...
user avatar
8 votes

Why can't the commitment schemes have both information theoretic hiding and binding properties?

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 ...
user avatar
8 votes
Accepted

Formal Proof of Shamir's Secret Sharing Scheme Security

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$ (...
user avatar
7 votes

Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box?

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$-...
user avatar
7 votes
Accepted

An electronic voting system

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 ...
user avatar
  • 125k
7 votes
Accepted

Secret sharing over reals - constructing a (k,n) threshold scheme

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 ...
user avatar
  • 134k
6 votes
Accepted

Shamir Secret Sharing GF(p) or GF(2^8)

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 ...
user avatar
  • 134k
6 votes

Shamir's Secret Sharing vs. Asmuth-Bloom scheme

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 ...
user avatar
  • 420
6 votes

Shamir's Secret Sharing vs. Asmuth-Bloom scheme

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 ...
user avatar
  • 134k
6 votes
Accepted

Terminology for secret sharing?

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 ...
user avatar
  • 37.8k
6 votes
Accepted

Would EdDSA be broken by replacing H(R, A, M) with H(A, M)?

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$ ...
user avatar
  • 7,266
5 votes

Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box?

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$ ...
user avatar
  • 355
5 votes

Any reason to use Shamir given faster XOR threshold secret sharing algos?

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 ...
user avatar
  • 134k
5 votes

Shamir's Secret Scheme : Knowing the threshold

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 ...
user avatar
5 votes
Accepted

Asmuth-Bloom's threshold secret sharing scheme

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 ...
user avatar
  • 134k
5 votes

Would EdDSA be broken by replacing H(R, A, M) with H(A, M)?

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 ...
user avatar
  • 134k
4 votes
Accepted

Elliptic curves with pairings at 128-bit security in libpbc?

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 ...
user avatar
  • 6,129
4 votes
Accepted

Undetectable cheater in Shamir's Secret Sharing scheme

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 ...
user avatar
3 votes

Shamir's Secret Sharing vs. Asmuth-Bloom scheme

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 ...
user avatar
  • 135
3 votes
Accepted

Does Ed25519 support cryptographic threshold signatures?

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 ...
user avatar
3 votes
Accepted

Finding a key given partial keys

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 ...
user avatar
  • 2,013
3 votes
Accepted

ECDSA threshold signing

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 ...
user avatar
3 votes

Why won't a BFT protocol using simple signing/voting work?

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 ...
user avatar
  • 131
3 votes

Under what conditions is broadcast possible? (Cryptographically, and in the model of Maurer 2006)

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 ...
user avatar
  • 10.8k
3 votes

Difference between Asmuth-Bloom and Shamir's Secret Sharing

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 ...
user avatar
  • 131
3 votes
Accepted

Threshold decryption in multi-key homomorphic encryption

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 ...
user avatar
3 votes

Problems on ANF equation?

Using the S-box package of SageMath used ...
user avatar
  • 43.5k
3 votes
Accepted

How to do unmasked addition on SSS masked shares?

It seems that the question you're asking is about how to add a public (unmasked?) value to a secret-shared value. I suggest you edit the question a bit to clarify that this is not related to AES ...
user avatar
  • 3,802

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