Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC

Juliane Krämer; Patrick Struck; Maximiliane Weishäupl

Paper 2024/1233

Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC

Juliane Krämer, University of Regensburg

Patrick Struck

, University of Konstanz

Maximiliane Weishäupl, University of Regensburg

Abstract

In this work, we continue the analysis of the binding properties of implicitly-rejecting key-encapsulation mechanisms (KEMs) obtained via the Fujisaki-Okamoto (FO) transform. These binding properties, in earlier literature known under the term robustness, thwart attacks that can arise when using KEMs in complex protocols. Recently, Cremers et al. (CCS'24) introduced a framework for binding notions, encompassing previously existing but also new ones. While implicitly-rejecting FO-KEMs have been analyzed with respect to multiple of these notions, there are still several gaps. We complete the picture by providing positive and negative results for the remaining notions. Further, we show how to apply our results to the code-based KEMs BIKE and HQC, which were round-4 candidates in NIST's PQC standardization process. Through this, we close a second gap as our results complete the analysis of the binding notions for the NIST round-4 KEMs. Finally, we give a modified version of the FO transform that achieves all binding notions.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: KEM Key-Encapsulation Mechanism Robustness Binding PQC BIKE HQC
Contact author(s): juliane kraemer @ ur de
patrick struck @ uni-konstanz de
maximiliane weishaeupl @ ur de
History: 2025-04-08: revised; 2024-08-02: received; See all versions
Short URL: https://ia.cr/2024/1233
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1233,
      author = {Juliane Krämer and Patrick Struck and Maximiliane Weishäupl},
      title = {Binding Security of Implicitly-Rejecting {KEMs} and Application to {BIKE} and {HQC}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1233},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1233}
}