En rättvis två-parts myntkastning protokoll är ett där båda parter producerar samma bit som är nästan jämnt fördelade (dvs, det är lika med 0 och 1 med sannolikhet som är som mest negligerbart långt från hälften). Det är väl känt att det är omöjligt att uppnå rättvisa mynt kasta även i närvaro av fail-stop motståndare (Cleve, FOCS 1986). I själva verket, Cleve visade att för varje mynt kasta protokoll körs för r rundor, en effektiv fail-stop motståndare kan förvränga produktionen genom  på (1/r). Eftersom detta är det bästa möjliga kallas ett protokoll som begränsar varje motståndares partiskhet mot O(1/r) optimalt rättvist. Det enda optimala protokollet som är känt för att existera bygger på förekomsten av oöverträffad överföring, eftersom det använder allmänna säkra beräkningar (Moran, Naor och Segev, TCC 2009). Det är dock möjligt att uppnå en bias av O(1/ ε r) i r rundor endast beroende på antagandet att det finns enkelriktade funktioner. I detta papper visar vi att det är omöjligt att uppnå optimalt rättvis myntkastning via en svart låda konstruktion från enkelriktade funktioner för r som är mindre än O (n/ log n), där n är in-/utgångslängden för den enkelriktade funktion som används. En viktig följd av detta är att det är omöjligt att konstruera ett optimalt rättvist myntkastningsprotokoll via en svart låda konstruktion från enkelriktade funktioner vars runda komplexitet är oberoende av säkerhetsparametern n som bestämmer säkerheten för den enkelriktade funktion som används. Informellt sett är huvudingrediensen i vårt bevis att eliminera slumpmässig-orraklet från "säkra" protokoll med "låg rund-komplexitet" och simulera protokollet säkert mot halvhederliga motståndare i den enkla modellen. Vi anser att vår simuleringslemma är av större intresse.
Mer specifikt visar REF hur man "kompilerar ut" den slumpmässiga orakel från mynt-till-protokollet genom att fråga (poly(n)r oracle frågor av parterna varr är antalet rundor i protokollet.
On the Black-Box Complexity of Optimally-Fair Coin Tossing
{'venue': 'TCC', 'journal': None, 'mag_field_of_study': ['Computer Science']}