Optimal randomizer efficiency in the bounded-storage model
type: Item
instance of: scholarly article
title: Optimal randomizer efficiency in the bounded-storage model
zbMATH Open document ID: 1077.94015
author: Stefan Dziembowski
author: Ueli M. Maurer
published in: Journal of Cryptology
publication date: 2004-09-22T00:00:00Z
full work available at URL: 145 2003 Article 309.pdf
review text: 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.
reviewed by: Nicolae Constantinescu
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 94A17
Mathematics Subject Classification ID: 68P25
zbMATH DE Number: 2102326
zbMATH Keywords: bounded-storage model
zbMATH Keywords: unconditional security
zbMATH Keywords: one-time pad
zbMATH Keywords: information theory
zbMATH Keywords: min-entropy
Wikidata QID: Q99673058
MaRDI profile type: Publication
OpenAlex ID: W2085355422
DBLP publication ID: journals/joc/DziembowskiM04
DOI: 10.1007/S00145-003-0309-Y
description: scientific article; zbMATH DE number 2102326