# Questions tagged [threshold-cryptography]

Threshold cryptography is the art of chopping a secret into little bits, so that the secret can only be learned by possessing more than a threshold number of those bits.

87 questions
Filter by
Sorted by
Tagged with
60 views

### Sage code for finding generator matrix of MDS code

Let $L$ be an $[n,k]$ code. A $k\times n$ matrix $G$ whose rows form a basis for $L$ is called a generator matrix for $L$. A linear $[n,k,d]$ code with largest possible minimum distance is called ...
63 views

### BGW multiplication by Gennaro et al.: Why does H(x) have exactly degree t and why is $2t + 1 \le n$ necessary?

With this question I am referring to the BGW multiplication by Gennaro et al (PDF here). The multiplication is described on the 4th page. (Another source for me was "A pragmatic Introduction to ...
45 views

### Threshold implementation of ciphers

What is the principle behind threshold implementation of block ciphers and how is this protecting against side channel attacks?
72 views

### Gennaro & Goldfeder Key Generation Protocol

As I am going through the “Fast Multiparty Threshold ECDSA with Fast Trustless Setup” paper by Gennaro & Goldfeder, 2018, I am stumbled by the key generation protocol (Sect. 4.1, p.10): In Phase ...
37 views

### Coin tosses in the context of commitment schemes

I was reading the “Fast Multiparty Threshold ECDSA with Fast Trustless Setup” paper by Gennaro & Goldfeder, 2018 and I encountered this portion (Sect. 2.4, p.6): This excerpt leaves me slightly ...
96 views

### Are Shamir shares independent?

Assume we have a secret $s \in Z_p$. We generate the set of secret shares $\{ (x_i, s_i) \}_{i=1}^{N}$ according to a $(N,k)$ Shamir's scheme. The evaluations are generated according to the following ...
26 views

### Threshold Signature with Accumulation Scheme?

Is there a threshold signature scheme that can be accumulated? That is, given a message $M$ signed by $k-1$ parties and the $(k-1)$-threshold signature $\sigma_{k-1}$, a party can verify $\sigma_{k-1}$...
39 views

80 views

### Understanding multiplication of Shamir secret sharing during threshold (EC)DSA signing

I have been looking at the threshold (EC)DSA schemes for honest majority by Gennaro et al. https://www.sciencedirect.com/science/article/pii/S0890540100928815. In the scheme, there are steps where we ...
95 views

### Secure Secret Sharing to a Distributed Key

Setup There are two groups, $A$ and $B$. Each group is in a Shamir's secret sharing scheme ($t_A$ of $N_A$ and $t_B$ of $N_B$). Each group has a public key that is associated with the identity of the ...
253 views

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

An EdDSA signature is (R, S) where R = r*B and S = r + H(R, A, M)*s. Notation from Wikipedia en.wikipedia.org/wiki/EdDSA. Given that the hash function H, is indeed collision-resistant, would using S = ...
36 views

### Threshold Encryption Scheme for Multiple Messages

In a threshold encryption scheme, a dealer generates $(PK,SK1,…,SKn)$ and distributes the secret keys to users indexed by $1,…,n$, and if a combiner obtains $t+1$ partially-decrypted ciphertexts, it ...
56 views

### Threshold lower than $\dfrac{n}{2}$ in distributed key generation

While I was studying protocols for distributed key generation with malicious adversaries, Gennaro et al.$^{[1]}$ pointed out that the protocols that provide both secrecy and robustness should have a ...
33 views

### Black-box secret sharing schemes

My question is about black box secret sharing schemes (BBSSS). Do these schemes have any advantages over the better known secret sharing schemes like Shamir’s?
67 views

### Problems on ANF equation?

I tried to solve SBox as given in this link I am trying to understand this paper SBox. In this on page no.4 the correct equation of given SBox is mentioned. I am not getting how to design ANF equation ...
69 views

### Generate ANF equation? [duplicate]

Given an SBox, how can I generate its component equations (in ANF)? given in this link: https://en.wikipedia.org/wiki/Algebraic_normal_form For example, let's say I have this SBox: \{1, a, 4, c ,6 ,...
41 views

### Privacy preserving aggregation of encrypted data

I have the following problem: I have $t$ servers $S_1, S_2, S_3, \ldots, S_t$, each of them storing some $key : value$ list. They have to upload this data into a big dropbox server $D$, but in such a ...
63 views

### Practical Threshold Signatures

In Practical Threshold Signature it says that there is a requirement in which the RSA public exponent $e$ must be more than $l$. $l$ in this case is the number of players in the threshold group. My ...
58 views

### Which groups are secure for DL-Problem?

I was wondering why some groups provide more security to cryptosystems relying on DL-Problem.
217 views

### Is this distributed random oracle scheme safe?

This question comes from an issue raised in another question: Non interactive threshold signature without bilinear pairing (is it possible)? Is the proposed random oracle model safe when trying to ...
80 views

### Derived keys usable by threshold signatures

Suppose there are $n$ members in a $(t,n)$ threshold signature scheme. The global secret key $sk$ is not known to any single party, as the keys are generated distributed. The parties are able to ...
345 views

### Threshold decryption in multi-key homomorphic encryption

I have a problem understanding the security of threshold decryption in multi-key homomorphic encryption (MKHE) with so called "noise flooding". In particular I think that it is not secure, so probably ...
322 views

### In a shamir secret sharing scheme, why can't the secret be a middle coefficient and only the first or the last?

In the shamir secret sharing scheme, the Secret s is set as the constant in the equation $y_p = s+ \sum_{i=0}^{i = t-1} a_i * x_p^i$ s can only be the constant term or the last coefficient or the ...
231 views

### Non interactive threshold signature without bilinear pairing (is it possible)?

All threshold signature schemes that I have seen need bilinear pairings to avoid parameter exchange between parties. These are normally commitment schemes for a certain secret. I believe a 2-round ...
74 views

### Is there any implementation of threshold BGN homomorphic encryption? [closed]

The BGN paper (Evaluating 2-DNF Formulas on Ciphertexts) used a threshold variant of BGN. I also want to use this cryptosystem, however, I cannot find any open-source implementation. Is there any such ...
92 views

### Distributed key generation (for discrete-log based cryptosystems) with fake shares

Under the definition of Gennaro et al (link), a DKG protocol needs to satisfy “correctness” and “secrecy”. Correctness is divided into three sub-properties: C1. All subsets of $t+1$ shares provided ...
1k views

### Formal Proof of Shamir's Secret Sharing Scheme Security

Shamir's Secret Sharing scheme is perfectly secure. Could you please suggest where I can read a formal proof of Shamir's Secret Sharing scheme being perfectly secure?
137 views

### Pairing-based cryptography VS ZK-proofs: what's more efficient for threshold systems?

In some papers (e.g. 1, 2) the authors approve that pairings are more efficient than classic zk-proofs (e.g. proof of discrete logarithm knowledge) for the described applications (threshold encryption,...
260 views

### Difference between Asmuth-Bloom and Shamir's Secret Sharing

Both Asmuth and Shamir are threshold based secret sharing schemes and perfectly secure. In which point of view Asmuth bloom secret sharing scheme is better than Shamir secret sharing scheme. Could ...
90 views

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

In this paper, Ueli Maurer uses a very cool model to generalize a number of results about broadcast, secret sharing and secure multiparty computation. Rather than talking about an adversary being ...
335 views

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

After following a discussion that Shamir's Secret Sharing scheme cannot be used to share a real number as secret, I came across the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. ...
95 views

### Combining share decryption on Paillier threshold scheme

I am trying to implement the Paillier threshold scheme described by Fouque, et al, but I am having an issue when combining share decryptions. The scheme calculates the plaintext $M$ with the formula: ...
65 views

### Threshold homomorphic

Quite a specific question, but are there any threshold signatures that are also homomorphic? Preferably ones that work in the discrete log setting and don't require any pairings.
257 views

### Ed25519 threshold signature verification without knowing the single personal public keys

I read about ways to create a t-of-n threshold signature, corresponding to a collective public key of n players. (https://datatracker.ietf.org/doc/html/draft-ford-cfrg-cosi-00 and Does Ed25519 support ...
114 views

### Verification in Threshold RSA or Threshold Paillier

In the key generation of the threshold version of RSA or the threshold version of the Paillier cryptosystem (e.g. "Shoup - 2000 - Practical threshold signatures" or "Fouque et al. - 2000 - Sharing ...
232 views

### How to compute Lambda in a Threshold Paillier scheme

I am evaluating a threshold Paillier scheme as described in the paper: Ivan Damgard, Mads Jurik, Jesper Buus Nielsen, "A Generalization of Paillier’s Public-Key System with Applications to Electronic ...
40 views

### Threshold signature without revealing id of signers to the recombiner

I want a threshold signature t out of n algorithm where set of t signers are not known before hand and want to remain anonymous after signing. How is recombination possible if id of signer is not ...
347 views

### Can we use Shamir secret sharing conversely?

In Shamir secret sharing scheme, we have a secret and then the shares are generated based on the secret. The question is can we generate the shares before knowing the 'secret' (which is uniformly ...
413 views

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

PBFT and most consensus algorithms are more complicated than a simple voting scheme. By simple voting I mean the following: we require all nodes to sign their local copy of the state and send this ...
55 views

### identify PK in ring signatures by using (t,n)-threshold

Consider a group of $n$ public keys $pk_1,...,pk_n$ with corresponding secret keys $sk_1,...,sk_n$. I'm looking for a cryptographic primitive with the following properties: Ring signature property. ...
935 views

### ECDSA threshold signing

I searched "ECDSA threshold signing" recently and found a lot of papers where it is said that their authors solved the problem of ECDSA threshold signing efficiently: e.g. here and here. Why there ...
189 views

### Baek and Zheng’s Threshold Cryptosystem - limit on threshold?

I have just completed an implementation of Simple and Efficient Threshold Cryptosystem from the Gap Diffie-Hellman Group by Baek and Zheng and am hitting a problem with high values of the threshold. ...
882 views

### How to forge a Shamir secret share?

On this website, we have a lot of questions and answers devoted to Shamir secret sharing. We make it clear that Shamir secret sharing does not guarantee integrity. When we want integrity, we need to ...
114 views

### Finding a key given partial keys

I'm working through an exam paper for a cryptography exam and I've come across a question I'm unsure on. Six users have been given the partial keys below $P(x) = (k + \sum_{i=1}^2 c_ix^i)\bmod{503}$ ...
Consider Shamir's Secret Sharing scheme with $n=5, t=3$ (i.e, there are 5 shares, and when we have 3 of them we can reconstruct our secret $s$). Let $f(x)$ be the dealing function, i.e the secret $s$ ...