Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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.

Filter by
Sorted by
Tagged with
0
votes
0answers
22 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
44 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 ...
1
vote
1answer
83 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
78 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
51 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 ...
2
votes
0answers
68 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
62 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
236 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
48 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
176 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
82 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
100 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
56 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
106 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
150 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
85 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
88 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
103 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
441 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
87 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
102 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
155 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
109 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
84 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
77 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
115 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
97 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
217 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
120 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
322 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
58 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
230 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 ...
4
votes
1answer
179 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
33 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
255 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
227 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
83 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 ...
1
vote
1answer
94 views

Combining secret keys into a single shared key

Let's say there are $n$ participants each with their own secret key $x_i$. Is it possible for them somehow to build a shared key which is an arithmetic sum of all their secret keys ($x_0 + x_1 + ... + ...
5
votes
2answers
100 views

What's the functional difference between fountain codes and polynomial secret sharing?

Fountain codes, as I understand it, allow for the reconstruction of a set of data (e.g. a 64-bit word), by sending (without corruption or failure) chunks of data generated using a probabilistic ...
1
vote
2answers
236 views

Multiparty key exchange for end-to-end encryption

I need to make end-to-end encrypted messaging between 2 and more parties without trusting a server. Each party has it's secret and private keys. The obvious solution is to make ECDH between all of ...
1
vote
2answers
142 views

Security of Shamir secret sharing with regards to the threshold

Consider Shamir Secret Sharing Scheme (SSSS). This is completely unfounded, but my intuition tells me that the threshold k we set (AKA the number of shares required ...
1
vote
0answers
43 views

Preserving location privacy

What are cryptographic techniques that could be used so that if I wanna to enable a server to send message to certain nodes in a network with preserving the privacy location for them ??
1
vote
1answer
144 views

Question regarding reconstruction vector in LSSS

Suppose we have a policy $A \wedge ( D \vee (B \wedge C))$ with attributes ${\{A,B,C,D}\}$. The set of subsets of attributes which satisfy this policy is ${\{{\{A,D}\},{\{A,B,C}\},{\{A,B,D}\},{\{A,C,D}...
1
vote
1answer
159 views

Reconstruction vector in Linear secret sharing schemes

Suppose we have a policy $A \wedge ( D \vee (B \wedge C))$ with attributes ${\{A,B,C,D}\}$. The set of subsets of attributes which satisfy this policy is ${\{{\{A,D}\},{\{A,B,C}\},{\{A,B,D}\},{\{A,C,D}...
1
vote
1answer
65 views

Eliptic curve verifiable secret sharing

I am implementing the following the algorithm instructions as shown in 1 (section IV, B). When trying to verify the share given the commits, $a_jG$ verifier $i$ checks whether $f(i)G=\sum_{j=0}^{t} (...
1
vote
1answer
289 views

Reverse Shamir's Secret Sharing Algorithm?

Shamir's Secret Sharing algorithm works by breaking a single secret to multiple parts. While it is trivial to implement the reverse in a $n$-out-of-$n$ scheme, how would one implement an $m$-out-of-$n$...
1
vote
1answer
420 views

AES encryption using MPC SPDZ protocol

I'm reading the article about SPDZ protocol for secure multiparty computation (and also improvements for offline phase like MASCOT). However I'm thinking about practical application of SPDZ for AES ...
5
votes
2answers
120 views

$t$-out-of-$n$ Secret Sharing over $\Bbb Z_2$?

Is it possible to construct a $t$-out-of-$n$ secret sharing scheme over $\Bbb Z_2$? Shamir Secret Sharing allows for an arbitrary threshold $t$ and an arbitrary number of participants $n$, but ...
1
vote
1answer
107 views

Number of possible access structure with $n$ person

I want to count number of possible access structures in closed form(if possible) as a variable of $n$,the number of share holder. I have tried in several ways. Still no good progress. It is very hard ...
2
votes
2answers
97 views

Multiparty secret generation protocol

The goal is to create a secret S on a trusted server by having users A, B and C each send a private seed to the server, in such a way that any 2 of them can later recover S by resubmitting their ...