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,
  non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits
  of communication and yields entropy n- O(log n) and min-entropy
  n/2 - O(log n). Our protocol achieves the same entropy bound as
  the recent, also non-explicit, protocol of Gradwohl
  et al., however achieves much higher min-entropy: 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) min-entropy. Therefore
  they do not perform as well with respect to the explicit
  constructions of Gradwohl et al. entropy-wise, but still
  have much better min-entropy.  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.