Skip to content

Back to the catalog

PoP! Goes the VOLE: Shorter Proofs of Possession for KEM Certificates
eprint.iacr.orgpaper

PoP! Goes the VOLE: Shorter Proofs of Possession for KEM Certificates

This IACR ePrint paper proposes and benchmarks a non-interactive Proof of Possession (PoP) for the code-based post-quantum KEM HQC, built using the VOLE-in-the-Head (VOLEitH) zero-knowledge paradigm, to solve the practical problem of issuing KEM-based certificates needed by protocols like KEMTLS. The authors integrate their HQC PoP into the ACME certificate-issuance protocol and compare it against existing PoP schemes for Kyber and FrodoKEM, showing Kyber issues certificates faster but at the cost of protocol or NIST-standard compatibility, while their HQC-based PoP keeps compatibility and achieves smaller proof sizes, which matters under unstable-network conditions due to larger KEM-based CSRs.

TL;DR A VOLE-in-the-Head based Proof of Possession for HQC KEM certificates, benchmarked against Kyber and FrodoKEM in ACME, stays NIST-compliant while shrinking proof size.
Open original ↗
Document

What it is

A VOLE-in-the-Head (VOLEitH)-based non-interactive Proof of Possession (PoP) scheme for HQC, the NIST-standardized code-based post-quantum KEM. Authored by Bettaieb, Giron, Kulkarni, and Palumbi (TII and UTFPR), and integrated into the ACME protocol for automated certificate issuance.

How it works

Certificate authorities issuing KEM-based certificates (needed for KEMTLS) must verify that a requester actually holds the private key matching a submitted KEM public key, since KEMs lack a native signing operation for this. The paper's PoP uses the VOLEitH zero-knowledge paradigm to let the certificate requester prove possession of the HQC private key non-interactively, without revealing it, as part of the CSR submitted through ACME.

Preconditions / Affected

Applies to CAs and protocols adopting KEM-based certificates (e.g., for KEMTLS deployments) using HQC specifically. The comparison baseline covers PoP schemes for Kyber and FrodoKEM from Güneysu et al. (CCS '22).

What to do

The paper reports a three-way tradeoff among PoP schemes integrated into ACME:

  • Kyber-based PoP: fastest certificate issuance, but requires either breaking ACME/protocol compatibility (significant alterations to proposed internet standards) or breaking NIST-standard compliance.
  • HQC-based PoP (this paper): maintains both ACME compatibility and NIST compliance, and produces smaller proof sizes than the alternatives.
  • Under simulated unstable-network conditions (relevant because KEM-based CSRs are larger than classical ones), HQC-PoP's smaller proof size makes its overall performance competitive with the fastest (Kyber) option despite Kyber's raw speed advantage.

For teams planning KEMTLS/PQC certificate infrastructure, HQC-PoP is presented as the option that avoids forcing a choice between standards compliance and protocol compatibility — the Kyber alternative forces that tradeoff.

Caveats

The paper does not report absolute benchmark numbers (timings/proof-size figures) in the available text beyond qualitative comparisons ("smaller," "competitive," "faster"). No implementation/repository link or specific ACME extension details are given on this page.

Technologies named here

Techniques named here

  • Proof of Possession for KEM public keys
  • Network traffic analysis under unstable network conditions

Also named here

  • ACME

Related in Identity & Access