A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function

DOI10.1007/s11128-019-2175-zzbMath1417.81104MaRDI QIDQ669952

WanQing Wu, Huanguo Zhang

Publication date: 15 March 2019

Published in: Quantum Information Processing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11128-019-2175-z

zbMATH Keywords

degree; quantum algorithm; perfect nonlinear Boolean function

Mathematics Subject Classification ID

81P68: Quantum computation

94A60: Cryptography

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

06B30: Topological lattices

68Q12: Quantum algorithms and complexity in the theory of computing

81P94: Quantum cryptography (quantum-theoretic aspects)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How low can approximate degree and quantum query complexity be for total Boolean functions?
• On the power of Ambainis lower bounds
• Boolean function complexity. Advances and frontiers.
• Quantum algorithm to solve function inversion with time-space trade-off
• Complexity measures and decision tree complexity: a survey.
• Quantum walk public-key cryptographic system
• Construction of Boolean functions with excellent cryptographic criteria using bivariate polynomial representation
• Non-Linear Approximations in Linear Cryptanalysis
• Strengths and Weaknesses of Quantum Computing
• Separations in Query Complexity Based on Pointer Functions
• Quantum gates on hybrid qudits
• SQUARE attack on block ciphers with low algebraic degree
• Quantum lower bounds by polynomials
• A Framework for Chosen IV Statistical Analysis of Stream Ciphers
• Quantum Query Complexity of State Conversion