1109.1943 (J. Bouda et al.)

Encryption with Weakly Random Keys Using Quantum Ciphertext    [PDF]

J. Bouda, M. Pivoluska, M. Plesch

The lack of perfect randomness can cause significant problems in securing
communication between two parties. McInnes and Pinkas proved that
unconditionally secure encryption is impossible when the key is sampled from a
weak random source. The adversary can always gain some information about the
plaintext, regardless of the cryptosystem design. Most notably, the adversary
can obtain full information about the plaintext if he has access to just two
bits of information about the source (irrespective on length of the key). In
this paper we show that for every weak random source there is a cryptosystem
with a classical plaintext, a classical key, and a quantum ciphertext that
bounds the adversary's probability p to guess correctly the plaintext strictly
under the McInnes-Pinkas bound, except for a single case, where it coincides
with the bound. In addition, regardless of the source of randomness, the
adversary's probability p is strictly smaller than 1 as long as there is some
uncertainty in the key (Shannon/min-entropy is non-zero). These results are
another demonstration that quantum information processing can solve
cryptographic tasks with strictly higher security than classical information
processing.

View original: http://arxiv.org/abs/1109.1943