Nyligen har problemet med integriteten förstärkts med en aktiv motståndare fått mycket uppmärksamhet. Med tanke på en delad n-bit svag slumpmässig källa X med min-entropy k och en säkerhetsparameter s, är det huvudsakliga målet att konstruera en explicit 2-round integritetsförstärkning protokoll som uppnår entropy förlust O(s). Dodis och Wichs [DW09] visade att optimala protokoll kan uppnås genom att konstruera explicita icke-aducerbara extraktorer. Den mest kända explicita icke-aducerbara extraktorn uppnår dock endast k = 0.49n [Li12b] och bevis i [Li12b] tyder på att det kan vara svårt att konstruera explicita icke-aducerbara extraktorer för mindre min-entropi. I ett alternativt tillvägagångssätt införde Li [Li12a] idén om en icke-aducerbar kondensor och visade att explicita icke-aducerbara kondensatorer också ger optimal integritetsförstärkande protokoll. I den här tidningen ger vi den första konstruktionen av icke-förståeliga kondensorer för godtycklig mineropy. Med hjälp av vår konstruktion får vi ett tvåsidigt integritetsförstärkande protokoll med optimal entropiförlust för säkerhetsparameter upp till s =  och ( ε k). Detta är det första protokollet som samtidigt uppnår optimal rund komplexitet och optimal entropiförlust för godtycklig min-entropi k. Vi generaliserar också detta resultat för att få ett protokoll som körs i O(s/ ε k) rundor med optimal entropiförlust, för säkerhetsparameter upp till s =  och k. Detta förbättrar avsevärt protokollet i [CKOR10]. Slutligen ger vi en bättre icke-aducerbar kondensor för linjär min-entropi, och i detta fall få en 2-runda protokoll med optimal entropi förlust för säkerhetsparameter upp till s =  på (k), vilket förbättrar entropi förlust och kommunikation komplexiteten i protokollet i [Li12b]. * Stöds av ett Simons postdoktorskt stipendium.
Han konstruerade sedan explicit icke-förståeliga kondensatorer för entropi så liten som k = polylog(n) i REF och använde dem för att ge de första två runda integritetsförstärkning protokoll med optimal entropi förlust O(s), med förbehåll för begränsningen att k ≥ s 2.
Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}