# 3: Secret Sharing

DNS is the system that maps human-memorable Internet domains like irs.gov to machine-readable IP addresses like 166.123.218.220. If an attacker can masquerade as the DNS system and convince your computer that irs.gov actually resides at some other IP address, it’s not hard to imagine the kind of trouble you might be facing.

To protect against these kinds of attacks, a replacement called DNSSEC is slowly being rolled out. DNSSEC uses cryptography to make it impossible to falsify a domain-name mapping. The cryptography required to authenticate DNS mappings is certainly interesting, but an even more fundamental question is, who can be trusted with the master cryptographic keys to the system? The non-profit organization in charge of these kinds of things (ICANN) has chosen the following system. The master key is split into 7 pieces and distributed on smart cards to 7 geographically diverse people, who keep them in safe-deposit boxes.

At least five key-holding members of this fellowship would have to meet at a secure data center in the United States to reboot [DNSSEC] in case of a very unlikely system collapse.

“If you round up five of these guys, they can decrypt [the root key] should the West Coast fall in the water and the East Coast get hit by a nuclear bomb,” Richard Lamb, program manager for DNSSEC at ICANN, told TechNewsDaily.$$^{[1]}$$

How is it possible that any 5 out of the 7 key-holders can reconstruct the master key, but (presumably) 4 out of the 7 cannot? The solution lies in a cryptographic tool called a secret-sharing scheme, the topic of this chapter.

• 3.1: Definitions
To translate this informal statement into a formal security definition, we follow the The Central Principle of Security Definitions TM and define two libraries that allow the calling program to learn a set of shares (for an unauthorized set), and that differ only in which secret is shared. If the two libraries are interchangeable, then we conclude that seeing an unauthorized set of shares leaks no information about the choice of secret message.
• 3.2: A Simple 2-out-of-2 Scheme
• 3.3: Polynomial Interpolation
You are probably familiar with the fact that two points determine a line (in Euclidean geometry). It is also true that 3 points determine a parabola, and so on. The next secret sharing scheme we discuss is based on the following principle: d+1 points determine a unique degree- d polynomial, and this is true even working modulo a prime.
• 3.4: Shamir Secret Sharing
Part of the challenge in designing a secret-sharing scheme is making sure that any authorized set of users can reconstruct the secret. We have just seen that any d+1 points on a degree-d polynomial are enough to reconstruct the polynomial. So a natural approach for secret sharing is to let each user’s share be a point on a polynomial. That’s exactly what Shamir secret sharing does.
• 3.5: Visual Secret Sharing
• Exercises