Vi inleder studien av kompression som bevarar lösningen på ett fall av ett problem snarare än att bevara själva fallet. Vårt fokus ligger på kompressibiliteten av NP-beslutsproblem. Vi betraktar N P-problem som har långa fall men relativt korta vittnen. Frågan är, kan man effektivt komprimera en instans och lagra en kortare representation som upprätthåller informationen om huruvida den ursprungliga inmatningen är på språket eller inte. Vi vill att längden på den komprimerade instansen ska vara polynom i vittnets längd snarare än längden på den ursprungliga inmatningen. Sådan kompression gör det möjligt att kortfattat lagra instanser tills en framtida inställning kommer att göra det möjligt att lösa dem, antingen via ett tekniskt eller algoritmiskt genombrott eller helt enkelt tills tillräckligt med tid har förflutit. Vi ger en ny klassificering av NP med avseende på kompression. Denna klassificering utgör en stratifiering av N P som vi kallar VC-hierarkin. Hierarkin är baserad på en ny typ av reduktion som kallas W-minskning och det finns problem med kompression för varje klass. Vår motivation för att studera denna fråga härrör från de omfattande kryptografiska konsekvenser kompressibilitet har. Till exempel säger vi att SAT är komprimerbar om det finns en polynom p(·, ·) så att med en formel som består av m klausuler över n variabler är det möjligt att komma upp med en likvärdig (w.r.t tillfredsställande) formel av storlek som mest p(n, log m). Sedan ges en komprimeringsalgoritm för SAT vi tillhandahåller en konstruktion av kollisionsresistent hash funktioner från alla enkelriktade funktioner. Denna uppgift visade sig vara omöjlig genom nedskärningar av svarta lådor [41], och den konstruktion som presenteras är i själva verket icke-svart låda. En annan tillämpning av SAT compressibility är ett kryptoanalytiskt resultat gällande begränsningen av evig säkerhet i den avgränsade lagringsmodellen när den blandas med (tid) komplexitetsbaserad kryptografi. Dessutom studerar vi en strategi för att bygga *
Fällan-dörr kompression kan vara relaterad till ett begrepp av Harnik et al. REF om kompressibilitet av NP-beslutsproblem.
On the Compressibility of NP Instances and Cryptographic Applications
{'venue': "2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)", 'journal': "2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)", 'mag_field_of_study': ['Computer Science', 'Mathematics']}