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.

Filter by
Sorted by
Tagged with
2
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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?
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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}$...
0
votes
1answer
39 views

summation problem?

Let there are two given numbers $x,y$ which is $A=x+y$ and we know just $A$. How we can find this just $x$ and $y$? If you suppose $a$ a random number, then we know $x_1=a$ and $y_1=A-a$ satisfies in $...
1
vote
0answers
70 views

Distributed Random Oracle with Verifiable Shares

$Setup$: Let's assume a quorum of $n$ nodes where each have a secret share $y_i$ from a know and safe leaderless DKG protocol. Define $\mathcal{L}^i(y_i) = y$ as the lagrange interpolation for $x=0$, ...
2
votes
1answer
59 views

How to do unmasked addition on SSS masked shares?

I'm trying to understand how Shamir's Secret Sharing algorithm is applied to AES when doing threshold masking. I understand how the secrets are created and the secret is calculated and I'm now trying ...
0
votes
0answers
22 views

Conditional probability being Constant in Threshold Cryptography

I am working on Threshold implementation of algorithms to prevent side channel attacks. I am not that much proficient in Statistics and Probability theory. I want to know what is the significance of ...
1
vote
0answers
29 views

Threshold signature verified by an equivalent key

I am looking for references for the following problem: Consider we have a DSA with the keypair $(sk, pk)$ and a message $m$, such that its signature is $s = sig(m,sk)$ and the verification result is $...
1
vote
0answers
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 ...
5
votes
1answer
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 ...
3
votes
2answers
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 = ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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?
2
votes
1answer
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 ...
1
vote
0answers
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 ,...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
58 views

Which groups are secure for DL-Problem?

I was wondering why some groups provide more security to cryptosystems relying on DL-Problem.
3
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
3
votes
2answers
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?
1
vote
1answer
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,...
3
votes
1answer
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 ...
4
votes
1answer
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 ...
5
votes
1answer
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. ...
2
votes
1answer
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: ...
5
votes
0answers
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.
2
votes
0answers
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
2answers
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 ...
4
votes
3answers
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 ...
1
vote
0answers
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. ...
1
vote
2answers
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 ...
2
votes
1answer
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. ...
7
votes
3answers
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 ...
2
votes
1answer
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}$ ...
3
votes
2answers
487 views

Undetectable cheater in Shamir's Secret Sharing scheme

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$ ...
1
vote
1answer
152 views

One time blinding threshold encryption?

Paillier cryptosystem has self-blinding property. (change one ciphertext into another without changing the content of its decryption) Is there any threshold encryption scheme (or just encryption ...