To spend seven years honing a single concept requires a certain level of intellectual stubbornness. Just focusing on one fundamental question until the solution is clear enough to publish, without turning it into a book or branching out into other areas. That is essentially what Danny Dolev, Cynthia Dwork, and Moni Naor accomplished between 1991 and 2000. The outcome, a paper titled “Nonmalleable Cryptography,” went on to become one of the most cited works in the field’s history. More than 2,100 citations to date. In theoretical computer science, that number is uncommon.
The paper began as a conference contribution at the Symposium on the Theory of Computing (STOC) in 1991, which is akin to getting into a major film festival before anyone knows your name. The three researchers presented a seemingly straightforward concept: what if an encrypted message could be made impervious to both manipulation and decryption? The question of whether an attacker could deduce anything useful from a ciphertext had already been addressed by semantic security, the dominant standard at the time. Naor, Dwork, and Dolev posed a more challenging query. Is it possible for an attacker to create a different ciphertext with a hidden plaintext that is meaningfully related to the original without ever cracking the encryption?
It turned out that, in the majority of current systems, the answer was yes. And that possibility—almost undetectable until they gave it a name—opened a rather frightening door. Contract bidding served as their inspiring example. Consider a municipality that is gathering encrypted, sealed bids for a building project. The encrypted offer is submitted by Company A. Company B merely modifies Company A’s ciphertext in a way that consistently results in a marginally lower bid without ever cracking the encryption. Decryption is not necessary. It is not necessary to know the original figure. Quietly, the system is compromised from the outside. It’s the kind of attack that seems almost too sophisticated to be true, which could be one of the reasons it took the field so long to take it seriously.
Dwork, who works at IBM’s Almaden Research Center in San Jose, contributed accuracy and tenacity to the partnership. Naor had already given commitment schemes and zero-knowledge proofs a lot of thought while working primarily at the Weizmann Institute. Dolev had a long history of considering the fault-tolerant edges of distributed systems at Hebrew University in Jerusalem. Together, they were attempting to create something that did not presume the assailant was constrained, courteous, or even noticeable. When their cryptosystem was finally formalized and published in the SIAM Journal on Computing in 2000, it was the first to be shown to be safe against the chosen ciphertext attack that Rackoff and Simon had suggested, in which the attacker knows the target ciphertext and can query a decryption oracle on any other ciphertext she chooses. That adversarial model is truly brutal. The final paper’s density reflects the years of revision required to prove security under it.
The difference between 1991 and 2000 is intriguing because none of the three researchers were idle or distracted during that time. It’s more that the formal apparatus needed to validate the findings was still in its infancy. The paper had to keep up with the rapid evolution of cryptographic proof techniques during the 1990s. There is something almost archaeological about the 1995 submission, the 1999 acceptance, and the 2000 publication. Revision layers condensed into a single document.
There has been a significant downstream impact. Serious cryptographic schemes were expected to achieve non-malleability as a standard property. It influenced researchers’ perspectives on commitment schemes, zero-knowledge proofs, and building protocols that are impervious to adaptive adversaries. The 1991 framework served as the foundation for papers by Sahai, Crescenzo, Ishai, and Ostrovsky, as well as later by Bellare and Rogaway. This conceptual vocabulary contributes to the security guarantees of the Cramer-Shoup encryption scheme, which is regarded as one of the cleanest practical outcomes in public-key cryptography.
The seven-year timeline might have been beneficial. A 1992 result that was released too soon could have left gaps that took ten more years to fill. Rather, by the time the SIAM version was released, the field had advanced enough to comprehend what it was reading, the definitions were precise, and the proofs were strong. The slow paper may be the best one at times.
