PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerating HQC for Post-Quantum TLS 1.3 on x86 IoT Gateways

Jihoon Jang, Hyunju Park, Jebin Kim, Seokhie Hong, Suhri Kim

arXiv:2610.11107v1cs.CR

TL;DR

Post-quantum TLS at IoT gateways must limit added computation and communication costs, and the paper addresses HQC's implementation costs by optimizing it for x86 and integrating it into TLS 1.3. The optimized implementations reduce HQC operation costs, while measurements show that communication sizes dominate handshake time on constrained links.

  • Problem

    Post-quantum TLS at IoT gateways must protect device connections while limiting added computation and communication latency.

    Source: §I · p. 1

  • Method

    The paper optimizes HQC polynomial multiplication, decoding, Keccak-based functions, and support expansion for AVX2 and AVX-512 + GFNI, then integrates the implementations into TLS 1.3.

    Source: A. Setup · p. 12, §VIII · p. 13

  • Results

    AVX-512 cuts HQC key generation 24.9%–29.5%, encapsulation 10.4%–11.1%, and decapsulation 20.6%–26.1%; at 1 Mbit/s and 50 ms RTT, HQC-5 takes 243 ms versus ML-KEM-1024's 87 ms.

    Source: §VIII · pp. 13–14

  • Takeaways & Limitations

    On constrained links, HQC communication sizes determine overall handshake time more than the HQC implementation.

    Source: §VIII · p. 14

    The evaluation uses one Tiger Lake processor and TLS tests over emulated network paths; it does not evaluate additional platforms, resource-constrained end devices, or deployed wireless IoT networks.

    Source: §VIII · p. 14

Abstract

from arXiv · show

Post-quantum TLS at an IoT gateway must protect many device connections without large increases in handshake delay, CPU cost, or network traffic. HQC provides code-based diversity beyond ML-KEM, but its computation and ciphertext sizes can increase these costs. We optimize HQC for x86 processors with AVX2, AVX-512, and the Galois Field New Instructions (GFNI), and integrate the resulting implementations into TLS 1.3. We extend branch-free Toom-Cook/Karatsuba multiplication to AVX-512, accelerate Reed-Solomon decoding with GFNI, improve Reed-Muller decoding, accelerate SHA3-512 and fixed-weight sampling, and port Frobenius additive FFT (FAFFT) multiplication to AVX-512 + GFNI for HQC-5. On an Intel Core i5-1135G7 processor, our AVX2 implementation reduces decapsulation by 11.1-21.5% over the fastest prior AVX2 results. Our AVX-512 implementation reduces key generation by 24.9-29.5%, encapsulation by 10.4-11.1%, and decapsulation by 20.6-26.1% relative to Cabral et al. across the three HQC parameter sets. We evaluate the effects of these implementations on TLS 1.3 handshake latency and server and client CPU costs, as well as the effects of round-trip time (RTT) and bandwidth. In local loopback TLS measurements, our AVX-512 HQC-5 implementation reduces handshake latency from 3.22 ms to 2.92 ms compared with Cabral et al. On a constrained path with 1 Mbit/s bandwidth and an added RTT of 50 ms, the HQC-5 handshake takes 243 ms, compared with 87 ms for ML-KEM-1024. This indicates that HQC public-key and ciphertext sizes, rather than implementation speed, determine the remaining handshake cost on constrained links.

I. INTRODUCTION

The introduction motivates efficient post-quantum TLS for IoT gateways and identifies a gap in evaluating how HQC implementation changes affect TLS costs. The paper optimizes HQC on AVX2 and AVX-512 + GFNI, then measures component and protocol performance.

I. INTRODUCTION

  • Post-quantum TLS at IoT gateways must limit added computation and communication latency, while HQC provides code-based diversity beyond lattice-based ML-KEM.HQC's main components include polynomial multiplication, Reed-Muller and Reed-Solomon decoding, and Keccak-based functions.Source: §I · p. 1

