Weak randomness and quantum encryption
Seminar author:Jan Bouda
Event date and time:06/04/2012 09:30:am
Event location:IFAE seminar room (UAB)
Event contact:
Uniform randomness is a crucial part of many information processing systems,
including algorithms, data compression, communication complexity, and
cryptography. The randomness we encounter in the real-world in non-uniform,
usually as a consequence of imperfectness of the random number generator, or
due to the partial information the adversary has about the random bit
string. It turns out that for some problems it is not difficult to design a
solution tolerating a reasonable deviation from the uniform distribution,
including algorithmic problems, or e.g. message authentication. It is not
the case of encryption that vitally requires uniform randomness. In fact,
regardless of the cryptosystem, key and ciphertext length, knowledge of only
2 bits of key suffices to the adversary to determine the plaintext with
certainty in the classical world. We present a quantum encryption system
that is able to break the bound and show, that there is no direct equivalent
of the bound (i.e. no finite information about the key is sufficient for
this).