Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [secret-sharing]

Secret sharing refers to splitting a secret among multiple parties so that together they can reconstruct it. All parties, or just a threshold number of them, can be required for reconstruction. If fewer than the required number of parties participate, no information should be leaked about the secret.

1
vote
2answers
54 views

Does an encryption algorithm exist where encrypted data can be decrypted by multiple private keys?

Suppose I have Company1 with their own Public/Private Key Pairs and another Company2 with their public/private key pairs and yet ...
0
votes
0answers
38 views

How can a node establish pairwise shared key with other nodes using its own polynomial share together with other's public values?

A server has a symmetric bivariate polynomial $ F(x, y) = \sum_{{i,j}=0}^{t-1}a_{i,j}x^iy^j$ $\in GF(p)[X, Y] $ of degree $t-1$. For simpliciy, $ F(x, y) = a_{0,0}+a_{1,0} x+a_{0,1}y+ a_{1,1}xy$ mod ...
0
votes
1answer
48 views

What is the significance of $\prod \limits_{i=1}^{t}m_i > p \prod \limits_{i=1}^{t-1}m_{n-i+1}$ in Asmuth–Bloom threshold SSS?

In this paper by Asmuth–Bloom on threshold SSS, the algorithm is as follows: Shares Distribution To distribute $n$ shares of a secret $K$ among the set of participants $P = \{ p_i : 1 ≤ i ≤ n\}$, ...
0
votes
0answers
50 views

Security of (2,2) Shamir's visual secret sharing scheme : How are the 2 shares random?

