Journal Home > Volume 27 , Issue 4
Tsinghua Science and Technology 2022, 27(4): 751-759 https://doi.org/10.26599/TST.2021.9010022
Open Access | Issue | Published: 09 December 2021

New Advanced Computing Architecture for Cryptography Design and Analysis by D-Wave Quantum Annealer

Show Author's Information Xiangmin Ji,  Baonan Wang( ),  Feng Hu,  Chao Wang,  Huanguo Zhang
College of Computer Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China
College of Computer Science and Technology, Shanghai University of Electric Power, Shanghai 200090, China
Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai University, Shanghai 200444, China
Key laboratory of Specialty Fiber Optics and Optical Access Networks, Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai University, Shanghai 200444, China
School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, China
State Key Laboratory of Cryptology, Beijing 100878, China
Center for Quantum Computing, Peng Cheng Laboratory, Shenzhen 518000, China
Keywords:
Quantum Annealing (QA), factorization, Boolean functions, brain-inspired cognition
Cite this article:
Ji X, Wang B, Hu F, et al. New Advanced Computing Architecture for Cryptography Design and Analysis by D-Wave Quantum Annealer. Tsinghua Science and Technology, 2022, 27(4): 751-759. https://doi.org/10.26599/TST.2021.9010022
Download citation
EndNote(RIS)
BibTeX

652

Views

83

Downloads

Citations

5

Crossref

3

WoS

5

Scopus

0

CSCD

Abstract Full text About this article

Universal quantum computers are far from achieving practical applications. The D-Wave quantum computer is initially designed for combinatorial optimizations. Therefore, exploring the potential applications of the D-Wave device in the field of cryptography is of great importance. First, although we optimize the general quantum Hamiltonian on the basis of the structure of the multiplication table (factor up to 1 005 973), this study attempts to explore the simplification of Hamiltonian derived from the binary structure of the integers to be factored. A simple factorization on 143 with four qubits is provided to verify the potential of further advancing the integer-factoring ability of the D-Wave device. Second, by using the quantum computing cryptography based on the D-Wave 2000Q system, this research further constructs a simple version of quantum-classical computing architecture and a Quantum-Inspired Simulated Annealing (QISA) framework. Good functions and a high-performance platform are introduced, and additional balanced Boolean functions with high nonlinearity and optimal algebraic immunity can be found. Further comparison between QISA and Quantum Annealing (QA) on six-variable bent functions not only shows the potential speedup of QA, but also suggests the potential of architecture to be a scalable way of D-Wave annealer toward a practical cryptography design.


menu
Abstract
Full text
Outline
About this article

New Advanced Computing Architecture for Cryptography Design and Analysis by D-Wave Quantum Annealer

Show Author's information Xiangmin Ji, Baonan Wang( ), Feng Hu, Chao Wang, Huanguo Zhang
College of Computer Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China
College of Computer Science and Technology, Shanghai University of Electric Power, Shanghai 200090, China
Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai University, Shanghai 200444, China
Key laboratory of Specialty Fiber Optics and Optical Access Networks, Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai University, Shanghai 200444, China
School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, China
State Key Laboratory of Cryptology, Beijing 100878, China
Center for Quantum Computing, Peng Cheng Laboratory, Shenzhen 518000, China

Abstract

Universal quantum computers are far from achieving practical applications. The D-Wave quantum computer is initially designed for combinatorial optimizations. Therefore, exploring the potential applications of the D-Wave device in the field of cryptography is of great importance. First, although we optimize the general quantum Hamiltonian on the basis of the structure of the multiplication table (factor up to 1 005 973), this study attempts to explore the simplification of Hamiltonian derived from the binary structure of the integers to be factored. A simple factorization on 143 with four qubits is provided to verify the potential of further advancing the integer-factoring ability of the D-Wave device. Second, by using the quantum computing cryptography based on the D-Wave 2000Q system, this research further constructs a simple version of quantum-classical computing architecture and a Quantum-Inspired Simulated Annealing (QISA) framework. Good functions and a high-performance platform are introduced, and additional balanced Boolean functions with high nonlinearity and optimal algebraic immunity can be found. Further comparison between QISA and Quantum Annealing (QA) on six-variable bent functions not only shows the potential speedup of QA, but also suggests the potential of architecture to be a scalable way of D-Wave annealer toward a practical cryptography design.

Keywords: Quantum Annealing (QA), factorization, Boolean functions, brain-inspired cognition

References(37)

