15 votes

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 ...
13 votes
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 ...
  • 44.3k
12 votes
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 ...
  • 135k
11 votes

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, ...
11 votes
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 ...
  • 126k
11 votes
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.9k
10 votes
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.8k
10 votes

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.9k
10 votes

Why are binary extension fields preferred for Shamir secret sharing?

The main reason is that there is no disadvantage to using a binary extension field. Since the computing and communications infrastructure already runs over binary, this is the simplest and most ...
  • 16.9k
9 votes
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 ...
  • 135k
9 votes
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,026
9 votes

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 ...
8 votes

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 ...
  • 135k
8 votes

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
8 votes

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 ...
8 votes
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,832
8 votes

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 ...
8 votes
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$ ...
  • 126k
8 votes

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 ...
8 votes
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$ (...
8 votes
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 ...
  • 12k
7 votes
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 ...
7 votes
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 ...
  • 126k
7 votes
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 ...
7 votes
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
7 votes

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$-...
7 votes
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 ...
  • 135k
7 votes
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 ...
7 votes
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 ...
7 votes
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 ...

Only top scored, non community-wiki answers of a minimum length are eligible