Abstract
QC-MDPC code-based KEMs rely on decoders that have a small or even negligible Decoding Failure Rate (DFR). These decoders should be efficient and implementable in constant-time. One example for a QC-MDPC KEM is the Round-2 candidate of the NIST PQC standardization project, “BIKE”. We have recently shown that the Black-Gray decoder achieves the required properties. In this paper, we define several new variants of the Black-Gray decoder. One of them, called Black-Gray-Flip, needs only 7 steps to achieve a smaller DFR than Black-Gray with 9 steps, for the same block size. On current
platforms, our BIKE-1 (Level-1) constant-time decapsulation is \(1.9\times \) faster than the previous decapsulation with Black-Gray. We also report an additional \(1.25\times \) decapsulating speedup using the new
and
instructions available on “Ice-Lake” micro-architecture.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The paper [13] does not point to publicly available code.
References
Intel®64 and IA-32 architectures software developer’s manual. Combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4, November 2019. http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html
Aragon, N., et al.: BIKE: Bit Flipping Key Encapsulation (2017). https://bikesuite.org/files/round2/spec/BIKE-Spec-2019.06.30.1.pdf
Chou, T.: QcBits: constant-time small-key code-based cryptography. In: Gierlichs, B., Poschmann, A.Y. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2016, pp. 280–300. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53140-2_14
Drucker, N., Gueron, S.: Fast multiplication of binary polynomials with the forthcoming vectorized VPCLMULQDQ instruction. In: 2018 IEEE 25th Symposium on Computer Arithmetic (ARITH), June 2018
Drucker, N., Gueron, S.: A toolbox for software optimization of QC-MDPC code-based cryptosystems. J. Cryptographic Eng. 9, 1–17 (2019). https://doi.org/10.1007/s13389-018-00200-4
Drucker, N., Gueron, S.: Fast CTR DRBG for x86 platforms, March 2019. https://github.com/aws-samples/ctr-drbg-with-vector-aes-ni
Drucker, N., Gueron, S., Dusan, K.: Additional implementation of BIKE (2019). https://bikesuite.org/additional.html
Drucker, N., Gueron, S., Kostic, D.: On constant-time QC-MDPC decoding with negligible failure rate. Technical report 2019/1289, November 2019. https://eprint.iacr.org/2019/1289
Drucker, N., Gueron, S., Krasnov, V.: Fast multiplication of binary polynomials with the forthcoming vectorized VPCLMULQDQ instruction. In: 2018 IEEE 25th Symposium on Computer Arithmetic (ARITH), pp. 115–119, June 2018. https://doi.org/10.1109/ARITH.2018.8464777
Drucker, N., Gueron, S., Krasnov, V.: Making AES great again: the forthcoming vectorized AES instruction. In: Latifi, S. (ed.) 16th International Conference on Information Technology-New Generations. (ITNG 2019), pp. 37–41. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-14070-0_6
Eaton, E., Lequesne, M., Parent, A., Sendrier, N.: QC-MDPC: a timing attack and a CCA2 KEM. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 47–76. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_3
Gallager, R.: Low-density parity-check codes. IRE Trans. Inf. Theory 8(1), 21–28 (1962). https://doi.org/10.1109/TIT.1962.1057683
Guimarães, A., Aranha, D.F., Borin, E.: Optimized implementation of QC-MDPC code-based cryptography 31(18), e5089 (2019). https://onlinelibrary.wiley.com/doi/abs/10.1002/cpe.5089
Maurich, I.V., Oder, T., Güneysu, T.: Implementing QC-MDPC McEliece encryption. ACM Trans. Embed. Comput. Syst. 14(3), 441–4427 (2015). https://doi.org/10.1145/2700102
NIST: Post-Quantum Cryptography (2019). https://csrc.nist.gov/projects/post-quantum-cryptography. Accessed 20 Aug 2019
Sendrier, N., Vasseur, V.: On the decoding failure rate of QC-MDPC bit-flipping decoders. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 404–416. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_22
Acknowledgments
We thank Ray Perlner from NIST for pointing out that the mock-bits technique is not sufficient for security when using static keys, which drove us to change our BIKE implementation. This research was partly supported by: The Israel Science Foundation (grant No. 3380/19); The BIU Center for Research in Applied Cryptography and Cyber Security, and the Center for Cyber Law and Policy at the University of Haifa, both in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
A Pseudo-Code for B, BG, BGB, BGF
A description of the B, BG, BGB, BGF decoders is given in Sect. 4. Algorithm 3 provides a formal definition of them.
B Additional Information on the Experiments and Results
The following values of r were used by the best linear fit extrapolation method:
-
BIKE-1 Level-1: 9349, 9547, 9749, 9803, 9859, 9883, 9901, 9907, 9923, 9941, 9949, 10037, 10067, 10069, 10091, 10093, 10099, 10133, 10139.
For Level-1 studies the number of tests for every value of r is 3.84M for \(r \in [9349, 9901]\) and 384M for (larger) \(r \in [9907, 10139]\). For the line through two large points extrapolation method (see [8][Appendix C] and Level-1, we chose: \(r = 10141\) running 384M tests, and \(r = 10259\) running \(\sim {}7.3\) (technically 7.296) billion tests (Table 6).
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Drucker, N., Gueron, S., Kostic, D. (2020). QC-MDPC Decoders with Several Shades of Gray. In: Ding, J., Tillich, JP. (eds) Post-Quantum Cryptography. PQCrypto 2020. Lecture Notes in Computer Science(), vol 12100. Springer, Cham. https://doi.org/10.1007/978-3-030-44223-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-44223-1_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-44222-4
Online ISBN: 978-3-030-44223-1
eBook Packages: Computer ScienceComputer Science (R0)