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
17
votes
4answers
3k views

How do you find a cheater in Shamir Secret Sharing?

If there are 4 people involved, and every two of them should be able to know the secret (the polynomial is just a line) and you are given $f(x)$ and $x$ for each of those people, and you know one of ...
15
votes
4answers
5k views

Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box?

This linear secret sharing scheme allows us to share a secret between n parties, such that only an honest majority can reconstruct it. I understand that – because I do not allow the user to certify ...
15
votes
1answer
3k views

Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme

Shamir's original paper (PDF, 197kb) describing a threshold secret sharing scheme states: To make this claim more precise, we use modular arithmetic instead of real arithmetic. The set of ...
14
votes
1answer
2k views

Coefficients in Shamir's Secret Sharing Scheme

Sorry if this is a stupid question, but: in Shamir's scheme, we construct a polynomial and make our secret $S$ the zero-th coefficient $a_0$. What, if anything, necessitates this - in other words, can ...
12
votes
2answers
656 views

How can we distribute Shamir's secret sharing scheme shares without a dealer?

Let's say $k$ users have shares to a $(k,n)$ secret sharing scheme, and they want to issue new shares. How can they do this without collecting the shares together? In particular, no set of $k-1$ ...
11
votes
1answer
2k views

Should the secret key of Shamir's secret-sharing algorithm be interpreted byte by byte?

Should the secret message of Shamir's secret-sharing algorithm be interpreted and processed byte by byte? Interpreting it byte by byte makes it easier to process, but in case one of the shareholders ...
11
votes
2answers
1k views

K out of N encryption

A friend just showed me how to combine padlocks to achieve a lock that opens when k out of n people turn their keys. I was ...
10
votes
3answers
3k views

RS Erasure Coding and Shamir's Secret Sharing

So I was trying to understand the basic difference between erasure coding and secret sharing, and I found this paper (that you can find here or here). For what I understand, it states that Shamir's ...
10
votes
2answers
804 views

Secure degree reduction for Shamir's secret sharing

I understand the basic Shamir Secret Sharing protocol, and when two shares are multiplied, the degree of the polynomial increases. I've seen in a number of papers a reference to a degree reduction ...
10
votes
2answers
3k views

Why does Shamir's Secret Sharing Scheme need a finite field?

I read ampersand's question "Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme", where he asked why Shamir's Secret Sharing Scheme uses arithmetic in a ...
10
votes
1answer
405 views

Santa Claus' secret permutation

This December, $N$ friends play secret santa: they select a random permutation $\sigma$ of $N$ (without fixed point). For Santa Claus, everyone has to bring a gift to the next person in the ...
10
votes
2answers
1k views

Shared secret: Generating Random Permutation

-- or: How to Play Poker Without a Dealer I know this question is long but it's a really interesting theoretical problem about shared secrets and multi-party computation. General Problem: "Shared ...
9
votes
1answer
979 views

Shamir's Secret Share Over the Reals

What about using Shamir's secret share over the real numbers leaks information? I know there is a problem with random number generation, and someone suggested it leaks the parity of the polynomial, ...
9
votes
1answer
530 views

Secret sharing - no dealer, modifiable, verifiable

I need to find a secret sharing scheme with these properties: The scheme is set up by all participants, ie no single entity called the dealer The parameters of secret sharing need to be modifiable, ...
8
votes
2answers
777 views

post-quantum threshold secret sharing

I am looking for a references for post-quantum threshold secret sharing schemes. I am especially interested in knowing whether any one based on one-way compressor functions or cryptographic hashes ...
8
votes
2answers
6k views

Reverse engineering secret key in RSA encryption with the help of signature

Consider the following: $i$th message, $m_i$, in its original state. $i$th message, $M_i$, encrypted message $m_i$ using public key. Public key, $p$, in a $b$-bit RSA encryption setup. We can ...
8
votes
2answers
1k views

Is multiplicative secret sharing secure?

I suggested mulitiplicative secret sharing in an answer to another question, but noted that I wasn't sure if it was even secure and was hoping someone would comment on the security. Since no one did, ...
8
votes
1answer
2k views

