Optimal randomizer efficiency in the bounded-storage model (Q1879466)

This paper deals with information theoretically secure encryption and key agreement. This means that secure expansion of a short secret key into a much longer key is considered in the bounded-storage model. Such model is based, contrary to classical and practical cryptographic systems, only on the sole assumption that the adversary Eve can store only \(s\) bits, even if her computational power is unlimited. The communicating parties, Alice and Bob generate their key, which is a one-time pad, based on a publicly available source of random bits which can output a string of bits \(R\) of length \(t\). The one-time pad \(X\) of length \(n\) is also based on the shorter key \(K\), therefore suiting both the one time pad and the key the adversary can gain no information on the ciphertext. The main contribution of the paper is providing a stronger security proof. This comprises of the observation of the inability of the adversary to correctly predict the last bit of the expanded key even if she has access to all previous key bits and proving the negligeability of any strategy the adversary chooses for the faction of randomizers that give her a non-negligible advantage. The first three sections of the paper are introductory to the matter, sections 4 and 5 deal with parameter sizes closest to practical interest. Reasonable parameter sizes studied in previous sections lead to the conclusion that randomness efficiency \(v\) should be in the range 10. Open problems remain as the authors wonder about the security of proposed schemes under the assumption of an adversary with the ability to store \(s\) quantum bits rather than \(s\) classical bits.