高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

张江 范淑琴

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

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

doi: 10.11999/JEIT190685
基金项目: 国家重点研发计划(2017YFB0802005, 2018YFB0804105),国家自然科学基金(61602046, 61932019),中国科协“青年人才托举工程”(2016QNRC001)
详细信息
    作者简介:

    张江:男,1986年生,副研究员,主要研究方向为基于格的密码协议及其可证明安全

    范淑琴:女,1978年生,教授,主要研究方向为基于格的密码分析

    通讯作者:

    张江 jiangzhang09@gmail.com

  • 中图分类号: TN918, TP309.7

On the Hardness of the Asymmetric Learning With Errors Problem

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)提出了非对称含错学习问题,该文将从理论上详细研究非对称含错学习问题和标准含错学习问题关系,并证明在特定错误分布下非对称含错学习问题和含错学习问题是多项式时间等价的,从而为基于非对称含错学习问题设计安全的格密码算法奠定了理论基础。
  • 图  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
    NSA. National Security Agency. Cryptography today[EB/OL]. https://www.nsa.gov/ia/programs/suiteb_cryptography/, 2015.
    NIST. Post-quantum cryptography standardization[EB/OL]. http://csrc.nist.gov/groups/ST/post-quantum-crypto/submission-requirements/index.html, 2016.
    中国科学技术学会. 科普时报: 中国科协发布12个领域60大科技难题[EB/OL]. http://www.cast.org.cn/art/2018/6/22/art_90_77662.html, 2018.
    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.
    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.
    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.
    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.
    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.
    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)
计量
  • 文章访问数:  1106
  • HTML全文浏览量:  465
  • PDF下载量:  57
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-09-14
  • 修回日期:  2019-11-20
  • 网络出版日期:  2019-11-29
  • 刊出日期:  2020-02-19

目录

    /

    返回文章
    返回

    官方微信,欢迎关注