A. Contributions

  • The paper extends branch-free Toom-Cook/Karatsuba multiplication to AVX-512 and ports FAFFT to AVX-512 + GFNI, reducing HQC-5 multiplication cycles by 14.1% and 17.7%, respectively.The decomposition-tree implementation stays within about 1% of Robert and V´eron at HQC-1 and HQC-3.Source: A. Contributions · p. 2
  • GFNI-based Reed-Solomon decoding reduces cycles by 83.2%–87.1% on AVX2 and 88.9%–91.0% on AVX-512, while Reed-Muller decoder costs fall by 18.2%–20.4% and 3.7%–9.9%, respectively.The Reed-Solomon comparisons are against Chen et al. on AVX2 and Cabral et al. on AVX-512; the Reed-Muller comparisons use the same respective baselines.Source: A. Contributions · p. 2
  • AVX-512 implementations of SHA3-512 oracles hash_g and hash_i reduce their cycle counts by 37.4%–46.4% and 46.2%–46.7%, while support expansion costs fall by 34.5%–36.8%.The oracle comparisons are against Cabral et al..Source: A. Contributions · p. 2

A. Contributions / B. Related Works

  • The authors integrate optimized HQC into TLS 1.3 and measure handshake latency and client and server CPU costs, including the effects of RTT and bandwidth.Earlier PQ-TLS studies compared KEM choices using the implementations available in their TLS stacks; this work varies HQC implementations in one fixed stack.Source: §I · p. 1, A. Contributions · p. 2, B. Related Works · p. 3

A. Contributions

  • AVX-512 reduces HQC key generation by 24.9%–29.5%, encapsulation by 10.4%–11.1%, and decapsulation by 20.6%–26.1% relative to Cabral et al..At HQC-5, the FAFFT configuration increases these reductions to 33.1%, 16.3%, and 27.4%, respectively.Source: A. Contributions · p. 2

C. Organization

The paper is organized into preliminaries, optimization methods, experiments, and TLS assessment. The preliminaries establish field and polynomial notation and identify the hash-oracle and XOF conventions used later.

C. Organization

  • The paper reviews HQC, AVX-512 and GFNI instructions, and TLS 1.3 key exchange before describing optimizations, experiments, and protocol assessment.The remaining sections cover HQC optimization methods in Sections III–V, experiments in Section VI, TLS 1.3 assessment in Section VII, and conclusions in Section VIII.Source: C. Organization · p. 3, §II · p. 3

A. Notation

  • The notation defines F2 as the binary field, FRS as the field for HQC's Reed-Solomon code, and R as F2[x]/(xN −1).Trun(v, n′) keeps the low n′ bits of vector v.Source: A. Notation · p. 3
  • The paper denotes the extendable-output function by XOF and instantiates H and J with SHA3-256 and G and I with SHA3-512.Bold lowercase letters denote elements of R or code vectors.Source: A. Notation · p. 3

B. HQC

HQC is a code-based KEM with three parameter sets, and its implementation combines polynomial multiplication, decoding, and Keccak-based operations. This section describes how the scheme maps Reed–Solomon field arithmetic to GFNI and specifies the x86 instructions used in the implementations.

B. HQC

  • HQC is a code-based KEM based on syndrome-decoding hardness for quasi-cyclic codes; HQC-1, HQC-3, and HQC-5 target NIST security levels 1, 3, and 5.HQC applies an implicit-rejection transform to the HQC-PKE scheme.Source: B. HQC · p. 3
  • Polynomial multiplication and Reed–Muller/Reed–Solomon decoding are HQC components, and Figure 1 shows their contribution to Cabral et al.’s HQC-5 AVX-512 KEM cycle counts.The figure’s Keccak category includes SHA3-256 and SHA3-512 oracles and the SHAKE256 XOF; support expansion converts sampled positions into a length-N binary vector.Source: B. HQC · pp. 3–4, Figure 1 · p. 4

C. AVX-512 and GFNI

  • The implementations use AVX-512 with VPCLMULQDQ for binary-polynomial multiplication and GFNI for byte-wise arithmetic; the AVX-512 target additionally requires AVX-512 and VPCLMULQDQ.The experiments use an Intel Tiger Lake processor; the AVX2 target requires AVX2, PCLMULQDQ, and GFNI.Source: C. AVX-512 and GFNI · p. 4
  • GFNI arithmetic on the Reed–Solomon field maps operands to the AES field for multiplication or inversion, then maps the results back.The mapping is a linear isomorphism; inversion uses the same conversion.Source: C. AVX-512 and GFNI · p. 4

D. TLS 1.3 and Post-Quantum TLS

TLS 1.3 carries a KEM public key and ciphertext in handshake flights, so KEM deployment affects both gateway computation and connection latency. The paper also identifies polynomial multiplication as a major HQC cycle cost and describes how its products arise in KEM operations.

D. TLS 1.3 and Post-Quantum TLS

  • A TLS 1.3 KEM key share has the client generate a key pair and send its public key, after which the server encapsulates and the client decapsulates the shared secret.The client performs key generation and decapsulation, while the server performs one encapsulation per handshake.Source: D. TLS 1.3 and Post-Quantum TLS · p. 4
  • The KEM public key and ciphertext travel in handshake flights, so their communication sizes add directly to handshake traffic.The paper uses liboqs and oqs-provider to expose KEMs as OpenSSL key-share groups.Source: D. TLS 1.3 and Post-Quantum TLS · p. 4

III. POLYNOMIAL MULTIPLICATION

  • HQC computes four binary-polynomial products for key generation, encryption, and decryption, and their sizes make them a large part of its cycle count.The products are h·y, h·r2, s·r2, and u·y; the polynomial length N ranges from 17,669 to 57,637.Source: §III · p. 5

A. Toom-Cook / Karatsuba for AVX-512

The section develops AVX-512 polynomial multiplication using Toom-Cook/Karatsuba and a port of FAFFT, then compares their cycle counts across HQC parameter sets. It reports that the best method depends on the parameter set, with FAFFT taking the lead at HQC-5.

A. Toom-Cook / Karatsuba for AVX-512

  • GFmulOpt is extended to search AVX-512 Toom-Cook/Karatsuba decomposition trees, using Robert and V´eron’s AVX-512 multiplication as the base case.The resulting implementations are used for y·h in key generation and y·u in decryption.Source: A. Toom-Cook / Karatsuba for AVX-512 · p. 5
  • For encryption, vect_mul2x packs h and s alongside duplicated r2 so the two independent products run in parallel.Its measured cycle counts are below twice the corresponding single-product costs for all three parameter sets.Source: A. Toom-Cook / Karatsuba for AVX-512 · p. 5, C. Performance · p. 6

B. Additive-FFT for AVX-512

  • The FAFFT port uses AVX-512 GFNI and processes twice as many elements per iteration for encoding, decoding, and butterfly operations.Precomputed twiddle tables replace constant construction in AVX-512, while reduced basis-conversion ranges skip padded zeros; the tables trade storage for instruction count.Source: B. Additive-FFT for AVX-512 · pp. 5–6

C. Performance

  • 12.6%, 9.8%, and 24.0% are the polynomial-multiplication cost reductions over Cabral et al. for HQC-1, HQC-3, and HQC-5, respectively.TC/Karat has the lowest cycle count at HQC-1 and HQC-3, while FAFFT has the lowest at HQC-5.Source: Table III · p. 6, C. Performance · p. 6
  • FAFFT’s relative cost versus TC/Karat falls from 77% at HQC-1 to 45% at HQC-3, becoming a 4.1% advantage at HQC-5.The crossover is realized by twiddle-table use and reduced basis conversions.Source: C. Performance · p. 6

IV. RM/RS DECODING

HQC decoding first uses Reed–Muller decoding to produce bytes and then Reed–Solomon decoding to correct residual errors. The section’s Reed–Muller change replaces binary search in find_peaks with a horizontal vector reduction.

