# Tag Info

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 ...
• 5,662
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 ...
• 134k

### 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 ...
• 1,253

### 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 ...
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$ (...
• 84.8k

### 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$-...
• 44.5k
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 ...
• 125k
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 ...
• 134k
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 ...
• 134k

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

### 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 ...
• 134k
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 ...
• 37.8k
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$ ...
• 7,266

### 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$ ...
• 355

### 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 ...
• 134k

### 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 ...
• 10.2k
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 ...
• 134k

### 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 ...
• 134k
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 ...
• 6,129
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 ...

### 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 ...
• 135
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 ...
• 2,237
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 ...
• 2,013
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 ...

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

### 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 ...
• 10.8k

### 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 ...
• 131
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 ...
• 5,662

### Problems on ANF equation?

Using the S-box package of SageMath used ...
• 43.5k