Abstrakt. Protokoll för säker multipartsberäkning (MPC) kan delas in i två typer: (1) protokoll som endast garanterar säkerhet i närvaro av en ärlig majoritet, och (2) protokoll som garanterar säkerhet även om det inte finns någon ärlig majoritet. Kända protokoll av den första typen är vanligtvis mycket effektivare än kända protokoll av den andra typen. Detta gäller även i hybridmodeller som tillåter oraklet tillgång till idealiska kryptografiska primitiva såsom oöverträffad överföring (OT). Motiverade av denna effektivitetsklyfta presenterar vi en effektiv kompilator för att omvandla MPC-protokoll av den första typen till MPC-protokoll av den andra typen i OT-hybridmodellen. Mer allmänt kombinerar vår kompilator ett protokoll av den första typen med ett protokoll av den andra typen, men där säkerheten hos den senare bara behöver hålla emot halvhederliga motståndare. Denna kompilator följer metoden "MPC in the Head" som initierades av Ishai, Kushilevitz, Ostrovsky och Sahai (STOC '07) och vidareutvecklades av Harnik, Ishai, Kushilevitz och Nielsen (TCC '08). Genom att kombinera vår kompilator med varianter av protokoll från litteraturen får vi flera applikationer för säker tvåpartsberäkning och för MPC utan ärlig majoritet. Dessa inkluderar: -Constant-rate två-parts beräkning i OT-hybrid modellen. Genom att applicera vår kompilator på en variant av ett effektivt MPC-protokoll från Damgård och Ishai (Crypto '06), får vi ett statistiskt (UC) säkert tvåpartsprotokoll i OT-hybridmodellen som kan utvärdera en generell krets C av storlek s med en total kommunikations komplexitet av O(s). (För enkelhetens skull ignorerar vi härifrån på additiva termer som beror polynomiskt på säkerhetsparametern k, kretsdjupet och log s. Dessa termer domineras av den ledande termen i de flesta typiska fall av stora kretsar.) Detta förbättrar över O(k 3 s) komplexiteten i det bästa tidigare protokollet, och matchar den bästa asymptotiska komplexiteten i semi-honest modellen. Ovanstående resultat generaliseras till ett konstant antal parter. Stöds delvis av ISF-bidrag 1310/06, BSF-bidrag 2004361 och NSF-bidrag 0205594, 0430254, 0456717, 0627781, 0716389. Delvis med stöd av NSF beviljar CNS 07-16626 och CNS 07-47027. Denna forskning stöddes delvis från NSF-bidrag 0627781, 0716389, 0456717, och 0205594, ett subbidrag från SRI som en del av Army Cyber-TA-programmet, ett utrustningsbidrag från Intel, en Alfred P. Sloan Foundation Fellowship, och en Okawa Foundation Research Grant. - Förlänga GTs i den illvilliga modellen. Vi får ett protokoll för att generera många GTs från få GTs vars amorterade kostnad i kommunikation och kryptografisk beräkning är en konstant multipel av det effektiva protokollet för den halvhederliga modellen som ges av Ishai, Kilian, Nissim och Petrank (Crypto '03). Detta protokoll kan användas för att effektivt implementera en off-line precomputation av GTs som krävs av våra protokoll i OT-hybrid-modellen. -Black-box konstruktioner för konstant runt MPC utan ärlig majoritet. Vi tillämpar vår allmänna kompilator på en variant av ett MPC-protokoll från Damgård och Ishai (Crypto '05) för att få allmänna beräkningssäkra MPC-protokoll i OT-hybridmodellen som endast använder ett konstant antal rundor, och bara göra en svart-box tillgång till en pseudorandom generator. Detta ger ett mycket annorlunda alternativ till ett liknande resultat för de två partifall som nyligen erhölls av Lindell och Pinkas (Eurocrypt '07), och ger de första konstant-runda protokoll för tre eller fler parter som bara gör en svart-box användning av kryptografiska primitiva (och undvika dyra noll-kunskap bevis).
Nyligen, Ishai et al. konstruerade UC säkra protokoll med skadlig majoritet i OT hybrid modell körs i (stora) konstanta rundor REF (se bild 1).
Founding Cryptography on Oblivious Transfer --- Efficiently
{'venue': 'CRYPTO', 'journal': None, 'mag_field_of_study': ['Computer Science']}