Bör krypto vara rädd för kvantberäkning?

Saker att veta:

– Quantum computing, en banbrytande teknologi, har en enorm potential för att revolutionera beräkningar med sin oöverträffade beräkningskraft. – Kvantberäkningar, trots att det är åtminstone flera år från ett stort genombrott, uppfattas som ett betydande hot mot kryptografi på grund av dess enorma databehandlingskapacitet. – Den potentiella inverkan av kvantberäkning på kryptografi och säkra system som Bitcoins proof-of-work måste övervägas noggrant. Som världens säkraste inkörsport till krypto, förtjänar sådana grundläggande frågor Ledgers fulla uppmärksamhet.

Quantum Computing: The Next Big Tech Leap

Datorerna vi använder dagligen bearbetar information baserad på "bitar". En bit kan bara innehålla ett av följande värden: 0 eller 1, och kan strängas ihop för att skapa en bit binär kod. Idag är allt vi gör med en dator, från att skicka e-post och titta på videor till att dela musik, möjligt på grund av sådana strängar av binära siffror. 

Den binära karaktären hos traditionella datorer sätter begränsningar på deras datorkraft. Dessa datorer utför bara operationer ett steg i taget och kämpar för att exakt simulera verkliga problem. Däremot fungerar den fysiska världen baserat på amplituder snarare än binära siffror, vilket gör den mycket mer komplex. Det är här kvantdatorer kommer in i bilden.

1981 sa Richard Feynman att "naturen är inte klassisk, och om du vill göra en simulering av naturen, är det bättre att göra den kvantmekanisk." Istället för att manipulera bitar använder kvantberäkningar "kvantbitar" eller qubits, vilket gör att den kan bearbeta data på ett mycket mer effektivt sätt. Qubits kan vara noll, ett och, viktigast av allt, en kombination av noll och ett.

Quantum computing står vid vägskälet mellan fysik och datavetenskap. För att sätta saker i perspektiv skulle en kvantdator på 500 qubit kräva mer klassiska bitar än ... antalet atomer i hela universum.

Är Quantum ett hot mot kryptografi?

Offentlig nyckelkryptering, även kallad asymmetrisk kryptografi, utgör grunden för kryptovalutasäkerhet. Det involverar en kombination av en offentlig nyckel (tillgänglig för alla) och en privat nyckel. De snabba beräkningsmöjligheterna hos qubits ökar potentialen för att bryta kryptering och störa säkerheten för kryptovalutaindustrin om kvantberäkningen fortsätter att utvecklas.

Två algoritmer måste övervägas noga: Shors och Grovers. Båda algoritmerna är teoretiska eftersom det för närvarande inte finns någon maskin för att implementera dem, men som du kommer att se kan den potentiella implementeringen av dessa algoritmer vara skadlig för kryptografi.

Å ena sidan möjliggör Shors (1994) kvantalgoritm, uppkallad efter Peter Shor, att faktorisera stora heltal eller lösa det diskreta logaritmproblemet i polynomtid. Denna algoritm kan bryta kryptografi med publik nyckel med en tillräckligt kraftfull kvantdator. Shors algoritm skulle bryta den stora majoriteten av asymmetrisk kryptografi som används idag eftersom den är baserad på RSA (beroende på heltalsfaktoriseringsproblemet) och elliptisk kurvkryptering (beroende på det diskreta logaritmproblemet i en elliptisk kurvgrupp). 

Å andra sidan är Grovers (1996) algoritm en kvantsökningsalgoritm utarbetad av Lov Grover 1996, som kan användas för att lösa ostrukturerade sökproblem. Grover-algoritmen sätter en betydande buckla i symmetriska primitivers säkerhet men är inte oöverstiglig. Det rekommenderas i allmänhet att dubbla nyckellängden för att kompensera för denna paus kvadratrotskomplexitet. Att använda AES256 istället för AES128 anses tillräckligt, men det bör noteras att denna tumregel kanske bara ibland är giltig för alla chiffer[5]. När det gäller hashfunktioner, som är en del av den symmetriska primitivets landskap, tror man att det inte har någon inverkan på kollisionsmotståndet. Men forskare hittade exempel på problemet där detta är osant[6] (förbildssökning med flera mål, till exempel).

I huvudsak utgör båda algoritmerna potentiella faror för kryptografi. Shors algoritm förenklar processen att faktorisera stora siffror, vilket gör det lättare att avslöja en privat nyckel kopplad till en offentlig nyckel, och Grovers algoritm kan äventyra kryptografisk hashning mer effektivt än nuvarande datorer.

