McBits Revisited
This paper presents a constant-time fast implementation for a high-security code-based encryption system. The implementation is based on the “McBits” paper by Bernstein, Chou, and Schwabe in 2013: we use the same FFT algorithms for root finding and syndro
- PDF / 525,826 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 212 Views
Abstract. This paper presents a constant-time fast implementation for a high-security code-based encryption system. The implementation is based on the “McBits” paper by Bernstein, Chou, and Schwabe in 2013: we use the same FFT algorithms for root finding and syndrome computation, similar algorithms for secret permutation, and bitslicing for low-level operations. As opposed to McBits, where a high decryption throughput is achieved by running many decryption operations in parallel, we take a different approach to exploit the internal parallelism in one decryption operation for the use of more applications. As the result, we manage to achieve a slightly better decryption throughput at a much higher security level than McBits. As a minor contribution, we also present a constant-time implementation for encryption and key-pair generation, with similar techniques used for decryption. Keywords: McEliece · Niederreiter · Bitslicing · Software implementation
1
Introduction
In recent years, due to the advance in quantum computing, cryptographers are paying more and more attention to post-quantum cryptography. In particular, NIST’s call for proposal [16] serves as an announcement to declare that postquantum cryptography is going to be reality, and the whole world needs to be prepared for that. Among other things, we need post-quantum public-key encryption schemes, and the most promising candidates today are from codebased cryptography and lattice-based cryptography. In 1978, McEliece proposed his hidden-Goppa-code cryptosystem [13] as the first code-based encryption system. Until today, almost 40 years of research has been invested on cryptanalyzing the system, yet nothing has really shaken its security. It has thus become one of the most confidence-inspiring post-quantum encryption systems we have today, and it is important to evaluate how practical the system is for deployment. This work was supported by the Cisco University Research Program, by the National Science Foundation under grant 1018836, and by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005. Permanent ID of this document: a6d277b6724b21ae996418cbec02d682. Date: 2017.06.26. c International Association for Cryptologic Research 2017 W. Fischer and N. Homma (Eds.): CHES 2017, LNCS 10529, pp. 213–231, 2017. DOI: 10.1007/978-3-319-66787-4 11
214
T. Chou Table 1. Number of cycles for decoding for McBits and our software. reference m n t bytes sec perm synd key eq root all arch 13 6624 115 958482 252 23140 83127 102337 65050 444971 IB McBits [3] 13 6960 119 1046739 263 23020 83735 109805 66453 456292 IB This paper 13 8192 128 1357824 297
3783 62170 170576 53825 410132 IB 3444 36076 127070 34491 275092 HW
In 2013, Bernstein, Chou, and Schwabe published the “McBits” paper [3], which presents a software implementation of Niederreiter’s dual form [15] of the McEliece cryptosystem. McBits features (1) a very high decoding (and thus decryption) throughput which is an order of magnitude faster than the previous implementation by Biswas and
Data Loading...
