Vi studerar komplexiteten i att säkert utvärdera aritmetiska kretsar över finita ringar. Denna fråga motiveras av naturliga säkra beräkningsuppgifter. Fokusering främst på fallet med två-part protokoll med säkerhet mot skadliga parter, våra främsta mål är att: (1) endast göra black-box samtal till ringen operationer och standard kryptografiska primitiver, och (2) minimera antalet sådana black-box samtal samt kommunikationen overhead. Vi presenterar flera lösningar som skiljer sig åt i sina effektivitets-, generalitets- och underliggande intrakterbarhetsantaganden. Dessa inkluderar: • Ett ovillkorligt säkert protokoll i OT-hybridmodellen som gör en svart-box användning av en godtycklig ring R, men där antalet ringoperationer växer linjärt med (en övre gräns på) log  på. • Beräkningssäkra protokoll i OT-hybridmodellen som gör en svart-box användning av en underliggande ring, och där antalet ringoperationer inte växer med ringstorleken. Protokollen bygger på varianter av tidigare intractability antaganden relaterade till linjära koder. I den mest effektiva instansen av dessa protokoll, tillämpas på en lämplig klass av fält, den (amorterade) kommunikationskostnaden är ett konstant antal fältelement per multiplikationsgrind och beräkningskostnaden domineras av O(log k) fältoperationer per grind, där k är en säkerhetsparameter. Dessa resultat utvidgar en tidigare metod av Naor och Pinkas för säker polynom utvärdering (SIAM J. Jämfört med 35(5), 2006). • Ett protokoll för ringarna Z m = Z/mZ som endast använder en svart låda med ett homomorfiskt krypteringsschema. När m är primtal, det (amorterade) antalet samtal till krypteringsschemat för varje port av kretsen är konstant. Alla våra protokoll är i själva verket UC-säkra i OT-hybrid modellen och kan generaliseras till multipart beräkning med ett godtyckligt antal skadliga parter.
REF lyckas att få kommunikation overhead av O( en log k) för en säkerhetsparameter k.
Secure Arithmetic Computation with No Honest Majority
{'venue': 'IACR Cryptology ePrint Archive', 'journal': 'IACR Cryptology ePrint Archive', 'mag_field_of_study': ['Computer Science']}