Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems

DOI10.1007/s11424-020-0028-6zbMath1483.68137arXiv1712.06239OpenAlexW2949352214MaRDI QIDQ2121215

Yu-Ao Chen, Xiao-Shan Gao

Publication date: 1 April 2022

Published in: Journal of Systems Science and Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1712.06239

zbMATH Keywords

condition numberquantum algorithmpolynomial system solvingHHL algorithmblock cipher AESBoolean equation solvinghash function SHA-3/KeccakMPKCstream cipher Trivum

Mathematics Subject Classification ID

Cryptography (94A60) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum cryptography (quantum-theoretic aspects) (81P94)

Related Items (2)

A polynomial system for bit-based division property solving by quantum algorithm ⋮ Quantum algorithm design: techniques and applications

Uses Software

• Trivium
• Keccak

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean functions and their applications in cryptography
• Characteristic set algorithms for equation solving in finite fields
• Old and new results on algebraic connectivity of graphs
• Efficient quantum algorithms for simulating sparse Hamiltonians
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Non-full Sbox linearization: applications to collision attacks on round-reduced \textsc{keccak}
• On the complexity of solving quadratic Boolean systems
• Solving binary \(\mathcal {MQ}\) with Grover's algorithm
• Solving multivariate polynomial systems and an invariant from commutative algebra
• Multivariate public key cryptosystems
• Applying Grover’s Algorithm to AES: Quantum Resource Estimates
• Trivium
• Adiabatic quantum state generation and statistical zero knowledge
• Eigenvalues of the Laplacian of a graph^∗
• Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
• Conditional Cube Attack on Reduced-Round Keccak Sponge Function

This page was built for publication: Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems