Vi löser ett långvarigt öppet problem som har strävat efter en fullständig karakterisering av (potentiellt randomiserade) finita funktioner för 2-partsberäkningar som är säkra mot aktiva motståndare. Sedan den första sådana fullständiga funktionen upptäcktes [Kilian, FOCS 1988], har frågan om vilka finita 2-partsfunktioner som är kompletta studerats i stor utsträckning, vilket leder till karakterisering i många speciella fall. I detta arbete löser vi helt och hållet detta problem. Vi tillhandahåller en polynomalgoritm för att testa om en 2-parts finita säker funktionsutvärdering (SFE) funktionalitet (eventuellt randomiserade) är komplett eller inte. De viktigaste verktygen i vår lösning är: • En formell linjär algebraisk uppfattning om redundans i en generell 2-parts randomiserad funktion. • En uppfattning om statistiskt testbara spel. En typ av interaktivt bevis i informations-teoretisk miljö där båda parter är beräknande obundna men skiljer sig i sin kunskap om en hemlighet. • En förlängning av den (svaga) konversationen av Shannons kanal som kodar teorem, där en motståndare kan välja den kanal som är baserad på dess vy. Vi visar att alla funktioner f, om de är fullständiga, kan genomföra någon (randomized) krets C med hjälp av endast O ( till C + δ) samtal till f, där σ är den statistiska säkerhetsparametern. Särskilt för varje tvåpartsfunktion g etablerar detta en universell uppfattning om dess kvantitativa "kryptografiska komplexitet" oberoende av installationen och har nära kopplingar till kretsens komplexitet. * Detta dokument är resultatet av sammanslagningen av två oberoende verk. Ett av dessa verk är tillgängligt online som [Kra13].
REF utökar studien och ger en karakterisering av alla finita tvåpartsfunktioner (inklusive randomiserade funktioner) som är kompletta mot skadliga motståndare.
A Full Characterization of Completeness for Two-Party Randomized Function Evaluation
{'venue': 'IACR Cryptology ePrint Archive', 'journal': 'IACR Cryptology ePrint Archive', 'mag_field_of_study': ['Computer Science']}