On the Reliability of TVLA-Based Timing Side-Channel Evaluation for ML-KEM in Shared Compute Environments

Japan’s CRYPTREC project — jointly operated by NICT, the Information-technology Promotion Agency (IPA), and other government bodies — completed its external evaluation of ML-KEM for inclusion in the CRYPTREC Ciphers List in April 2026, explicitly highlighting secure and efficient implementation, particularly resistance to side-channel and physical attacks, as the central remaining concern for national post-quantum migration. This concern is not hypothetical: KyberSlash, a pair of timing vulnerabilities in the official Kyber/ML-KEM reference implementation exploiting secret-dependent division instructions, was awarded Best Paper at CHES 2025 and allowed full secret-key recovery on embedded targets. Motivated by this, we conduct a Test Vector Leakage Assessment (TVLA) of a reference ML-KEM-768 implementation’s decapsulation routine, following the standard non-specific fixed-versus-random methodology. Critically, and unlike most published TVLA studies, we run the protocol five times with independent keypairs and, for each run, pair every treatment comparison (fixed ciphertext vs. random ciphertext) with a control comparison (fixed ciphertext vs. itself, split in half) that should show no difference under ideal measurement conditions. We find that only 1 of 5 treatment comparisons exceeds the standard |t| > 4.5 leakage-detection threshold, but 2 of 5 control comparisons also exceed it, with control |t| values (up to 7.62) larger than the flagged treatment value (6.83). This shows that in an ordinary, shared, virtualized compute environment — the kind of hardware available to most students and independent researchers, as opposed to a dedicated side-channel laboratory with core-pinning, disabled frequency scaling, and cycle-accurate instrumentation — naive single-run TVLA verdicts are not reliable, since environmental timing noise alone can exceed the conventional detection threshold in a condition where, by construction, no secret-dependent signal exists. We propose a control-gated TVLA protocol and report a supplementary performance and size benchmark of ML-KEM-768 against classical X25519 and RSA-2048, clearly caveated for the implementation-language mismatch between our pure-Python ML-KEM reference and OpenSSL’s compiled classical primitives.