Paper 2017/733
Decoding Generalized ReedSolomon Codes and Its Application to RLCE Encryption Scheme
Yongge Wang
Abstract
This paper compares the efficiency of various algorithms for implementing public key encryption scheme RLCE on 64bit CPUs. By optimizing various algorithms for polynomial and matrix operations over finite fields, we obtained several interesting (or even surprising) results. For example, it is well known (e.g., Moenck 1976) that Karatsuba's algorithm outperforms classical polynomial multiplication algorithm from the degree 15 and above (practically, Karatsuba's algorithm only outperforms classical polynomial multiplication algorithm from the degree 35 and above ). Our experiments show that 64bit optimized Karatsuba's algorithm will only outperform 64bit optimized classical polynomial multiplication algorithm for polynomials of degree 115 and above over finite field $GF(2^{10})$. The second interesting (surprising) result shows that 64bit optimized Chien's search algorithm ourperforms all other 64bit optimized polynomial root finding algorithms such as BTA and FFT for polynomials of all degrees over finite field $GF(2^{10})$. The third interesting (surprising) result shows that 64bit optimized Strassen matrix multiplication algorithm only outperforms 64bit optimized classical matrix multiplication algorithm for matrices of dimension 750 and above over finite field $GF(2^{10})$. It should be noted that existing literatures and practices recommend Strassen matrix multiplication algorithm for matrices of dimension 40 and above. All experiments are done on a 64bit MacBook Pro with i7 CPU with a single thread. The reported results should be appliable to 64 or larger bits CPU. For 32 or smaller bits CPUs, these results may not be applicable. The source code and library for the algorithms covered in this paper will be available at http://quantumca.org/.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint. MINOR revision.
 Contact author(s)
 yonwang @ uncc edu
 History
 20170801: received
 Short URL
 https://ia.cr/2017/733
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/733, author = {Yongge Wang}, title = {Decoding Generalized ReedSolomon Codes and Its Application to RLCE Encryption Scheme}, howpublished = {Cryptology ePrint Archive, Paper 2017/733}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/733}}, url = {https://eprint.iacr.org/2017/733} }