Fast polynomial inversion for post quantum QC-MDPC cryptography. (English) Zbl 1529.81057
Summary: New post-quantum Key Encapsulation Mechanism (KEM) designs, evaluated as part of the NIST PQC standardization Project, pose challenging tradeoffs between communication bandwidth and computational overheads. Several KEM designs evaluated in Round-2 of the project are based on QC-MDPC codes. BIKE-2 uses the smallest communication bandwidth, but its key generation requires a costly polynomial inversion. In this paper, we provide details on the optimized polynomial inversion algorithm for QC-MDPC codes (originally proposed in the conference version of this work). This algorithm makes the runtime of BIKE-2 key generation tolerable. It brings a speedup of \(11.4 \times\) over the commonly used NTL library, and \(83.5 \times\) over OpenSSL. We achieve additional speedups by leveraging the latest Intel’s Vector- instructions, \(14.3 \times\) over NTL and \(103.9 \times\) over OpenSSL. Our algorithm and implementation were the reason that BIKE team chose BIKE-2 as the only scheme for its Round-3 specification (now called BIKE).
MSC:
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
| 94A60 | Cryptography |
| 81P68 | Quantum computation |
| 15A09 | Theory of matrix inversion and generalized inverses |
| 81P73 | Computational stability and error-correcting codes for quantum computation and communication processing |
| 81-10 | Mathematical modeling or simulation for problems pertaining to quantum theory |
Keywords:
polynomial inversion; BIKE; QC-MDPC codes; constant-time algorithm; constant-time implementation; NIST PQC round-3References:
| [1] | Aragon, N.; Barreto, P. S.L. M.; Bettaieb, S.; Bidoux, L.; Blazy, O.; Deneuville, J.-C.; Gaborit, P.; Ghosh, S.; Gueron, S.; Güneysu, T.; Melchor, C. A.; Misoczki, R.; Persichetti, E.; Sendrier, N.; Tillich, J.-P.; Vasseur, V.; Zémor, G., BIKE: bit flipping key encapsulation (2020) |
| [2] | NIST, Post-quantum cryptography (2019) |
| [3] | Aragon, N.; Barreto, P. S.L. M.; Bettaieb, S.; Bidoux, L.; Blazy, O.; Deneuville, J.-C.; Gaborit, P.; Gueron, S.; Güneysu, T.; Melchor, C. A.; Misoczki, R.; Persichetti, E.; Sendrier, N.; Tillich, J.-P.; Vasseur, V.; Zémor, G., BIKE: bit flipping key encapsulation (2019) |
| [4] | McEliece, R. J., A public-key cryptosystem based on algebraic coding theory, Deep Space Network Progress Report, 44, 114-116 (1978) |
| [5] | Niederreiter, H., Knapsack-type cryptosystems and algebraic coding theory, Probl. Control Inf. Theory, 15, 2, 157-166 (1986) · Zbl 0611.94007 |
| [6] | Drucker, N.; Gueron, S.; Kostic, D., Fast polynomial inversion for post quantum QC-MDPC cryptography, (Dolev, S.; Kolesnikov, V.; Lodha, S.; Weiss, G., Cyber Security Cryptography and Machine Learning (2020), Springer International Publishing: Springer International Publishing Cham), 110-127 |
| [7] | Drucker, N.; Gueron, S.; Kostic, D., Fast polynomial inversion for post quantum QC-MDPC cryptography, Cryptology ePrint Archive, Report 2019/298 (2020) |
| [8] | Open Quantum Safe Project, liboqs (2020) |
| [9] | Amazon Web Services, s2n (2020) |
| [10] | Misoczki, R., BIKE - bit-flipping key encapsulation (2019) |
| [11] | Aguilar Melchor, C.; Aragon, N.; Bettaieb, S.; Loïc, B.; Blazy, O.; Deneuville, J.-C.; Gaborit, P.; Persichetti, E.; Zémor, G., Hamming quasi-cyclic (HQC) (2017) |
| [12] | Hülsing, A.; Rijneveld, J.; Schanck, J.; Schwabe, P., High-speed key encapsulation from NTRU, (Fischer, Wieland; Homma, Naofumi, Cryptographic Hardware and Embedded Systems - CHES 2017 (2017), Springer International Publishing: Springer International Publishing Cham), 232-252 · Zbl 1440.94058 |
| [13] | Baldi, M.; Barenghi, A.; Chiaraluce, F.; Pelosi, G.; Santini, P., LEDAcrypt (2019) |
| [14] | Itoh, T.; Tsujii, S., A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases, Inf. Comput., 78, 3, 171-177 (1988) · Zbl 0672.68015 |
| [15] | Bernstein, D. J.; Yang, B.-Y., Fast constant-time gcd computation and modular inversion, IACR Trans. Cryptogr. Hardw. Embed. Syst., 2019, 3, 340-398 (2019) |
| [16] | Guimarães, A.; Aranha, D. F.; Borin, E., Optimized implementation of QC-MDPC code-based cryptography, Concurr. Comput., Pract. Exp., 31, 18, Article e5089 pp. (2019) |
| [17] | Guimar, A.; Borin, E.; Aranha, D. F.; Guimarães, A.; Borin, E.; Aranha, D. F., Introducing arithmetic failures to accelerate QC-MDPC code-based cryptography, Code Based Cryptogr., 2, 44-68 (2019) · Zbl 1533.94042 |
| [18] | Wu, Chien-Hsing; Wu, Chien-Ming; Shieh, Ming-Der; Hwang, Yin-Tsung, High-speed, low-complexity systolic designs of novel iterative division algorithms in \(g f( 2^m)\), IEEE Trans. Comput., 53, 3, 375-380 (2004) |
| [19] | Shoup, V., Number theory c++ library (ntl) version 11.3.2 (November 2018) |
| [20] | Gaudry, P. Z. Pierrick; Brent, Richard; Thome, E., gf2x-1.2 (July 2017) |
| [21] | The OpenSSL Project, OpenSSL 1.1.1: the open source toolkit for SSL/TLS |
| [22] | Drucker, N.; Gueron, S.; Kostic, D., Additional implementation of BIKE (2019) |
| [23] | Bos, J. W.; Kleinjung, T.; Niederhagen, R.; Schwabe, P., ECC2K-130 on cell CPUs, (Bernstein, D. J.; Lange, T., Progress in Cryptology - AFRICACRYPT 2010 (2010), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 225-242 · Zbl 1284.94054 |
| [24] | Drucker, N.; Gueron, S.; Kostic, D., Additional implementation of BIKE (2020) |
| [25] | Drucker, N.; Gueron, S.; Kostic, D., Intel®64 and IA-32 architectures software developer’s manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4 |
| [26] | Drucker, N.; Gueron, S.; Krasnov, V., Fast multiplication of binary polynomials with the forthcoming vectorized VPCLMULQDQ instruction, (2018 IEEE 25th Symposium on Computer Arithmetic (ARITH) (2018)), 115-119 |
| [27] | Gueron, Shay (October 2018) |
| [28] | Sendrier, N.; Vasseur, V., On the decoding failure rate of QC-MDPC bit-flipping decoders, (Ding, J.; Steinwandt, R., Post-Quantum Cryptography, Vol. 2 (2019), Springer International Publishing: Springer International Publishing Cham), 404-416 · Zbl 1512.94174 |
| [29] | Drucker, N.; Gueron, S.; Kostic, D., QC-MDPC decoders with several shades of gray (Dec 2019), Cryptology ePrint Archive, Report 2019/1423 |
| [30] | Drucker, N.; Gueron, S.; Kostic, D.; Persichetti, E., On the Applicability of the Fujisaki-Okamoto Transformation to the BIKE KEM (2020), Cryptology ePrint Archive, Report 2020/510 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
