Foundations of Cryptography

Welcome class! Today, we are discussing the concept of secret sharing. Can anyone tell me what they think this might mean?

Is it about sharing a secret among friends?

That's a good start! Secret sharing in cryptography involves distributing a secret among multiple parties to ensure robust access control. For example, think about how a bank locker requires two keys to open.

So, if one key is lost, we still can't access the locker?

Exactly! This ensures that no single entity can access the locker alone. This principle is the foundation of many secure systems.

What about the nuclear weapons example you mentioned?

Good question! The nuclear access codes were shared among high-level officials so that at least two had to collaborate to launch. This setup greatly increases security.

To remember this, think of the acronym 'SAFEC': Security through Access control from Finite Entities and Collaboration.

In summary, secret sharing enhances security and prevents unauthorized use.

Now, let's introduce the (n, t) secret sharing model. Can anyone explain what the parameters 'n' and 't' mean?

I think 'n' is the total number of parties sharing the secret?

Correct! 'n' refers to the number of shareholders. What about 't'?

Isn't 't' the threshold required to reconstruct the secret?

Yes! The threshold 't' means that at least 't + 1' shareholders are needed to reconstruct the secret. This provides a safeguard against unauthorized access.

What happens if we have only 't' or fewer shareholders?

Great question! In such cases, it's impossible to reconstruct the secret, protecting it from leakage. Remember the mnemonic 'No More Than t gets it.'

To summarize, the (n, t) secret sharing model is both a practical and secure method for secret distribution.

Next, let’s discuss Shamir's secret sharing scheme. Can anyone give a brief description of how it works?

Does it involve polynomials?

Yes! The dealer creates a random polynomial of degree 't' where the constant term is the secret to share. Who can explain why choosing a polynomial works?

Because you need at least 't + 1' points to reconstruct it?

Exactly! This ensures that any groups of 't' participants cannot identify the secret since multiple polynomials can pass through a given number of points.

How do we get our shares?

Good question! The shares are calculated by evaluating the polynomial at different distinct points, which only the dealer knows. As a mnemonic, think 'Random Roots Reconstruct.'

So, the use of polynomials in Shamir's scheme makes it very robust and secure.

Let’s now explore the security aspect. Why do you think the secret shares must be kept private?

So that no one can reconstruct the secret without enough shares?

Exactly! If 't' or fewer shares are gained, the secret remains safe. How does the finite field aid this security?

It prevents revealing any information about the secret based on share values?

Spot on! Since multiple polynomials can create the same shares, knowing some shares won't leak the actual secret. This concept can be remembered with 'Finite Fields Feel Secure'.

In summary, Shamir's scheme utilizes secret sharing with polynomials and finite fields to ensure security and privacy effectively.