När kommer krypteringsbrytande kvantdatorer att dyka upp?

Låt oss gå igenom några av de senaste experimenten och se hur snabbt forskningen går. Den första riktiga kvantdatorn är fortfarande långt borta, men det hindrar inte en global ras från att nå "kvantöverhöghet". För Ayal Itzkovitz, managing partner i en kvantfokuserad riskkapitalfond, "om vi för tre år sedan inte visste om det var helt möjligt att bygga en sådan dator, nu vet vi redan att det kommer att finnas kvantdatorer som kommer att kunna göra något annat än klassiska datorer." 

En händelse som alla förmodligen har hört talas om var Googles "quantum supremacy experiment" 2019 med en enhet med 54 qubits. År 2021, Kinas universitet för vetenskap och teknik löste en mer komplex beräkning med 56 qubits, och nådde 60 qubits senare. Dess mål var att utföra en beräkning som inte involverade Shors algoritm som likaså skulle demonstrera en kvanthastighetsuppgång jämfört med klassisk datoranvändning.

Per definition visar dessa experiment inte framsteg mot att bryta kryptografi eftersom de utformades för att undvika storleken och komplexiteten för att utföra kvantheltalsfaktorisering. Men de visar att det inte längre är svårt att bygga in fler qubits i en kvantdator, med olika hårdvarulösningar tillgängliga, Googles "Sycamore"-chip-qubits skiljer sig fundamentalt från USTC:s fotoner. Nästa viktiga steg för att komma till en krypteringsbrytande dator anses generellt vara att bygga feltoleranta beräkningar och felkorrigerande qubits. 

BSI:s status för kvantdatorutveckling [1] visar hur långt från att bryta en 160 bitars diskret logaritm (lägsta blå linje i följande bild) nuvarande kvantdatorer är. Abskissan visar hur en minskning av felfrekvensen genom rena hårdvaruförbättringar eller feltolerant beräkning hjälper till att nå sådana beräkningsnivåer utan att dramatiskt skala antalet tillgängliga qubits (y-axeln).

Att implementera Shors algoritm på ett skalbart sätt kräver feltoleranta beräkningar på några tusen logiska qubits: minst 2124 qubits för att bryta en 256-bitars elliptisk kurva som bitcoins secp256k1, från Förbättrade kvantkretsar för diskreta logaritmer för elliptiska kurvor[7]. En "logisk" qubit i ett sådant system är sammansatt av flera qubits utformade för att fungera som en felkorrigerad version av en enda qubit.

Tusen logiska qubits översätts grovt till flera miljoner qubits, som täcker storleken på en fotbollsplan. En praktisk demonstration av en sådan feltolerant beräkning gjordes nyligen i Feltolerant styrning av en felkorrigerad qubit[2], där en enda logisk qubit vars felsannolikhet är lägre än för qubitarna den är gjord av. Detta områdes förbättring förväntas följa snabbt eftersom det kommer att bli fokus. 

Framsteg i denna riktning kommer direkt att översättas till ett konkret hot mot kryptografi med offentliga nyckel. Slutligen kan en annan möjlighet för snabba framsteg komma från rena algoritmiska förbättringar eller upptäckter som bara är hårdvara. BSI:s status för kvantdatorutveckling[1] förklarar: "Det kan finnas störande upptäckter som dramatiskt skulle förändra [det nuvarande kunskapsläget], de viktigaste är kryptografiska algoritmer som kan köras på kortsiktiga icke-felkorrigerade maskiner eller dramatiska genombrott i felfrekvensen av vissa plattformar.” Det är med andra ord inte bara ett problem att kunna bygga stora datorer med många qubits (faktiskt att bygga fler qubits tillförlitligt är inte huvudfokus, feltolerant datoranvändning är), utan också en algoritmisk sådan och möjligen en materialforskning ett.

När vi skrev den här artikeln publicerade IBM sina resultat på ett 127-qubit-chip med en felfrekvens på 0.001, och planerar att ge ut ett 433-qubit-chip nästa år och ett 1121-qubit-chip 2023. 

Sammantaget är det fortfarande svårt att förutsäga hur snabbt en kvantdator kommer att vakna till liv. Ändå kan vi lita på expertutlåtanden i frågan: En resursuppskattningsram för kvantattacker mot kryptografiska funktioner – den senaste utvecklingen[3] och Expertundersökning om kvantrisk[4] visar att många experter är överens om att om 15 till 20 år borde vi ha en kvantdator tillgänglig.

citerar En resursuppskattningsram för kvantattacker mot kryptografiska funktioner – den senaste utvecklingen [3] som en sammanfattning:

