A more efficient implementation of Shor's algorithm
16 hours ago
- #Cryptography
- #Quantum Computing
- #Shor's Algorithm
- A new paper improves Shor's algorithm efficiency by reducing memory needed for 256-bit elliptic-curve cryptography attacks by a factor of 20, though it remains impractical on current quantum computers.
- Researchers used a zero-knowledge proof (via SP1 and STARKs) to demonstrate knowledge of an optimized quantum circuit without revealing details, citing security concerns like Bitcoin blockchain attacks.
- The circuit requires fewer than 1,200 logical qubits and 90 million gates, translating to ~500,000 physical qubits—far beyond IBM's Condor with 1,121 qubits, highlighting scalability challenges.
- Verification involved compressing proofs from STARK to SNARK (Groth16), relying on a secure multi-party computation for randomness, resulting in a 1.7MB proof file verified in under 14 minutes on a laptop.
- The approach raises concerns about open mathematics, as withheld details limit scientific collaboration and integration with other advances, such as potential qubit reduction techniques.
- Adopting post-quantum cryptography is urged, as practical quantum computers remain distant, and this work obscures the timeline for their availability.