pith. sign in

arxiv: 2605.21349 · v1 · pith:ANB6PXNLnew · submitted 2026-05-20 · 💻 cs.CR

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

Tushin Mallick , Ashish Kundu , Ramana Kompella This is my paper

Pith reviewed 2026-05-21 03:47 UTC · model grok-4.3

classification 💻 cs.CR
keywords onion routingTormulti-circuit key establishmentquantum resilienceharvest now decrypt latersession keyanonymity
0
0 comments X

The pith

Splitting a session key into fragments sent over separate Tor circuits multiplies the work needed to reconstruct it.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a session-key establishment method that breaks a freshly generated key into multiple fragments, each encrypted separately and sent across its own ephemeral Tor circuit between onion services. An adversary must independently deanonymize every circuit to link the fragments into one session, so the overall success probability falls multiplicatively as more fragments are added. The design addresses harvest-now-decrypt-later threats by avoiding quantum-vulnerable public-key primitives and relying instead on the standard correlation bound of onion routing. A Flask-based prototype on AWS EC2, with both ends as onion services, measures end-to-end latency dominated by Tor delays.

Core claim

A freshly generated key is distributed as independently encrypted fragments across distinct ephemeral Tor circuits established via NEWNYM signals. Reconstruction requires every fragment; security rests on the end-to-end correlation bound for onion routing, under which an adversary controlling a fraction of relays must succeed separately on each circuit and the per-fragment success probability decays multiplicatively with the number of fragments.

What carries the argument

Multi-fragment distribution over independent per-bundle Tor circuits, where each fragment travels its own circuit created with a NEWNYM signal and reconstruction needs the complete set.

If this is right

  • The effective security level against linking grows multiplicatively with each added fragment.
  • The scheme runs on unmodified Tor relays and onion services.
  • Measured key establishment completes in 13-20 seconds on average, with roughly 88 percent of the time spent in Tor operations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same fragment-splitting idea could be tested in other anonymity networks that share onion-routing correlation properties.
  • Reducing circuit-setup overhead while preserving independence would widen the range of sessions for which the latency cost remains acceptable.

Load-bearing premise

Deanonymization successes on circuits created via NEWNYM for the same session remain statistically independent with no extra linking opportunities created by the bundling.

What would settle it

An experiment or trace analysis showing that circuits established with NEWNYM for one session can be correlated at a higher rate than the product of their individual probabilities would falsify the security argument.

Figures

Figures reproduced from arXiv: 2605.21349 by Ashish Kundu, Ramana Kompella, Tushin Mallick.

