摘要
列表译码自上世纪50年代提出以来,不仅在通信与编码等方面得到了广泛应用,也在计算复杂性理论和密码学领域有着广泛的应用。近年来,随着量子计算的发展,基于整数分解等传统困难问题设计的密码方案受到了巨大的威胁。由于编码理论中一些计算问题的NP困难性被广泛认为是量子概率多项式时间不可攻克的,建立在其上的基于纠错码的密码体制得到了越来越多的重视,列表译码也越来越引起人们的关注。该文系统梳理了列表译码在密码学中的应用,包括早期在证明任何单向函数都存在硬核谓词、设计叛徒追踪方案、以多项式重建作为密码原语设计公钥方案、改进传统基于纠错码的密码方案和求解离散对数问题(DLP)等方面的应用,以及近期,列表译码在设计安全通信协议、求解椭圆曲线离散对数问题、设计新的基于纠错码的密码方案等方面的应用。该文对列表译码的算法改进及其在密码协议设计和密码分析中的应用、新应用场景探索等方面的发展趋势进行了探讨。
Since the conception of list decoding is proposed in the 1950 s, list decoding not only is applied to communication and coding theory, but also plays a significant role in computational complexity and cryptography. In recent years, with the rapid development of quantum computing, the traditional cryptographic schemes based on factorization and other difficult problems are greatly threatened. The codebased cryptosystems, whose security relies on the NP-hard problems in coding theory, are attracting more and more attention as a candidate of the post-quantum cryptography, and so does the list decoding algorithm. This paper systematically reviews the applications of list decoding to cryptography, including early applications in proving that any one-way function has hard-core bits, designing traitor tracing schemes, designing public key schemes using polynomial reconstruction as cryptographic primitives, improving the traditional code-based cryptosystems and solving Discrete Logarithm Problems(DLP), and recent applications to designing secure communication interactive protocols, solving the elliptic curve discrete logarithm problem, and designs new cryptographic schemes based on error correction codes. Finally, the new research issues of the algorithm improvement of list decoding, its application to the design of cryptographic protocol and cryptoanalysis, and the exploration of new application scenarios are discussed.
作者
张卓然
张煌
张方国
ZHANG Zhuoran;ZHANG Huang;ZHANG Fangguo(School of Data and Computer Science,Sun Yat-sen University,Guangzhou 510006,China;Guangdong Key Laboratory of Information Security,Guangzhou 510006,China)
出处
《电子与信息学报》
EI
CSCD
北大核心
2020年第5期1049-1060,共12页
Journal of Electronics & Information Technology
基金
国家自然科学基金(61672550,61972429)
国家重点研发计划(2017YFB0802503)。
关键词
公钥密码
列表译码
离散对数
后量子密码
Public key cryptography
List decoding
Discrete logarithm
Post-quantum cryptography
