Bør Crypto frykte kvanteberegning?

Publisert av Platon

Følgere: 0

Ting å vite:

– Quantum computing, en banebrytende teknologi, har et enormt potensial for å revolusjonere databehandling med sin uovertrufne beregningskraft.

– Kvantedatabehandling, til tross for at det er minst flere år fra et stort gjennombrudd, blir oppfattet som en betydelig trussel mot kryptografi på grunn av dens enorme databehandlingsevner.

– Den potensielle innvirkningen av kvantedatabehandling på kryptografi og sikre systemer som Bitcoins proof-of-work må vurderes nøye. Som verdens sikreste inngangsport til krypto, fortjener slike grunnleggende spørsmål Ledgers fulle oppmerksomhet.

Quantum Computing: The Next Big Tech Leap

Datamaskinene vi bruker daglig behandler informasjon basert på "biter". En bit kan bare inneholde én av følgende verdier: 0 eller 1, og kan settes sammen for å lage et stykke binær kode. I dag er alt vi gjør med en datamaskin, fra å sende e-post og se videoer til å dele musikk, mulig på grunn av slike strenger av binære sifre.

Den binære naturen til tradisjonelle datamaskiner setter begrensninger på deres datakraft. Disse datamaskinene utfører kun operasjoner ett trinn om gangen og sliter med å simulere virkelige problemer nøyaktig. Derimot opererer den fysiske verden basert på amplituder i stedet for binære sifre, noe som gjør den mye mer kompleks. Det er her kvantedatamaskiner kommer inn i bildet.

I 1981 sa Richard Feynman at "naturen ikke er klassisk, og hvis du vil lage en simulering av naturen, bør du gjøre den kvantemekanisk." I stedet for å manipulere biter, bruker kvanteberegning "kvantebiter", eller qubits, slik at den kan behandle data på en mye mer effektiv måte. Qubits kan være null, én, og viktigst av alt, en kombinasjon av null og én.

Bør Crypto frykte kvanteberegning? PlatoBlockchain Data Intelligence. Vertikalt søk. Ai. — Bør Crypto frykte kvanteberegning?

Kvantedatabehandling står i krysset mellom fysikk og informatikk. For å sette ting i perspektiv, ville en 500-qubit kvantedatamaskin kreve mer klassiske biter enn ... antall atomer i hele universet.

Er Quantum en trussel mot kryptografi?

Offentlig nøkkelkryptering, også referert til som asymmetrisk kryptografi, danner grunnlaget for kryptovalutasikkerhet. Det involverer en kombinasjon av en offentlig nøkkel (tilgjengelig for alle) og en privat nøkkel. De raske beregningsmulighetene til qubits øker potensialet for å bryte kryptering og forstyrre sikkerheten til kryptovalutaindustrien hvis kvanteberegningen fortsetter å utvikle seg.

To algoritmer må vurderes nøye: Shor's og Grover's. Begge algoritmene er teoretiske fordi det for øyeblikket ikke er noen maskin for å implementere dem, men som du vil se, kan den potensielle implementeringen av disse algoritmene være skadelig for kryptografi.

På den ene siden gjør Shors (1994) kvantealgoritme, oppkalt etter Peter Shor, det mulig å faktorisere store heltall eller løse det diskrete logaritmeproblemet i polynomtid. Denne algoritmen kan bryte offentlig nøkkelkryptografi med en tilstrekkelig kraftig kvantedatamaskin. Shors algoritme ville bryte det store flertallet av asymmetrisk kryptografi som brukes i dag, siden den er basert på RSA (avhengig av heltallsfaktoriseringsproblemet) og elliptisk kurvekryptering (avhengig av det diskrete logaritmeproblemet i en elliptisk kurvegruppe).

På den annen side er Grovers (1996) algoritme en kvantesøkealgoritme utviklet av Lov Grover i 1996, som kan brukes til å løse ustrukturerte søkeproblemer. Grover-algoritmen setter et betydelig inngrep i symmetriske primitivers sikkerhet, men er ikke uoverkommelig. Det anbefales generelt å doble nøkkellengden for å kompensere for denne pausens kvadratrotkompleksitet. Å bruke AES256 i stedet for AES128 anses som nok, men det bør bemerkes at denne tommelfingerregelen kan bare noen ganger være gyldig for alle chiffer[5]. Når det gjelder hasjfunksjoner, som er en del av det symmetriske primitivets landskap, antas det at det ikke har noen innvirkning på kollisjonsmotstanden. Imidlertid fant forskere tilfeller av problemet hvor dette er usant[6] (for eksempel multi-target preimage-søk).

