基于列表译码方法在查询访问模型下含错学习问题的分析

王明强; 庄金成

doi:10.11999/JEIT190624

基于列表译码方法在查询访问模型下含错学习问题的分析

doi: 10.11999/JEIT190624

王明强^{1, 2},
庄金成^{1, 3, ,}

1.
山东大学密码技术与信息安全教育部重点实验室青岛 266237
2.
山东大学数学学院济南 250100
3.
山东大学网络空间安全学院青岛 266237

基金项目: 国家自然科学基金(61672019)

详细信息

作者简介:
王明强：男，1970年生，教授，研究方向为算法数论和公钥密码学

庄金成：男，1987年生，教授，研究方向为算法数论和公钥密码学

通讯作者:
庄金成　jzhuang@sdu.edu.cn

中图分类号: TN918; TP309
计量
- 文章访问数: 1694
- HTML全文浏览量: 872
- PDF下载量: 70
- 被引次数: 0
出版历程
- 收稿日期: 2019-08-14
- 修回日期: 2019-12-05
- 网络出版日期: 2019-12-09
- 刊出日期: 2020-02-19

Analysis of Learning With Errors in Query Access Model: A List Decoding Approach

Mingqiang WANG^{1, 2},
Jincheng ZHUANG^{1, 3
, ,}

1.
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education Shandong University, Qingdao 266237, China
2.
School of Mathematics, Shandong University, Jinan 250100, China
3.
School of Cyber Science and Technology, Shandong University, Qingdao 266237, China

Funds: The National Natural Science Foundation of China (61672019)

摘要

摘要: Regev在2005年提出了含错学习问题(LWE)，这个问题与随机线性码的译码问题密切相关，并且在密码学特别是后量子密码学中应用广泛。原始的含错学习问题是在随机访问模型下提出的，有证据证明该问题的困难性。许多研究者注意到的一个事实是当攻击者可以选择样本时，该问题是容易的。但是目前据作者所知并没有一个完整的求解算法。该文分析了查询访问模型下的带有错误学习问题，给出了完整的求解算法。分析采用的工具是将该问题联系到隐藏数问题，然后应用傅里叶学习算法进行列表译码。
- 含错学习问题 /
- 查询访问模型 /
- 隐藏数问题 /
- 傅里叶学习 /
- 列表译码
Abstract: Regev introduced the Learning With Errors (LWE) problem in 2005, which has close connections to random linear code decoding and has found wide applications to cryptography, especially to post-quantum cryptography. The LWE problem is originally introduced in random access model, and there are evidences that indicate the hardness of this problem. It is well known that the LWE problem is vulnerable if the attacker is allowed to choose samples. However, to the best of the author’s knowledge, a complete algorithm has not been published. In this paper, the LWE problem in query samples access model is analyzed. The technique is to relate the problem to the hidden number problem, and then Fourier learning method is applied to the list decoding.
- Learning With Errors (LWE) problem /
- Query access model /
- Hidden number problem /
- Fourier learning /
- List decoding

HTML全文

参考文献(12)

KEARNS M J and VAZIRANI U V. An Introduction to Computational Learning Theory[M]. Cambridge, London England: The MIT Press, 1994.

BLUM A, KALAI A, and WASSERMAN H. Noise-tolerant learning, the parity problem, and the statistical query model[J]. Journal of the ACM, 2003, 50(4): 506–519. doi: 10.1145/792538.792543

PIETRZAK K. Cryptography from learning parity with noise[C]. The 38th International Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, 2012: 99–114.

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.

BONEH D and VENKATESAN R. Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[C]. The 16th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 1996: 129–142.

GALBRAITH S D and SHANI B. The multivariate hidden number problem[C]. The 8th International Conference on Information Theoretic Security, Lugano, Switzerland, 2015: 250–268.

GOLDREICH O and LEVIN L A. A hard-core predicate for all one-way functions[C]. The 21st Annual ACM Symposium on Theory of Computing, Seattle, USA, 1989: 25–32.

KUSHILEVITZ E and MANSOUR Y. Learning decision trees using the Fourier spectrum[C]. The 23rd Annual ACM Symposium on Theory of Computing, New Orleans, USA, 1991: 455–464.

AKAVIA A, GOLDWASSER S, and SAFRA S. Proving hard-core predicates using list decoding[C]. The 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, USA, 2003: 146–157.

GALBRAITH S D, LAITY J, and SHANI B. Finding significant Fourier coefficients: Clarifications, simplifications, applications and limitations[J]. Chicago Journal of Theoretical Computer Science, 2018, 6: 1–38.

AKAVIA A. Solving hidden number problem with one bit oracle and advice[C]. The 29th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2009: 337–354.

MICCIANCIO D and MOL P. Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions[C]. The 31st Annual Conference on Advances in Cryptology, Santa Barbara, USA, 2011: 465–484.

施引文献

资源附件(0)

访问统计