Onion-Routed Multi-Circuit Key Establishment for Quantum-Resilient Sessions

Tushin Mallick 1, Ashish Kundu, Ramana Kompella · 2026

Read Onion-Routed Multi-Circuit Key Establishment for Quantum-Resilient Sessions by Tushin Mallick 1, Ashish Kundu, Ramana Kompella (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21349.txt.

Introduction

Tushin Mallick, Ashish Kundu, and Ramana Kompella propose onion-routed multi-circuit key establishment for quantum-resilient sessions. RSA, Diffie-Hellman, and elliptic-curve cryptography fall to Shor's algorithm, and harvest-now, decrypt-later attacks turn future capability into present risk. Their scheme splits a fresh key into encrypted fragments sent over distinct ephemeral Tor circuits between an onion-service proxy and client. Reconstruction requires every fragment, each on its own circuit set up via a NEWNYM signal.

Catalog record

CREATORTushin Mallick 1, Ashish Kundu, Ramana Kompella
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55138
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21349

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Onion-Routed Multi-Circuit Key Establishment for Quantum-Resilient Sessions Tushin Mallick 1, Ashish Kundu, Ramana Kompella Abstract Public-key primitives that today anchor session-key establishment—RSA, Diffie–Hellman, and elliptic-curve cryptography—reduce to integer factorization or discrete logarithm and are therefore vulnerable to Shor’s algorithm on a sufficiently capable quantum computer. The harvest-now, decrypt-later (HNDL) threat model turns this future capability into a present liability: ciphertext archived today can be decrypted retrospectively once a cryptographically relevant quantum computer becomes available. We propose a session-key establishment scheme that distributes a freshly generated key as multiple, independently encrypted fragments across distinct, ephemeral Tor circuits between an onion-service proxy and an onion-service client. Reconstruction requires every fragment; each fragment travels its own per-bundle circuit established via a NEWNYM signal. The security argument rests on the standard end-to-end correlation bound for onion routing: an adversary controlling a fraction of Tor relays must independently deanonymize every fresh circuit to correlate the fragments belonging to one session, and the per-fragment probability of success decays multiplicatively in the number of fragments. We implement the design as a Flask-based prototype on AWS EC2, with both the proxy and the client deployed as Tor onion services, and measure end-to-end key-establishment latency. The implemented prototype completes a key establishment in 13–20 s on average (7–50 s including tails), of which approximately 88% is attributable to Tor-related delay—a cost we discuss in the context of the privacy-versus-responsiveness trade-off. 1 1 footnotetext: This work was carried out when the author was at Cisco Research, San Jose, CA, during Summer Internship 2025. He is currently at Northeastern University, Boston, MA. I Introduction Modern secure communication on the open Internet rests on a small set of public-key primitives—RSA, Diffie–Hellman (DH), and elliptic-curve cryptography (ECC)—whose security reduces to the conjectured intractability of integer factorization or discrete logarithms. Shor’s algorithm solves both problems in quantum polynomial time [ 1 ] , so a sufficiently capable quantum computer breaks all three. While no such machine yet exists, contemporary risk analyses treat its eventual arrival as an engineering problem rather than a theoretical one [ 2 ] . The operational urgency comes from the harvest-now, decrypt-later (HNDL) threat model: an adversary intercepts and archives ciphertext today and defers decryption until a cryptographically relevant quantum computer (CRQC) becomes available. For data whose confidentiality must hold for years or decades, present-day classical key establishment is therefore already inadequate. Mosca’s inequality X+Y\geq Z captures the resulting risk, where X is the required confidentiality lifetime of the data, Y is the migration runway to quantum-resistant cryptography, and Z is the time until a CRQC is fielded [ 2 ] . The U.S. National Institute of Standards and Technology (NIST) has finalized the first post-quantum cryptography (PQC) standards—FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA) in August 2024 [ 3 , 4 , 5 ] —and major content delivery networks and browsers have begun deploying hybrid classical/PQC handshakes in production [ 6 ] . Motivation. Two observations motivate the present work. First, even after PQC standards are universally available, the wire-level migration is gated by a long tail of constrained, embedded, and operational-technology endpoints that cannot readily accept new cryptographic primitives [ 7 ] . During that migration window, classical key establishment will continue to be performed on links subject to HNDL collection. Second, while the cryptographic content of a session-key exchange is one defensible surface, the metadata of the exchange is another. Knowing which two endpoints established a session, and when, is independently sensitive in many settings; it also creates the linkage an HNDL adversary needs in order to correlate a future decryption with an identified pair of communicants. Defenses that protect only the former leave the latter intact. We address both observations by routing the key-establishment traffic through the Tor anonymity network [ 8 ] and by distributing the established key as multiple independently encrypted fragments across separate, ephemeral Tor circuits. This approach is an instance of the general multi-path quantum resistance framework that is proposed and described elsewhere and is out of the scope of this paper (We will add a reference to that work when a publicly available reference is available). The circuit-creation interface exposed by the Tor controller (the NEWNYM signal accessible via the stem library [ 9 ] ) makes it cheap to obtain a fresh path through the network for each fragment bundle. Both the client and the key-distribution proxy expose Tor onion services, so neither party reveals its network location to the other or to any single relay on the path. Our Contributions. This paper is the anonymous-paths companion to the Aquaman protocol [ 10 ] . We make the following contributions. • We instantiate the deferred anonymous-paths variant over the public Tor network: both proxy and client are exposed as Tor onion services, and a fresh circuit per fragment bundle is obtained via the NEWNYM control signal. • We prove a multi-circuit linkability bound: an adversary surveilling a fraction f of Tor relays correlates every one of the n ephemeral circuits with probability at most f^{2n} (Proposition 1 ), and formalize the property as anonymity-preserving reconstruction (Definition 1 ). • We implement the design on AWS EC2 and measure end-to-end key-establishment latency of 13–20 s, of which roughly 88% is attributable to Tor. Scope. We do not propose a new key encapsulation mechanism, and we do not claim that the onion-routing layer alone provides post-quantum confidentiality of the fragment payload: per-fragment encryption is performed under the recipient’s classical public key, and an HNDL adversary that captures and later decrypts a single fragment recovers that fragment’s plaintext. The contribution is on linkability : distributing the fragments across independent, anonymous Tor circuits raises the cost of identifying which decrypted fragments must be combined to reconstruct a key and, hence, of attributing the reconstructed key to a specific pair of endpoints. The scheme composes with a post-quantum KEM on the wire as a defense-in-depth measure; we discuss this composition but do not implement it in the current prototype. The proposed approach in this paper is based on the general multi-path quantum resistance framework that is proposed and described elsewhere and is out of the scope of this paper (We will add a reference to that work when a publicly available reference is available). Outline. Section II reviews the relevant cryptographic and networking background. Section III surveys related work in post-quantum migration, multi-path key establishment, and anonymous communication. Section IV formalizes the threat model. Section V describes the system design. Section VII reports the prototype implementation and empirical evaluation. Section VIII discusses limitations and the usability–security trade-off with conlcusion in Section IX . II Background This section reviews the technical material on which the design rests: the quantum threat to asymmetric cryptography, the Tor anonymity network and its onion-service protocol, and the use of secret sharing for key distribution. We deliberately omit introductory cryptographic material that is well covered elsewhere and focus on the points that bear directly on the design choices in Section V . II-A The Quantum Threat to Asymmetric Cryptography Shor’s algorithm provides a quantum polynomial-time solution to integer factorization and to the discrete-logarithm problem in finite fields and on elliptic curves [ 1 ] . Because RSA, classical

Read the complete text