The annual Crypto<\/em> 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<\/a> list that has since become a marquee of outstanding cryptographic research.<\/p>\n\n\n\n The newest addition<\/a> to this prestigious list is a recent paper<\/a> 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)<\/em>. In slightly more detail, they have managed to construct this elusive primitive \u201cin a standard model\u201d (alongside proving two similarly significant, but less accessible, theorems). Let us explore what this means.<\/p>\n\n\n\n First, what do I mean by reducing assumptions to a \u201cstandard model\u201d?<\/p>\n\n\n\n A common way to divide labor when working on a new cryptographic idea is to first work in a model<\/em> that assumes we have already solved some related problems (though we actually didn\u2019t). If we manage to build a primitive in that model, and prove its security, we in fact reduced<\/em> 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<\/em> model.<\/p>\n\n\n\n Calling a model \u201cstandard\u201d 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<\/em> 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.<\/p>\n\n\n\n (It is important not to confuse model assumptions with hardness assumptions,<\/em> such as the difficulty of factoring numbers into primes or computing discrete logarithms. Hardness assumptions are about the real world,<\/em> and are used in real-world implementations. A model is a mathematical tool for \u201cworking backwards\u201d, proving what we can do assuming<\/em> some other problem is already solved.)<\/p>\n\n\n\n Reducing the assumptions underlying one-shot signatures to a standard model is a key result of Shmueli and Zhandry\u2019s paper.<\/p>\n\n\n\n One-shot signatures were first discussed<\/a> by Amos et al. in 2020 (although they implicitly follow from an earlier work<\/a> by Zhandry, which makes even stronger assumptions, one of which was broken<\/a>). 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.)<\/p>\n\n\n\n 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)<\/em>. Loosely speaking, iO allows you to \u201cscramble\u201d computer programs in a way that does not leak information about their implementation (for example, encrypting messages without revealing the secret key).<\/p>\n\n\n\n The good news is that iO has a wide range of other implications (Barak and Brakersky crowned it<\/a> \u201cthe Swiss Army Knife of Cryptography\u201d), making it a very hot research topic. The bad news is that constructing iO is notoriously difficult<\/em>. Despite the idea first proposed as early as 1996 (though only appearing explicitly in the literature in a 2001 paper by Barak et al.<\/a>, also see the 2007 survey by Goldwasser and Rothblum<\/a>), it took until 2020 before a full construction was proposed in an earthquake of a paper<\/a> by Jain-Lin-Sahai.<\/p>\n\n\n\n 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<\/em> primitive, this construction is inappropriate in most scenarios. The only known post-quantum<\/em> iO constructions rely on specialized assumptions.<\/p>\n\n\n\n There are still a few hurdles to jump, but Shmueli and Zhandry\u2019s construction bridges the gap considerably.<\/p>\n\n\n\n In the late 1960s, Stephan Wiesner<\/a>, an upcoming Columbia graduate student, came to a startling realization: if used just right<\/em>, the laws of quantum mechanics allow creating a new form of money<\/a>. Money that is impossible to forge<\/em>. The very first example of a new form of security, derived from the laws of nature themselves.<\/p>\n\n\n\n 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\u2019s career. However, the manuscript continued to circulate, inspiring a new form of cryptography that is now known as uncloneable cryptography<\/em> and is considered one of the central pillars of quantum cryptography.<\/p>\n\n\n\n At a high level, the key realization of uncloneable cryptography is that if you assume end users have quantum capabilities (often very modest<\/em> capabilities, much more feasible than universal quantum computers), wonderful things happen. Ostensibly impossible<\/em> 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.<\/em>)<\/p>\n\n\n\n However, these protocols tend to make one requirement that feels out of reach: users need the ability to transmit quantum states<\/em> to each other. A quantum internet<\/em>.<\/p>\n\n\n\n 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<\/em>. In some cases, it turns out that it isn\u2019t (for example, it is not hard to prove that unconditionally secure key exchange is impossible without quantum communication). But curiously, not in all cases<\/em>. And OSS very elegantly captures the \u201csecret sauce\u201d that allows concocting quantum magic over a classical channel.<\/p>\n\n\n\n But what are<\/em> one-shot signatures?<\/p>\n\n\n\n Recall that a signature scheme<\/em> provides the ability to sign documents<\/em> such that only you<\/em> can sign messages (using a secret signing key<\/em>), but everyone<\/em> can verify them (using a corresponding public verification key<\/em>). In one-shot<\/em> signature schemes, the signature key is a quantum state that can only be used once<\/em>. After that, the state collapses, and all that\u2019s left is a classical signature.<\/p>\n\n\n\n Let’s see the power of this primitive in practice.<\/p>\n\n\n\n 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.<\/em><\/p>\n\n\n\n The easiest way to go about this is to use Wiesner\u2019s 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 \u201cquantumness\u201d to the concertgoer.<\/p>\n\n\n\n Say Alice wants to go to the concert.<\/p>\n\n\n\n When buying<\/strong> the ticket, she first generates a key pair: a classical verification key Models vs. Reality<\/h2>\n\n\n\n
Dreams of a Quantum Internet<\/h2>\n\n\n\n
Dequantumizing Communication With OSS<\/h2>\n\n\n\n