[1]
K. R. Brown, Quantum technologies and the National Quantum Initiative, Quantum Engineering, vol. 1, no. 1, p. e7, 2019.
DOI Google Scholar
[2]
J. Mlynek, The European quantum technology flagship: Paving the way for the second quantum revolution, Quantum Engineering, vol. 1, no. 1, p. e5, 2019.
DOI Google Scholar
[3]
C. Wang and H. G. Zhang, Impact of commercial quantum computer on cryptography, (in Chinese), Information Security and Communications Privacy, no. 2, pp. 31-32&35, 2012.
Google Scholar
[4]
A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik, Finding low-energy conformations of lattice protein models by quantum annealing, Scientific Reports, vol. 2, p. 571, 2012.
DOI Google Scholar
[5]
R. Martonák, G. E. Santoro, and E. Tosatti, Quantum annealing of the traveling-salesman problem, Phys. Rev. E, vol. 70, no. 5, p. 057701, 2004.
DOI Google Scholar
[6]
A. Cho, DOE pushes for useful quantum computing, Science, vol. 359, no. 6372, pp. 141-142, 2018.
DOI Google Scholar
[7]
J. Brainard, What’s coming up in 2018, Science, vol. 359, no. 6371, pp. 10-12, 2018.
DOI Google Scholar
[8]
E. Gibney, Physics: Quantum computer quest, Nature, vol. 516, no. 7529, pp. 24-26, 2014.
DOI Google Scholar
[9]
B. N. Wang, F. Hu, H. N. Yao, and C. Wang, Prime factorization algorithm based on parameter optimization of Ising model, Scientific Reports, vol. 10, p. 7106, 2020.
DOI Google Scholar
[10]
H. Neven, V. S. Denchev, M. Drew-Brook, J. Y. Zhang, W. G. Macready, and G. Rose, NIPS 2009 demonstration: Binary classification using hardware implementation of quantum annealing, Quantum, https://www.mendeley.com/catalogue/1a199e97-f0c3-35c1-ae5f-db23280f06a9/, 2009.
[11]
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science, vol. 292, no. 5516, pp. 472-475, 2001.
DOI Google Scholar
[12]
B. N. Wang, F. Hu, and C. Wang, Optimization of quantum computing models inspired by D-Wave quantum annealing, Tsinghua Science and Technology, vol. 25, no. 4, pp. 508-515, 2020.
DOI Google Scholar
[13]
N. Wang, G. G. Guo, B. N. Wang, and C. Wang, Traffic clustering algorithm of urban data brain based on a hybrid-augmented architecture of quantum annealing and brain-inspired cognitive computing, Tsinghua Science and Technology, vol. 25, no. 6, pp. 813-825, 2020.
DOI Google Scholar
[14]
M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, et al., Quantum annealing with manufactured spins, Nature, vol. 473, no. 7346, pp. 194-198, 2011.
DOI Google Scholar
[15]
O. Titiloye and A. Crispin, Quantum annealing of the graph coloring problem, Discrete Optimization, vol. 8, no. 2, pp. 376-384, 2011.
DOI Google Scholar
[16]
F. Neukart, G. Compostella, C. Seidel, D. von Dollen, S. Yarkoni, and B. Parney, Traffic flow optimization using a quantum annealer, Frontiers in ICT, vol. 4, p. 29, 2017.
DOI Google Scholar
[17]
W. C. Peng, B. N. Wang, F. Hu, Y. J. Wang, X. J. Fang, X. Y. Chen, and C. Wang, Factoring larger integers with fewer qubits via quantum annealing with optimized parameters, Sci. China Phys. Mech. Astron., vol. 62, no. 6, p. 60311, 2019.
DOI Google Scholar
[18]
X. M. Wang, Quest towards “factoring larger integers with commercial D-Wave quantum annealing machines”, Sci. China Phys. Mech. Astron., vol. 62, no. 6, p. 960331, 2019.
DOI Google Scholar
[19]
A. D. King, J. Carrasquilla, J. Raymond, I. Ozfidan, E. Andriyash, A. Berkley, M. Reis, T. Lanting, R. Harris, F. Altomare, et al., Observation of topological phenomena in a programmable lattice of 1800 qubits, Nature, vol. 560, no. 7719, pp. 456-460, 2018.
DOI Google Scholar
[20]
R. Harris, Y. Sato, A. J. Berkley, M. Reis, F. Altomare, M. H. Amin, K. Boothby, P. Bunyk, C. Deng, C. Enderud, et al., Phase transitions in a programmable quantum spin glass simulator, Science, vol. 361, no. 6398, pp. 162-165, 2018.
DOI Google Scholar
[21]
S. X. Jiang, K. A. Britt, A. J. McCaskey, T. S. Humble, and S. Kais, Quantum annealing for prime factorization, Scientific Reports, vol. 8, p. 17667, 2018.
DOI Google Scholar
[22]
B. N. Wang, F. Hu, H. G. Zhang, and C. Wang, From evolutionary cryptography to quantum artificial intelligent cryptography, (in Chinese), Journal of Computer Research and Development, vol. 56, no. 10, pp. 2112-2134, 2019.
Google Scholar
[23]
M. R. Geller and Z. Y. Zhou, Factoring 51 and 85 with 8 qubits, Scientific Reports, vol. 3, p. 3023, 2013.
DOI Google Scholar
[24]
X. H. Peng, Z. Y. Liao, N. Y. Xu, G. Qin, X. Y. Zhou, D. Suter, and J. F. Du, Quantum adiabatic algorithm for factorization and its experimental implementation, Phys. Rev. Lett., vol. 101, no. 22, p. 220405, 2008.
DOI Google Scholar
[25]
J. H. Chen, C. H. Tan, and X. Y. Li, Practical cryptanalysis of a public key cryptosystem based on the Morphism of polynomials problem, Tsinghua Science and Technology, vol. 23, no. 6, pp. 671-679, 2018.
DOI Google Scholar
[26]
C. Wang, F. Hu, H. G. Zhang, and J. Wu, Evolutionary cryptography theory-based generating method for secure ECs, Tsinghua Science and Technology, vol. 22, no. 5, pp. 499-510, 2017.
DOI Google Scholar
[27]
H. Z. Wang, H. G. Zhang, S. W. Mao, W. Q. Wu, and L. Q. Zhang, New public-key cryptosystem based on the morphism of polynomials problem, Tsinghua Science and Technology, vol. 21, no. 3, pp. 302-311, 2016.
DOI Google Scholar
[28]
D. Połap and M. Woźniak, Voice recognition by neuro-heuristic method, Tsinghua Science and Technology, vol. 24, no. 1, pp. 9-17, 2019.
DOI Google Scholar
[29]
D. J. Bernstein, Introduction to post-quantum cryptography, in Post-Quantum Cryptography, D. J. Bernstein, J. Buchmann, and E. Dahmen, eds. Berlin, Germany: Springer, 2009, pp. 1-14.
DOI
[30]
F. Hu, L. Lamata, M. Sanz, X. Chen, X. Y. Chen, C. Wang, and E. Solano, Quantum computing cryptography: Finding cryptographic Boolean functions with quantum annealing by a 2000 qubit D-Wave quantum computer, arXiv preprint arXiv: 1806.08706, 2020.
DOI Google Scholar
[31]
F. Hu, L. Lamata, M. Sanz, X. Chen, X. Y. Chen, C. Wang, and E. Solano, Quantum computing cryptography: Finding cryptographic Boolean functions with quantum annealing by a 2000 qubit D-Wave quantum computer, Physics Letters A, vol. 384, p. 126214, 2020.
DOI Google Scholar
[32]
A. K. Lenstra, H. W. Lenstra, M. S. Manasse, and J. M. Pollard, The number field sieve, in Proc. 22nd Annu. ACM Symp. Theory of Computing, Baltimore, MD, USA, 1990, pp. 564-572.
DOI
[33]
C. Gidney, Factoring with n+2 clean qubits and n-1 dirty qubits, arXiv preprint arXiv: 1706.07884v2, 2018.
Google Scholar
[34]
C. Wang, Y. J. Wang, and F. Hu, Shaping the future of commercial quantum computer and the challenge for information security, (in Chinese), Chinese Journal of Network and Information Security, vol. 2, no. 3, pp. 17-27, 2016.
Google Scholar
[35]
H. P. Liu, D. Guo, F. C. Sun, W. Q. Yang, S. Furber, and T. C. Sun, Embodied tactile perception and learning, Brain Science Advances, vol. 6, no. 2, pp.132-158, 2020.
DOI Google Scholar
[36]
D. Tang, Recent progress in (fast) algebraic immunity of Boolean functions, (in Chinese), Journal of Cryptologic Research, vol. 4, no. 3, pp. 262-272, 2017.
Google Scholar
[37]
W. G. Zhang and E. Pasalic, Constructions of resilient S-boxes with strictly almost optimal nonlinearity through disjoint linear codes, IEEE Transactions on Information Theory, vol. 60, no. 3, pp. 1638-1651, 2014.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 20 February 2021
Accepted: 12 March 2021
Published: 09 December 2021
Issue date: August 2022

Copyright

© The author(s) 2022

Acknowledgements

This study was supported by the Special Zone Project of National Defense Innovation, the National Natural Science Foundation of China (Nos. 61572304 and 61272096), the Key Program of the National Natural Science Foundation of China (No. 61332019), the Shanghai Sailing Plan of "Science and Technology Innovation Action Plan" (No. 21YF1415100), Fujian Provincial Natural Science Foundation Project (No. 2021J01129), and Open Research Fund of State Key Laboratory of Cryptology.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return