Figuren visar det resulterande neurala nätverket för att lösa en liten probleminstans (krypteringsnyckel för att bryta). Cirklarna representerar neuroner, svarta linjer anger excitatoriska synapsförbindelser, och röda linjer anger hämmande synapskopplingar. Nätverket kodar primfaktorerna för successiva polynomvärden. Kredit:Dr. John V. Monaco, Amerikanska armén
Forskare från U.S. Army Research Laboratory har upptäckt ett sätt att utnyttja framväxande hjärnliknande datorarkitekturer för ett urgammalt talteoretiskt problem känt som heltalsfaktorisering.
Genom att efterlikna hjärnfunktionerna hos däggdjur i datoranvändning, Arméforskare öppnar upp ett nytt lösningsutrymme som går bort från traditionella datorarkitekturer och mot enheter som kan fungera inom extrema storlekar -, vikt-, och energibegränsade miljöer.
"Med mer datorkraft på slagfältet, vi kan bearbeta information och lösa beräkningssvåra problem snabbare, " sa Dr. John V. "Vinnie" Monaco, en ARL-datavetare. "Programmera den typ av enheter som passar dessa kriterier, till exempel, hjärninspirerade datorer, är utmanande, och att knäcka kryptokoder är bara ett program som visar att vi vet hur man gör det här."
Problemet i sig kan uttryckas enkelt. Ta ett sammansatt heltal N och uttryck det som produkten av dess primära komponenter. De flesta människor har slutfört denna uppgift någon gång i grundskolan, ofta en övning i elementär räkning. Till exempel, 55 kan uttryckas som 5*11 och 63 som 3*3*7. Vad många inte insåg är att de utförde en uppgift som om den slutfördes tillräckligt snabbt för stora antal, kan bryta mycket av dagens internet.
Offentlig nyckelkryptering är en metod för säker kommunikation som används allmänt idag, baserad på RSA-algoritmen utvecklad av Rivest, Shamir, och Adleman 1978. Säkerheten för RSA-algoritmen bygger på svårigheten att faktorisera ett stort sammansatt heltal N, den offentliga nyckeln, som distribueras av mottagaren till alla som vill skicka ett krypterat meddelande. Om N kan inkluderas i dess huvudkomponenter, sedan den privata nyckeln, behövs för att dekryptera meddelandet, kan återvinnas. Dock, svårigheten att faktorisera stora heltal blir snabbt uppenbar.
När storleken på N ökar med en enda siffra, tiden det skulle ta att faktor N genom att prova alla möjliga kombinationer av primtalsfaktorer är ungefär fördubblad. Det betyder att om ett tal med tio siffror tar 1 minut att faktorisera, ett nummer med tjugo siffror tar cirka 17 timmar och ett nummer med 30 siffror cirka två år, en exponentiell ökning av ansträngningen. Denna svårighet ligger till grund för säkerheten för RSA-algoritmen.
Utmanar detta, Monaco och hans kollega Dr. Manuel Vindiola, av labbets Computational Sciences Division, demonstrerade hur hjärnliknande datorer snabbar upp de för närvarande mest kända algoritmerna för att faktorisera heltal.
Teamet av forskare har utarbetat ett sätt att faktorisera stora sammansatta heltal genom att utnyttja den massiva parallelliteten hos nya datorarkitekturer som efterliknar däggdjurshjärnans funktion. Så kallade neuromorfa datorer fungerar under helt andra principer än konventionella datorer, som bärbara datorer och mobila enheter, allt baserat på en arkitektur som beskrevs av John von Neumann 1945.
I von Neumann-arkitekturen, minnet är skilt från centralenheten, eller CPU, som måste läsa och skriva till minnet över en buss. Denna buss har en begränsad bandbredd, och mycket av tiden, CPU:n väntar på att komma åt minnet, ofta kallad von Neumanns flaskhals.
neuromorfa datorer, å andra sidan, inte lider av en von Neumann flaskhals. Det finns ingen CPU, minne, eller buss. Istället, de innehåller många individuella beräkningsenheter, ungefär som neuroner i hjärnan.
Dr. John V. "Vinnie" Monaco är en datorforskare i Army Research Laboratory. Kredit:Dr. John V. Monaco
Dessa enheter är sammankopplade med fysiska eller simulerade vägar för att överföra data runt, analogt med synaptiska kopplingar mellan neuroner. Många neuromorfa enheter fungerar baserat på de fysiska responsegenskaperna hos det underliggande materialet, såsom grafenlasrar eller magnetiska tunnelövergångar. På grund av detta, dessa enheter förbrukar storleksordningar mindre energi än deras motsvarigheter från von Neumann och kan arbeta på en molekylär tidsskala. Som sådan, alla algoritmer som kan köras på dessa enheter kommer att dra nytta av deras kapacitet.
Den snabbhet som ARL-forskarna förvärvat beror på formuleringen av en metod för heltalsfaktorisering med hjälp av en neuromorf co-processor. De nuvarande snabbaste algoritmerna för att faktorisera heltal består huvudsakligen av två steg, siktning och en matrisreduktion, och siktningssteget omfattar det mesta av beräkningsansträngningen.
Siktning innebär att söka efter många heltal som uppfyller en viss egenskap som kallas B-smooth, heltal som inte innehåller en primtalsfaktor större än B. Monaco och Vindiola kunde konstruera ett neuralt nätverk som upptäcker B-släta tal snabbare och med större noggrannhet än på en von Neumann-arkitektur. Deras algoritm utnyttjar den massiva parallelliteten hos hjärninspirerade datorer och individuella nervcellers medfödda förmåga att utföra aritmetiska operationer, såsom tillägg. När neuromorfa arkitekturer fortsätter att öka i storlek och hastighet, inte begränsat av Moores lag, deras förmåga att hantera större heltalsfaktoriseringsproblem växer också. I sitt arbete, det uppskattas att 1024-bitars nycklar kan gå sönder på ungefär ett år, en uppgift som en gång ansågs vara utom räckhåll. För jämförelse, det aktuella rekordet, ett nummer med 232 decimalsiffror (RSA-768) tog ungefär 2, 000 år av beräkningstid under flera år.
Ur ett bredare perspektiv, denna upptäckt driver oss att ifrågasätta hur ett skifte i datorparadigm kan påverka några av våra mest grundläggande säkerhetsantaganden. När nya enheter övergår till att införliva massiv parallellism och utnyttja materialfysik för att beräkna, den beräkningshårdhet som ligger till grund för vissa säkerhetsprotokoll kan utmanas på sätt som inte tidigare föreställts. Detta arbete öppnar också dörren till nya forskningsområden inom framväxande datorarkitekturer, när det gäller algoritmdesign och funktionsrepresentation, tillsammans med lågeffekts maskininlärning och tillämpningar för artificiell intelligens.
"Krypterade meddelanden i krigföring har ofta ett utgångsdatum, när innehållet blir obrukbart, " sade Monaco. "Det är brådskande att dekryptera fiendens kommunikation, speciellt de på fältnivå, eftersom dessa går ut snabbast, jämfört med kommunikation på högre nivåer. Under fältförhållanden, ström och anslutningsmöjligheter är extremt begränsade. Detta är en stark motiverande faktor för att använda en hjärninspirerad dator för en sådan uppgift där konventionella datorer inte är praktiska."