Understanding Feldman's VSS with a simple example

I'm trying to understand Feldman's VSS Scheme. The basic idea of that scheme is that one uses Shamir secret sharing to share a secret and commitments of the coefficients of the polynomial to allow the ...
8
votes
1answer
434 views

Do people not care about side channel resistance?

Recently, I have been browsing a lot through libraries that implementing Shamir secret sharing. I see a lot of code that implements this cryptographic algorithm without any side channel (timing/branch/...
8
votes
1answer
386 views

Verifiable, Distributed Secret Santa Assignments

My family was planning a secret santa and I thought about how I might write a little web app to dole out these secret assignments. But the downsides to this approach are obvious: there's no way for ...
7
votes
4answers
1k views

Practical examples of Threshold Secret Sharing?

Threshold secret sharing is pretty cool, but unlike, say, public-key cryptography, I haven't really heard about it "in the wild". It appears to be confined to discussions of theoretical scenarios, as ...
7
votes
4answers
940 views

Shamir's Secret Sharing vs. Asmuth-Bloom scheme

I need to make use of a secret sharing scheme and I don't really know how to decide which one to use, Shamir's or Asmuth-Bloom (using CRT). The complexity for recovering the secret seems to be linear ...
7
votes
2answers
942 views

Recover from compromised shares with Shamir Secret Sharing

He is a quote from Wikipedia page for Secret Sharing: If the players store their shares on insecure computer servers, an attacker could crack in and steal the shares. If it is not practical to ...
7
votes
3answers
1k views

Threshold Secret sharing - How to create a shared secret from pre existing secret parts?

In usual $(t, n)$ secret sharing schemes, a secret $S$ is split into $n$ parts so that any $t$ out of $n$ parts reconstruct the original secret. So, suppose that there is a group of $n$ participants ...
7
votes
1answer
234 views

Does Runge phenomenon affect Shamir's secret sharing scheme?

Lagrange interpolation seems to be affected by the so-called Runge phenomenon when one tries to interpolate polynomials of high degree from a set of equidistant points. Lagrange interpolation is ...
7
votes
3answers
768 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 ...
7
votes
2answers
454 views

Manual secret sharing?

What are feasible options for an equivalent of Shamir Secret Sharing using small tables, preferably usable with pen-and-paper? We want to share a secret $K$ into $n\ge2$ shares, so that $m$ shares ($2\...
7
votes
2answers
246 views

$(k, n)$ threshold secret sharing to $(k+k', n + n')$ without reissuing all shares

Given a $(k,n)$ threshold secret sharing used to back up a secret (meaning that the dealer has access to the secret at all times), is it possible to update it to a $(k+k', n+n')$ threshold secret ...
6
votes
4answers
2k views

How to require two keyholders to decrypt a document?

I want to create a system to encrypt a document and store it with a 3rd party, but not have the 3rd party be able to decrypt it until some unspecified later date. It seems like the solution would be ...
6
votes
2answers
444 views

Do deterministic secret sharing schemes exist?

Are there algorithms for secure secret sharing such that the algorithm depends solely on the value being secured, relying on no randomness in its calculations. If there aren't, is such an algorithm ...
6
votes
2answers
656 views

Determining the Shamir's secret sharing scheme for the following problem

I'm having trouble solving the Shamir's Secret Sharing scheme for the following problem that states: Problem: A certain military office, which is in control of a powerful missile, consists of six ...
6
votes
2answers
433 views

Is there an efficient 2 out of 3 secret sharing scheme based on XOR?

I want to know if there is an efficient secret sharing scheme based on XOR such that a share of the message is given to three people and at least two must combine their share in order to construct the ...
6
votes
2answers
972 views

An electronic voting system

This semester I am taking the course Cryptography. I will have a presentation about the topic "Voting Scheme". I am preparing myself by reading from the book “Cryptography : an Introduction” by N....
6
votes
2answers
286 views

Shamir's Secret Scheme : Knowing the threshold

If I am decoding a key by applying shares, is it possible to know when the threshold has been reached, and the secret revealed, without having to be told what the threshold is? Also, is it possible ...
6
votes
1answer
2k views

How come Shamir Secret Sharing uses Lagrange interpolation?

I've read that Newton polynomials have better computational complexity, but Shamir's uses Lagrange polynomials instead. Does anyone know if there are particular reason why Newton polynomials aren't ...
6
votes
2answers
206 views

Using XOR to derive a data key for ECIES

I have been thinking about a rather simple enhancement for (EC)IES / RSA-KEM. The scheme would allow you to encrypt data while the calculation of the session / data key can be performed afterwards or ...
6
votes
1answer
256 views

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

In this][1] 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 ...
6
votes
1answer
259 views

Background: Secret Sharing and Multiplication Triples

I know that a nearly identical question was asked in (Secret Sharing and Multiplication Triples), but I am a few points shy of asking follow up questions in the comments, so I understand if this is ...
6
votes
1answer
207 views

Secret Sharing: Is this simplification secure?

I am a mathematician with no background in crypto or security. For work, I had to read up Chap.13 "Secret Sharing Schemes" in Stinson's Cryptography (3rd ed). My question is about a simplification of ...
6
votes
1answer
1k views

Elliptic Curve Crypto, is a distributed signing method possible using Shamir's Secret Sharing?

Note: A distributed signature scheme exists for RSA: Practical Threshold Signatures, Victor Shoup. Is it possible to adapt such scheme for ECC? A centralized signing machine is vulnerable to ...
6
votes
1answer
91 views

Is there a studied notion of “party independent transfer”?

I've been thinking about the following set-up involving three parties, Alice, Bob and Charlie: Bob and Charlie decide among themselves who is going to receive a bit from Alice (perhaps by a coin toss)...
6
votes
1answer
1k views

Threshold Signatures for RSA and DSA

I have a few questions relating to threshold signatures: a scheme where $n$ participants hold a key share and any $t$ of them can conduct a protocol using their shares that results in a valid RSA or ...
6
votes
0answers
257 views

Share Conversion between Different Finite Fields

Let us have any linear secret sharing scheme (LSSS) that works on some field $Z_{p}$, where p is some prime or a power of a prime e.g., Shamir Secret Sharing, Additive secret Sharing. The problem at ...
5
votes
4answers
737 views

Shamir Secret Sharing: Why cannot we recover polynomial's root if we have $t-1$ shares?

Imagine we have $t-1$ shares in $(t,n)$ shamir secret sharing. So at least $t$ shares are needed. Question: Why cannot we use $t-1$ shares to find a root of the polynomial and then recover the ...
5
votes
3answers
1k views

Can I pre-define the points in Shamir's Secret Sharing algorithm

With Shamir's secret sharing is it possible to pre-define the points returned by the algorithm? For simplicity if I have (k, n) where k=2, and n=4, and I have the points X,Y,Z, and Q. Can I create ...
5
votes
2answers
447 views

SPDZ for the 2-party case

There exist protocols for 2-party computation e.g., GMW that use Boolean circuits. I could also use Paillier and arithmetic circuits for a 2 party computation. However after reading about SPDZ is my ...
5
votes
2answers
2k views

Shamir's Secret Sharing Scheme - prime security?

Does the prime (which needs to be larger than the message) have to be chosen randomly for security, or can it just be a huge constant? Also, the Wikipedia article for SSSS states The size of each ...
5
votes
1answer
386 views

Does zero-padding the secret in Shamir's sharing scheme increase security?

When performed in binary Galois fields $GF_{2^n}$, Shamir's threshold secret sharing scheme produces shares that are each the same bit-size as the secret. Though the scheme is "perfectly secure" in ...
5
votes
1answer
139 views

Secret sharing where the combination of shares matters

In Shamir's secret sharing scheme, any combination of shares (that pass the threshold) will result in the secret being revealed. Is it possible to have a system where some combinations are invalid? ...
5
votes
3answers
2k views

Secret sharing scheme with possibility to change the secret

Here's a scenario I want to handle with a secret sharing scheme: Alice wants to share the secret $S$ with Bob, Charlie and Dave. Alice generates private shares based on $S$ for Bob, Charlie and Dave, ...

1
2 3 4 5
8