Wat is Algoritme van Shor?

Antwoord: A. Publieke-sleutelcryptografie zoals RSA en elliptische-krommecryptografie

De veiligheid van RSA berust op de moeilijkheid van het ontbinden van grote getallen in priemfactoren, en die van elliptische-krommecryptografie op de moeilijkheid van het discrete-logaritmeprobleem. Het algoritme van Shor lost deze problemen in polynomiale tijd op door met de kwantum-fouriertransformatie perioden te bepalen. Sleutels die te lang zijn om op klassieke computers in een realistische tijd te kraken, zouden dan met een voldoende grote fouttolerante kwantumcomputer kunnen worden gekraakt. Tegen symmetrische cryptografie zoals AES is er alleen de kwadratische versnelling van het algoritme van Grover, en die kan met langere sleutels worden opgevangen.

Antwoord: C. Een enorm aantal poorten moet foutloos worden uitgevoerd, wat veel logische qubits vereist die met foutcorrectie zijn gebouwd, plus een gigantisch aantal fysieke qubits om die te ondersteunen

Om RSA-2048 te kraken moeten op ruwweg duizend tot enkele duizenden logische qubits poorten in de orde van miljarden achter elkaar worden uitgevoerd. De logische foutkans moet daarom extreem laag zijn, en foutcorrectie vraagt enkele honderden of meer fysieke qubits per logische qubit. Schattingen uit de jaren 2020 komen op ruwweg honderdduizenden tot tientallen miljoenen fysieke qubits met foutkansen van ongeveer 0,1% (de cijfers hangen sterk af van de aannamen), ordes van grootte meer dan de schaal van de huidige apparaten. Deze schattingen worden echter kleiner naarmate de algoritmen verbeteren, dus de voorbereiding op de migratie van cryptografie moet vroeg beginnen.