范淑琴
密码科学技术国家重点实验室 北京 100878
基金项目:国家重点研发计划(2017YFB0802005, 2018YFB0804105)，国家自然科学基金(61602046, 61932019)，中国科协“青年人才托举工程”(2016QNRC001)
详细信息
作者简介:张江：男，1986年生，副研究员，主要研究方向为基于格的密码协议及其可证明安全
范淑琴：女，1978年生，教授，主要研究方向为基于格的密码分析
通讯作者:张江 jiangzhang09@gmail.com
中图分类号:TN918, TP309.7计量
文章访问数:1404
HTML全文浏览量:567
PDF下载量:70
被引次数:0
出版历程
收稿日期:2019-09-14
修回日期:2019-11-20
网络出版日期:2019-11-29
刊出日期:2020-02-19
On the Hardness of the Asymmetric Learning With Errors Problem
Jiang ZHANG,,Shuqin FAN
State Key Laboratory of Cryptology, Beijing 100878, China
Funds:The National Key Research and Development Program of China (2017YFB0802005, 2018YFB0804105), The National Natural Science Foundation of China (61602046, 61932019), The Young Elite Scientists Sponsorship Program by China Association for Science and Technology (2016QNRC001)
摘要
摘要:由于基于最坏情况困难假设等优点，基于格的密码被认为是最具前景的抗量子密码研究方向。作为格密码的常用的两个主要困难问题之一，含错学习(LWE)问题被广泛用于密码算法的设计。为了提高格密码算法的性能，Zhang等人(2019)提出了非对称含错学习问题，该文将从理论上详细研究非对称含错学习问题和标准含错学习问题关系，并证明在特定错误分布下非对称含错学习问题和含错学习问题是多项式时间等价的，从而为基于非对称含错学习问题设计安全的格密码算法奠定了理论基础。
关键词:抗量子密码/
格密码/
含错学习问题
Abstract:Due to the advantages such as the worst-case hardness assumption, lattice-based cryptography is believed to the most promising research direction in post-quantum cryptography. As one of the two main hard problems commonly used in lattice-based cryptography, Learning With Errors (LWE) problem is widely used in constructing numerous cryptosystems. In order to improve the efficiency of lattice-based cryptosystems, Zhang et al. (2019) introduced the Asymmetric LWE (ALWE) problem. In this paper, the relation between the ALWE problem and the standard LWE problem is studied, and it shows that for certain error distributions the two problems are polynomially equivent, which paves the way for constructing secure lattice-based cryptosystems from the ALWE problem.
Key words:Post-qauntum cryptography/
Lattice-based cryptography/
Learning With Errors (LWE)
PDF全文下载地址:
https://jeit.ac.cn/article/exportPdf?id=9cfd52ca-b638-41a8-99bc-6c5303c3d6e4
