基于代数曲线的列表译码及其应用

Due to practical application in communications and theoretical interest in computer science and complexity theory, decoding has been the most important topic since the birth of coding theory. Compared with the traditional unique decoding model, a list-decoding algorithm can correct more errors, but output a list of codewords that contains the correct one. In this project, we mainly focus on the construction of codes with good list decodability properties and efficient decoding algorithms via algebraic curves. We are going to study this problem for codes over large alphabets as well as small alphabets (especially the binary case). We will apply the automorphism group of algebraic curves to obtain an interpolation equation and then use Chebotarev’s denisty theorem to control the number of solutions. Thus the size of the output list can be controlled. Meanwhile, we consider the local expansion of algebraic functions to design an efficient algorithm to output solutions. As an application of list decoding, we will apply list decoding model to a class of post-quantum cryptography, i.e., code-based cryptosystem. Our idea is to replace unique decoding in the current code-based scheme by list decoding. We are going to analyze security and key size in our modified code-based system with list decoding. In addition, we will also solve the problem of identifying the correct plaintext from a list. This project will not only have significance for the fields of coding theory and theoretical computer science, but also provide a new avenue for post-quantum cryptography.

自编码理论诞生以来，译码问题因其在通信，计算机等领域的广泛应用成为了一个重要的研究课题。译码是一个码能否应用到实际的关键因素之一。相比传统的唯一译码模型，在列表译码模型下，我们可以纠正更多的错误，但输出的是多个码字。本项目旨在研究如何利用代数曲线构造具有好的列表译码性质的码，同时具有快速的列表译码算法。我们分别研究大字符上和小字符上的码（包括二元码）。我们将利用代数曲线的自同构性质来得到一个方程，再由数论中的Chebotarev定理保证这个方程解的个数不会很大，从而控制列表译码输出的大小。同时也利用代数曲线上的函数局部展开来快速求解。此外，列表译码还可以应用到后量子密码中。我们将列表译码的思想引入到基于编码的密码公钥方案，重新分析该方案的安全性和高效性，并研究如何在一个列表的明文中找到正确的明文。本项目的研究不仅对编码理论本身和理论计算机领域有着重要意义，同时还为后量子密码提供一种新方案。

自编码理论诞生以来，译码问题因其在通信，计算机等领域的广泛应用吸引了众多研究者的兴趣，并成为了一个重要的课题。相比传统的唯一译码模型，在列表译码模型下，我们可以纠正更多的错误，同时输出的是多个码字。本项目中，我们主要研究如何利用代数曲线构造具有好的列表译码性质的码。我们考虑了当前在大域上具有较好列表译码性质的码作为外码与最优的二元码进行接连，从而得到了具有较好列表译码性质的二元码。同时，列表译码还可以应用到后量子密码中的基于编码的密码公钥方案。我们将列表译码的思想引入到基于编码的密码公钥方案，重新分析该方案的安全性和高效性。根据我们前期的关于代数几何码的列表译码的研究基础，我们给出了椭圆曲线上的代数几何码的子域子码的列表译码算法。说明了该方案的安全性，并将相关参数与Goppa码进行比较。我们在研究代数曲线并研究如何利用代数曲线相关知识来构造线性码的同时还得到了一些具有重要应用价值的良好线性码。如编码在数据存储，序列中的应用等。创新性的提出利用函数域的框架来构造极大修复局部可修复码的一种新框架。通过研究曲线的有理点的个数问题来研究了序列的相关系数，提出了长度为任意素数，性能优良的二元序列的构造方法。在本项目的资助下，共发表了9篇高质量的论文，均发表在信息论顶级期刊IEEE Trans. On Information Theory上。