HqcLethe streams HQC keys without per-client memory
HqcLethe: Streaming HQC Encapsulation for Tiny Stateless Servers · arXiv:2610.36808
In plain words
HQC is a way for two parties to create a shared secret key. Its public keys are too large for one network packet, and saving unfinished pieces for each client could let attackers use up a server’s memory.
HqcLethe lets a server handle small pieces and forget each request, while the client puts the replies together. A formal proof checks that the replies reveal no more than a normal HQC ciphertext. On a Raspberry Pi, measured memory stayed fixed across the tested client loads.
The research
How can a server accept an HQC public key that spans several network packets without holding memory for every unfinished handshake?
Buffering those fragments can let an attacker exhaust a server’s memory, while HQC’s polynomial multiplication cannot be split into simple matching input and output pieces.
HqcLethe streams HQC key encapsulation in packet-sized pieces, letting a stateless server avoid per-client memory while the client rebuilds the ciphertext.
To test the design’s costs, the authors compared HqcLethe with McTiny, an earlier stateless key-exchange design, and measured its memory use on a Raspberry Pi 3B+.
At category 5 on one x86 host, HqcLethe used 27 times fewer UDP payload bytes and 9.5 times less server CPU per exchange than McTiny. On the Pi, the minimum memory limit needed for sessions to complete was 1.2–1.6 MiB across tested HQC levels and loads, including 64 clients.
These results support efficiency and fixed memory in those setups, but the performance comparison covers different protocols and cryptographic choices.
The performance figures come from one x86 host and compare different designs, so they do not isolate the effect of streaming alone. The memory result covers the tested Raspberry Pi loads; HqcLethe does not prevent network-link saturation, and integration into a full protocol remains future work.
What the evidence shows
- The memory problem
HqcLethe is a key-exchange method for a client and a server that keeps no per-client state. HQC is a key-encapsulation mechanism: it lets the server create a shared secret and ciphertext from the client's public key.
The problem is that HQC public keys span several packets. If the server buffers unfinished handshakes, an attacker can make it allocate memory for many clients. The paper asks how to use HQC without making server memory grow with those unfinished connections.
- Stream the computation
HqcLethe divides the server’s polynomial multiplication into packet-sized residue computations using the Chinese remainder theorem. The server returns masked residues without keeping client state, and the client reconstructs the ciphertext.
This changes where the work happens: the server can forget each request, while the client gathers the pieces needed for the result.
- Check the masking
The raw residues would expose intermediate values absent from an ordinary HQC ciphertext. HqcLethe masks them so they disappear when the client reconstructs and reduces the result.
A mechanized Rocq/SSProve proof establishes that, under stated assumptions on the moduli, no distinguisher can tell the masked-residue procedure from a simulator using ordinary HQC encryption.
- Compare stateless designs
The authors compared HqcLethe with McTiny, an earlier stateless key exchange using Classic McEliece. At category 5 on the same x86 host, HqcLethe used 27 times fewer total UDP payload bytes and 9.5 times less server CPU per exchange.
The comparison covers different designs and cryptographic choices, so it does not show which individual change caused the difference.
- Weigh the tradeoff
A separate comparison with a stateful server that buffers fragments makes the cost of statelessness visible: at category 5, HqcLethe used about twice the bytes and 4.1 times the server CPU per session. On a Raspberry Pi 3B+, its measured memory limit stayed at 1.2–1.6 MiB across tested HQC levels and loads, including one and 64 clients. These implementation results support the design within the reported testbeds.
Deep
- Original paper authors
- Wind Wong, Klaus v. Gleissenthall
- Submitted to arXiv
- License
- CC BY 4.0