Figure 1
Figure 1. Figure 1: System architecture. Each client (Alice, Bob) hosts a Tor onion service and communicates with its proxy—also a Tor onion service—over the Tor [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper proposes distributing freshly generated session keys as multiple encrypted fragments across distinct ephemeral Tor circuits (established via NEWNYM signals) between onion-service endpoints. Reconstruction requires all fragments; security is argued to follow from the standard Tor end-to-end correlation bound, with per-fragment deanonymization probability decaying multiplicatively as the number of circuits increases. A Flask-based prototype on AWS EC2 is implemented and evaluated for end-to-end latency (13-20 s average).

Significance. If the independence assumption holds and the multiplicative decay is rigorously justified, the design would offer a practical, post-quantum-resistant key-establishment method that reuses existing Tor infrastructure rather than introducing new cryptographic primitives. The reported latency figures highlight a concrete privacy-versus-responsiveness trade-off that could inform deployment decisions in high-privacy settings.

major comments (2)
  1. [Abstract / Security Argument] Abstract and security argument: the central claim that 'the per-fragment probability of success decays multiplicatively in the number of fragments' rests on an unproven assumption that NEWNYM-triggered circuits for fragments of the same session remain independent under the standard Tor correlation bound. No reduction, proof sketch, or quantitative analysis is supplied showing that shared client timing, descriptor reuse, or entry-guard overlap do not create additional linking vectors; this independence is load-bearing for the multiplicative p^k security statement.
  2. [Implementation and Evaluation] Implementation section: latency results (13-20 s average) are presented without error bars, statistical significance tests, or direct baseline comparison against single-circuit Tor key establishment under identical conditions, making it impossible to quantify the incremental cost of the multi-circuit construction.
minor comments (1)
  1. [Design / Prototype] Notation for circuit establishment via NEWNYM should be defined more explicitly (e.g., a diagram or pseudocode listing the exact sequence of signals and circuit IDs) to aid reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful and constructive report. We address each major comment below, indicating where revisions have been made to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract / Security Argument] Abstract and security argument: the central claim that 'the per-fragment probability of success decays multiplicatively in the number of fragments' rests on an unproven assumption that NEWNYM-triggered circuits for fragments of the same session remain independent under the standard Tor correlation bound. No reduction, proof sketch, or quantitative analysis is supplied showing that shared client timing, descriptor reuse, or entry-guard overlap do not create additional linking vectors; this independence is load-bearing for the multiplicative p^k security statement.

    Authors: We agree that the multiplicative decay claim depends on circuit independence. Under the standard Tor threat model, each NEWNYM-triggered circuit is built with independent path selection, and the adversary must succeed in end-to-end correlation on every circuit separately. The NEWNYM signal forces circuit teardown and fresh guard selection, which we argue substantially reduces entry-guard overlap and timing correlation across fragments of one session. Descriptor reuse is avoided by establishing circuits to distinct onion-service endpoints. Nevertheless, we acknowledge that the original manuscript provides no explicit discussion or sketch addressing these potential linking vectors. In the revised version we have added a dedicated paragraph in the Security Analysis section that qualitatively examines client timing, descriptor reuse, and guard overlap, explaining why these factors do not invalidate the multiplicative bound within the standard Tor model. A full formal reduction remains outside the paper's scope but is noted as future work. revision: partial

  2. Referee: [Implementation and Evaluation] Implementation section: latency results (13-20 s average) are presented without error bars, statistical significance tests, or direct baseline comparison against single-circuit Tor key establishment under identical conditions, making it impossible to quantify the incremental cost of the multi-circuit construction.

    Authors: The referee correctly identifies a weakness in the evaluation presentation. In the revised manuscript we have updated the Evaluation section to report means with standard-deviation error bars from 50 independent runs, include the results of paired t-tests confirming statistical significance, and add a side-by-side baseline using an otherwise identical single-circuit Tor key-establishment implementation on the same AWS EC2 instances. These changes make the incremental latency cost of the multi-circuit design directly measurable. revision: yes

Circularity Check

0 steps flagged

Security argument grounded in external Tor correlation bound with no internal reduction

full rationale

The paper's security claim explicitly rests on the pre-existing end-to-end correlation bound for standard onion routing rather than any equation, parameter fit, or derivation internal to the manuscript. The multiplicative decay p^k is presented as a direct consequence of applying that external bound to the multi-circuit bundle, without the paper re-deriving or redefining the independence of per-circuit deanonymization events. No self-citation chain, ansatz smuggling, or renaming of a known result occurs in the load-bearing security step; the NEWNYM-based circuit construction is described as preserving the standard model assumptions without introducing a self-referential loop. The implementation measurements are separate from the security argument and do not feed back into it.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The design rests on the pre-existing Tor onion-routing security model and the assumption that NEWNYM circuits behave as independent fresh circuits for correlation purposes; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption The standard end-to-end correlation bound for onion routing applies unchanged to the ephemeral per-fragment circuits created via NEWNYM.
    This bound is invoked directly as the foundation of the multiplicative security argument.

