Shafi Goldwasser and Silvio Micali: Proving Cryptography Works

Zusammenfassung

Before Shafi Goldwasser and Silvio Micali, cryptography was a craft: you built a cipher, and you trusted it until someone broke it. As Berkeley graduate students in the early 1980s — both advised by Manuel Blum — they turned it into a science. Their 1982 work on probabilistic encryption gave cryptography its first rigorous definition of security and a proof that a scheme meets it; their 1985 paper with Charles Rackoff invented zero-knowledge proofs, the paradox-flavored idea that you can prove a statement is true while revealing nothing else whatsoever. Rejected three times before a conference would take it, the zero-knowledge paper went on to win the first Gödel Prize, reshape complexity theory, and — three decades later — run inside privacy coins, blockchain rollups, and identity systems. The pair shared the 2012 Turing Award for laying “the complexity-theoretic foundations for the science of cryptography.”

Two Roads to Berkeley

Shafi Goldwasser (born 1959 in New York City, raised in Tel Aviv) came to cryptography sideways: a mathematics degree at Carnegie Mellon (1979), then graduate school at UC Berkeley, where she fell in with the orbit of Manuel Blum, the complexity theorist who treated cryptographic puzzles as questions about computational hardness. Silvio Micali (born October 13, 1954 in Palermo, Sicily) had studied mathematics at La Sapienza in Rome before joining the same group; he finished his Berkeley Ph.D. under Blum in 1982, Goldwasser hers in 1984. In 1983 both landed at MIT, where both have remained — Goldwasser later also professor at the Weizmann Institute and director of Berkeley’s Simons Institute for the Theory of Computing (2018–2024).

The field they entered had just been detonated by Diffie and Hellman’s public-key revolution and the RSA cryptosystem (see Public Key Cryptography). But nobody could say precisely what “secure” meant. RSA as then used was deterministic: the same message always encrypts to the same ciphertext, so an eavesdropper can confirm a guess — fatal if the message space is small (“attack at dawn” or “attack at dusk”). Security claims were folklore plus the absence of a known break.

Probabilistic Encryption: Defining “Secure”

It started, characteristically for the Blum school, with a game: how can two distrustful players deal a fair hand of mental poker over a telephone line? Goldwasser and Micali’s answer grew into their 1982 paper Probabilistic Encryption, which did three things no one had done before. It defined security as a precise adversary game — semantic security: whatever an eavesdropper can compute about the plaintext from the ciphertext, she could have computed without it. It showed the definition is achievable, with an encryption scheme that flips coins so that one message encrypts to many possible ciphertexts. And it proved the scheme meets the definition, assuming a clean number-theoretic problem is hard.

That three-step template — define the threat model, construct the scheme, reduce its security to a hard problem — is provable security, and it is how all serious cryptography has been done since. Randomized encryption, the paper’s “extravagant” device, is today a baseline requirement of every standardized encryption mode.

Zero-Knowledge: Proving Without Revealing

In 1985, with Charles Rackoff, they published The Knowledge Complexity of Interactive Proof Systems — and gave the world the zero-knowledge proof. The setting is an interactive game: a prover wants to convince a skeptical verifier that a statement is true. The shocking result is that for a vast class of statements this can be done so that the verifier ends up certain the statement holds, yet has learned nothing else — formally, everything the verifier saw could have been simulated without the prover’s help. You can prove you know a password without uttering it, prove a transaction is valid without disclosing amounts, prove you are over 18 without showing your birthdate.

The paper had been rejected three times by conference committees who could not see the point before STOC accepted it in 1985. In 1993 it won the first Gödel Prize ever awarded. Its companion notion of interactive proofs detonated complexity theory: the chain of results it triggered led to IP = PSPACE and the PCP theorem — work on probabilistically checkable proofs and hardness of approximation that earned Goldwasser a share of the 2001 Gödel Prize as well (see P vs. NP and Complexity Theory).

Around the twin pillars the two built much of modern cryptography’s vocabulary, with collaborators including Oded Goldreich and Avi Wigderson: the first provably secure digital signature scheme (Goldwasser–Micali–Rivest, 1988), pseudorandom functions (Goldreich–Goldwasser–Micali, 1986), the Blum–Micali pseudorandom generator, secure multiparty computation (the GMW protocol, 1987 — mutually distrustful parties jointly computing on private data), and Micali’s verifiable random functions (1999).

From Paradox to Infrastructure

For two decades zero-knowledge proofs were celebrated theory with almost no deployments — too slow, too exotic. Then the 2010s arrived. Succinct non-interactive variants (zk-SNARKs) made proofs small and fast to verify; the privacy cryptocurrency Zcash (2016) put them into production money; Ethereum’s zk-rollups now use them to compress thousands of transactions into one verifiable proof; governments and companies prototype them for credentials that disclose only what is necessary (see The Cryptocurrency Revolution and The Privacy War). Micali joined the deployment wave personally, founding Algorand (2017), a proof-of-stake blockchain whose consensus leans on his verifiable random functions. In 2013 the two received the 2012 Turing Award; the citation credited them with making cryptography “a precise science.”

⚠️ Dead End: Peppercoin and the Micropayments Mirage

Micali’s earlier entrepreneurial outing is a textbook dead end. Peppercoin, co-founded around 2001 with RSA’s Ron Rivest, used elegant cryptographic aggregation to make payments of a few cents economically viable — solving the problem that card processing fees dwarf a 25-cent purchase. The cryptography worked; the market never showed up. Consumers preferred subscriptions and advertising-funded content to per-article nickels, merchants saw no demand, and Peppercoin was sold off quietly in 2007. It joined a long graveyard of technically sound micropayment schemes (DigiCash, Millicent, the Web’s still-reserved HTTP status code 402 Payment Required) — a reminder that proving a protocol secure is the easy half; proving people want it admits no reduction. Ironically, the micropayments dream was later partially resurrected by the blockchain systems zero-knowledge proofs now power.

Fun Fact: Two Gödels

Goldwasser was the first person ever to win the Gödel Prize twice — 1993 for zero-knowledge, 2001 for the PCP/hardness-of-approximation line — a double that only a handful of researchers have matched since. Not bad for a body of work whose founding paper the field initially rejected three times.