5.10 Matej Pivoluska - Encryption with Weakly Random Keys Using Quantum Ciphertext
- Details
- Category: Autumn 2011
- Published on Thursday, 29 September 2011 14:08
- Written by Super User
- Hits: 835
Weakly Random Keys Using Quantum Ciphertext
Matej Pivoluska, FI MUNI
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, adversary can obtain full information
about the plaintext if only two bits of the source are
fixed (if the key is sampled from a distribution on n-bits,
for which the probability of each element is bounded from above by
1/(2^(n-2)).
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 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
demonstrate that quantum information processing can solve
cryptographic tasks with strictly higher security than
classical information processing.