Abstrakt. För säker tvåparts- och flerpartsberäkning med abort har klassificering av vilka primitiver är fullständiga studerats ingående i litteraturen. Men för en rättvis säker beräkning, där (i stort sett) antingen alla parter lär sig produktionen eller ingen gör det, har frågan om fullständiga primitiver i stort sett förblivit ostuderad. I detta arbete initierar vi en rigorös studie av fullständighet för primitiver som möjliggör rättvisa beräkningar. Vi visar följande resultat: -Ingen "kort" primitiv är komplett för rättvisa. I överraskande kontrast till andra begrepp om säkerhet för säker tvåpartsberäkning, visar vi att för rättvis säker beräkning, ingen primitiv storlek O (log k) är komplett, där k är en säkerhetsparameter. Så är fallet även om vi kan genomdriva parallellism i anrop till de primitiva (dvs, motståndaren får inte produktion från någon primitiv i en parallell anrop tills den skickar input till dem alla). Detta negativa resultat gäller oavsett eventuella beräkningsantaganden. - En rättvis hierarki. Vi förtydligar rättvisa landskapet ytterligare genom att visa förekomsten av en "rättvisa hierarki". Vi visar att för varje "kort" = O(log k), ingen protokoll gör (serial) tillgång till någon -bit primitiv kan användas för att konstruera även en ( + 1)-bitars samtidig sändning. -Positiva resultat. För att komplettera de negativa resultaten uppvisar vi en k-bit primitiv som är komplett för två-parts rättvis säker beräkning. Vi visar hur man generaliserar detta resultat till multi-party inställning. -Fairness-kombinationer. Vi introducerar också frågan om att bygga ett protokoll för rättvis säker beräkning från primitiva som kan vara felaktiga. Vi visar att detta är möjligt när en majoritet av fallen är ärliga. På flip-sidan visar vi att detta resultat är tight: ingen funktionalitet är komplett för rättvisa om hälften (eller mer) av fallen kan vara skadliga.
En omfattande studie av fullständiga primitiver för rättvisa kan hittas i REF.
On Complete Primitives for Fairness
{'venue': 'TCC', 'journal': None, 'mag_field_of_study': ['Computer Science']}