The 2024 Developer Survey results are live! See the results

# Tag Info

### 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 ...

### 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, ...
• 20.6k

### 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 ...
• 9,557
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 ...
• 49.2k

### 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 ...
• 231
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 ...
• 149k
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 ...
• 143k
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 ...
• 38.8k
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,086

### 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 ...
• 23.1k

### 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 ...
• 23.1k

### 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 ...
• 46.3k
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$ (...
• 87.5k

### 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 ...
• 46.3k
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 ...
• 5,002

### 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 ...
• 28.1k
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$ ...
• 143k
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 ...
• 87.5k
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 ...
• 24.5k