In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t-bit string R is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. If s < t, the adversary can store only partial information about R. The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n-bit one-time pad X with n jKj about which the adversary has essentially no information, thus at rst glance apparently contradicting Shannon's bound on the key size of a perfect cipher.
In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t-bit string R is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. If s < t, the adversary can store only partial information about R. The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n-bit one-time pad X with n jKj about which the adversary has essentially no information, thus at rst glance apparently contradicting Shannon's bound on the key size of a perfect cipher.
(MATH) In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t-bit string R is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. If s$xi;t, the adversary can store only partial information about R. The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n-bit one-time pad X with n»|K| about which the adversary has essentially no information, thus at first glance apparently contradicting Shannon's bound on the key size of a perfect cipher.All previous results in the bounded-storage model were partial or far from optimal, for one of the following reasons: either the secret key K had in fact to be longer than the derived one-time pad, or t had to be extremely large (tρns), or the adversary was assumed to be able to store only actual bits of R rather than arbitrary s bits of information about R, or the adversary could obtain a non-negligible amount of information about X.In this paper we prove the first non-restricted security result in the bounded-storage model, exploiting the full potential of the model: K is short, X is very long (e.g. gigabytes), t needs to be only moderately larger than s, and the security proof is optimally strong. In fact, we prove that s/t can be arbitrarily close to 1 and hence the storage bound is essentially optimal.
In the bounded-storage model (BSM) for information-theoretic secure encryption and key agreement, one makes use of a random string whose length is greater than the assumed bound on the adversary Eve's storage capacity. The legitimate parties, Alice and Bob, execute a protocol, over an authenticated channel accessible to Eve, to generate a secret key about which Eve has essentially no information even if she has infinite computing power. The string is either assumed to be accessible to all parties or communicated publicly from Alice to Bob. While in the BSM one often assumes that Alice and Bob initially share a short secret key, and the goal of the protocol is to generate a much longer key, in this communication, we consider the bare BSM without any initially shared secret key. It is proved that in the bare BSM, secret key agreement is impossible unless Alice and Bob have themselves very high storage capacity, namely, . This proves the optimality of a scheme proposed by Cachin and Maurer.
In the bounded storage model introduced by Maurer, the adversary is computationally unbounded and has a bounded storage capacity. In this model, perfect secrecy is guaranteed by using a publicly available random string whose length is larger than the adversary storage capacity. The protocol proposed by Maurer is simple, from the perspective of implementation, and efficient, from the perspective of the initial secret key size and random string length. However, he provided the proof of the security for the case where the adversary can access a constant fraction of the random string and store onlyoriginal bitsof the random string. In this paper, we provide a new proof of the security of the protocol proposed by Maurer for the general bounded storage model, i.e., the adversary can access all bits of the random string, and store the output of any Boolean function on the string. We reaffirm that the protocol isabsolutely semantically securein the general bounded storage model.
We address the problem of the-security of cryptographic protocols in face of future advances in computing technology and algorithmic research. The problem stems from the fact may be deemed that computations which at a given point in time may be deemed infeasible, can, in the course of years or decades, be made possible with improved hardware and/or breakthroughs in code-breaking algorithms. In such cases, the security of historical , but nonetheless highly confidential data may be in jeopardy. We present a scheme for efficient secure two-party communication with provable everlasting security. The security is guaranteed in face of any future technological advances, given the current state of of the art. Furthermore, the security of the messages is also guaranteed even if the secret encryption/decryption key is revealed in the future, The scheme is based on the bounded storage model and provides information-theoretic security in this model. The bounded storage model postulates an adversary who is computationally unbounded, and is only bounded in the amount of storage (not computation space) available to store the output of his computation. The bound on the storage can be arbitrarily large (e.g., 100 Tbytes), as long as it is fixed. Given this storage bound, our protocols guarantee that even a computationally all powerful adversary gains no information about a message (except with a probability that is exponentially small in the security parameter k). The bound on storage space need only hold at the time of the message transmission. Thereafter, no additional storage space or, computational power can help the adversary in deciphering the message. We present two protocols. The first protocol, which elaborates on the autoregressive (AR) protocol of Aumann and Rabin (see Advances in Cryptology-Crypto '99, p. 65-79, 1999), employs a short secret key whose size is independent of the length of the message, but uses many public random bits. The second protocol uses an optimal number of public random bits, but employs a longer secret key. Our proof of security utilizes a novel linear algebraic technique.
Several protocols are presented that allow two parties Alice and Bob not sharing any secret information initially (except possibly a short key to be used for authentication) to generate a long shared secret key such that even an enemy Eve with unlimited computing power is unable to obtain a non-negligible amount of information (in Shannon's sense) about this key. Two different models are considered. In a first model we assume that Alice can send information to Bob over a noisy main channel but that Eve is able to receive the same information over a parallel independent noisy channel from Alice to Eve. In a second, more general model we assume that Alice, Bob and Eve receive the output of a random source (e.g., a satellite broadcasting random bits) over three independent individual channels. The condition that the channels be independent can be replaced by the condition that they be independent only to a known, arbitrarily small degree. We demonstrate that even when Eve's channel is sup...
Abstract. The main purpose of this paper is to show that public key encryption can be secure against the “encryption emulation ” attack (on the sender’s encryption) by computationally unbounded adversary, with one reservation: a legitimate receiver decrypts correctly with probability that can be made arbitrarily close to 1, but not equal to 1. 1. Summary of our claims We thought it would make sense to summarize, for the reader’s convenience, our two main claims in a separate section, before proceeding to a narrative introduction. In Section 3, we describe a public-key encryption protocol that allows Bob (the sender) to send secret information to Alice (the receiver), encrypted one bit at a time, so that: (1) Assuming that Eve (the adversary): (a) is computationally unbounded, (b) knows everything about Bob’s encryption algorithm and hardware, (c) does not know Alice’s algorithm for creating public key, then: she cannot decrypt any single bit correctly with probability> 3 4