Divesh Aggarwal

Does Privacy Require True Randomness?


In TCC 2007, Bosley and Dodis [BD07] studied the question of whether
true randomness is inherent for achieving privacy, i.e. one can
deterministically extract nearly b almost unbiased random bits from
the secret key used to encrypt b-bit messages, and showed a positive
answer for the case of information-theoretic private-key encryption,
as well as computationally secure perfectly-binding primitives. An
interesting open question is whether these result can be extended to
other privacy primitives. In particular, can the same be said about
2-out-of-2 secret sharing schemes, which are strictly implied by
private-key encryption.

I will present the result from [BD07] and discuss some ideas regarding
the question of extracting randomness from the secret key used in a
secure 2-out-of-2 sharing scheme.