1) Decoder phases:

  • The decoder processes duplicated 128-bit codeword copies through expand_and_sum, a seven-stage Hadamard transform, and find_peaks to recover one byte.It selects the maximum-absolute-value coefficient and derives the decoded byte from its position and sign.Source: 1) Decoder phases · p. 6

2) Prior implementations:

3) Our Reed-Muller decoder:

  • The new find_peaks reduces vector maxima horizontally, then uses comparison masks to identify the row and coefficient without a data-dependent scalar index.The AVX2 implementation uses constant-time masks, while AVX-512 uses comparison masks and a vector permutation.Source: 3) Our Reed-Muller decoder · p. 7
  • The modified find_peaks has lower cycle counts than both the HQC AVX2 implementation and Cabral et al.’s AVX-512 implementation.The stated comparison is for the find_peaks phase.Source: 3) Our Reed-Muller decoder · p. 7

B. Reed-Solomon Decoder

The Reed-Solomon decoder corrects byte errors through six phases, while prior implementations leave much of its field arithmetic scalar or use PCLMULQDQ. The proposed decoder uses packed GFNI operations across the five field-arithmetic phases.

1) Decoder phases:

  • The six phases compute syndromes, recover and root-find the error-locator polynomial, form an auxiliary polynomial, compute error values, and correct the received word.The first five phases mainly use F_R_S arithmetic; correct_errors is a byte-wise XOR step.Source: 1) Decoder phases · p. 7

2) Prior implementations:

  • Prior implementations use PCLMULQDQ-based arithmetic or limit GFNI to syndrome computation, while Cabral et al. use AVX-512 without GFNI in compute_error_values.Chen et al. use GFNI for syndrome computation, but retain scalar field multiplication in the remaining phases.Source: 2) Prior implementations · p. 7

3) Our Reed-Solomon decoder:

  • Packed GFNI operations replace PCLMULQDQ-based field arithmetic in all five F_R_S-arithmetic phases for both AVX2 and AVX-512.Byte representations are converted before and after GFNI operations; AVX2 evaluates 32 Chien-search candidates per iteration, while AVX-512 evaluates 64.Source: 3) Our Reed-Solomon decoder · pp. 7–8
  • Chien search evaluates the error-locator polynomial with parallel Horner evaluation, and the auxiliary-polynomial convolution uses vector blocks of GFNI multiply-and-XOR steps.Error-value computation gathers error locations into byte vectors and computes inverses and numerator and denominator values in parallel.Source: 3) Our Reed-Solomon decoder · p. 8

C. Performance

On a Tiger Lake i5-1135G7, the clean full-decoder costs fall substantially for both Reed-Solomon and Reed-Muller decoding. Phase timings locate where reductions occur, while clean total rows provide the decoder-cost comparison.

C. Performance

  • 67.9%–77.9% lower Reed-Muller cost than the HQC AVX2 implementation, 18.2%–20.4% than Chen et al. on AVX2, and 3.7%–9.9% than Cabral et al. on AVX-512.These are clean per-call costs for reed_muller_decode; the improvement over prior optimized implementations mainly comes from find_peaks.Source: C. Performance · p. 8
  • 84.7%–88.8% lower Reed-Solomon cost than the HQC AVX2 implementation, 83.2%–87.1% than Chen et al. on AVX2, and 88.9%–91.0% than Cabral et al. on AVX-512.These are clean per-call costs for reed_solomon_decode.Source: C. Performance · p. 8
  • The Reed-Solomon gains concentrate in the five F_R_S-arithmetic phases; correct_errors runs under 100 cycles in every configuration.Phase rows use internal timing code to locate reductions; the clean total row is used for full-decoder cost comparisons.Source: C. Performance · pp. 8–9

V. KECCAK-BASED FUNCTIONS AND FIXED-WEIGHT SAMPLING