pith-pipeline@v0.9.0 · 5796 in / 1294 out tokens · 51509 ms · 2026-05-21T03:47:15.865096+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · 1 internal anchor

  1. [1]

    Polynomial-time algorithms for prime factorization and dis- crete logarithms on a quantum computer,

    P. W. Shor, “Polynomial-time algorithms for prime factorization and dis- crete logarithms on a quantum computer,”SIAM Journal on Computing, vol. 26, no. 5, pp. 1484–1509, Oct. 1997

    work page 1997

  2. [2]

    Cybersecurity in an era with quantum computers: Will we be ready?

    M. Mosca, “Cybersecurity in an era with quantum computers: Will we be ready?”IEEE Security & Privacy, vol. 16, no. 5, pp. 38–41, 2018

    work page 2018

  3. [3]

    Module-lattice-based key-encapsulation mechanism standard,

    National Institute of Standards and Technology, “Module-lattice-based key-encapsulation mechanism standard,” U.S. Department of Commerce, Federal Information Processing Standards Publication FIPS 203, Aug. 2024

    work page 2024

  4. [4]

    Module-lattice-based digital signature standard,

    ——, “Module-lattice-based digital signature standard,” U.S. Depart- ment of Commerce, Federal Information Processing Standards Publica- tion FIPS 204, Aug. 2024

    work page 2024

  5. [5]

    Stateless hash-based digital signature standard,

    ——, “Stateless hash-based digital signature standard,” U.S. Department of Commerce, Federal Information Processing Standards Publication FIPS 205, Aug. 2024

    work page 2024

  6. [6]

    State of the post-quantum Internet in 2025,

    B. Westerbaan and C. A. Wood, “State of the post-quantum Internet in 2025,” The Cloudflare Blog, Mar. 2025, https://blog.cloudflare.com/ pq-2025/

    work page 2025

  7. [7]

    Transition to post- quantum cryptography standards,

    National Institute of Standards and Technology, “Transition to post- quantum cryptography standards,” U.S. Department of Commerce, NIST Internal Report (Initial Public Draft) NIST IR 8547 ipd, Nov. 2024

    work page 2024

  8. [8]

    Tor: The second- generation onion router,

    R. Dingledine, N. Mathewson, and P. Syverson, “Tor: The second- generation onion router,” inProceedings of the 13th USENIX Security Symposium, San Diego, CA, Aug. 2004, pp. 303–320

    work page 2004

  9. [9]

    stem: Python controller library for Tor,

    The Tor Project, “stem: Python controller library for Tor,” https://stem. torproject.org/

    work page

  10. [10]

    Aquaman: A transparent proxy architecture for quantum resilient key establishment,

    T. Mallick, A. Kundu, and R. Kompella, “Aquaman: A transparent proxy architecture for quantum resilient key establishment,” Cisco Research, San Jose, CA, Technical Report, 2025, carried out during the first author’s summer internship at Cisco Research, 2025

    work page 2025

  11. [11]

    Report on post-quantum cryptography,

    L. Chen, S. Jordan, Y .-K. Liu, D. Moody, R. Peralta, R. Perlner, and D. Smith-Tone, “Report on post-quantum cryptography,” National Institute of Standards and Technology, Gaithersburg, MD, NIST Internal Report NIST IR 8105, Apr. 2016

    work page 2016

  12. [12]

    NIST selects HQC as fifth algorithm for post-quantum encryption,

    National Institute of Standards and Technology, “NIST selects HQC as fifth algorithm for post-quantum encryption,” NIST News, Mar. 11 2025, https://www.nist.gov/news-events/news/2025/03/ nist-selects-hqc-fifth-algorithm-post-quantum-encryption

    work page 2025

  13. [13]

    An efficient key recovery attack on SIDH,

    W. Castryck and T. Decru, “An efficient key recovery attack on SIDH,” inAdvances in Cryptology – EUROCRYPT 2023, ser. Lecture Notes in Computer Science, vol. 14008. Springer, 2023, pp. 423–447

    work page 2023

  14. [14]

    Side-channel and fault-injection attacks over lattice-based post-quantum schemes (Kyber, Dilithium): Survey and new results,

    P. Ravi, A. Chattopadhyay, J.-P. D’Anvers, and A. Baksi, “Side-channel and fault-injection attacks over lattice-based post-quantum schemes (Kyber, Dilithium): Survey and new results,”ACM Transactions on Embedded Computing Systems, vol. 23, no. 2, pp. 1–54, Mar. 2024

    work page 2024

  15. [15]

    Anonymity and one-way authentication in key exchange protocols,

    I. Goldberg, D. Stebila, and B. Ustaoglu, “Anonymity and one-way authentication in key exchange protocols,”Designs, Codes and Cryp- tography, vol. 67, no. 2, pp. 245–269, 2013

    work page 2013

  16. [16]

    Improved circuit-creation key exchange,

    The Tor Project, “Improved circuit-creation key exchange,” Tor De- sign Proposal 216 (ntor handshake), https://spec.torproject.org/proposals/ 216-ntor-handshake.html

    work page

  17. [17]

    Untagging Tor: A formal treatment of onion encryption,

    J. P. Degabriele and M. Stam, “Untagging Tor: A formal treatment of onion encryption,” inAdvances in Cryptology – EUROCRYPT 2018, ser. Lecture Notes in Computer Science. Springer, 2018, pp. 259–293

    work page 2018

  18. [18]

    How do onion services work?

    The Tor Project, “How do onion services work?” Tor Community Doc- umentation, https://community.torproject.org/onion-services/overview/

    work page

  19. [19]

    Tor rendezvous specification (v3),

    ——, “Tor rendezvous specification (v3),” Tor Specifications, https:// spec.torproject.org/rend-spec/

    work page

  20. [20]

    How does Tor really work? the definitive visual guide,

    B. Skerritt, “How does Tor really work? the definitive visual guide,” Online, 2023, https://skerritt.blog/how-does-tor-really-work/

    work page 2023

  21. [21]

    stemfrequently asked questions: How do i request a new identity from Tor?

    The Tor Project, “stemfrequently asked questions: How do i request a new identity from Tor?” https://stem.torproject.org/faq.html

    work page

  22. [22]

    Sampled traffic analysis by Internet- exchange-level adversaries,

    S. J. Murdoch and P. Zieli ´nski, “Sampled traffic analysis by Internet- exchange-level adversaries,” inPrivacy Enhancing Technologies (PETS), ser. Lecture Notes in Computer Science, vol. 4776. Springer, 2007, pp. 167–183

    work page 2007

  23. [23]

    DeepCorr: Strong flow correlation attacks on Tor using deep learning,

    M. Nasr, A. Bahramali, and A. Houmansadr, “DeepCorr: Strong flow correlation attacks on Tor using deep learning,” inProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS ’18), 2018, pp. 1962–1976

    work page 2018

  24. [24]

    De- anonymisation attacks on Tor: A survey,

    I. Karunanayake, N. Ahmed, R. Malaney, R. Islam, and S. K. Jha, “De- anonymisation attacks on Tor: A survey,”IEEE Communications Surveys & Tutorials, vol. 23, no. 4, pp. 2324–2350, 2021

    work page 2021

  25. [25]

    How to share a secret,

    A. Shamir, “How to share a secret,”Communications of the ACM, vol. 22, no. 11, pp. 612–613, Nov. 1979

    work page 1979

  26. [26]

    Breakdown of the large-scale wind in \Gamma=1/2 rotating Rayleigh-B\'enard flow

    S. M. Barnett and S. J. D. Phoenix, “Securing a quantum key distribution network using secret sharing,” arXiv:1112.0411, 2011

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  27. [27]

    Multi-path secret sharing for QKD key relay in IP networks,

    J. Li and M. Li, “Multi-path secret sharing for QKD key relay in IP networks,” Internet-Draft draft-li-ipsecme-qkd-multipath-secret-sharing- 01, IETF, Feb. 2026

    work page 2026

  28. [28]

    Secure opportunistic multipath key exchange,

    S. Costea, M. O. Choudary, D. Gucea, B. Tackmann, and C. Raiciu, “Secure opportunistic multipath key exchange,” inProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS ’18), 2018, pp. 2077–2094

    work page 2018

  29. [29]

    Post-quantum TLS without handshake signatures,

    P. Schwabe, D. Stebila, and T. Wiggers, “Post-quantum TLS without handshake signatures,” inProceedings of the 2020 ACM SIGSAC Con- ference on Computer and Communications Security (CCS ’20), 2020, pp. 1461–1480

    work page 2020

  30. [30]

    Post-quantum key exchange for the Internet and the Open Quantum Safe project,

    D. Stebila and M. Mosca, “Post-quantum key exchange for the Internet and the Open Quantum Safe project,” inSelected Areas in Cryptography – SAC 2016, ser. Lecture Notes in Computer Science, vol. 10532. Springer, Oct. 2017, pp. 1–24

    work page 2016

  31. [31]

    JEP 527: Post-quantum hybrid key exchange for TLS 1.3,

    OpenJDK, “JEP 527: Post-quantum hybrid key exchange for TLS 1.3,” Jun. 2025, https://openjdk.org/jeps/527

    work page 2025

  32. [32]

    Post-quantum forward-secure onion routing (future anonymity in today’s budget),

    S. Ghosh and A. Kate, “Post-quantum forward-secure onion routing (future anonymity in today’s budget),” inApplied Cryptography and Network Security (ACNS), ser. Lecture Notes in Computer Science, vol

    work page

  33. [33]

    Springer, 2015, pp. 263–286

    work page 2015

  34. [34]

    Circuit-extension handshakes for Tor achieving forward secrecy in a quantum world,

    J. M. Schanck, W. Whyte, and Z. Zhang, “Circuit-extension handshakes for Tor achieving forward secrecy in a quantum world,”Proceedings on Privacy Enhancing Technologies (PoPETs), vol. 2016, no. 4, pp. 219– 236, 2016

    work page 2016

  35. [35]

    Transitionally secure hybrid handshake,

    The Tor Project, “Transitionally secure hybrid handshake,” Tor Design Proposal 269, https://spec.torproject.org/proposals/ 269-hybrid-handshake.html

    work page

  36. [36]

    Post-quantum mi- gration of the Tor application,

    D. Berger, M. Lemoudden, and W. J. Buchanan, “Post-quantum mi- gration of the Tor application,”Journal of Cybersecurity and Privacy, vol. 5, no. 2, p. Article 13, Apr. 2025

    work page 2025

  37. [37]

    Quantum key dis- tribution: A networking perspective,

    M. Mehic, M. Niemiec, S. Rass, J. Ma, M. Peev, A. Aguado, V . Mart ´ın, S. Schauer, A. Poppe, C. Pacher, and M. V oznak, “Quantum key dis- tribution: A networking perspective,”ACM Computing Surveys, vol. 53, no. 5, 2020

    work page 2020

  38. [38]

    Untraceable electronic mail, return addresses, and digital pseudonyms,

    D. L. Chaum, “Untraceable electronic mail, return addresses, and digital pseudonyms,”Communications of the ACM, vol. 24, no. 2, pp. 84–90, Feb. 1981

    work page 1981

  39. [39]

    Performance and security improvements for Tor: A survey,

    M. AlSabah and I. Goldberg, “Performance and security improvements for Tor: A survey,”ACM Computing Surveys, vol. 49, no. 2, Sep. 2016

    work page 2016

  40. [40]

    RECTor: Robust and efficient correlation attack on Tor,

    F. Hou, M. Yang, K. Wang, L. Lan, J. Du, J. Cui, and Z. Wang, “RECTor: Robust and efficient correlation attack on Tor,” arXiv:2512.00436, 2025

    work page arXiv 2025

  41. [41]

    The Loopix anonymity system,

    A. M. Piotrowska, J. Hayes, T. Elahi, S. Meiser, and G. Danezis, “The Loopix anonymity system,” inProceedings of the 26th USENIX Security Symposium, 2017, pp. 1199–1216

    work page 2017

  42. [42]

    Dark- Horse: A UDP-based framework to improve the latency of Tor onion services,

    M. W. Imran, M. Kosek, V . Bajpai, J. Iyengar, and J. Schmitt, “Dark- Horse: A UDP-based framework to improve the latency of Tor onion services,” arXiv:2307.02429, 2023

    work page arXiv 2023

  43. [43]

    Performance measurements and statistics of Tor hidden services,

    K. Loesing, W. Sandmann, C. Wilms, and G. Wirtz, “Performance measurements and statistics of Tor hidden services,” inProceedings of the 2008 International Symposium on Applications and the Internet. IEEE, 2008, pp. 1–7

    work page 2008

  44. [44]

    PLS-assisted offload- ing for edge computing-enabled post-quantum security in resource- constrained devices,

    H. Amiriara, M. Mirmohseni, and R. Tafazolli, “PLS-assisted offload- ing for edge computing-enabled post-quantum security in resource- constrained devices,” inProceedings of the IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), 2025, alsoarXiv:2504.09437

    work page arXiv 2025