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 ...
Gordon Davisson's user avatar
14 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, ...
Geoffroy Couteau's user avatar
14 votes

For Symmetric Cryptography, why is it considered more important to safeguard a key than the function/algorithm for encrypting/decrypting a message?

Some facts for you to consider: Brutal-force a cryptographic key is much harder than brutal-force breaking into a house - the former can take as long as for a star to explode, while the latter take ...
DannyNiu's user avatar
  • 9,207
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 ...
kelalaka's user avatar
  • 48.5k
13 votes

For Symmetric Cryptography, why is it considered more important to safeguard a key than the function/algorithm for encrypting/decrypting a message?

At least two reasons. 1: security. You want your algorithm to be a good one. One of the best ways we know of ensuring cryptographic algorithms are good is to have as many experts as possible assess ...
ignis volens's user avatar
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 ...
poncho's user avatar
  • 147k
12 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 ...
fgrieu's user avatar
  • 141k
11 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 ...
Mikero's user avatar
  • 13.2k
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 ...
mikeazo's user avatar
  • 38.6k
11 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 ...
Cryptonaut's user avatar
  • 1,066
11 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 ...
kodlu's user avatar
  • 22.5k
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 ...
kodlu's user avatar
  • 22.5k
9 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 ...
Ilmari Karonen's user avatar
9 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$ (...
Thomas Pornin's user avatar
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 ...
Ilmari Karonen's user avatar
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 ...
cygnusv's user avatar
  • 4,952
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 ...
Geoffroy Couteau's user avatar
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)$. ...
Artjom B.'s user avatar
  • 2,045
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 ...
Yehuda Lindell's user avatar
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$ ...
fgrieu's user avatar
  • 141k
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 ...
Daniel S's user avatar
  • 23.8k
8 votes
Accepted

Is there a way to calculate a hash with two people so that no one knows the pre-image but if they get together they do?

One simple option: The preimage consists of 2 segments $M_A$, $M_B$ of 64 bytes each. They are given to or chosen by $A$ and $B$ respectively. $A$ computes the 32-byte $H_A=R(\mathsf{IV},M_A)$ where $...
fgrieu's user avatar
  • 141k
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 ...
Dilip Sarwate's user avatar
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 ...
Guut Boy's user avatar
  • 2,877
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$-...
Ilmari Karonen's user avatar
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 ...
poncho's user avatar
  • 147k
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 ...
Thomas Pornin's user avatar
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 ...
Dilip Sarwate's user avatar
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 ...
Geoffroy Couteau's user avatar
7 votes
Accepted

Secret sharing over reals - constructing a (k,n) threshold scheme

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 ...
poncho's user avatar
  • 147k

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