Informellt är en obfuscator O en (effektiv, probabilistisk) "kompilator" som tar som ingång ett program (eller krets) P och producerar ett nytt program O(P ) som har samma funktionalitet som P ännu är "oförståelig" i någon mening. Obfuscators, om de finns, skulle ha en mängd olika kryptografiska och komplexa-teoretiska tillämpningar, allt från programvaruskydd till homomorfisk kryptering till komplexa-teoretiska analoger av Ris teorem. De flesta av dessa tillämpningar är baserade på en tolkning av "oförståelig" villkor i obfuscation som innebär att O(P ) är en "virtuell svart låda", i den meningen att allt man effektivt kan beräkna givet O(P ), man kan också effektivt beräkna given orakle tillgång till P. I detta arbete, inleder vi en teoretisk undersökning av obfuscation. Vårt huvudsakliga resultat är att även under mycket svaga formaliseringar av ovanstående intuition är obfuscation omöjlig. Vi bevisar detta genom att bygga en familj av effektiva program P som är oobfuscatable i den meningen att (a) med tanke på alla effektiva program P som beräknar samma funktion som ett program P  på P, kan "källkod" P effektivt rekonstrueras, men (b) ges orakle tillgång till ett (slumpvis utvalda) program P P P, ingen effektiv algoritm kan rekonstruera P (eller ens skilja en viss bit i koden från slumpmässig) utom med försumbar sannolikhet. Vi utökar vår omöjlighet resulterar i ett antal sätt, inklusive även obfuscators som (a) inte nödvändigtvis kan beräknas i polynom tid, (b) bara ungefär bevara funktionaliteten, och (c) behöver bara arbeta för mycket begränsade modeller av beräkning (TC 0 ). Vi utesluter också flera potentiella tillämpningar av obfuscators, genom att bygga "oobfuscatable" signatursystem, krypteringssystem och pseudorandom funktionsfamiljer. I detta arbete inleder vi en teoretisk undersökning av obfuscation. Vi undersöker olika formaliseringar av begreppet, i ett försök att förstå vad vi kan och inte kan hoppas på att uppnå. Vårt huvudresultat är negativt, vilket visar att obfuscation (som det vanligtvis förstås) är omöjligt. Innan vi beskriver detta resultat och andra mer i detalj beskriver vi några av de potentiella tillämpningarna av obfuscators, både för motivation och för att förtydliga begreppet. Programvaruskydd.. De mest direkta tillämpningarna av obfuscators är för olika former av programvaruskydd. Genom definition, obfuscing ett program skyddar det mot omvänd ingenjörskonst. Till exempel, om en part, Alice, upptäcker en mer effektiv algoritm för factoring heltal, kan hon vilja sälja en annan part, Bob, ett program för till synes svagare uppgifter (såsom bryta RSA cryptosystem) som använder factoring algoritm som en subrutin utan att faktiskt ge Bob en factoring algoritm. Alice kan hoppas att uppnå detta genom att fördunkla programmet hon ger till Bob. Intuitivt, obfuscators skulle också vara användbart i vattenmärkning programvara (jfr, [CT; NSS]). En programvaruleverantör kan ändra ett programs beteende på ett sätt som unikt identifierar den person till vilken det säljs, och sedan fördunkla programmet för att garantera att detta "vattenmärke" är svårt att ta bort. Tar bort slumpmässiga orakler. Random Oracle Model [BR] är en idealiserad kryptografisk miljö där alla parter har tillgång till en verkligt slumpmässig funktion. Det är (heuritiskt) hoppats att protokoll utformade i denna modell kommer att förbli säker när den genomförs med hjälp av en effektiv, offentligt beräknande kryptografisk hash funktion i stället för den slumpmässiga funktionen. Även om det är känt att detta inte är sant i allmänhet [CGH], är det okänt om det finns effektivt beräkningsbara funktioner med tillräckligt starka egenskaper för att säkert användas i stället för den slumpmässiga funktionen i olika specifika protokoll 2. Man kan hoppas på att få sådana funktioner genom att fördunkla en familj av pseudorandom funktioner [GGM], vars input-output beteende är per definition oskiljaktiga från en verkligt slumpmässig funktion. Omvandla Privat-Key kryptering till Public-Key kryptering.. Obfuscation kan också användas för att skapa nya krypteringssystem med öppen nyckel genom att obfuscera ett krypteringssystem med privat nyckel. Med tanke på en hemlig nyckel K i en privat nyckel krypteringsschema, kan man publicera en obfuscation av krypteringsalgoritmen Enc K. Detta tillåter alla att kryptera, men bara en som har den hemliga nyckeln K bör kunna dekryptera. Intressant nog, i den ursprungliga tidningen av Diffie och Hellman [DH] var det ovan angivna skälet till att tro att public-key kryptosystem kan existera även om det inte fanns några kandidater kända ännu. Det vill säga, de föreslog att det skulle vara möjligt att fördunkla ett krypteringssystem med privat nyckel. 3 2 Vi noterar att resultaten av [CGH] också kan ses som att utesluta en mycket stark "virtuell svart låda" definition av obfuscators. Detta beror på att deras resultat innebär att ingen obfuscator tillämpas på någon pseudorandom funktion familj skulle kunna fungera för alla protokoll, medan en mycket stark virtuell svart låda definition skulle garantera detta. Vi konstaterar emellertid att våra viktigaste resultat utesluter en till synes mycket svagare definition av fördunkladhet. Dessutom noterar vi att utesluta starka virtuella svarta box definitioner är nästan omedelbar: Till exempel, en sak som kan beräknas effektivt från O(P ) är programmet O(P ) själv. Men för alla program P som motsvarar en funktion som är svår att lära sig från frågor, skulle det vara omöjligt att producera något program som motsvarar P i funktionalitet ges endast oracle tillgång till P. 3 Från [DH]: "En mer praktisk metod för att hitta ett par lätt beräknade inversa algoritmer E och D; sådan att D är svårt att sluta sig till från E, använder sig av svårigheten att analysera program i låg nivå språk. Alla som har försökt avgöra vilken operation som utförs av någon annans maskinspråksprogram vet att E själv (dvs. vad E gör) kan vara svårt att dra slutsatsen från en algoritm för E. Om programmet skulle göras avsiktligt förvirrande genom tillägg av onödiga variabler och uttalanden, då impossibilitet av Applikationer.. Att ge ytterligare bevis för att vårt omöjlighetsresultat inte är en artefakt av definitionsval, utan snarare är inneboende i den "virtuella svarta rutan" som bestämmer en omvänd algoritm kan göras mycket svårt. Naturligtvis måste E vara tillräckligt komplicerat för att förhindra dess identifiering från input-output par. Vad som i huvudsak krävs är en enkelriktad kompilator: en som tar ett lättförståeligt program skrivet på ett språk på hög nivå och översätter det till ett obegripligt program på något maskinspråk. Kompilatorn är enkelriktad eftersom det måste vara möjligt att göra sammanställningen, men omöjlig att vända processen. Eftersom effektivitet i storlek på programmet och körtid inte är avgörande i detta program, sådana kompilatorer kan vara möjligt om strukturen i maskinen språket kan optimeras för att hjälpa till i förvirringen." A:5 idé, vi visar också att flera av tillämpningarna av obfuscators är omöjliga. Vi gör detta genom att bygga oobfuscatable signatursystem, krypteringssystem och pseudorandom funktioner. Dessa är objekt som uppfyller standarddefinitionerna av säkerhet, men för vilka man effektivt kan beräkna den hemliga nyckeln K från alla program som signerar (eller krypterar eller utvärderar pseudorandom-funktionen, resp.) I förhållande till K. Därför är det mycket osäkert att dela ut "obfuskerade former" av dessa nyckeltalgoritmer. I synnerhet kompletterar vi Canetti et. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning.Kritik mot slumpmässig orakelmetodologi [CGH]. De visar att det finns (kontrigerade) protokoll som är säkra i den idealiserade Random Oracle Model (av [BR]), men är osäkra när den slumpmässiga oraklet ersätts med någon (effektivt beräknande) funktion. Våra resultat innebär att även för naturliga protokoll som är säkra i slumpmässiga orakel modellen, (t.ex. Fiat-Shamir typ system [FS]), finns det (kontrived) pseudorandom funktioner, så att dessa protokoll är osäkra när slumpmässiga orakel ersätts med något program som beräknar (kontrived) pseudorandom funktion. Vi nämner att efter vårt arbete, Barak [Bar1] konstruerade utan tvekan naturliga protokoll som är säkra i den slumpmässiga orakelmodellen (t.ex. De som erhålls genom tillämpning av Fiat-Shamir heuristic [FS] på hans argument om nollkunskap för offentliga mynt) men är osäkra när det slumpmässiga oraklet ersätts av någon effektivt beräkningsbar funktion. Definition 2.1 (TM obfuscator). En probabilistisk algoritm O är en TM obfuscator för samlingen F av Turing maskiner om följande tre villkor håller: 5 Se Fotnot 7.
Den första formella behandlingen av program obfuscation initierades av Barak et al REF som definierar en obfuscator O som en effektiv, probabilistisk kompilator som omvandlar ett program P till funktionellt likvärdigt obfuscated program O(P) som beter sig som en "virtuell svart-box".
On the (Im)possibility of Obfuscating Programs
{'venue': 'IACR Cryptology ePrint Archive', 'journal': 'IACR Cryptology ePrint Archive', 'mag_field_of_study': ['Computer Science']}