"De för närvarande utplacerade publika nyckelscheman, såsom RSA och ECC, är helt brutna av Shors algoritm. Däremot reduceras säkerhetsparametrarna för symmetriska metoder och hashfunktioner med högst en faktor två av de kända attackerna – genom "brute force"-sökningar med Grovers sökalgoritm. Alla dessa algoritmer kräver storskaliga, feltoleranta kvantmaskiner, som ännu inte är tillgängliga. De flesta i expertgruppen är överens om att de sannolikt kommer att bli verklighet inom 10 till 20 år.”

Nu när vi har undersökt varför kvantalgoritmer kan skada kryptografi, låt oss analysera de betydande riskerna för krypto- och Web3-fälten. 

Quantum: Vilka risker för kryptovalutor?

Bitcoin-fallet:

Låt oss börja med Pieter Wuilles analys av problemet för Bitcoin, som ibland anses vara "kvantsäkert" på grund av att adresser är hash offentliga nycklar och därmed inte exponera dem.

Att inte kunna bryta en privat Bitcoin-nyckel baserat på antagandet att hash gör det omöjligt förlitar sig också på att aldrig avslöja sin publika nyckel, oavsett medel, vilket redan är fel för många konton.

Med hänvisning till en annan tråd ger Pieter Wuille en uppfattning om effekten av att få ~37% av exponerade medel (vid den tiden) stulna. Bitcoin skulle förmodligen tanka, och till och med oexponerad, förlorar alla andra också.

Den avgörande punkten här är att nämna att framstegen mot att bygga en kvantdator kommer att vara steg: miljarder dollar investeras offentligt i detta område och alla förbättringar har resonans över hela världen, vilket Googles kvantöverlägsenhetsexperiment visade.

Det innebär att det tar tid att hamna i riskzonen och alternativa lösningar kan läggas upp på rätt sätt. Man kan föreställa sig att sätta upp en del av kedjan med hjälp av post-kvantkryptografiska algoritmer för att signera och tillåta människor att överföra sina pengar till den nya kedjan från den gamla en gång nyheten om en ganska biffig kvantdator verkar vara nära förestående.

Ethereum-fallet:

Fallet Ethereum är intressant eftersom ETH 2.0 inkluderar en backupplan för ett katastrofalt misslyckande i EIP-2333.

Om ETH2:s BLS-signaturer går sönder, vilket skulle hända samtidigt som ECDSA eftersom de båda är lika sårbara inför Shors algoritm, kommer en hård gaffel av blockkedjan att exekveras innan algoritmen misstänks vara äventyrad. Sedan avslöjar användare en förbild av sin nyckel som endast legitima ägare kan ha. Detta utesluter nycklar som hämtats genom att bryta en BLS-signatur. Med den förbilden undertecknar de en specifik transaktion som tillåter dem att flytta till den hårda gaffeln och använda nya post-kvantalgoritmer.

Detta är inte en byte till en post-kvantkedja ännu, men det ger en flyktlucka. Lite mer information här..

Postkvantsignaturer:

Några saker kan förbättras när det gäller att byta till ett post-kvantsignaturschema för användning i en kryptovaluta. De nuvarande NIST-finalisterna har ganska stora minneskrav. När signaturstorleken inte är orimligt större än den för en ECDSA, ökar storleken på den publika nyckeln blockstorlekarna och de associerade avgifterna.  

Kandidatens namn	Storlek
Rainbow	58.3 kB
dilithium	3.5 kB
Falcon	1.5 kB
GeMSS	352 kB
Picknick	12 kB
SPHINCS+	7 kB

Falcon-algoritmen utformades för att minimera storleken på den publika nyckeln och signaturen. Dess 1563 byte är dock fortfarande långt ifrån de 65 byte som ECDSA för närvarande når.

