Abstrakt. På grund av dess universalitet oöverträffad överföring (OT) är en primitiv av stor betydelse för säker flerpartiberäkning. OT är omöjligt att genomföra från grunden på ett villkorslöst säkert sätt, men det finns många minskningar av OT till andra varianter av OT, såväl som andra primitiva såsom bullriga kanaler. Det är viktigt att veta hur effektiva sådana ovillkorligt säkra minskningar kan vara i princip, d.v.s. hur många fall av en given primitiv åtminstone behövs för att genomföra GT. För perfekta (terrorfria) implementationer är bra nedre gränser kända, t.ex. Gränserna till Bäver (STOC '96) eller Dodis och Micali (EUROCRYPT '99). I praktiken är man dock vanligtvis villig att tolerera en liten sannolikhet för fel och det är känt att dessa statistiska minskningar i allmänhet kan vara mycket effektivare. De kända gränserna har således endast begränsad tillämpning. I den första delen av detta arbete ger vi gränser för effektiviteten av säker (ensidig) tvåpartiberäkning av godtyckliga finita funktioner från distribuerad slumpmässighet i det statistiska fallet. Av dessa resultat härleder vi gränser för effektiviteten hos protokoll som använder (olika varianter av) GT som en svart låda. När det tillämpas på implementeringar av OT, våra gränser generalisera kända resultat till det statistiska fallet. Våra resultat håller i synnerhet för omvandlingar mellan ett ändligt antal primitiva och för varje fel. Dessutom ger vi gränser för effektiviteten i protokoll som genomför Rabin OT. I den andra delen studerar vi effektiviteten i kvantprotokoll som implementerar OT. Nyligen visade Salvail, Schaffner och Sotakova (ASIACRYPT '09) att de flesta klassiska lägre gränser för fullkomligt säkra minskningar av GT till distribuerad slumpmässighet fortfarande håller i en kvantinställning. Vi presenterar ett statistiskt säkert protokoll som bryter mot dessa gränser av en godtyckligt stor faktor. Vi presenterar sedan en svagare nedre gräns som håller i den statistiska kvantinställningen. Vi använder detta för att visa att inte ens kvantprotokollen kan förlänga OT. Slutligen presenterar vi två lägre gränser för minskningar av OT till åtaganden och ett protokoll baserat på stränga åtaganden som är optimalt med avseende på båda dessa gränser.
Winkler och Wulschlegger REF visar en lägre gräns för den korrelerade slumpmässighet komplexiteten i säker tvåpartsberäkning.
On the efficiency of classical and quantum oblivious transfer reductions
{'venue': 'CRYPTO', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}