I hovedsak utgjør begge algoritmene potensielle farer for kryptografi. Shors algoritme forenkler prosessen med å faktorisere store tall, noe som gjør det lettere å avdekke en privat nøkkel koblet til en offentlig nøkkel, og Grovers algoritme er i stand til å kompromittere kryptografisk hashing mer effektivt enn dagens datamaskiner.

Når vil krypteringsbrytende kvantedatamaskiner dukke opp?

La oss gå gjennom noen av de siste eksperimentene og se hvor raskt forskningen går. Den første virkelige kvantedatamaskinen er fortsatt langt unna, men det forhindrer ikke et globalt løp i å nå "kvanteoverlegenhet". For Ayal Itzkovitz, administrerende partner i et kvantefokusert VC-fond, "hvis vi for tre år siden ikke visste om det var helt mulig å bygge en slik datamaskin, nå vet vi allerede at det vil være kvantedatamaskiner som vil kunne gjøre noe annet enn klassiske datamaskiner."

En hendelse som alle sikkert har hørt om, var Googles "kvanteoverherredømmeeksperiment" i 2019 med en enhet med 54 qubits. I 2021 ble Universitetet for vitenskap og teknologi i Kina løste en mer kompleks beregning ved å bruke 56 qubits, og nådde 60 qubits senere. Målet var å utføre en beregning som ikke involverer Shors algoritme, som på samme måte ville demonstrere en kvantehastighet i forhold til klassisk databehandling.

Per definisjon viser ikke disse eksperimentene fremgang mot å bryte kryptografi fordi de ble designet for å unngå størrelsen og kompleksiteten ved å utføre kvanteheltallsfaktorisering. Imidlertid viser de at det ikke lenger er vanskelig å bygge flere qubits inn i en kvantedatamaskin, med forskjellige maskinvareløsninger tilgjengelig, Googles "Sycamore"-brikkequbits er fundamentalt forskjellige fra USTCs fotoner. Det neste viktige trinnet for å komme til en krypteringsbrytende datamaskin anses generelt å være å bygge feiltolerante beregninger og feilkorrigerende qubits.

BSIs status for kvantedatamaskinutvikling [1] viser hvor langt fra å bryte en 160-bits diskret logaritme (laveste blå linje i følgende bilde) gjeldende kvantedatamaskiner er. Abscissen viser hvordan reduksjon av feilraten gjennom rene maskinvareforbedringer eller feiltolerant databehandling bidrar til å nå slike databehandlingsnivåer uten å dramatisk skalere antall tilgjengelige qubits (y-aksen).

Implementering av Shors algoritme på en skalerbar måte krever feiltolerant beregning på noen få tusen logiske qubits: 2124 qubits på et minimum for å bryte en 256-bit elliptisk kurve som bitcoins secp256k1, fra Forbedrede kvantekretser for elliptiske kurvediskrete logaritmer[7]. En 'logisk' qubit i et slikt system er sammensatt av flere qubits designet for å fungere som en feilkorrigert versjon av en enkelt qubit.

Tusen logiske qubits kan grovt oversettes til flere millioner qubits, som dekker størrelsen på en fotballbane. En praktisk demonstrasjon av en slik feiltolerant beregning ble nylig gjort i Feiltolerant kontroll av en feilkorrigert qubit[2], der en enkelt logisk qubit hvis feilsannsynlighet er lavere enn for qubitene den er laget av. Dette områdets forbedring forventes å følge raskt ettersom det vil bli fokus.

Fremgang i denne retningen vil direkte oversettes til en konkret trussel mot offentlig nøkkelkryptografi. Til slutt kan en annen mulighet for rask fremgang komme fra rene algoritmiske forbedringer eller bare maskinvare-oppdagelser. BSIs status for kvantedatamaskinutvikling[1] forklarer: «Det kan være forstyrrende oppdagelser som dramatisk vil endre [nåværende kunnskapsstatus], de viktigste er kryptografiske algoritmer som kan kjøres på nærtids ikke-feilkorrigerte maskiner eller dramatiske gjennombrudd i feilraten av noen plattformer." Med andre ord, det er ikke bare et problem å kunne bygge store datamaskiner med mange qubits (det er faktisk ikke hovedfokuset å bygge flere qubits pålitelig, feiltolerant databehandling), men også en algoritmisk og muligens materialforskning. en.

Mens vi skrev denne artikkelen publiserte IBM sine resultater på en 127-qubit-brikke med en feilrate på 0.001, og planlegger å utstede en 433-qubit-brikke neste år og 1121-qubit-brikke i 2023.

