Tectonic Chief Scientist Dr. Omri Shmueli and Collaborator Prof. Mark Zhandry Win Crypto 2025 Best Paper Award

The annual Crypto conference, organized by the International Association for Cryptologic Research (IACR) since 1981, is widely regarded as one of the premier venues for exchanging and developing ideas and reporting cutting-edge research. Since 2004, several IACR conferences have conferred Best Paper awards, initiating the IACR publication awards list that has since become a marquee of outstanding cryptographic research.

The newest addition to this prestigious list is a recent paper by Omri Shmueli (Tectonic, NTT Research) and Mark Zhandry (Stanford, NTT Research), providing significant breakthroughs towards constructing a cryptographic primitive called one-shot signatures (OSS). In slightly more detail, they have managed to construct this elusive primitive “in a standard model” (alongside proving two similarly significant, but less accessible, theorems). Let us explore what this means.

Models vs. Reality

First, what do I mean by reducing assumptions to a “standard model”?

A common way to divide labor when working on a new cryptographic idea is to first work in a model that assumes we have already solved some related problems (though we actually didn’t). If we manage to build a primitive in that model, and prove its security, we in fact reduced the original problem to the related problems. This allows us to start with tailor-made assumptions, gradually remove them, until hopefully there are none. A close second outcome is reducing the construction to a standard model.

Calling a model “standard” is a cultural statement, not a mathematical one. It could mean that surveying a random cohort of ten cryptographers, say, at least seven will agree that it is standard. Relying on a standard model means that considerable effort is already dedicated to removing the remaining obstacles, and typically, there already is a great deal of knowledge and important observations about them.

(It is important not to confuse model assumptions with hardness assumptions, such as the difficulty of factoring numbers into primes or computing discrete logarithms. Hardness assumptions are about the real world, and are used in real-world implementations. A model is a mathematical tool for “working backwards”, proving what we can do assuming some other problem is already solved.)

Reducing the assumptions underlying one-shot signatures to a standard model is a key result of Shmueli and Zhandry’s paper.

One-shot signatures were first discussed by Amos et al. in 2020 (although they implicitly follow from an earlier work by Zhandry, which makes even stronger assumptions, one of which was broken). Their paper primarily focuses on the implications of such signatures, while also providing a construction, albeit in a highly specialized model. (Moreover, while the construction was not explicitly broken, and is still potentially secure, there is a flaw in the security proof that the authors deem fundamental. See the latter attached at the top of the preprint.)

For a while, no significant headway was recorded, and OSS seemed like a dead end. Until Shmueli and Zhandry closed the gap almost entirely by providing a construction in a standard model: post-quantum indistinguishability obfuscation (iO). Loosely speaking, iO allows you to “scramble” computer programs in a way that does not leak information about their implementation (for example, encrypting messages without revealing the secret key).

The good news is that iO has a wide range of other implications (Barak and Brakersky crowned it “the Swiss Army Knife of Cryptography”), making it a very hot research topic. The bad news is that constructing iO is notoriously difficult. Despite the idea first proposed as early as 1996 (though only appearing explicitly in the literature in a 2001 paper by Barak et al., also see the 2007 survey by Goldwasser and Rothblum), it took until 2020 before a full construction was proposed in an earthquake of a paper by Jain-Lin-Sahai.

The authors base their construction on four standard hardness assumptions. Unfortunately, one of which is known to be quantum-broken. Since OSS is a quantum primitive, this construction is inappropriate in most scenarios. The only known post-quantum iO constructions rely on specialized assumptions.

There are still a few hurdles to jump, but Shmueli and Zhandry’s construction bridges the gap considerably.

Dreams of a Quantum Internet

In the late 1960s, Stephan Wiesner, an upcoming Columbia graduate student, came to a startling realization: if used just right, the laws of quantum mechanics allow creating a new form of money. Money that is impossible to forge. The very first example of a new form of security, derived from the laws of nature themselves.

Unfortunately, Wiesner was ahead of his time. Scientific journals failed to recognize the importance of his work, which was not published until a decade and a half later, impacting the rest of Wiesner’s career. However, the manuscript continued to circulate, inspiring a new form of cryptography that is now known as uncloneable cryptography and is considered one of the central pillars of quantum cryptography.

At a high level, the key realization of uncloneable cryptography is that if you assume end users have quantum capabilities (often very modest capabilities, much more feasible than universal quantum computers), wonderful things happen. Ostensibly impossible things. (The most famous example is the BB84 protocol by Bennett and Brassard, which allows users to exchange keys over an insecure channel with unconditional security.)

However, these protocols tend to make one requirement that feels out of reach: users need the ability to transmit quantum states to each other. A quantum internet.

A natural question, and one that motivated OSS a great deal, is whether it is possible to achieve some of these miraculous properties without quantum communication. In some cases, it turns out that it isn’t (for example, it is not hard to prove that unconditionally secure key exchange is impossible without quantum communication). But curiously, not in all cases. And OSS very elegantly captures the “secret sauce” that allows concocting quantum magic over a classical channel.

Dequantumizing Communication With OSS

But what are one-shot signatures?

Recall that a signature scheme provides the ability to sign documents such that only you can sign messages (using a secret signing key), but everyone can verify them (using a corresponding public verification key). In one-shot signature schemes, the signature key is a quantum state that can only be used once. After that, the state collapses, and all that’s left is a classical signature.

Let's see the power of this primitive in practice.

Say we want to organize a rock concert (or even better, a cryptography conference). To prevent counterfeiting, we have decided to use uncloneable quantum tickets.

The easiest way to go about this is to use Wiesner’s quantum money (mentioned above) and treat each coin as a unique ticket. One hitch, though: concertgoers must carry fragile quantum tickets from the ticket office, storing them at home, and then transporting them again to the venue. This makes our otherwise completely reasonable solution quite brittle. Fortunately, one-shot signatures allow delegating the “quantumness” to the concertgoer.

Say Alice wants to go to the concert.

When buying the ticket, she first generates a key pair: a classical verification key pk_A, and a quantum signature key |sk_A⟩. Alice then sends pk_A to the ticket office, which signs it with its (standard, classical) signature key, and provides a signature sigma_T. Now (pk_A, sigma_T) is verifiably signed by the ticket office.

When redeeming the ticket, the bouncer first verifies that (pk_A, sigma_T) was indeed signed by the ticket office, ensuring that Alice paid for the ticket. Then, the bouncer sends Alice a random string r. Then, Alice finally uses |sk_A⟩ (destroying it in the process) to sign r. She provides the signature to the bouncer, who then verifies it with pk_A. This is the quantum-digital version of tearing the ticket. (Replacing the string r between verifications prevents using the same ticket twice.)

Let us sit back and appreciate what we have done: a classical ticket office sends classical data to slightly quantum users, who later communicate completely classically with the classical bouncer to enter the concert. At no point did anyone but the user have access to the quantum state. If we assume that the first part of the bouncer interaction can happen over the phone, the state didn’t have to move. Yet somehow, still, by the power of quantum uncloneability, the venue can rest assured that no ticket was forged or double-used.

Such is the power of one-shot signatures, and the marvelous construction by Shmueli and Zhandry.

(In future posts, we will introduce the notions described above in more detail and outline more exciting applications.)