Quantum money is a representative application in cryptography that utilizes quantum technology to achieve security that is unattainable with classical systems. Since the theoretical proposal by Wiesner in 1983, the most recent instantiation is the quantum money using class group actions on elliptic curves, proposed by Montgomery and Sharif in Asiacrypt'24. In this work, we propose a concrete cryptanalysis by leveraging the efficiency of evaluating division polynomials with the coordinates of rational points, offering a speedup of O ( log 4 p ) compared to the brute-force attack. While the resulting attack still runs in exponential time, our method provides the first nontrivial algorithmic insight into their structural hardness. Furthermore, due to the algebraic properties of rational points and quadratic twists, our technique naturally yields a more efficient verification procedure for the underlying quantum money. We believe this new line of analysis opens promising directions for future research in elliptic-curve-based quantum cryptography.
Quantum money is a representative application in cryptography that utilizes quantum technology to achieve security that is unattainable with classical systems. Since the theoretical proposal by Wiesner in 1983, the most recent instantiation is the quantum money using class group actions on elliptic curves, proposed by Montgomery and Sharif in Asiacrypt'24. In this work, we propose a concrete cryptanalysis by leveraging the efficiency of evaluating division polynomials with the coordinates of rational points, offering a speedup of O ( log 4 p ) compared to the brute-force attack. While the resulting attack still runs in exponential time, our method provides the first nontrivial algorithmic insight into their structural hardness. Furthermore, due to the algebraic properties of rational points and quadratic twists, our technique naturally yields a more efficient verification procedure for the underlying quantum money. We believe this new line of analysis opens promising directions for future research in elliptic-curve-based quantum cryptography.
Public verification of quantum money has been one of the central objects in quantum cryptography ever since Wiesner's pioneering idea of using quantum mechanics to construct banknotes against counterfeiting. So far, we do not know any publicly-verifiable quantum money scheme that is provably secure from standard assumptions. In this work, we provide both negative and positive results for publicly verifiable quantum money. **In the first part, we give a general theorem, showing that a certain natural class of quantum money schemes from lattices cannot be secure. We use this theorem to break the recent quantum money scheme of Khesin, Lu, and Shor. **In the second part, we propose a framework for building quantum money and quantum lightning we call invariant money which abstracts some of the ideas of quantum money from knots by Farhi et al.(ITCS'12). In addition to formalizing this framework, we provide concrete hard computational problems loosely inspired by classical knowledge-of-exponent assumptions, whose hardness would imply the security of quantum lightning, a strengthening of quantum money where not even the bank can duplicate banknotes. **We discuss potential instantiations of our framework, including an oracle construction using cryptographic group actions and instantiations from rerandomizable functional encryption, isogenies over elliptic curves, and knots.
Quantum cryptography enhances security and addresses vulnerabilities present in traditional cryptography, thereby providing better protection against potential risks posed by quantum computing. As quantum computing progresses, the feasibility of quantum cryptanalysis increases, necessitating the development of various post-quantum cryptography techniques. These techniques include cryptography that relies on lattices, codes, hash functions, multivariate polynomials, and isogenies, all aimed at ensuring stronger security measures. This paper focuses specifically on isogeny-based cryptography, a novel branch of cryptography that utilizes isogenies between elliptic curves to construct cryptographic tools. These schemes are known for their speed, efficiency, and resistance to quantum attacks. Our research delves into the latest advancements in isogeny-based cryptography, exploring the challenges and opportunities for future investigation. We firmly believe that isogeny-based cryptography holds great potential in shaping the future of cryptography, and we encourage fellow researchers to delve into this captivating field.
Our modern world is dependent on online communications and transactions. To ensure privacy in these digital actions, it is extremely common to use protocols such as the Diffie-Hellman key exchange scheme. Unfortunately, these systems have been shown to be vulnerable to attacks from a quantum adversary. This means that an overhaul of the field of cryptography is needed in order to anticipate and mitigate this threat.Over the past years, the community has begun to answer this call by proposing and analyzing new techniques that are conjectured to be quantum safe. One such example is the study of cryptographic group actions. These mappings mimic some of the structure from the Diffie-Hellman protocol,but abstract it enough so that new mathematical operations can be employed that avoid quantum attacks. Currently, the main examples of group actions come from isogenies, codes, and lattices.In order for a protocol to be used in the real-world we would hope for it to be secure, fast, and requiring little storage. This means that in these early stages of research and development of cryptographic group actions, it is essential to begin to answer some of the questions surrounding security and efficiency. This thesis contributes to this effort by focusing on these aspects across different group actions that have been proposed for use in the literature.It is certainly true that each individual group action needs its own study of security. When designers are trying to achieve some advanced functionalities in a protocol, they may sometimes alter the underlying security assumptions.Each time this is done, the new assumptions need their own careful study as well. In this thesis we consider four different variants of group action security assumptions spanning the isogeny, tensor, linear code, and matrix code group actions. We analyze their security by either offering concrete attacks or giving a polynomial time reduction to a more well-studied assumption. This helps to indicate whether a problem is appropriate for use in cryptography, and what parameters to use if so.In addition to security, this thesis is also inscribed in the effort to study the efficiency of group actions by including three works studying the isogeny group action and related subroutines. They span the core isogeny problem for oriented elliptic curves, evaluating isogenies from a kernel generator, and supersingularity testing. With an effort from the community to improve overall runtimes, we can hope to get closer to reasonable speeds for real-life use.By studying the security and efficiency of cryptographic group actions, this thesis shines light on group actions as a promising framework for post-quantum cryptographic solutions.
Abstract. Given two ordinary elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit a nonzero isogeny between them, but finding such an isogeny is believed to be computationally difficult. The fastest known classical algorithm takes exponential time, and prior to our work no faster quantum algorithm was known. Recently, public-key cryptosystems based on the presumed hardness of this problem have been proposed as candidates for post-quantum cryptography. In this paper, we give a new subexponential-time quantum algorithm for constructing nonzero isogenies between two such elliptic curves, assuming the Generalized Riemann Hypothesis (but with no other assumptions). Our algorithm is based on a reduction to a hidden shift problem, and represents the first nontrivial application of Kuperberg's quantum algorithm for finding hidden shifts. This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream quantum-resistant cryptosystems such as lattice-based cryptosystems. As part of this work, we also present the first classical algorithm for evaluating isogenies having provably subexponential running time in the cardinality of the base field under GRH.
We propose and develop new schemes for post-quantum cryptography based on isogenies over elliptic curves. First we show that ordinary elliptic curves are have less than exponential security against quantum computers. These results were used as the motivation for De Feo, Jao and Pl\\^ut's construction of public key cryptosystems using supersingular elliptic curve isogenies. We extend their construction and show that isogenies between supersingular elliptic curves can be used as the underlying hard mathematical problem for other quantum-resistant schemes. For our second contribution, we propose is an undeniable signature scheme based on elliptic curve isogenies. We prove its security under certain reasonable number-theoretic computational assumptions for which no efficient quantum algorithms are known. This proposal represents only the second known quantum-resistant undeniable signature scheme, and the first such scheme secure under a number-theoretic complexity assumption. Finally, we also propose a security model for evaluating the security of authenticated encryption schemes in the post-quantum setting. Our model is based on a combination of the classical Bellare-Namprempre security model for authenticated encryption together with modifications from Boneh and Zhandry to handle message authentication against quantum adversaries. We give a generic construction based on Bellare-Namprempre for producing an authenticated encryption protocol from any quantum-resistant symmetric-key encryption scheme together with any digital signature scheme or MAC admitting any classical security reduction to a quantum-computationally hard problem. We apply the results and show how we can explicitly construct authenticated encryption schemes based on isogenies.
The impending arrival of large-scale quantum computers poses a significant threat to modern public-key cryptography, which is largely based on the hardness of integer factorization and the discrete logarithm problem. Elliptic Curve Cryptography (ECC), a cornerstone of current digital security, is particularly vulnerable to attacks by quantum algorithms, notably Shor's algorithm. This has catalyzed the development of Post-Quantum Cryptography (PQC), a new generation of cryptographic systems designed to be secure against both classical and quantum adversaries. Among the various PQC families, isogeny-based cryptography has emerged as a compelling, albeit complex, candidate. This paper explores the reimagination of elliptic curve principles for a post-quantum world through the lens of isogeny graphs. We provide a comprehensive overview of the transition from classical ECC to isogeny-based schemes, detailing the mathematical foundations of elliptic curve isogenies and the construction of supersingular isogeny graphs. The core of our analysis focuses on how the problem of finding a secret isogeny path between two curves in this graph forms the basis for quantum-resistant cryptographic protocols. We review the evolution of seminal protocols such as Supersingular Isogeny Diffie-Hellman (SIDH) and its variants, discussing their initial promise. Crucially, the paper also addresses the recent groundbreaking cryptanalytic attacks on SIDH, which have reshaped the landscape of isogeny-based cryptography. We analyze the implications of these attacks and the ongoing research to develop new, more secure isogeny-based schemes like SQISign. By comparing the performance metrics (key size, performance, security) of isogeny-based systems with other leading PQC candidates, such as those based on lattices and codes, this paper offers a balanced perspective on their potential role in future cryptographic standards.