# Tag Info

## Hot answers tagged secret-sharing

### Computational Complexity Of Breaking Information Theoretic Security

Here's an simpler but analogous problem that may illustrate what's going on: Given that $X=Y+Z$ and $Y=5$, compute $X$. The problem isn't that the answer is difficult to compute, the problem is that ...
Accepted

### Computational Complexity Of Breaking Information Theoretic Security

This is about the Theory of Computability not the Theory of Complexity. The halting problem is a decision problem in CS. From Wikipedia's introduction; In computability theory, the halting problem is ...
• 43k
Accepted

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

Here is an active attack on the privacy of out-of-the-box SSS. For this attack, we'll assume that the attacker (without a valid share) is allowed to participate (with $T-1$ friends with honest key ...
• 131k

### What are the ways to generate Beaver triples for multiplication gate?

Nowadays, the most standard method is to use oblivious transfers. Oblivious transfer involve a sender with two messages $(m_0,m_1)$ and a receiver with a selection bit $b$. At the end of the protocol, ...
• 16.6k
Accepted

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

In RSA, assuming knowledge of the public key but not the private key, analyzing any number of triplets of matching message, encrypted message, and signature $(m,M,sg)$, does not help (as far as we ...
• 122k
Accepted

### What are the weaknesses of Shamir's Secret Sharing?

let's say have used a 64-bit secret key to encrypt a file and then we split the key into 2 pieces of 32-bit That right there is your misunderstanding. Shamir secret sharing does not split a secret ...
• 37.7k

### Practical examples of Threshold Secret Sharing?

I worked on a secure document management project 20 years ago which used secret sharing. It is widely used in financial networks. Actual use cases with public details that are easily accessible ...
• 16.1k
Accepted

### Recover from compromised shares with Shamir Secret Sharing

The point is that the dealer generating the update needn't know what the shared secret is. If we had a dealer that remembered what the shared secret was (or we asked enough people to contribute their ...
• 131k
Accepted

### Beavers Triple Vs BGW Multiplication on MPC

Yes, preprocessing Beaver triples in an offline phase leads to a faster online phase. The online phase of an AND gate requires just two openings plus local computations. But there are other ...
• 10.6k

### Computational Complexity Of Breaking Information Theoretic Security

As others have noted, information-theoretic security really has no connection to computational complexity. Yes, with sufficient computing power, you could enumerate all the solutions (including the ...
• 44.2k

### Choosing finite field size in Shamir's Secret Sharing Scheme

Actually, you can do Shamir Secret Sharing over any finite field $GF(p^k)$, for any prime $p$ and any integer $k$. If $k=1$, you have the $GF(p)$ field you mentioned; however it works on extension ...
• 131k

### Running time of Shamir's secret sharing scheme

Is the running times of corresponding steps true? No. Step 3 of the dealer has to be executed $n$ times (once for each party) with each execution taking $O(t)$ time. So it must be $O(t\cdot n)$. ...
• 2,015

### Multiplying two additively shared values

This cannot be achieved information-theoretically. This is typically the task that requires multiparty computation protocol to be achieved. In particular, the common method for what you want is called ...
• 16.6k
Accepted

### Secret sharing scheme with ability to add or update share number

With Shamir's Secret Sharing you can add as many shares as you want, as long as the threshold and the secret is unchanged. You can see that neither the generation of the polynomial that produces the ...
• 4,822

### Secret sharing where the combination of shares matters

Yes. It is possible to construct secret sharing schemes for general (monotone) access structures. You can read about the first construction in the paper called Secret Sharing Scheme Realizing General ...
• 26.9k
Accepted

### Is this a good way of splitting a private key into a 2 of 3 scheme?

The proposed sharing scheme does allow reconstruction of key $K$ from any two of the three shares $K_A$, $K_B$, $K_C=(X_A,X_B)$, because: $K=K_A+K_B$ from $K_A$ and $K_B$ $K=K_A\oplus X_A$ from $K_A$ ...
• 122k

### What is the maximum number of shares in Shamir's Secret Sharing?

The maximum number of shares in Shamir's secret sharing is limited by the size of the underlying finite field. In particular, the maximum is one less than the number of elements in the field, since ...
• 44.2k
Accepted

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

Let's recall Shamir's Secret Sharing. We work in a finite field $\mathbb{F}_q$ of cardinal $q$. The secret to share is $s$; we want $n$ shares with a threshold $t$. We suppose that $n < q$ (...
• 84.5k
Accepted

### Can we use fixed Beaver's multiplication triples many times?

If you reuse the same multiplication triples, then you leak information about the secret shared values that you multiply. Let's recall how the multiplication works in Beaver's protocol for secure ...
• 1,006
Accepted

### Shamir secret sharing where some specific people are required to participate

It's very straightforward. You divide your secret into three random shares $s=s_x\oplus s_y\oplus s_z$. Now divide $s_z$ into $N-2$ shares using SSSS and pass these to the non-special participants ...
• 9,596
Accepted

### How are one-time pads distributed?

If you perform the distribution digitally (using networks) then you have a problem. Unless you use another one time pad you lose the perfect confidentiality as the distribution itself won't deliver ...
Accepted

### An electronic voting system

Full disclosure: In 2007 I founded an association aiming at voting transparency. I'm proud that my efforts may have had some role, however small, in the fact that the number of French cities using ...
• 122k
Accepted

### When all shares of a secret are given to adversary as a permuted matrix

Let us first consider the problem without involving Shamir secret-sharing at all. Suppose that $n = 140$ and that the secret $\sigma$ is a 140-byte Twitter message. The space is thus restricted ...
• 2,616
Accepted

### SPDZ for the 2-party case

Your understanding is correct. The SPDZ protocol can be used for any number of two or more parties. In fact, this is one of the strengths of the SPDZ protocol. Namely, many recent secure computation ...
• 2,857

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

Here's one more way in which a dishonest participant can mess with Shamir's secret sharing: Let's briefly review how secret reconstruction in Shamir's $(k,n)$ secret sharing works. Given the $x$-...
• 44.2k
Accepted

### Secret sharing between a very large number of participants

Is there an algorithm that can realistically generate keys for value of k between 1,000 and 1,000,000? How about Shamir's Secret Sharing method? For $k = 1000000$, generating a share would take a ...
• 131k
Accepted

### Do people not care about side channel resistance?

Some implementers take notice of side-channels. An excerpt which is most relevant to your question: Another important point is that when timing attacks apply, they are all-encompassing: if the ...
• 84.5k
Accepted

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

Each person might be allotted more than one share of the secret. Let $G$, $C$ and $D$ denote the number of shares allotted to a General, a Colonel, and a Desk Clerk respectively, and let $T$ denote ...
• 2,616
Accepted

### secret sharing with 3 parties under constraint

This problem is known as conditional disclosure of secret in cryptography. There have been many nice recent works on the subject, I suggest having a quick look at this one for example. In you exact ...
• 16.6k
This $(k,n)$ scheme works, but isn't very interesting. Effectively, it is: For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the ...