High Entropy Random Selection Protocols

摘要: We study the two party problem of randomly selecting a string among all strings length n. want protocol to have property that output distribution has high entropy, even when one parties is dishonest and deviates from protocol. develop protocols achieve high, close n, entropy. In literature randomness guarantee usually expressed as being uniform or in terms resiliency. The notion entropy not directly comparable resiliency, but we establish connection between allows us compare our with existing ones. We construct an explicit yields ni¾? O(1) 4log*nrounds, improving over Goldreich et al. [3] also achieves this needs O(n) rounds. Both these need O(n2) bits communication. Next reduce communication protocols. show existence, non-explicitly, 6 rounds, 2n+ 8lognbits O(logn) min-entropy n/2 i¾? O(logn). Our same bound recent, non-explicit, Gradwohl [4], however much higher min-entropy: versus O(logn). Finally exhibit very simple connect security parameter geometric well studied Kakeya motivated by harmonic analysis analytical number theory. are only able prove 3n/4 still min-entropy. Therefore they do perform respect constructions [4] entropy-wise, better conjecture o(n) entropy. construction its relation follows new different approach random selection than any previously known