IACR News item: 06 March 2015
Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park
ePrint ReportIn this work we revisit this question and ask: what about protocols where players can send longer messages? Can increased communication allow for a larger fraction of corrupt players?
We introduce a model of \\emph{strong adaptive} corruptions, in which an adversary sees all messages sent by honest parties in any given round and, based on the message content, decides whether to corrupt a party (and alter its message or sabotage its delivery) or not. This is in contrast to the (classical) adaptive adversary who can corrupt parties only based on past messages, and cannot alter messages already sent.
We prove that any one-round coin-flipping protocol, \\emph{regardless of message length}, can be secure against at most $\\widetilde{O}(\\sqrt n)$ strong adaptive corruptions. Thus, increased message length does not help in this setting.
We then shed light on the connection between adaptive and strongly adaptive adversaries, by proving that for any symmetric one-round coin-flipping protocol secure against $t$ adaptive corruptions, there is a symmetric one-round coin-flipping protocol secure against $t$ strongly adaptive corruptions. Going back to the standard adaptive model, we can now prove that any symmetric one-round protocol with arbitrarily long messages can tolerate at most $\\widetilde{O}(\\sqrt n)$ adaptive corruptions.
At the heart of our results there is a new technique for converting any one-round secure protocol with arbitrarily long messages into a secure one where each player sends only $\\polylog(n)$ bits. This technique may be of independent interest.
Additional news items may be found on the IACR news page.