HQC’s hash oracles, SHAKE-based expansion, and fixed-weight sampling use Keccak-f[1600]. The section describes prior SIMD implementations and AVX-512 implementations for the SHA3-512 oracles.

A. Background

  • All five HQC symmetric primitives use Keccak-f[1600], differing in absorb pattern, output length, and domain separator.The four random oracles are H, J, G, and I; SHAKE-based expansion is the fifth primitive.Source: A. Background · p. 9
  • H and J use SHA3-256, G and I use SHA3-512, and SHAKE-256 supports public-vector expansion and rejection sampling.The SHA3-512 oracle G derives the per-encapsulation seed, while I derives the key-pair seed.Source: A. Background · p. 9

B. Prior Implementations

  • Cabral et al. provide AVX-512 Keccak and SHA3-256 oracles, but leave G, I, and incremental SHAKE-256 on scalar wrappers.Their AVX-512 SHAKE specialization covers public-vector expansion on encapsulation and decapsulation paths.Source: B. Prior Implementations · p. 9

1) SHA3 oracles:

  • The paper implements G and I with AVX-512 using Cabral et al.’s five-register state layout and permutation, with fixed permutation counts by parameter set.I uses one permutation for every parameter set; G uses one at HQC-1 and two at HQC-3 and HQC-5.Source: 1) SHA3 oracles · p. 9

2) Fixed-weight sampling:

The paper optimizes HQC components and evaluates them under controlled single-core conditions. Its KEM results compare AVX2 decapsulation with prior results and AVX-512 operations with Cabral et al.

2) Fixed-weight sampling:

  • Support expansion scans output words against support positions with branch-free masks, and AVX-512 processes eight 64-bit output words per iteration.The sampled positions are not used as memory addresses in this constant-time implementation.Source: 2) Fixed-weight sampling · p. 9

D. Performance

  • AVX-512 reduces per-call costs by 37.4%–46.4% for G, 46.2%–46.7% for I, and 34.5%–36.8% for support expansion versus Cabral et al..The G and I baselines use scalar wrappers; the support-expansion baseline uses AVX2.Source: D. Performance · p. 10

A. Setup

  • Measurements use one 2.4 GHz Intel Core i5-1135G7 core with Turbo Boost and Hyper-Threading disabled and the benchmark pinned to a physical core.Reported values are medians of 1,000 samples after 10,000 warmup iterations.Source: A. Setup · p. 11

B. Component Performance

  • Clean decoder totals show reductions of 84.7%–88.8% for Reed-Solomon versus the HQC AVX2 implementation and 88.9%–91.0% versus Cabral et al. on AVX-512.Reed-Muller reductions are 67.9%–77.9% versus the HQC AVX2 implementation and 3.7%–9.9% versus Cabral et al. on AVX-512.Source: B. Component Performance · p. 11

C. KEM Performance

  • 24.9%–29.5% lower AVX-512 key-generation cost, 10.4%–11.1% lower encapsulation cost, and 20.6%–26.1% lower decapsulation cost than Cabral et al..At HQC-5, FAFFT further reduces key generation, encapsulation, and decapsulation by 5.0%, 6.7%, and 6.1% over Ours (TC/Karat), respectively; TC/Karat remains faster at HQC-1 and HQC-3.Source: C. KEM Performance · p. 11
  • 11.1%–21.5% lower AVX2 decapsulation cost than the fastest prior result for each parameter set.At HQC-1 and HQC-3, the reduction mainly comes from GFNI Reed-Solomon decoding and find_peaks; at HQC-5, reduced-range AVX2 FAFFT adds a further reduction.Source: C. KEM Performance · p. 11

VII. TLS 1.3 INTEGRATION AND EVALUATION ON X86 IOT GATEWAYS

The section integrates HQC variants into a fixed TLS 1.3 stack and measures handshake latency and endpoint CPU costs. AVX-512 improves handshake times against prior HQC implementations, while HQC remains slower than ML-KEM at matched security.

