关于非对称含错学习问题的困难性研究

张江; 范淑琴

doi:10.11999/JEIT190685

引用本文: 张江, 范淑琴. 关于非对称含错学习问题的困难性研究[J]. 电子与信息学报, 2020, 42(2): 327-332. doi: 10.11999/JEIT190685 shu

Citation: Jiang ZHANG, Shuqin FAN. On the Hardness of the Asymmetric Learning With Errors Problem[J]. Journal of Electronics and Information Technology, 2020, 42(2): 327-332. doi: 10.11999/JEIT190685 shu

关于非对称含错学习问题的困难性研究

张江 ^,
, 范淑琴

密码科学技术国家重点实验室北京 100878

作者简介: 张江: 男，1986年生，副研究员，主要研究方向为基于格的密码协议及其可证明安全;
范淑琴: 女，1978年生，教授，主要研究方向为基于格的密码分析

通讯作者: 张江,jiangzhang09@gmail.com

基金项目: 国家重点研发计划(2017YFB0802005, 2018YFB0804105)，国家自然科学基金(61602046, 61932019)，中国科协“青年人才托举工程”(2016QNRC001)

摘要: 由于基于最坏情况困难假设等优点，基于格的密码被认为是最具前景的抗量子密码研究方向。作为格密码的常用的两个主要困难问题之一，含错学习(LWE)问题被广泛用于密码算法的设计。为了提高格密码算法的性能，Zhang等人(2019)提出了非对称含错学习问题，该文将从理论上详细研究非对称含错学习问题和标准含错学习问题关系，并证明在特定错误分布下非对称含错学习问题和含错学习问题是多项式时间等价的，从而为基于非对称含错学习问题设计安全的格密码算法奠定了理论基础。

关键词:

English

On the Hardness of the Asymmetric Learning With Errors Problem

Jiang ZHANG ^,
, Shuqin FAN

State Key Laboratory of Cryptology, Beijing 100878, China

Corresponding author: Jiang ZHANG,jiangzhang09@gmail.com

Received Date: 2019-09-14
Accepted Date: 2019-11-20
Available Online: 2020-02-01
Fund Project: The National Key Research and Development Program of China (2017YFB0802005, 2018YFB0804105), The National Natural Science Foundation of China (61602046, 61932019), and the Young Elite Scientists Sponsorship Program by China Association for Science and Technology (2016QNRC001)

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:

1. [1]
  SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484–1509. doi: 10.1137/S0097539795293172
2. [2]
  NSA. National Security Agency. Cryptography today[EB/OL]. https://www.nsa.gov/ia/programs/suiteb_cryptography/, 2015.
3. [3]
  NIST. Post-quantum cryptography standardization[EB/OL]. http://csrc.nist.gov/groups/ST/post-quantum-crypto/submission-requirements/index.html, 2016.
4. [4]
  中国科学技术学会. 科普时报: 中国科协发布12个领域60大科技难题[EB/OL]. http://www.cast.org.cn/art/2018/6/22/art_90_77662.html, 2018.
5. [5]
  REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. The 37th Annual ACM Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93.
6. [6]
  AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA,1996: 99–108.
7. [7]
  ZHANG Jiang, YU Yu, FAN Shuqin, et al. Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes[R]. Cryptology ePrint Archive 2019/510, 2019.
8. [8]
  APPLEBAUM B, CASH D, PEIKERT C, et al. Fast cryptographic primitives and circular-secure encryption based on hard learning problems[C]. The 29th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2009: 595–618.
9. [9]
  MICCIANCIO D and REGEV O. Worst-case to average-case reductions based on Gaussian measures[C]. The 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004: 372–381.
10. [10]
  PEIKERT C. An efficient and parallel Gaussian sampler for lattices[C]. The 30th Annual Conference on Advances in Cryptology, Santa Barbara, USA, 2010: 80–97.
1. [1]
  王明强, 庄金成. 基于列表译码方法在查询访问模型下含错学习问题的分析. 电子与信息学报, 2020, 42(2): 322-326.
2. [2]
  陈虎, 胡予濮. NTRU格上无证书加密. 电子与信息学报, 2016, 38(2): 347-353.
3. [3]
  江明明, 郭宇燕, 余磊, 宋万干, 魏仕民. 有效的标准模型下格上基于身份的代理重加密. 电子与信息学报, 2019, 41(1): 61-66.
4. [4]
  李峥, 马智, 吕欣, 冯登国. 基于量子CSS纠错码的量子公钥密码和消息认证. 电子与信息学报, 2006, 28(3): 537-541.
5. [5]
  眭晗, 吴文玲. 后量子对称密码的研究现状与发展趋势. 电子与信息学报, 2020, 42(2): 287-294.
6. [6]
  付向群, 鲍皖苏, 史建红, 李发达. 基于多离散对数问题的公钥密码. 电子与信息学报, 2014, 36(6): 1423-1427.
7. [7]
  欧庆于, 罗芳, 叶伟伟, 周学广. 分组密码算法抗故障攻击能力度量方法研究. 电子与信息学报, 2017, 39(5): 1266-1270.
8. [8]
  姜正涛, 柳毅, 王育民. 基于LFSR高次剩余问题构造公钥密码体制的研究. 电子与信息学报, 2006, 28(3): 542-545.
9. [9]
  倪博煜, 董晓阳. 改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用. 电子与信息学报, 2020, 42(2): 295-306.
10. [10]
  唐学海, 李超, 谢端强. CLEFIA密码的Square攻击. 电子与信息学报, 2009, 31(9): 2260-2263.
11. [11]
  李大兴, 李大为. 关于实多项式型公钥密码体制的破译和有关问题的探讨. 电子与信息学报, 1994, 16(3): 284-289.
12. [12]
  王美一, 唐学海, 李超, 屈龙江. 3D密码的Square攻击. 电子与信息学报, 2010, 32(1): 157-161.
13. [13]
  李大兴, 李大为. 密码分析的连分数策略. 电子与信息学报, 1992, 14(2): 113-119.
14. [14]
  胡斌, 金晨辉, 冯春海. Plateaued函数的密码学性质. 电子与信息学报, 2008, 30(3): 660-664.
15. [15]
  孙林红, 叶顶锋, 吕述望, 冯登国. 序列密码的复合攻击法. 电子与信息学报, 2004, 26(1): 72-76.
16. [16]
  王保仓, 韦永壮, 胡予濮. 基于随机背包的公钥密码. 电子与信息学报, 2010, 32(7): 1580-1584.
17. [17]
  多磊, 李超. Rijndael密码的逆序Square攻击. 电子与信息学报, 2004, 26(1): 65-71.
18. [18]
  赵军, 曾学文, 郭志川. 支持国产密码算法的高速PCIe密码卡的设计与实现. 电子与信息学报, 2019, 41(10): 2402-2408.
19. [19]
  吕述望, 张如文. 一类Feistel密码的线性分析. 电子与信息学报, 2003, 25(9): 1237-1242.
20. [20]
  曹珍富. Z[]环上的两类密码体制. 电子与信息学报, 1992, 14(3): 286-290.
图 1 高斯分布和二项分布

下载: 全尺寸图片幻灯片