Microsoft Research - MSR Cryptography Talk Series: Quantum Lattice Enumeration in Limited Depth, Fernando Virdia
Fernando Veria's presentation at MSR delves into the challenges of quantum enumeration in the context of post-quantum cryptography. The main focus is on assessing the threat posed by quantum algorithms to new cryptographic standards, particularly those involving lattice-based cryptography. Veria discusses the limitations of current quantum algorithms, such as Grover's search, when constrained by maximum depth, which affects their efficiency in breaking cryptographic schemes like AES. He introduces a new quantum enumeration algorithm that considers these depth constraints and explores its implications on the security of cryptographic standards like Kyber. The talk highlights the difficulty in achieving a quadratic speedup with quantum enumeration due to these constraints and the need for further research to close existing gaps. Veria emphasizes the importance of understanding the distribution of nodes in enumeration trees and the potential impact of different pruning strategies on quantum enumeration efficiency.
Key Points:
- Quantum algorithms face significant challenges under depth constraints, impacting their ability to break cryptographic schemes efficiently.
- The new quantum enumeration algorithm considers depth constraints, offering insights into the security of lattice-based cryptography like Kyber.
- Current quantum speedups, such as Grover's, may not be as effective under practical constraints, necessitating further research.
- Understanding the distribution of nodes in enumeration trees is crucial for improving quantum enumeration strategies.
- Further exploration of pruning strategies and their impact on quantum enumeration could lead to more efficient algorithms.