A. Setup

  • The TLS stack uses liboqs and oqs-provider, with separate HQC variants implementing the same HQC v5.0.0 specification.Measurements use sequential full TLS 1.3 handshakes without resumption; client CPU time covers key generation and decapsulation, while server CPU time covers encapsulation.Source: A. Setup · p. 12

B. Handshake Performance

  • Our AVX-512 implementation reaches handshake times of 1.57 ms, 2.05 ms, and 2.96 ms for HQC-1, HQC-3, and HQC-5, respectively.The liboqs reference implementation takes 18.4 ms, 50.5 ms, and 121.0 ms for those parameter sets.Source: B. Handshake Performance · p. 12, Table VIII · p. 13
  • 8.0% lower handshake time at HQC-5, with AVX-512 TC/Karat; AVX-512 FAFFT reaches the lowest HQC-5 time, 2.92 ms.The reductions versus Cabral et al. were robust at HQC-3 and HQC-5; the HQC-1 difference varied across sessions.Source: B. Handshake Performance · p. 12, Table VIII · p. 13
  • At matched security, AVX2 mlkem-native is faster, with our AVX-512 TC/Karat handshake times 12%, 40%, and 97% higher at HQC-1, HQC-3, and HQC-5.The passage attributes these differences to computational costs and protocol message sizes.Source: B. Handshake Performance · p. 12
  • The comparison omits reported AVX-512-optimized ML-KEM versions because their source code is unavailable; multi-way implementations target throughput, not single-handshake latency.Source: B. Handshake Performance · p. 12
  • At HQC-1, the AVX-512 TC/Karat server on-CPU cost is 736 µs per handshake; client CPU cost exceeds server cost in every HQC configuration.The client performs key generation and decapsulation, whereas the server performs encapsulation.Source: B. Handshake Performance · p. 12

C. Network Performance

Network conditions can outweigh implementation-level speedups: constrained-link HQC-5 handshake time is determined more by communication sizes than by the HQC implementation. The section also reports build-size tradeoffs and limits the evaluation to one processor and emulated paths.

C. Network Performance

  • With 50 ms added RTT and no rate limit, HQC-5 takes about 104 ms while HQC-1 and HQC-3 take about 52 ms in every optimized configuration.The 14,421-byte HQC-5 ciphertext expands the server flight to about 15.5 KB, exceeding the default 10-segment TCP initial congestion window and causing an additional round trip.Source: C. Network Performance · p. 13

D. Storage and Memory Cost

  • FAFFT-based builds occupy 2.5 MB–2.75 MB due to transform tables, while the AVX-512 TC/Karat build occupies 1.14 MB.TC/Karat is a smaller HQC-5 alternative when storage is limited; endpoint peak resident memory remains 9 to 10 MB across configurations.Source: D. Storage and Memory Cost · p. 13

VIII. CONCLUSION

  • AVX-512 TC/Karat reduces KEM key-generation, encapsulation, and decapsulation costs by 24.9%–29.5%, 10.4%–11.1%, and 20.6%–26.1%, respectively, relative to Cabral et al.The conclusion also describes AVX2 and AVX-512 + GFNI optimizations for multiplication, decoding, SHA3-512, and fixed-weight sampling.Source: §VIII · p. 13

C. Network Performance

  • At 1 Mbit/s and 50 ms added RTT, HQC-5 takes about 243 ms, versus 87 ms for ML-KEM-1024; HQC communication sizes determine constrained-link handshake time more than implementation choice.At added RTT 0, HQC-5 takes about 193 ms and ML-KEM-1024 takes 37 ms.Source: §VIII · p. 14, Table IX · p. 14

VIII. CONCLUSION

  • The evaluation uses one Tiger Lake processor with Turbo Boost and Hyper-Threading disabled, and tests TLS over emulated network paths.Further evaluation on other server platforms, resource-constrained end devices, and deployed wireless IoT networks is future work.Source: §VIII · p. 14
Loading 2610.11107v1…