- Open Access
- Access by Xinjiang University
Isogeny graphs in superposition and quantum onion routing
Phys. Rev. A 114, 012624 – Published 28 July, 2026
DOI: https://doi.org/10.1103/9ml3-5nhy
Abstract
Onion routing provides anonymity by layering encryption so that no relay can link sender to destination. A quantum analog faces a core obstacle: Layered quantum encryption generally requires symmetric encryption schemes, whereas classically one would heavily rely on public key encryption. We propose a symmetric-encryption-based quantum onion routing (QOR) scheme by instantiating each layer with the Abelian ideal class group action from the theory of complex multiplication. Session keys are established locally via a Diffie-Hellman key exchange between neighbors in the chain of communication. Furthermore, we propose a “nonlocal” key exchange between the sender and receiver. The underlying problem remains hard even for quantum adversaries and underpins the security of current postquantum schemes. We connect our construction to isogeny graphs and their association schemes, using the Bose-Mesner algebra to formalize commutativity and guide implementation. We give two implementation paths: (i) a universal quantum oracle evaluating the class group action with polynomially many quantum resources and (ii) an intrinsically quantum approach via continuous-time quantum walks, outlined here and developed in a companion paper. A small Qiskit example illustrates the mechanics (by design, not the efficiency) of the QOR.
Physics Subject Headings (PhySH)
Article Text
References (25)
- W. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes, CSIDH: An efficient post-quantum commutative group action, in Advances in Cryptology–ASIACRYPT, Lecture Notes in Computer Science (Springer, Berlin, 2018), pp. 395–427.
- A. M. Childs, Quantum information processing in continuous time, Ph.D. thesis, Massachusetts Institute of Technology, 2004.
- N. E. Mullin, Uniform mixing of quantum walks and association schemes, Ph.D. thesis, University of Waterloo, 2013.
- S. Lang, Elliptic Functions (Springer, Berlin, 1987).
- M. Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Semin. Univ. Hambg. 14, 197 (1941).
- W. Castryck and T. Decru, CSIDH on the surface, in Post-Quantum Cryptography—11th International Conference—PQCrypto, edited by J. Ding and J.-P. Tillich (Springer, Cham, 2020), pp. 111–129.
- D. A. Cox, Primes of the Form : Fermat, Class Field Theory and Complex Multiplication (Wiley, New York, 1989).
- D. Jao, S. D. Miller, and R. Venkatesan, Expander graphs based on GRH with an application to elliptic curve cryptography, J. Number Theory 129, 1491 (2009).
- N. Biggs, Algebraic Graph Theory, 2nd ed. (Cambridge University Press, New York, 1992).
- C. Godsil and G. Royle, Algebraic Graph Theory (Chapman & Hall, New York, 1993).
- S. Hallgren, Fast quantum algorithms for computing the unit group and class group of a number field, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (ACM, New York, 2005), pp. 468–474.
- H. Cohen and H. W. Lenstra, Jr., Heuristics on class groups of number fields, in Noordwijkerhout, Lecture Notes in Mathematics Vol. 1068 (Springer, Berlin, 1984), pp. 33–62.
- A. M. Childs, D. Jao, and V. Soukharev, Constructing elliptic curve isogenies in quantum subexponential time, J. Math. Cryptol. 8, 1 (2014).
- C. Godsil, Algebraic combinatorics, Chapman & Hall Mathematics Series (Chapman & Hall, New York, 1993).
- A. Schönhage, Fast reduction and composition of binary quadratic forms, in Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC'91 (ACM, New York, 1991), pp. 128–133.
- P. Dartois, J. K. Eriksen, T. B. Fouotsa, A. H. Le Merdy, R. Invernizzi, D. Robert, R. Rueger, F. Vercauteren, and B. Wesolowski, PEGASIS: Practical effective class group action using 4-dimensional isogenies, in Advances in Cryptology–CRYPTO (2025), Lecture Notes in Computer Science (Springer, Berlin, 2025), pp. 67–98.
- P. Dartois, J. K. Eriksen, R. Invernizzi, and F. Vercauteren, qt-Pegasis: Simpler and faster effective class group actions, J. Instrum. 20, P09012 (2025).
- A. Bhand and M. R. Murty, Class numbers of quadratic fields, Hardy-Ramanujan J. 42, 17 (2019).
- F. Campos, J. Chávez-Saab, J.-J. Chi-Domínguez, M. Meyer, K. Reijnders, F. Rodríguez-Henríquez, P. Schwabe, and T. Wiggers, Optimizations and practicality of high-security CSIDH, in Advances in Cryptology–CRYPTO 2024, Lecture Notes in Computer Science (Springer, Berlin, 2024).
- D. X. Charles, K. E. Goren, and K. E. Lauter, Cryptographic hash functions from expander graphs, J. Cryptol. 22, 93 (2009).
- C. Godsil, Periodic graphs, Electron. J. Combin. 18, P23 (2011).
- N. Saxena, S. Severini, and I. E. Shparlinski, Parameters of integral circulant graphs and periodic quantum dynamics, Int. J. Quantum Inf. 05, 417 (2007).
- The PARI Group, PARI/GP version 2.15.5, Univ. Bordeaux, 2024, https://pari.math.u-bordeaux.fr/.
- The Sage Developers, SageMath, the Sage Mathematics Software System (Version 10.4), 2024, https://www.sagemath. org/.
- R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Phys. Rev. X 8, 041015 (2018).
