Fair enough

Blog about  “On the Classification of Finite Boolean Functions up to Fairness” by Nikolaos Makriyannis.

Written by Carsten Baum

Nikolaos gave a talk about finite boolean functions (think about some finite sets X, Y and the functions mapping from X x Y to {0,1}) and which of those are actually computable by two parties in a fair way. Fair here means that, if at least one party gets the output, then both of them do. There is a classic result by Cleve (C’86) that shows that there is no way how one can implement secure fair coin flipping between two parties, and there have been two recent lines of work:

1. GHKL’08 showed that there exists a protocol such that one is possible to compute a certain set of functions in a fair way. Asharov then showed in A’14 a classification of functions that one can evaluate using the GHKL’08 protocol.
2. Based on C’86, every function that implies secure coin flipping cannot be evaluated in a fair way. ALR’13 gave a classification of functions that imply secure coin flipping.

The talk was about extensions on both lines of work. First, he gave a definition with two properties of a function that can be used to determine whether GHKL can be applied (which are quite technical so I refer to the paper here). Second, he shows that a larger class of functions imply coin flipping. His proof relies on the fact that sampling of random variables under certain conditions implies secure coin flipping, so these instances of sampling must be impossible as well. He then shows that so-called “semi-balanced functions” imply sampling. This extends the result of ALR’13.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s