Computational cryptography › Live on mainnet today
Foundational assumption

Key exchange / public-key encryption exist

In plain words

Can two parties agree on a secret while everyone listens? Some parts of Ethereum depend on that stronger kind of assumption. Others, like ordinary account signatures, don't.

The idea: A plain one-way function lets you lock something that only you can open later, but not something a stranger can lock for you, or a secret two strangers can agree on in public. For that the problem needs extra structure: a hidden shortcut (a trapdoor, as in RSA), or a way for two secrets to combine (as in Diffie-Hellman). The second needs less: Diffie-Hellman gives encryption without any trapdoor. Impagliazzo and Rudich showed that no straightforward ("black-box") construction gets this from a one-way function alone, which is why it's a separate, stronger bet.

Why it matters: Shows which pieces of Ethereum would survive if public-key encryption turned out to be impossible.

The details

On the map: needs more than one-way functions (Cryptomania). If impossible, every KE-tagged assumption falls: P2P handshakes, BLS consensus, KZG blobs, BN254 SNARKs. ECDSA accounts (ECDLP only), hashes and STARKs survive

The assumption that two parties can agree on a secret over a public channel, or encrypt to a public key. It needs more than one-way functions[1, 2].

On this map, the assumptions tagged KE each give key exchange on their own: curve Diffie-Hellman (used in peer-to-peer handshakes), co-CDH and q-SDH on BLS12-381 (BLS signatures, KZG), and the q-type assumptions on BN254 (SNARK verifiers). If public-key encryption were impossible, all of those would fall.

What would survive: ECDSA accounts, which rest on discrete log alone, plus every hash-based component: Merkle-Patricia tries, SSZ, STARKs and all the hash-based post-quantum plans.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (18 boxes)

References

  1. R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89, 1989. doi:10.1145/73007.73012
  2. R. Impagliazzo. A personal view of average-case complexity. Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, 1995. doi:10.1109/sct.1995.514853