MIT-forskare har utvecklat en ny kryptografisk krets som kan användas för att skydda lågeffekt "internet of things" (IoT) enheter i den kommande tidsåldern av kvantberäkningar.

Kvantdatorer kan i princip utföra beräkningar som idag är praktiskt taget omöjliga för klassiska datorer. Att ta ut kvantdatorer online och på marknaden kan en dag möjliggöra framsteg inom medicinsk forskning, drog upptäckt, och andra applikationer. Men det finns en hake:Om hackare också har tillgång till kvantdatorer, de kan potentiellt bryta igenom de kraftfulla krypteringsscheman som för närvarande skyddar data som utbyts mellan enheter.

Dagens mest lovande kvantresistenta krypteringsschema kallas "gitterbaserad kryptografi, " som döljer information i extremt komplicerade matematiska strukturer. Hittills, ingen känd kvantalgoritm kan bryta igenom dess försvar. Men dessa system är alldeles för beräkningsintensiva för IoT-enheter, som bara kan spara tillräckligt med energi för enkel databehandling.

I ett dokument som presenterades vid den nyligen genomförda International Solid-State Circuits Conference, MIT-forskare beskriver en ny kretsarkitektur och statistiska optimeringstrick som kan användas för att effektivt beräkna gitterbaserad kryptografi. De 2-millimeter-kvadrat-chips som teamet utvecklade är tillräckligt effektiva för integrering i alla nuvarande IoT-enheter.

Arkitekturen är anpassningsbar för att rymma de flera gitterbaserade scheman som för närvarande studeras som förberedelse för dagen då kvantdatorer kommer online. "Det kan vara några decennier från nu, men att ta reda på om dessa tekniker verkligen är säkra tar lång tid, " säger första författaren Utsav Banerjee, en doktorand i elektroteknik och datavetenskap. "Det kan tyckas tidigt, men tidigare är alltid bättre."

Dessutom, forskarna säger, kretsen är den första i sitt slag som uppfyller standarder för gitterbaserad kryptografi som fastställts av National Institute of Standards and Technology (NIST), en byrå från det amerikanska handelsdepartementet som hittar och skriver regler för dagens krypteringsscheman.

Anantha Chandrakasan följer med Banerjee på tidningen, dekanus för MIT:s School of Engineering och Vannevar Bush professor i elektroteknik och datavetenskap, och Abhishek Pathak från Indian Institute of Technology.

Effektiv provtagning

I mitten av 1990-talet MIT Professor Peter Shor utvecklade en kvantalgoritm som i princip kan bryta igenom alla moderna kryptografisystem. Sedan dess, NIST har försökt hitta de säkraste postkvantkrypteringssystemen. Detta sker i faser; varje fas tar upp en lista över de säkraste och mest praktiska systemen. Två veckor sedan, byrån gick in i sin andra fas för postkvantkryptografi, med gallerbaserade scheman som utgör hälften av listan.

I den nya studien, forskarna implementerade först på kommersiella mikroprocessorer flera NIST-gitterbaserade kryptografischeman från byråns första fas. Detta avslöjade två flaskhalsar för effektivitet och prestanda:generering av slumptal och datalagring.

Att generera slumptal är den viktigaste delen av alla kryptografischeman, eftersom dessa siffror används för att generera säkra krypteringsnycklar som inte kan förutsägas. Det beräknas genom en tvådelad process som kallas "sampling".

Sampling genererar först pseudoslumptal från en känd, ändlig uppsättning värden som har lika sannolikhet att väljas. Sedan, ett "efterbearbetningssteg" omvandlar dessa pseudoslumptal till en annan sannolikhetsfördelning med en specificerad standardavvikelse - en gräns för hur mycket värdena kan variera från varandra - som slumpar siffrorna ytterligare. I grund och botten, de slumpmässiga talen måste uppfylla noggrant utvalda statistiska parametrar. Detta svåra matematiska problem förbrukar cirka 80 procent av all beräkningsenergi som behövs för gitterbaserad kryptografi.

Efter att ha analyserat alla tillgängliga metoder för provtagning, forskarna fann att en metod, kallas SHA-3, kan generera många pseudoslumptal två eller tre gånger mer effektivt än alla andra. De finjusterade SHA-3 för att hantera gitterbaserad kryptografi-sampling. Dessutom, de tillämpade några matematiska knep för att göra pseudoslumpmässiga samplingar, och efterbearbetningskonverteringen till nya distributioner, snabbare och effektivare.

De använder den här tekniken med energieffektiv anpassad hårdvara som bara tar upp 9 procent av ytan på deras chip. I slutet, detta gör processen att ta prover av två storleksordningar mer effektiv än traditionella metoder.

Dela upp data

På hårdvarusidan, forskarna gjorde innovationer inom dataflödet. Gitterbaserad kryptografi bearbetar data i vektorer, som är tabeller med några hundra eller tusen tal. Att lagra och flytta dessa data kräver fysiska minneskomponenter som tar upp cirka 80 procent av hårdvaruytan i en krets.

Traditionellt, data lagras på en enda två- eller fyraports RAM-enhet (Random Access Memory). Multiport-enheter möjliggör den höga datagenomströmning som krävs för krypteringsscheman, men de tar mycket plats.

För deras kretsdesign, forskarna modifierade en teknik som kallas "number theoretic transform" (NTT), som fungerar på samma sätt som Fouriertransformens matematiska teknik som bryter ner en signal till de multipla frekvenser som den utgör. Den modifierade NTT delar upp vektordata och allokerar delar över fyra enkelports RAM-enheter. Varje vektor kan fortfarande nås i sin helhet för sampling som om den var lagrad på en enda flerportsenhet. Fördelen är att de fyra enports REM-enheterna upptar ungefär en tredjedel mindre total yta än en multiportsenhet.

"Vi modifierade i princip hur vektorn fysiskt mappas i minnet och modifierade dataflödet, så denna nya kartläggning kan införlivas i provtagningsprocessen. Genom att använda dessa arkitekturknep, vi minskade energiförbrukningen och ockuperade ytan, samtidigt som den önskade genomströmningen bibehålls, " säger Banerjee.

Kretsen innehåller också en liten instruktionsminneskomponent som kan programmeras med anpassade instruktioner för att hantera olika samplingstekniker – såsom specifika sannolikhetsfördelningar och standardavvikelser – och olika vektorstorlekar och operationer. Detta är särskilt användbart, eftersom gitterbaserade kryptografisystem sannolikt kommer att förändras något under de kommande åren och decennierna.

Justerbara parametrar kan också användas för att optimera effektivitet och säkerhet. Ju mer komplex beräkningen är, ju lägre effektivitet, och vice versa. I deras tidning, forskarna beskriver hur man navigerar dessa kompromisser med sina justerbara parametrar. Nästa, forskarna planerar att justera chippet för att köra alla gitterbaserade kryptografischeman som listas i NIST:s andra fas.

Den här historien återpubliceras med tillstånd av MIT News (web.mit.edu/newsoffice/), en populär webbplats som täcker nyheter om MIT-forskning, innovation och undervisning.