From the Visual Cryptography by Shamir and Noar. Let us take the pixel expansion as 2. Therefore, each pixel will be represented by 2 pixels (also called as subpixels) in a share. Since this is a (2,...
1
vote
0answers
39 views

Pseudorandom zero-sharing: how does it work?

TL;DR How can the shares of the PRZS protocol proposed in [CDI05] reconstruct the "secret" $0$? Is the number of shares required to reconstruct $0$ equal to $2t + 1$? Long question The paper "...
2
votes
1answer
59 views

Secure multi-party computation for digital signature

Is there any practical algorithm that will allow to use public key cryptography (RSA or ECC) in the following way There are N parties. Up to M are malicious adversaries (were trusted, but got taken ...
2
votes
1answer
162 views

Is GMW different from Secret Sharing?

Is GMW (How to play ANY mental game) protocol different from Secret Sharing?? If so, how is it different from Secret sharing?
1
vote
1answer
54 views

How to apply lagrange interpolation on bilinear pairings?

I have seen in some places applications of Shamir secret sharing and lagrange interpolation mixed with bilinear pairings, however I fail to understand how this works. For instance, here I find the ...
1
vote
0answers
54 views

Purpose of the ZKPoPK in the original SPDZ protocol

What is the purpose of ZKPoPK in the SPDZ paper? And will the following can detect the active adversaries in 2 party spdz excluding ZKPoPK step? Each party sends a commitment on his MAC key ∆_i ...
0
votes
1answer
54 views

Two parties SPDZ Protocol Input sharing

Assume we have two computing parties for SPDZ protocol. The two parties are also the input parties. How can they share the MACs on their input shares assuming one party is the master who owns the MAC ...
1
vote
0answers
45 views

How does the user check whether $y < M$ without knowing all shares?

CRT-based Verifiable Secret Sharing Scheme In this paper, section 4 Verifiable Secret Sharing Scheme, the dealer phase and the combiner phase are as follows: Dealer Phase To share a secret $d \in ...
2
votes
0answers
47 views

Adding new share (Shamir Secret Shares ) [duplicate]

I am using this https://github.com/gburca/ssss-js Shamir implementation. I generated 4 shares from secret (threshold of 2). I am wondering if I can recreate (interpolate) original polynomial from ...
0
votes
0answers
18 views

How space efficient is the Asmuth-Bloom scheme

This answer to another question states that shares in Asmuth-Bloom scheme are $n$ times larger than the secret. From my understanding of the scheme, the share space is defined by the largest modulo $...
1
vote
0answers
28 views

Confirmation signature - Improved Feldman VSS

I am working through the implementation of A Distributed Private-Key Generator for Identity-Based Cryptography. In the paper (Figure 1, page 8) the validation of a share by a node says that once ...
3
votes
0answers
50 views

Is it possible to randomize the secret in homomorphic secret sharing?

I was reading the Homomorphic Secret Sharing from Paillier Encryption paper. I see that the authors suggest to secret share $\lambda y$ as $\lambda y = z_1 + z_2$. Then, one can exponentiate an ...
1
vote
1answer
72 views

Is my proof of Asmuth-Bloom scheme's perfection correct?

I am trying to understand how Asmuth-Bloom's secret sharing is perfect. My "proof" so far (in a 3 out of 4 scheme): $y=s + a * m_0 \bmod m_1 * m_2 * m_3$ Having $k-1$ shares, it will yield a valid ...
2
votes
3answers
62 views

Impact of a non-uniform distribution in a secret sharing scheme

When it comes to the secret sharing schemes, it seems that the random numbers need to be drawn uniformly. Is there any difference between the random numbers from uniform distribution and the non-...
1
vote
1answer
27 views

How is the generator used in Feldman's Verifiable Secret Sharing scheme determined? [duplicate]

According to the Wikipedia description of Feldman's VSS scheme First, a cyclic group G of prime order p, along with a generator g of G, is chosen publicly as a system parameter. (Typically, one ...
1
vote
0answers
38 views

Differential privacy and Shamir's scheme

I have been unable to find any proofs (for my own reference) that demonstrate that Shamir's secret sharing scheme does (or does not) satisfy the definition of $\textbf{differential privacy}$ as ...
2
votes
1answer
46 views

Asmuth-Bloom Secret Sharing $m_0$ public?

i am trying to figure out how Asmuth-Bloom secret sharing works and followed the example on wikipedia and replaced it with own numbers. Namely, i used: $S=3$ $k=3$ $n=4$ $m_0 = 13, m_1=45, m_2=46, ...
6
votes
1answer
215 views

Why is a number of shares that is greater than a threshold required to construct secret?

In this paper of Asmuth–Bloom threshold SSS, the algorithm is as follows: Shares Distribution To distribute n shares of a secret $K$ among the set of participants $P = \{ p_i : 1 ≤ i ≤ n\}$, the ...
2
votes
2answers
43 views

Why is Blakley secret sharing in finite space?

The paper says it requires a finite space. I wonder what the reason is, since from my understanding it should be perfectly fine to use the "normal" infinite space. So why does Blakley use a finite ...
3
votes
1answer
138 views

How is Blakley's Secret Sharing Scheme perfect?

Currently, I am trying to understand Blakley's secret sharing scheme. However, there seem to be multiple descriptions of it, which are very different from another, but everyone states that the scheme ...
0
votes
1answer
45 views

Two-way secret sharing for authentication?

Secret sharing, using methods such as Shamir's Secret Sharing allows for t out of n shares to recreate a secret. For authentication, the secret can be a user ID. A client with a logged-in user can ...
1
vote
1answer
77 views

How can I generate large primes for Pedersen commitment?

I want to make a commitment on Shamir's Secret Sharing, based on the work of Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing". To implement the commitment ...
2
votes
0answers
40 views

What is difference between Unipartite Secret Construction, Bipartite Secret Construction and Multipartite Secret Construction

In this paper authors extend Asmuth–Bloom and Kaya schemes to bipartite access structures and further investigate how SSSs realizing multipartite access structures can be conducted with the CRT. The ...
1
vote
1answer
50 views

Combining secret/public keys

Suppose that we have three authorities which each of them generate one secret/public key for Alice. It means that Alice has three secret keys and three related public keys. Suppose that Alice combines ...
1
vote
1answer
107 views

Mathematics behind the paper “how to leak a secret” for ring signature

I'm reading the paper "How to Leak a Secret" (Rivest, Shamir, Tauman; 2001). On page 8/14, in chapter 3.4, the authors present the following "combining function": $$C_{k,v}(y_1, y_2,\ldots,y_r) = ...
3
votes
1answer
66 views

secret sharing scheme difference

confused about differences between 5 out of 5 threshold secret sharing scheme and 4 out of 5 threshold secret sharing scheme. how would the share and reconstruction schemes be different assuming both ...
1
vote
0answers
45 views

PCI DSS requirement 3.5.3

3.5.3 Store secret and private keys used to encrypt/decrypt cardholder data in one (or more) of the following forms at all times: ............ As at least two full-length key components or key shares, ...
1
vote
1answer
49 views

Shamir Secret Sharing and Diffie-Hellman procedure

Alice needs to share an already generated numeric secret $s$ with Bob and she doe not want the world to see it. The problem is that she has never contacted Bob before. I thought Alice and Bob could ...
1
vote
2answers
207 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?
0
votes
1answer
53 views

Secret shared input for garbled circuit?

I’m curious about what the secret shared input for a garbled circuit is. Essentially, a garbled circuit is a two party computation framework where each of two players has each input as bit string. In ...
1
vote
1answer
80 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
113 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 ...
1
vote
1answer
83 views

Secret sharing over reals - Difficulty with Computer implementation

I asked a question recently regarding the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. Kushilevitz which describes a secret sharing scheme for real numbers in the interval $[0,1]$. I ...
3
votes
1answer
71 views

Change a secret key in an embedded device

There is a device that uses a secret key Sk to encrypt data. Assume this Sk is compromised. Could the following scheme be considered safe, in case we want to change the compromised Sk: We store some ...
4
votes
1answer
67 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 ...
0
votes
1answer
50 views

Shamir Scheme: Whats the problem of not using random x-coordinates?

i would like to know why there is a problem of not using random x-coordinates in shamir secret sharing schemes. I consider that after evaluating the points in a polynomial $f(x)$, the share is ...
2
votes
0answers
67 views

Verifiable secret sharing - Benaloh scheme; some doubts not answered earlier

I reviewed the paper "Secret sharing homomorphisms: keeping shares of a secret secret" by J.C. Benaloh yesterday and I had some difficulty understanding his version of verifiable secret sharing to ...
5
votes
1answer
129 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. ...
1
vote
2answers
75 views

Multi-secret sharing (Packed secret sharing) - Some questions

In the publication - "Communication complexity of secure computation", I have encountered a small problem - on page 5 of the literature under the heading "Theorem 1" they have described a $(c,d; k,n)$ ...
2
votes
2answers
166 views

Shamir Secret Sharing Scheme - leak of information

After going through some literature, I've convinced myself that to recover the exact secret using Shamirs Secret Sharing scheme, we must have S(the secret converted into a number) < p (choice of ...
1
vote
1answer
45 views

Shamir Secret Sharing Scheme - some doubts not answered earlier

my first question on here. I've gone through some examples of Shamirs Secret Sharing Scheme, but I have 2 rather pressing doubts - i. Why do we choose the co-efficients of the polynomial from the ...
1
vote
0answers
103 views

Private Key Sharding - How is it Secure in a Distributed Network?

In a Distributed Network in order for a private key not to be compromised sharding will have to take place off the network, correct? If so: Why is it when a Distributed Network shards private keys ...
2
votes
1answer
154 views

How to perform Shamir Secret Sharing with a Tabula Recta?

In this post, a couple comments suggested that a tabula recta could be used to perform Shamir Secret Sharing. I'm specifically interested in this statement: you could just have a table of all 100 ...
1
vote
0answers
31 views

Is recursive secret sharing of practical value?

This paper describes recursive secret sharing. In one of their illustrations, a binary secret of length L, along with 3 other binary secrets of lengths shorter ...
0
votes
2answers
138 views

How to compute secure sum using secure multparty computation?

Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X $, $Y$ and $Z$ respectively (with 2 bits ...
1
vote
1answer
161 views

How does one construct a 27x27 tabula recta for 2-of-3 secret sharing?

In the answer to this post at security.stackexchange, someone describes how, using pencil and paper, one can do 2-of-3 secret sharing with a tabula recta. But I don't understand how he created his ...
1
vote
1answer
66 views

Why every access structure is a multipartite access structure?

The set of authorized subsets of participants is called an access structure. In a multipartite access structure, the set of participants is divided into several parts and all participants in the ...