Methods for solving equations with errors based on the HHL algorithm

doi:10.19682/j.cnki.1005-8885.2022.2015

中国邮电高校学报(英文) ›› 2022, Vol. 29 ›› Issue (4): 9-20.doi: 10.19682/j.cnki.1005-8885.2022.2015

Methods for solving equations with errors based on the HHL algorithm

Lv Lihui, Wang Hong, Ma Zhi, Duan Qianheng, Fei Yangyang, Meng Xiangdong

1. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China
2. Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China

收稿日期:2022-05-27 修回日期:2022-06-05 接受日期:2022-06-11 出版日期:2022-08-31 发布日期:2022-08-31
通讯作者: Wang Hong, E-mail: redwang@meac-skl.cn E-mail:redwang@meac-skl.cn
基金资助:
This work was supported by the National Key R&D Program of China (2021YFB3100100) and the National Natural Science
Foundation of China (61972413, 61901525).

Methods for solving equations with errors based on the HHL algorithm

Lv Lihui, Wang Hong, Ma Zhi, Duan Qianheng, Fei Yangyang, Meng Xiangdong

1. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China
2. Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China

Received:2022-05-27 Revised:2022-06-05 Accepted:2022-06-11 Online:2022-08-31 Published:2022-08-31
Contact: Wang Hong, E-mail: redwang@meac-skl.cn E-mail:redwang@meac-skl.cn
Supported by:
This work was supported by the National Key R&D Program of China (2021YFB3100100) and the National Natural Science
Foundation of China (61972413, 61901525).

摘要/Abstract

摘要： To solve polynomial systems, Harrow, Hassidim, and Lloyd (HHL) proposed a quantum algorithm called HHL algorithm. Based on the HHL algorithm, Chen et al. presented an algorithm, the solving the Boolean solutions of polynomial systems (PoSSoB) algorithm. Furthermore, Ding et al. introduced the Boolean Macaulay matrix and analyzed the lower bound on the condition number. Inspired by Ding et al. 's research, several related algorithms are proposed in this paper. First, the improved PoSSoB algorithm using the Boolean Macaulay matrix is proved to have lower complexity. Second, for solving equations with errors, a quantum algorithm for the max-polynomial system solving (Max-PoSSo) problem is proposed based on the improved PoSSoB algorithm. Besides, the Max-PoSSo algorithm is extended to the learning with errors (LWE) problem and its special case, the learning parity with noise (LPN) problem, providing a quantitative criterion, the condition number, for the security of these basic problems.

关键词: Harrow, Hassidim, and Lloyd, polynomial system solving, max-polynomial system solving, learning parity with noise, learning with errors

Abstract: To solve polynomial systems, Harrow, Hassidim, and Lloyd (HHL) proposed a quantum algorithm called HHL algorithm. Based on the HHL algorithm, Chen et al. presented an algorithm, the solving the Boolean solutions of polynomial systems (PoSSoB) algorithm. Furthermore, Ding et al. introduced the Boolean Macaulay matrix and analyzed the lower bound on the condition number. Inspired by Ding et al. 's research, several related algorithms are proposed in this paper. First, the improved PoSSoB algorithm using the Boolean Macaulay matrix is proved to have lower complexity. Second, for solving equations with errors, a quantum algorithm for the max-polynomial system solving (Max-PoSSo) problem is proposed based on the improved PoSSoB algorithm. Besides, the Max-PoSSo algorithm is extended to the learning with errors (LWE) problem and its special case, the learning parity with noise (LPN) problem, providing a quantitative criterion, the condition number, for the security of these basic problems.

Key words: Harrow, Hassidim, and Lloyd, polynomial system solving, max-polynomial system solving, learning parity with noise, learning with errors

中图分类号:

TP301.6

Lv Lihui, Wang Hong, Ma Zhi, Duan Qianheng, Fei Yangyang, Meng Xiangdong. Methods for solving equations with errors based on the HHL algorithm[J]. The Journal of China Universities of Posts and Telecommunications, 2022, 29(4): 9-20.

参考文献

