Kvantetrussel: Hvilken kryptografi dør og hvilken lever? (Eller: Hvorfor er ZK-STARK-er PQ-sikre?) Tidligere forklarte jeg hvordan en kvantedatamaskin fungerer: Tenk på problemløsning som å prøve å rømme fra en labyrint. Det finnes mange mulige veier, og du må sjekke hver eneste til du finner utgangen. Slik fungerer en klassisk (ikke-kvantemekanisk) datamaskin. Men kvantemekanikkens lover gjør det mulig å gjøre det bedre. De lar et system (en haug med partikler) utforske parallelle *alle* forskjellige stier i labyrinten. Stiene som fører til en utgang forblir levedyktige, mens de som leder til en blindvei forsvinner. Deretter velger universet tilfeldig en av de gjenværende levedyktige veiene (dette er delen Einstein ikke likte, og sier «Gud spiller ikke terning», bare at han faktisk gjør det). Slik løser en kvalitetskontroll problemer som en klassisk datamaskin ville tatt millioner av år å løse. Men det finnes typer kryptografiske primitiver som kan brytes av en kvantedatamaskin, og de som forblir trygge. Hvordan er dette mulig? I min forrige forklaring utelot jeg en viktig del: Ikke alle labyrinter er like. Det finnes noen labyrinter hvor blindveiene forsvinner, og universet har bare en god vei som fører til en utgang. Jeg kaller disse «kvante-enkle labyrinter» fordi når universet prøver en vei for en slik labyrint, vil det alltid være en vei som leder til en utgang. Lett å nå enden av labyrinten betyr lett å bryte. Men i «kvanteharde labyrinter» forblir alle stier «levende», enten de når en blindvei eller en utgang. For en slik labyrint er en kvantedatamaskin ikke bedre enn en klassisk datamaskin. Når Gud kaster terningen og velger en vei, er alle veier – gode og dårlige – like sannsynlige til å dukke opp. Så en kvantedatamaskin gjør analogien til en klassisk datamaskin, og sjekker tilfeldig en enkelt sti i labyrinten. Nå spør du sikkert: Hvilke labyrinter er kvante-enkle og hvilke er det ikke? ...