列表译码在密码中的应用综述

作     者：张卓然 张煌 张方国 ZHANG Zhuoran;ZHANG Huang;ZHANG Fangguo

作者机构：中山大学数据科学与计算机学院广州510006 广东省信息安全技术重点实验室广州510006 

出 版 物：《电子与信息学报》 (Journal of Electronics & Information Technology)

年 卷 期：2020年第42卷第5期

页      面：1049-1060页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(61672550,61972429) 国家重点研发计划(2017YFB0802503)。 

主　　题：公钥密码 列表译码 离散对数 后量子密码 

摘      要：列表译码自上世纪50年代提出以来,不仅在通信与编码等方面得到了广泛应用,也在计算复杂性理论和密码学领域有着广泛的应用。近年来,随着量子计算的发展,基于整数分解等传统困难问题设计的密码方案受到了巨大的威胁。由于编码理论中一些计算问题的NP困难性被广泛认为是量子概率多项式时间不可攻克的,建立在其上的基于纠错码的密码体制得到了越来越多的重视,列表译码也越来越引起人们的关注。该文系统梳理了列表译码在密码学中的应用,包括早期在证明任何单向函数都存在硬核谓词、设计叛徒追踪方案、以多项式重建作为密码原语设计公钥方案、改进传统基于纠错码的密码方案和求解离散对数问题(DLP)等方面的应用,以及近期,列表译码在设计安全通信协议、求解椭圆曲线离散对数问题、设计新的基于纠错码的密码方案等方面的应用。该文对列表译码的算法改进及其在密码协议设计和密码分析中的应用、新应用场景探索等方面的发展趋势进行了探讨。