Alt i alt er det fortsatt vanskelig å forutsi hvor raskt en kvantedatamaskin vil komme til live. Likevel kan vi stole på ekspertuttalelser om saken: Et ressursestimeringsrammeverk for kvanteangrep mot kryptografiske funksjoner – siste utvikling[3] og Ekspertundersøkelse om kvanterisiko[4] viser at mange eksperter er enige om at om 15 til 20 år bør vi ha en kvantedatamaskin tilgjengelig.

siterer Et ressursestimeringsrammeverk for kvanteangrep mot kryptografiske funksjoner – siste utvikling [3] som en oppsummering:

«De gjeldende offentlige nøkkelordningene, som RSA og ECC, er fullstendig ødelagt av Shors algoritme. Derimot reduseres sikkerhetsparametrene til symmetriske metoder og hashfunksjoner med høyst en faktor på to av de kjente angrepene – ved «brute force»-søk ved bruk av Grovers søkealgoritme. Alle disse algoritmene krever storskala, feiltolerante kvantemaskiner, som ennå ikke er tilgjengelige. De fleste i ekspertmiljøet er enige om at de sannsynligvis vil bli en realitet innen 10 til 20 år.»

Nå som vi har undersøkt hvorfor kvantealgoritmer kan skade kryptografi, la oss analysere de betydelige risikoene som ligger i krypto- og Web3-feltene.

Quantum: Hvilke risikoer for kryptovalutaer?

Bitcoin-saken:

La oss starte med Pieter Wuilles analyse av problemet for Bitcoin, noen ganger ansett som "kvantesikker" på grunn av adresser som hasjer av offentlige nøkler og dermed ikke eksponere dem.

Å ikke kunne bryte en privat Bitcoin-nøkkel basert på antagelsen om at hasjer gjør det umulig, er også avhengig av å aldri avsløre ens offentlige nøkkel, uansett midler, noe som allerede er feil for mange kontoer.

Med henvisning til en annen tråd gir Pieter Wuille en ide om virkningen av å få stjålet ~37% av de utsatte midlene (den gang). Bitcoin ville trolig hakket, og til og med ueksponert, taper alle andre også.

Det avgjørende punktet her er omtale at fremgangen mot å bygge en kvantedatamaskin vil være inkrementell: milliarder av dollar er offentlig investert i dette feltet og enhver forbedring gir gjenklang over hele verden, som Googles kvanteoverlegenhetseksperiment viste.

Det betyr at det vil ta tid å ende opp med midler i fare, og alternative løsninger kan legges ut riktig. Man kan tenke seg å sette opp en del av kjeden ved å bruke post-kvantekryptografiske algoritmer for å signere og la folk overføre pengene sine til den nye kjeden fra den gamle en gang nyheten om en rimelig kraftig kvantedatamaskin virker nært forestående.

Ethereum-saken:

Saken med Ethereum er interessant ettersom ETH 2.0 inkluderer en backupplan for en katastrofal feil i EIP-2333.

I tilfelle ETH2s BLS-signaturer går i stykker, noe som vil skje samtidig med ECDSA siden de begge er like sårbare i møte med Shors algoritme, vil en hard fork av blokkjeden bli utført før algoritmen mistenkes å være kompromittert. Deretter avslører brukere et forhåndsbilde av nøkkelen deres som bare legitime eiere kan ha. Dette ekskluderer nøkler hentet ved å bryte en BLS-signatur. Med det forhåndsbildet signerer de en spesifikk transaksjon som lar dem flytte til den harde gaffelen og bruke nye post-kvantealgoritmer.

Dette er ikke en overgang til en post-kvantekjede ennå, men det gir en fluktluke. Litt mer informasjon her..

Postkvantesignaturer:

Et par ting kan forbedres når det gjelder å bytte til et post-kvantesignaturskjema for bruk i en kryptovaluta. De nåværende NIST-finalistene har ganske store minnekrav. Når signaturstørrelsen ikke er urimelig større enn for en ECDSA, øker den offentlige nøkkelstørrelsen blokkstørrelser og de tilknyttede gebyrene.

Kandidat navn	Størrelse
Rainbow	58.3 kB
Dilitium	3.5 kB
Falcon	1.5 kB
GeMSS	352 kB
Piknik	12 kB
SPHINCS +	7 kB

Falcon-algoritmen ble designet for å minimere størrelsen på den offentlige nøkkelen og signaturen. Imidlertid er dens 1563 byte fortsatt langt fra de 65 byte ECDSA nå når.

