张煌,
张方国,
1.中山大学数据科学与计算机学院 广州 510006
2.广东省信息安全技术重点实验室 广州 510006
基金项目:国家自然科学基金(61672550, 61972429)，国家重点研发计划(2017YFB0802503)
详细信息
作者简介:张卓然：女，1995年生，博士生，研究方向为基于纠错码的密码学
张煌：男，1988年生，博士生，研究方向为格密码和零知识
张方国：男，1972年生，教授，研究方向为密码学理论及其应用，特别是椭圆曲线密码体制、安全多方计算、可证明安全性等
通讯作者:张方国 isszhfg@mail.sysu.edu.cn
中图分类号:TP393计量
文章访问数:2250
HTML全文浏览量:901
PDF下载量:120
被引次数:0
出版历程
收稿日期:2019-11-01
修回日期:2020-02-25
网络出版日期:2020-03-19
刊出日期:2020-06-04
Survey on Applications of List Decoding to Cryptography
Zhuoran ZHANG,Huang ZHANG,
Fangguo ZHANG,
1. School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China
2. Guangdong Key Laboratory of Information Security, Guangzhou 510006, China
Funds:The National Natural Science Foundation of China (61672550, 61972429), The National Key R & D Program of China (2017YFB0802503)
摘要
摘要:列表译码自上世纪50年代提出以来，不仅在通信与编码等方面得到了广泛应用，也在计算复杂性理论和密码学领域有着广泛的应用。近年来，随着量子计算的发展，基于整数分解等传统困难问题设计的密码方案受到了巨大的威胁。由于编码理论中一些计算问题的NP困难性被广泛认为是量子概率多项式时间不可攻克的，建立在其上的基于纠错码的密码体制得到了越来越多的重视，列表译码也越来越引起人们的关注。该文系统梳理了列表译码在密码学中的应用，包括早期在证明任何单向函数都存在硬核谓词、设计叛徒追踪方案、以多项式重建作为密码原语设计公钥方案、改进传统基于纠错码的密码方案和求解离散对数问题(DLP)等方面的应用，以及近期，列表译码在设计安全通信协议、求解椭圆曲线离散对数问题、设计新的基于纠错码的密码方案等方面的应用。该文对列表译码的算法改进及其在密码协议设计和密码分析中的应用、新应用场景探索等方面的发展趋势进行了探讨。
关键词:公钥密码/
列表译码/
离散对数/
后量子密码
Abstract:Since the conception of list decoding is proposed in the 1950s, 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 code-based 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.
Key words:Public key cryptography/
List decoding/
Discrete logarithm/
Post-quantum cryptography
PDF全文下载地址:
https://jeit.ac.cn/article/exportPdf?id=3edd90d5-49df-42b3-be50-85f3b7ae85f7
