Vereshchagin, Nikolai K. ;
Buhrman, Harry ;
Cristandl, Matthias ;
Koucky, Michal ;
Lotker, Zvi ;
PattShamir, Boaz
High Entropy Random Selection Protocols
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 4log^* 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 + 8log 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 3n/4 but still n/2  O(log n) minentropy. Therefore
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.
BibTeX  Entry
@InProceedings{vereshchagin_et_al:DSP:2008:1309,
author = {Nikolai K. Vereshchagin and Harry Buhrman and Matthias Cristandl and Michal Koucky and Zvi Lotker and Boaz PattShamir},
title = {High Entropy Random Selection Protocols},
booktitle = {Algebraic Methods in Computational Complexity},
year = {2008},
editor = {Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
number = {07411},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1309},
annote = {Keywords: Shannon entropy, Random string ds}
}
2008
Keywords: 

Shannon entropy, Random string ds 
Seminar: 

07411  Algebraic Methods in Computational Complexity

Issue date: 

2008 
Date of publication: 

2008 