Non-malleable extractors and symmetric key cryptography from weak secrets

FREE-DOWNLOAD Y Dodis… – Proceedings of the 41st annual ACM symposium …, 2009 –
We study the question of basing symmetric key cryptogra- phy on weak secrets. In this
setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the
adversary has at least k bits of uncertainty about it (formalized using conditional