On Constant-Time QC-MDPC Decoders with Negligible Failure Rate
On Constant-Time QC-MDPC Decoders with Negligible Failure Rate
复制标题
故障率可忽略不计的恒定时间 QC-MDPC 解码器
DOI：
10.1007/978-3-030-54074-6_4
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Kostic, Dusan
中科院分区：
文献类型：
--
作者：
Drucker, Nir;Gueron, Shay;Kostic, Dusan
基于QC-MDPC代码的KEM位翻转密钥封装（BIKE）是NIST PQC标准化项目的第二轮候选者之一。它有一个变体，被证明是IND-CCA安全的。证明模型的KEM与一些黑盒（“理想”）原语。具体地，解封装调用称为“解码器”的理想原语，需要以可忽略的解码失败率（DFR）递送其输出。BIKE的具体实例用一种新的解码算法“Backflip”代替了这种理想的原语，该算法具有可忽略的DFR。然而，它运行的步骤数是可变的，这个数字取决于输入和键。本文提出了一种解码器，具有可忽略的DFR，也运行在一个固定的（和小）的步骤。我们建议BIKE的实例化使用我们推荐的参数的解码器。我们研究了解码器的DFR作为该方案的参数的函数，以获得通信带宽和解码器运行的步骤数之间的有利平衡。此外，我们建立了一个恒定时间的软件实现的建议的实例化，并表明其性能特征是相当接近的IND-CPA的变种。最后，我们讨论了一个微妙的差距，需要解决每个IND-CCA安全KEM（BIKE包括）的解封具有非零故障概率：平均DFR和“最坏情况”的故障概率之间的差异，每个密钥和密文。
The QC-MDPC code-based KEM Bit Flipping Key Encapsulation (BIKE) is one of the Round-2 candidates of the NIST PQC standardization project. It has a variant that is proved to be IND-CCA secure. The proof models the KEM with some black-box (“ideal”) primitives. Specifically, the decapsulation invokes an ideal primitive called “decoder”, required to deliver its output with a negligible Decoding Failure Rate (DFR). The concrete instantiation of BIKE substitutes this ideal primitive with a new decoding algorithm called “Backflip”, that is shown to have the required negligible DFR. However, it runs in a variable number of steps and this number depends on the input and on the key. This paper proposes a decoder that has a negligible DFR and also runs in a fixed (and small) number of steps. We propose that the instantiation of BIKE uses this decoder with our recommended parameters. We study the decoder’s DFR as a function of the scheme’s parameters to obtain a favorable balance between the communication bandwidth and the number of steps that the decoder runs. In addition, we build a constant-time software implementation of the proposed instantiation, and show that its performance characteristics are quite close to the IND-CPA variant. Finally, we discuss a subtle gap that needs to be resolved for every IND-CCA secure KEM (BIKE included) where the decapsulation has nonzero failure probability: the difference between average DFR and “worst-case” failure probability per key and ciphertext.