

Symposium on logic and computability "Logic and Computation Day"
June 7, 2013 11:00–11:45, Moscow, Steklov Mathematical Institute of RAS






High Entropy Random Selection Protocols
N. K. Vereshchagin^{} ^{} M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Number of views: 
This page:  57 

Abstract:
We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy $n  O(1)$ and has $4 \log^* n$ rounds, improving over the protocol of Goldwasser et.al. that also achieves this entropy but needs $O(n)$ rounds. Both these protocols need $O(n^2)$ bits of communication. Next we reduce the communication in our protocols. We show the existence, nonexplicitly, of a protocol that has 6rounds, $2n + 8\log n$ bits of communication and yields entropy $n  O(\log n)$ and minentropy $n/2  O(\log n)$. Our protocol achieves the same entropy bound as the recent, also nonexplicit, protocol of Gradwohl et.al., however achieves much higher minentropy: $n/2  O(\log n)$ versus $O(\log n)$. Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy $(3/4)n$ but still $n/2  O(\log n)$ minentropy. Therefor they do not perform as well with respect to the explicit constructions of Gradwohl et.al. entropywise, but still have much better minentropy. We conjecture that these simple protocols achieve $n  o(n)$ entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols. Based on joint paper with Harry Buhrman, Matthias Christandl, Michal Koucky, Zvi Lotker, Boaz PattShamir.
Language: English

