By Jay Liu postat 18 oktober 2022
Det är en allmän uppfattning att kvantdatorer inte kommer att kunna orsaka någon allvarlig skada på våra säkerhetssystem på minst 15 år. Det är då fullskaliga, feltoleranta kvantdatorer förväntas vara tillgängliga och kunna köra Shors algoritm för att knäcka RSA inom rimlig tid. Tja, verkligheten är mycket mörkare: verkliga kvantsäkerhetshot är mycket mer omedelbara, troligen inom fem år.
Du kanske frågar: "Verkligen? Hur så?"
Dessa kortsiktiga säkerhetshot kommer från heuristiska algoritmer som körs på felbenägna kvantenheter från NISQ-eran vi redan befinner oss i idag.
Med Shors algoritm kräver faktorisering av ett 2048-bitars RSA-nummer 100,000 10 feltoleranta qubits som körs i 20 dagar, eller 8M NISQ qubits i XNUMX timmar. Eftersom vi inte kommer att ha så storskaliga kvantdatorer på minst ett decennium kan vi känna att vi har mycket tid till hands för att förbereda oss.
Men med dagens NISQ-enheter har vi på Zapata Computing kommit fram till en heuristisk algoritm som heter Variationell Quantum Factoring (VQF, patenterad), som vi uppskattar kan faktorisera ett 2048-bitars RSA-nummer med ungefär 6,000 XNUMX NISQ qubits inom en timme. Baserat på publicerade produktfärdplaner från ledande kvantdatorföretag, förväntas NISQ kvantdatorer i denna skala vara tillgängliga inom fem år.
Tänk på det. Kvantsäkerhetshotet är mycket mer omedelbart än vad de flesta inser.
Tja, du kanske undrar, "Vad är en heuristisk algoritm, och varför är den i det här fallet så mycket kraftfullare än Shors algoritm när det gäller att bryta ett RSA-nummer?"
Datorkomplexitetspionjären och Turingpristagaren, Stephen Cook, definierar det väl:
"En heuristisk algoritm är en som är utformad för att lösa ett problem på ett snabbare och mer effektivt sätt än traditionella metoder genom att offra optimalitet, noggrannhet, precision eller fullständighet för hastighet."
Med andra ord, en heuristisk algoritm är inte matematiskt komplett eller bevisad i teorin, men den fungerar i praktiken. Ett välkänt exempel på en heuristisk algoritm är neurala nätverk, som har visat sig vara extremt effektiva i applikationer som ansiktsigenkänning, trots att det inte finns några matematiska bevis för att det borde fungera. Dessutom blir det mer exakt och kraftfullare när bättre konvolutionella neurala nätverk utformas.
Vår VQF-algoritm är ett annat exempel. Till skillnad från Shors algoritm är det en hybridalgoritm som använder både kvantdatorer och klassiska datorer. Specifikt mappar den factoringproblemet till ett kombinatoriskt optimeringsproblem, använder klassiska datorer för förbearbetning och använder den välkända kvantapproximativa optimeringsalgoritmen (QAOA). Detta tillvägagångssätt har avsevärt minskat antalet qubits som krävs för att faktorisera ett stort antal.
NISQ-hotet är mycket närmare sikt än PQC-hotet
Medan de flesta ansträngningar inom akademin, standardorgan och säkerhetsföretag är inriktade på att mildra säkerhetshot från eran Post-Quantum Cryptography (PQC) ett decennium eller mer på vägen med förväntade hot från Shors algoritmer som körs i fullskalig, feltolerant kvantum. datorer har VQF-algoritmen avslöjat genomförbarheten av kortsiktiga säkerhetshot från heuristiska algoritmer som körs på kvantdatorer i den NISQ-era vi redan befinner oss i idag.
Vi har tittat noga på denna fråga och pratat med stora företag, regeringar och organisationer. Det här är den typ av cybersäkerhetshot som de är mest oroade över.
Med vår djupa bänk av kvantforskare och vår Orquestra® mjukvaruplattform körs på kvantdatorer har vi utvecklat en uppsättning verktyg och tjänster för att hjälpa dig att bli bättre förberedd på säkerhetshot från NISQ-eran och därefter, inklusive forskning, bedömning, testning, klassificering och verifiering.
Låt oss börja idag.
Jay Liu, VP of Product på Zapata Computing
