An Efficient Implementation Scheme for Lattice Reduction in the List-Decoding Algorithm for the Binary Goppa Codes

Abstract

This paper presents a scheme that is designed for the effective implementation of lattice reduction for polynomial matrices within the list-decoding algorithm that is applied to the binary Goppa codes. The reduced form of a polynomial matrix is obtained by transforming the given polynomial matrix into a matrix in the weak Popov form. To achieve efficient lattice reduction within the list-decoding algorithm, the proposed scheme reorganizes the polynomial matrix by leveraging its inherent properties and converts it into the weak Popov form. When using the proposed implementation technique to convert the reorganized polynomial matrix into the weak Popov form, the number of simple transformations of the first kind that had to be performed was reduced by about 15% compared to the technique used to convert the original matrix to the weak Popov form. As a result, the execution time of lattice reduction was also decreased.

Keywords

• Binary Goppa codes
• McEliece cryptosystem
• list-decoding algorithm
• weak Popov form
• polynomial matrix
• lattice reduction