Kryptografiska tekniker kan minska blockstorlekar, som att aggregera flera signaturer tillsammans. Detta [multisignaturschema](https://eprint.iacr.org/2020/520) för GeMSS-signaturen gör just det och minskar lagringskostnaden per signatur till något acceptabelt, trots den enorma engångsavgiften för en GeMSS-signatur .

Hot mot kryptografisk hårdvara:

Signaturstorlekar påverkar också hårdvaruplånböcker där minnet är mycket begränsat: en Ledger Nano S har 320 KB tillgängligt flashminne och endast 10 kilobyte RAM. Om vi ​​plötsligt behövde använda Rainbow-signaturer skulle det inte vara möjligt att generera den publika nyckeln på ett inbyggt sätt.

Men eftersom hela kryptogemenskapen påverkas av problemet, inklusive bank-, telekommunikations- och identitetsindustrin, som utgör större delen av marknaden för säkra chips, förväntar vi oss att hårdvaran snabbt anpassar sig till behovet av post-kvantalgoritmer. vänlig hårdvara och ta bort det minnet (eller ibland prestanda) tillsammans i tid.

Konsekvenserna av dessa avbrott är undergången av det nuvarande banksystemet, telekommunikationer och identitetssystem som pass. Vad ska man göra inför en sådan apokalyptisk framtid? Var inte rädd, eller lite, eftersom kryptografer har täckt det.

Finns det ett botemedel, doktor?

Medan våra nuvarande datorer skulle behöva tusentals år för att bryta kryptografi med publik nyckel, skulle fullt utvecklade kvantdatorer göra detta på minuter eller timmar. Standarder för "kvantsäkerhet" kommer oundvikligen att behövas för att motverka detta hot och säkerställa säkerheten för våra framtida finansiella transaktioner och onlinekommunikation.

Arbete pågår redan med vad som brukar kallas "Post-quantum kryptografi" det skulle möjligen vara "kompatibel med dagens datorer men som också kommer att kunna motstå angripare från kvantdatorer i framtiden." Postkvantkryptering tar algoritmer och matematiska standarder till nästa nivå samtidigt som den tillåter kompatibilitet med nuvarande datorer.

Smakämnen NIST-tävling skapad just för tillfället har redan nått sin tredje omgång och tagit fram en lista över potentiella kandidater för standardisering. De Post-Quantum Security Conference lanserades så långt tillbaka som 2006 för att studera kryptografiska primitiver som skulle motstå kända kvantattacker.

Grunden till denna forskning härrör från expertvarningar om att krypterad data redan riskerar att äventyras, eftersom de första praktiska kvantdatorerna förväntas dyka upp inom de närmaste 15 åren.
Den här typen av attack är känd som "hamstra data nu, attackera senare", där en stor organisation lagrar krypterad information från andra parter som den vill bryta och väntar tills en tillräckligt kraftfull kvantdator tillåter den att göra det. Detta är samma oro som den här artikeln till exempel, "USA är orolig för att hackare stjäl data idag så att kvantdatorer kan knäcka det på ett decennium", men det säger inte vad aktörer på statlig nivå kan göra i samma veva. De har mycket mer resurser och lagring tillgänglig.

Utgående Tankar

Den exakta hastigheten med vilken krypterad kommunikation kommer att bli sårbar för kvantforskning är fortfarande svår att avgöra.

En sak är säker: även om betydande framsteg görs inom kvantberäkning, är vi fortfarande långt ifrån att ha förmågan att knäcka kryptografi med dessa maskiner. Sannolikheten för ett plötsligt genombrott som resulterar i designen av en sådan dator är minimal, vilket ger oss tid att förbereda oss för dess ankomst. Om det skulle inträffa över en natt skulle konsekvenserna bli katastrofala och påverka inte bara kryptovalutor utan ett brett spektrum av sektorer. 

Lyckligtvis finns lösningar, inklusive post-kvantkryptering, tillgängliga för att ta itu med hotet, men kryptoindustrin har ännu inte sett hur brådskande det är att investera i dessa åtgärder. 

Kryptovalutamarknaden måste noga övervaka kvantutvecklingen. När det gäller hårdvara finns det liten anledning till oro eftersom vi förväntar oss utvecklingen av nya säkra element för att möta efterfrågan. Det är avgörande att hålla sig à jour med de senaste framstegen inom sidokanals- och felresistenta versioner av dessa algoritmer, för att tillhandahålla en tillförlitlig implementering för våra användare.

Referensprojekt:

[1]: BSI:s status för kvantdatorutveckling

[2]: Feltolerant styrning av en felkorrigerad qubit

[3]: En resursuppskattningsram för kvantattacker mot kryptografiska funktioner – den senaste utvecklingen

[4]: Expertundersökning om kvantrisk

[5]: Utöver kvadratiska hastigheter i kvantattacker på symmetriska scheman

[6]: En effektiv Quantum Collision Search-algoritm och konsekvenser för symmetrisk kryptografi

[7]: Förbättrade kvantkretsar för diskreta logaritmer för elliptiska kurvor

• SEO-drivet innehåll och PR-distribution. Bli förstärkt idag.
• Platoblockchain. Web3 Metaverse Intelligence. Kunskap förstärkt. Tillgång här.
• Källa: https://www.ledger.com/blog/should-crypto-fear-quantum-computing