Fairness in two-party computation : characterizing fair functions

Author

Makriyannis, Nikolaos

Director

Daza, Vanesa ORCID

Date of defense

2016-09-20

Pages

166 p.



Department/Institute

Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions

Doctorate programs

Programa de doctorat en Tecnologies de la Informació i les Comunicacions

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ó.

Keywords

Cryptography; Two-Party Computation; Malicious adversaries; Fairness

Subjects

62 - Engineering. Technology in general

Documents

tnm.pdf

1012.Kb

 

Rights

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/

This item appears in the following Collection(s)