References
[1] FAUGERE J C. A new efficient algorithm for computing Grobner bases (F4). Journal of Pure and Applied Algebra, 1999, 139(1/2/3): 61 -88.
[2] FAUGERE J C. A new efficient algorithm for computing Grobner bases without reduction to zero (F5). Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (ISSAC'02), 2002, Jul 7 -10, 2002, Lille, France. New York, NY, USA: ACM, 2002: 75 -83.
[3] GAO X S, HUANG Z Y. Characteristic set algorithms for equation solving in finite fields. Journal of Symbolic Computation, 2012, 47(6): 655 -679.
[4] GAO X S, VAN DER HOEVEN J, YUAN C M, et al. Characteristic set method for differential-difference polynomial
systems. Journal of Symbolic Computation, 2009, 44(9): 1137 -1163.
[5] BARD G V. Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis. Ph D Thesis. College Park, MD, USA: University of Maryland, 2007.

[6] BARD G V, COURTOIS N T, JEFFERSON C. Efficient methods for conversion and solution of sparse systems of low-degree multivariate polynomials over GF(2) via SAT-solvers. International Association for Cryptologic Research (IACR)
Cryptology ePrint Archive, Paper 2007/024, 2007.
[7] HARROW A W, HASSIDIM A, LLOYD S. Quantum algorithm for linear systems of equations. Physical Review Letters, 2009, 103(15): Article 150502.
[8] AMBAINIS A. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS'12), 2012, Feb 29 - Mar 3, Paris, France. Schloss Dagstuhl, Germany: Leibniz-Center for Informatics, 2012: 636 -647.
[9] CHILDS A M, KOTHARI R, SOMMA R D. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 2017, 46(6): 1920 -1950.
[10] CHEN Y A, GAO X S. Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems. Journal of Systems Science and Complexity, 2022, 35(1): 373 -412.
[11] DING J T, GHEORGHIU V, GILYEN A, et al. Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems. ArXiv Preprint, arXiv: 2111. 00405, 2021.
[12] HASTAD J. Satisfying degree-d equations over GF[2]n. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques: Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'11) and 15th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'11), 2011, Aug 17 - 19, Princeton, NJ, USA. LNTCS 6845. Berlin, Germany: Springer, 2011: 242 -253.
[13] ZHAO S W, GAO X S. Minimal achievable approximation ratio for MAX-MQ in finite fields. Theoretical Computer Science, 2009, 410(21/22/23): 2285 -2290.
[14] ALBRECHT M, CID C. Cold boot key recovery by solving polynomial systems with noise. Applied Cryptography and
Network Security: Proceedings of the 9th International Conference on Applied Cryptography and Network Security (ACNS'11), 2011, Jun 7 -10, Nerja (Malaga), Spain. LNSC 6715. Berlin, Germany: Springer, 2011: 57 -72.
[15] HUANG Z Y, LIN D D. A new method for solving polynomial systems with noise over F2 and its applications in cold boot key recovery. Selected Areas in Cryptography: Proceedings of the 19th Selected Areas in Cryptography (SAC'12), 2012, Aug 15 - 16, Windsor, Canada. LNSC 7707. Berlin, Germany: Springer, 2013: 16 -33.
[16] CHEN Y A, GAO X S, YUAN C M. Quantum algorithms for optimization and polynomial systems solving over finite fields. ArXiv Preprint, arXiv: 1802. 03856, 2018.
[17] BLUM A, KALAI A, WASSERMAN H. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 2003, 50(4): 506 -519.
[18] LEVIEIL E, FOUQUE P A. An improved LPN algorithm. Security and Cryptography for Networks: Proceedings of the 5th International Conference on Security and Cryptography for Networks (SCN'06), 2006, Sept 6 - 8, Maiori, Italy. LNSC
4116. Berlin, Germany: Springer, 2006: 348 -359.
[19] GUO Q, JOHANSSON T, LONDAHL C. Solving LPN using covering codes. Advances in Cryptology: Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'14): Part I, 2014, Dec 7 - 11, Kaoshiung, China. LNSC 8873. Berlin, Germany: Springer, 2014: 1 -20.
[20] BOGOS S, VAUDENAY S. Optimization of LPN solving algorithms. Advances in Cryptology: Proceedings of the 22nd
International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'16): Part I,
2016, Dec 4 - 8, Hanoi, Vietnam. LNCS 10031. Berlin, Germany: Springer, 2016: 703 -728.
[21] ZHANG B, GONG X X. New algorithms for solving LPN. International Association for Cryptologic Research (IACR)
Cryptology ePrint Archive, Paper 2007/780, 2017.
[22] MICCIANCIO D. Improving lattice based cryptosystems using the Hermite normal form. Cryptography and Lattices: Proceedings of the 2001 International Cryptography and Lattices Conference (CaLC'01), 2001, Mar 29 -30, Providence, RI, USA. LNCS 2146. Berlin, Germany: Springer, 2001: 126 -145.
[23] BERRY D W, AHOKAS G, CLEVE R, et al. Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 2007, 270(2): 359 -371.

Methods for solving equations with errors based on the HHL algorithm

Methods for solving equations with errors based on the HHL algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价

[1]	Zhang Jiangbo, Zheng Jiali, Quan Yixuan, Lin Zihan, Xie Xiaode. Improved sparrow search algorithm for RFID network planning[J]. 中国邮电高校学报(英文版), 2023, 30(1): 93-102.
[2]	谢孝德郑嘉利林子涵何思怡冯敏瑜. Random mating mayfly algorithm for RFID network planning[J]. 中国邮电高校学报(英文版), 2022, 29(5): 40-50.
[3]	林子涵郑嘉利谢孝德冯敏瑜何思怡. RFID network planning based on improved brain storm optimization algorithm[J]. 中国邮电高校学报(英文版), 2022, 29(5): 30-39.
[4]	Quan Yixuan, Zheng Jiali, Xie Xiaode, Lin Zihan, Luo Wencong. Hybrid gray wolf optimization-cuckoo search algorithm for RFID network planning [J]. 中国邮电高校学报(英文版), 2021, 28(6): 91-102.
[5]	李丽, 郑嘉利, 全艺璇, 林子涵, 李映超, 黄天星. RFID Indoor positioning based on Semi-supervised Actor-Critic Co-training[J]. 中国邮电高校学报(英文版), 2020, 27(5): 69-81.
[6]	Lü Chaohui, Pan Jiaying. Extraction technique of region of interest from stereoscopic video[J]. 中国邮电高校学报(英文版), 2017, 24(5): 68-76.
[7]	Ren Xingyi, Song Meina, E Haihong, Song Junde. Social media mining and visualization for point-of-interest recommendation[J]. 中国邮电高校学报(英文版), 2017, 24(1): 67-76.
[8]	张小红胡应梦. RFID mutual-authentication protocol with synchronous updated-keys based on Hash function[J]. Acta Metallurgica Sinica(English letters), 2015, 22(6): 27-35.