International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Nikolaos Makriyannis

Affiliation: Universitat Pompeu Fabra

Publications

Year
Venue
Title
2019
TCC
On Fully Secure MPC with Solitary Output
We study the possibility of achieving full security, with guaranteed output delivery, for secure multiparty computation of functionalities where only one party receives output, to which we refer as solitary functionalities. In the standard setting where all parties receive an output, full security typically requires an honest majority; otherwise even just achieving fairness is impossible. However, for solitary functionalities, fairness is clearly not an issue. This raises the following question: Is full security with no honest majority possible for all solitary functionalities?We give a negative answer to this question, by showing the existence of solitary functionalities that cannot be computed with full security. While such a result cannot be proved using fairness-based arguments, our proof builds on the classical proof technique of Cleve (STOC 1986) for ruling out fair coin-tossing and extends it in a nontrivial way.On the positive side, we show that full security against any number of malicious parties is achievable for many natural and useful solitary functionalities, including ones for which the multi-output version cannot be realized with full security.
2018
TCC
On the Complexity of Fair Coin Flipping
Iftach Haitner Nikolaos Makriyannis Eran Omri
A two-party coin-flipping protocol is $$\varepsilon $$ε-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $$\varepsilon $$ε. Cleve [STOC ’86] showed that r-round o(1 / r)-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript ’85] constructed a $$\varTheta (1/\sqrt{r})$$Θ(1/r)-fair coin-flipping protocol, assuming the existence of one-way functions. Moran et al. [Journal of Cryptology ’16] constructed an r-round coin-flipping protocol that is $$\varTheta (1/r)$$Θ(1/r)-fair (thus matching the aforementioned lower bound of Cleve [STOC ’86]), assuming the existence of oblivious transfer.The above gives rise to the intriguing question of whether oblivious transfer, or more generally “public-key primitives”, is required for an $$o(1/\sqrt{r})$$o(1/r)-fair coin flipping. This question was partially answered by Dachman-Soled et al. [TCC ’11] and Dachman-Soled et al. [TCC ’14], who showed that restricted types of fully black-box reductions cannot establish $$o(1/\sqrt{r})$$o(1/r)-fair coin-flipping protocols from one-way functions. In particular, for constant-round coin-flipping protocols, [10] yields that black-box techniques from one-way functions can only guarantee fairness of order $$1/\sqrt{r}$$1/r.We make progress towards answering the above question by showing that, for any constant , the existence of an $$1/(c\cdot \sqrt{r})$$1/(c·r)-fair, r-round coin-flipping protocol implies the existence of an infinitely-often key-agreement protocol, where c denotes some universal constant (independent of r). Our reduction is non black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner et al. [FOCS ’18] to facilitate a two-party variant of the attack of Beimel et al. [FOCS ’18] on multi-party coin-flipping protocols.
2017
TCC
2015
TCC
2014
EPRINT

Program Committees

TCC 2019