Fairness in two-party computation : characterizing fair functions

Abstract

Secure two-party computation is a classic problem in cryptography. It involves two parties computing a function of their private inputs, and only revealing what the output suggests. Additional security requirements may include fairness, which states that either all parties receive output, or no one does. A seminal result from the 1980's demonstrates that fairness cannot be guaranteed for all functions, and only recently have certain functions been shown to be computable with fairness. The two results naturally give rise to a distinction between fair functions and unfair ones. In this work, we investigate the characterization of such functions in the two-party setting. In the end, we obtain a full characterization for Boolean functions, and we develop a number of useful techniques for characterizing arbitrary fair functions.

Secure two-party computation és un problema clàssic en criptografia. Dos participants acorden calcular una funció de les seves entrades privades, de manera que només es revela el que se'n derivi del resultat. Altres requisits de seguretat poden incloure fairness, que exigeix que o bé tots els participants obtenen el resultat, o ningú ho fa. Un resultat fonamental de la dècada dels 80 demostra que la propietat no es pot garantir per a totes les funcions, i només recentment s'ha demostrat que algunes sí que tenen aquesta propietat. Els dos resultats donen lloc a una distinció entre les funcions que són fair, i les que no ho són. En aquest treball, investiguem la caracterització d'aquestes funcions en l'entorn de dos participants, obtenint una caracterització completa de funcions Booleanes. A més a més, desenvolupem una sèrie de tècniques útils per caracteritzar qualsevol funció.