How replaceable is public key crypto?

Suppose that there were was no number theory, no elliptic curves, no lattice-based crypto. Perhaps because our universe was rigged against cryptographers, or perhaps because our society had never decided to explore abstruse mathematics.

How bad would this be? Would electronic commerce be impossible? Would modern society crumble? In this post I’ll explore the possibility that it would be more “annoying” than “catastrophic.”

The model

I’ll assume that we have some 256 bit cryptographic hash function F, but no other cryptographic primitives. (Actually I’m going to be sloppy and basically just pretend that F works like a random oracle that anyone can access. I think all the constructions can adapted to work with an arbitrary hash function but that’s not very important.)

Constructing F doesn’t require number theory or any kind of magic. You can basically just start from a bunch of bits and jumble them up in some random way. The trick is just to make sure they are really jumbled, that there wasn’t some pattern that an attacker could exploit.

(Of course you can use a hash function to implement Merkle’s Puzzles, but I’ll assume attackers have a lot of computation so that we need stronger security. You can also use a hash function to implement Lamport signatures, gives the defender an exponential advantage. That’s worth having in mind, but we won’t really talk about signatures because establishing shared secrets for communication seems much harder.)

Distributing shared secrets

Without public key cryptography, if Alice and Bob want to talk privately then they basically need a shared secret. If they have a shared secret s and Alice wants to send a message m, then Alice sends ⊕ m (the XOR of s and m), and Bob can recover m by computing ⊕ (s ⊕ m) = m.

The first important observation is that a 256-bit shared secret allows Alice and Bob to talk for as long as they want, by just using their secret to create a new pseudorandom pad for each message. That is, if Alice and Bob share a secret s, then Alice can send a message m by picking k at random, and sending the pair (k, F(sk) ⊕ m). It’s easy to confirm that Bob can still get the message, and if F is random then this is secure.

I can make this message tamper-evident by instead sending (k, F(sk) ⊕ m, F(skm)). Then an attacker can’t construct any valid-looking message, so even if they can modify messages the only thing they can do is block some of them.

So now the game becomes: how do we distribute shared secrets to any pair of people who want to talk?

There are two useful primitives:

  • If Alice and Bob have a shared secret, and Bob and Charlie have a shared secret, then Alice and Charlie can established a shared secret by sending it through Bob. The downsides are that you need these pre-existing links, and that Bob knows their shared “secret” and so can eavesdrop if they use it.
  • If Alice and Bob have two shared secrets, they can XOR them to get a new more secure shared secret. In particular, if Charlie knows one of their shared secrets, and Denise knows the other one, then Charlie and Denise would need to work together in order to discover the new secret. If we do this across many intermediaries, Alice and Bob just need to rely on one intermediary keeping the secret secure.

The big problem is now establishing these initial shared secrets. Here’s a proposal, mirroring current infrastructure for certificate authorities:

  • There are a bunch of independently operated “secret distributors.” Each secret distributor has a shared secret with each computer manufacturer. When I buy a computer, it comes with a shared secret for each secret distributor (which is sent from the manufacturer to the secret distributor using their shared secret). This is analogous to the status quo, where we put public keys for trusted “root” certificate authorities on each computer.
  • A company like Amazon will have a shared secret with a handful of secret distributors. Registering an identity with secret distributors is analogous to getting a certificate signed by a certificate authority in the status quo, and involves establishing a public identity.
  • To communicate securely with Amazon, we use several secret distributors (who can talk privately to both you and Amazon) and then XOR the resulting keys. You and Amazon then both store this secret (you store it encrypted on your machine, they store it in the same way they’d store a hash of your password).

This system mirrors the existing centralized system of certificate authorities, but you could also implement a distributed version analogous to a web of trust. I think you can achieve secure communication as long as a reasonable fraction (say 10%) of users are honest, and if the honest users are sufficiently well-connected, even if they don’t know who each other are. But actually implementing that involves a lot of algorithmic work and I think it’s an open problem.

How does this compare to the status quo?

In the status quo, services like Amazon verify their identity and then getting a certificate signed. How different is this from establishing a shared secret with a handful of distributors?

  • If a secret distributor cheats, they can eavesdrop on your messages to Amazon. The same is true for a certificate authority signing a bogus certificate, but it’s much easier to tell when a certificate authority fails because they have to actually publish the bad certificate. This is why I think you’d need to ensemble over a bunch of secret distributors, while it’s reasonable to trust a single authority in the status quo (though realistically the status quo doesn’t seem that secure).
  • The secret distributors are active participants in each new sign-on to Amazon, whereas a certificate authority can be passive after the initial signing. This is still a small share of total web traffic, but it would be a huge extra hassle at several points and probably we’d have to be more mindful about what traffic is encrypted (e.g. this blog might not be encrypted until you make a wordpress account, which would involve a round-trip to secret distributors). The biggest problem may be that these active participants need to maintain shared secrets, so it’s really hard to delegate.
  • We need the secrets that come with your computer to remain secret. This is harder than ensuring integrity, which is all that is needed in the status quo, and if the manufacturer cheats by observing a secret then it’s harder to observe (than if they’d inserted a backdoor). We can ameliorate these problems by aggregating secret keys from separate distribution mechanisms. For example, computers could be sold with a small secure chip from a separate manufacturer that implements a pseudorandom function.
  • An attacker who stores my communication and then later gets my shared secret (e.g. through a security breach at a secret distributor or Amazon) can decrypt all that communication. We can ameliorate this risk by periodically refreshing our secrets and then burning the old one.
  • Spreading high-integrity data is much easier than spreading secret data. Root certificates can in principle be transmitted from person to person by word of mouth. But re-establishing shared secrets requires new physical distribution. Ideally you’d just solve this with the same secure hardware, so that as long as the integrity of the secret-generating chip is preserved then you can just regenerate secrets. (And if the integrity of your computer hardware is compromised, you generally need to get rid of it anyway.)
  • This requires keeping track of more secrets, but the additional cost seems negligible compared to the other issues above (and normally you track more than 256 bits for each contact anyway). All of these operations are very fast and simple compared to public key cryptography, so at least we save a bit of trouble from not needing to implement that.

(Glenn Willen points out on Facebook that the key difference may be that the Certificate Authority system works quite poorly, and in practice public-key cryptography works OK anyway (and in particular is protected from passive eavesdropping), while this system would actually require secret distributors to work in order to have protection even from passive eavesdropping.)


Overall this sounds like a big pain, and like it introduces some additional surface for attacks; but it doesn’t sound different-in-kind from existing infrastructure for signing public keys. Thinking through this exercise overall made me feel like public key cryptography is less critical than I’d assumed. I think the additional costs in this post mostly don’t interact multiplicatively with other security concerns, and so I expect losing public key cryptography would only increase the total cost of computer security by a modest fraction.

I expect there are other big costs that I didn’t think of, and overall I think there is a significant probability that it would be radically harder to make do without public key cryptography, for one reason or another. I also think these costs would have been prohibitive earlier in history (and may only become manageable in practice once we have relatively good tamper-resistant hardware), and so this certainly would have delayed the availability of secure communication.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s