Abstrakt. I en av de banbrytande dokumenten om kryptografi, föreslog Ralph Merkle ett heuristiskt protokoll för utbyte av en hemlig nyckel över en osäker kanal genom att använda en idealiserad privat nyckel krypteringsprogram. Merkles protokoll antas förbli säkert så länge gapet mellan motståndarens och de ärliga partiernas körtid är som mest kvadratiskt (snarare än superpolynom). I detta arbete initierar vi ett försök att basera liknande former av kryptografi med öppen nyckel på välgrundade antaganden. Vi föreslår en variant av Merkles protokoll vars säkerhet kan baseras på enkelriktadheten hos den underliggande primitiva. Särskilt med hjälp av en enkelriktad funktion av exponentiell styrka, får vi ett viktigt avtal protokoll mot motståndare vars körtid är nästan quadratic i körtiden för de ärliga parterna. Detta protokoll ger motståndaren en liten (men icke-försumbar) fördel i att gissa nyckeln. Vi visar att säkerheten i protokollet kan förstärkas genom att använda en enkelriktad funktion med en stark form av en svårkärnig predikat, vars existens följer av en förmodad "drömversion" av Yaos XOR lemma. Å andra sidan visar vi att denna typ av svårkärnig predikat inte kan baseras på (även exponentiellt stark) enväg genom att använda en svart-box konstruktion. Genom att fastställa ovanstående resultat avslöjar vi intressanta samband mellan det aktuella problemet och problem från andra områden. I synnerhet föreslår vi ett paradigm för att omvandla (ovillkorat) säkra protokoll i Maurers bundna lagringsmodell till (beräkningsmässigt) säkra protokoll i den slumpmässiga oraklet modellen, vilket omvandlar lagringsfördel till beräkningsfördel. Vårt huvudprotokoll kan ses som ett exempel på detta paradigm. Slutligen observerar vi att en kvantmotståndare helt kan bryta säkerheten i vårt protokoll (samt Merkles heuristiska protokoll) genom att använda den fyrfaldiga hastighetshöjningen av Grovers kvantsökningsalgoritm. Detta väcker en spekulation om att det kan finnas ett närmare samband mellan (klassisk) offentlig-nyckel kryptografi och kvantdator än vad man allmänt tror.
Senare förbättrades antagandet till starka enkelriktade funktioner REF.
Basing weak public-key cryptography on strong one-way functions
{'venue': 'TCC', 'journal': None, 'mag_field_of_study': ['Computer Science']}