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.
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.
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 this paper, we propose a new provably secure cryptosystem for two party communication that provides security in the face of new technological breakthroughs. Most of the practical cryptosystems in use today can be breached in the future with new sophisticated methods. This jeopardizes the security of older but highly confidential messages. Our protocol is based on the bounded storage model first introduced in [1]. The protocol is secure as long as there is bound on the storage, however large it may be. We also suggest methods to extend the protocol to unbounded storage models where access to adversary is limited. Our protocol is a substantial improvement over previously known protocols and uses short key and optimal number of public random bits size of which is independent of message length. The smaller and constant length of key and public random string makes the scheme more practical. The protocol generates key using elements of the additive groupZn. Our protocol is very generalized and the protocol in [1] is a special case of our protocol. Our protocol is a step forward in making provably secure cryptosystems practical. An important open problem raised in [2] was designing an algorithm with short key and size of public random stringO(B)whereBbounds the storage of adversary. Our protocol satisfies the conditions and is easy to implement.
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.
(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.
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.
We provide an encryption protocol for storing highly confidential data of a user on a public cloud storage. We show that the protocol provides unconditional security. More specifically, we prove that the protocol is semantically secure against an all-powerful adversary with unbounded computational power and storage capacity who has complete access to the communication line. The provided protocol is very simple, it is implemented by exploiting finite group modular addition and XOR operations. The protocol provides a high security gain defined as the ratio of the amount of data (in bits) that can be securely stored on the public cloud and the number of secret bits required to be stored at the user end. As an illustrative example, according to the protocol, by using 40.2 Terabytes (TBs) of secret bits, a user is able to store 5.9 ×108TBs of data on a public storage with guaranteed everlasting security.