Kryptografiske teknikker kan redusere blokkstørrelser, som å samle flere signaturer sammen. Denne [multisignaturordningen](https://eprint.iacr.org/2020/520) for GeMSS-signaturen gjør nettopp det og reduserer lagringskostnadene per signatur til noe akseptabelt, til tross for den enorme engangsavgiften for en GeMSS-signatur .

Trusler mot kryptografisk maskinvare:

Signaturstørrelser påvirker også maskinvarelommebøker der minnet er svært begrenset: en Ledger Nano S har 320 KB Flash-minne tilgjengelig og bare 10 kilobyte RAM. Hvis vi plutselig trengte å bruke Rainbow-signaturer, ville det ikke være mulig å generere den offentlige nøkkelen på en naturlig måte.

Siden imidlertid hele det kryptografiske fellesskapet er berørt av problemet, inkludert bank-, telekommunikasjons- og identitetsindustrien, som utgjør det meste av markedet for sikre brikker, forventer vi at maskinvare raskt tilpasser seg behovet for post-kvantealgoritmer. vennlig maskinvare og fjern det minnet (eller noen ganger ytelsen) sammen i tide.

Konsekvensene av disse bruddene er undergangen av det nåværende banksystemet, telekommunikasjon og identitetssystemer som pass. Hva skal man gjøre i møte med en slik apokalyptisk fremtid? Frykt ikke, eller litt, da kryptografer har dekket det.

Finnes det en kur, doktor?

Mens våre nåværende datamaskiner ville trenge tusenvis av år for å bryte offentlig nøkkelkryptografi, ville fullt utviklede kvantedatamaskiner gjøre dette på minutter eller timer. "Kvantesikkerhet"-standarder vil uunngåelig være nødvendig for å motvirke denne trusselen og sikre sikkerheten til våre fremtidige økonomiske transaksjoner og nettbasert kommunikasjon.

Arbeidet er allerede i gang med det som vanligvis kalles "Post-kvantekryptografi" det ville muligens være "kompatibel med dagens datamaskiner, men som også vil være i stand til å motstå angripere fra kvantedatamaskiner i fremtiden." Postkvantekryptografi bringer algoritmer og matematiske standarder til neste nivå, samtidig som det tillater kompatibilitet med dagens datamaskiner.

De NIST-konkurranse opprettet nettopp for anledningen har allerede nådd sin tredje runde og produsert en liste over potensielle kandidater for standardisering. De Post-kvantesikkerhetskonferanse ble lansert så langt tilbake som i 2006 for å studere kryptografiske primitiver som ville motstå kjente kvanteangrep.

Grunnlaget for denne forskningen stammer fra ekspertadvarsler om at krypterte data allerede er i fare for å bli kompromittert, ettersom de første praktiske kvantedatamaskinene forventes å dukke opp i løpet av de neste 15 årene.
Denne typen angrep er kjent som «hamstre data nå, angrep senere», der en stor organisasjon lagrer kryptert informasjon fra andre parter den ønsker å bryte og venter til en kraftig nok kvantedatamaskin lar den gjøre det. Dette er den samme bekymringen i denne artikkelen, for eksempel, "USA er bekymret for at hackere stjeler data i dag, slik at kvantedatamaskiner kan knekke det om et tiår", men det sier ikke hva aktører på statlig nivå kan gjøre på samme måte. De har mye mer ressurser og lagring tilgjengelig.

Lukke Thoughts

Den nøyaktige hastigheten som kryptert kommunikasjon vil bli sårbar for kvanteforskning er fortsatt vanskelig å fastslå.

En ting er sikkert: selv om det gjøres betydelige fremskritt innen kvantedatabehandling, er vi fortsatt langt fra å ha evnen til å knekke kryptografi med disse maskinene. Sannsynligheten for et plutselig gjennombrudd som resulterer i utformingen av en slik datamaskin er minimal, noe som gir oss tid til å forberede dens ankomst. Hvis det skulle skje over natten, ville konsekvensene være katastrofale, og påvirke ikke bare kryptovalutaer, men et bredt spekter av sektorer.

Heldigvis er løsninger, inkludert post-kvantekryptering, tilgjengelig for å møte trusselen, men kryptoindustrien har ennå ikke sett at det haster med å investere i disse tiltakene.

Kryptovalutamarkedet må følge kvanteutviklingen nøye. Når det gjelder maskinvare, er det liten grunn til bekymring da vi forventer utvikling av nye sikre elementer for å møte etterspørselen. Det er avgjørende å holde seg à jour med de siste fremskrittene innen sidekanal- og feilbestandige versjoner av disse algoritmene, for å kunne tilby en pålitelig implementering for brukerne våre.