Paper 2026/2929
When Confirmation Tags Are Not Enough: Full Key Recovery from Ordinary Decapsulation Outputs in a HCR-KEM
Abstract
Reconciliation in lattice-based key encapsulation mechanisms enables two parties to derive a common secret despite the presence of noise. However, confirming the reconciled value does not necessarily guarantee the validity of the ciphertext from which it was derived. In this paper, we investigate this security distinction through HCR-KEM, a reconciliation-based research construction that combines multi-shift forest reconciliation, an NTT-activity filter, a SHA3-256 confirmation tag, and implicit rejection. We demonstrate a complete key-recovery attack using only ordinary 32-byte decapsulation outputs, without requiring an explicit validity oracle. By constructing source-admissible unit-monomial ciphertexts, we isolate individual signed relations while fixing 289 non-target reconciliation positions. We then exploit the resulting relations through a publicly verifiable signed-graph certificate to recover all 1,536 secret coefficients. To improve the efficiency of this recovery, we introduce graph-aware peeling, which uses previously recovered coefficients to reduce the complexity of subsequent binary recovery trees. We evaluate the attack using the reference C implementation on 50 fresh matched keys. All 150 recovery executions succeed, with 3,000 correct honest-key predictions and no false matches among 3,000 negative controls. Graph-aware peeling requires an average of 3,565.18 decapsulation calls, compared with 4,382.54 for the optimal depth-four per-scalar method and 6,127.38 for the original method. This represents an 18.65\% reduction over the scalar-optimal baseline, with a mean paired saving of 817.36 calls and an approximate 95\% confidence interval of 810.49–824.23 calls. Finally, we establish a conditional reconciliation-independence criterion and apply it to the guaranteed-rejection branch of standard ML-KEM. Our findings identify a concrete limitation of confirmation-only ciphertext validation and demonstrate how graph structure can be exploited to improve adaptive key recovery.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Chosen-ciphertext attacksLattice-based cryptographyKey encapsulationkey-mismatch attacksReconciliation
- Contact author(s)
- rhamza @ tiu ac jp
- History
- 2026-11-22: approved
- 2026-11-18: received
- See all versions
- Short URL
- https://ia.cr/2026/2929
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2026/2929,
author = {Rafik HAMZA},
title = {When Confirmation Tags Are Not Enough: Full Key Recovery from Ordinary Decapsulation Outputs in a {HCR}-{KEM}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2929},
year = {2026},
url = {https://eprint.iacr.org/2026/2929}
}