We consider an Internet of battlefield things (IoBT) system in which multiple devices want to communicate securely with each other in the presence of an adversary with unbounded storage and unbounded computational power. We provide an information-theoretically secure protocol to exchange highly confidential messages among the devices in the system. The main idea behind the protocol is to provide one-time pad secret keys to exchange messages via using a random string that is securely shared among all the devices and pair-wise random secret keys established between each pair of devices. We show that the protocol provides ever-lasting security against the adversary with unbounded storage and unbounded computational power. More specifically, the protocol guarantees that the adversary gains no information about a message, except for an exponentially small probability in a security parameter. Moreover, we prove that revealing all the pair-wise secret keys does not provide any information to the adversary. In addition, we show that the pair-wise secret keys are established once to securely exchange multiple messages between devices in the system. Besides that, we prove that even if the random string is revealed to the adversary, the provided protocol is computationally secure.
We consider an Internet of battlefield things (IoBT) system in which multiple devices want to communicate securely with each other in the presence of an adversary with unbounded storage and unbounded computational power. We provide an information-theoretically secure protocol to exchange highly confidential messages among the devices in the system. The main idea behind the protocol is to provide one-time pad secret keys to exchange messages via using a random string that is securely shared among all the devices and pair-wise random secret keys established between each pair of devices. We show that the protocol provides ever-lasting security against the adversary with unbounded storage and unbounded computational power. More specifically, the protocol guarantees that the adversary gains no information about a message, except for an exponentially small probability in a security parameter. Moreover, we prove that revealing all the pair-wise secret keys does not provide any information to the adversary. In addition, we show that the pair-wise secret keys are established once to securely exchange multiple messages between devices in the system. Besides that, we prove that even if the random string is revealed to the adversary, the provided protocol is computationally secure.
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.
We propose efficient schemes for information-theoretically secure key exchange in the Bounded Storage Model (BSM), where the adversary is assumed to have limited storage. Our schemes generate a secret One Time Pad (OTP) shared by the sender and the receiver, from a large number of public random bits produced by the sender or by an external source. Our schemes initially generate a small number of shared secret bits, using known techniques. We introduce a new method to expand a small number of shared bits to a much longer, shared key.Our schemes are tailored to the requirements of sensor nodes and wireless networks. They are simple, efficient to implement and take advantage of the fact that practical wireless protocols transmit data in frames, unlike previous protocols, which assume access to specific bits in a stream of data.Indeed, our main contribution is twofold. On the one hand, we construct schemes that are attractive in terms of simplicity, computational complexity, number of bits read from the shared random source and expansion factor of the initial key to the final shared key. On the other hand, we show how to transform any existing scheme for key exchange in BSM into a more efficient scheme in the number of bits it reads from the shared source, given that the source is transmitted in frames.
Shannon showed that to achieve perfect secrecy in point-to-point communication, the message rate cannot exceed the shared secret key rate giving rise to the simple one-time pad encryption scheme. In this paper, we extend this work from point-to-point to networks. We consider a connected network with pairwise communication between the nodes. We assume that each node is provided with a certain amount of secret bits before communication commences. An eavesdropper with unlimited computing power has access to all communication and can hack a subset of the nodes not known to the rest of the nodes. We investigate the limits on information-theoretic secure communication for this network. We establish a tradeoff between the secure channel rate (for a node pair) and the secure network rate (sum over all node pair rates) and show that perfect secrecy can be achieved if and only if the sum rate of any subset of unhacked channels does not exceed the shared unhacked-secret-bit rate of these channels. We also propose two practical and efficient schemes that achieve a good balance of network and channel rates with perfect secrecy guarantee. This work has a wide range of potential applications for which perfect secrecy is desired, such as cyber-physical systems, distributed-control systems, and ad-hoc networks.
Shannon showed that to achieve perfect secrecy in point-to-point communication, the message rate cannot exceed the shared secret key rate giving rise to the simple one-time pad encryption scheme. In this paper, we extend this work from point-to-point to networks. We consider a connected network with pairwise communication between the nodes and assume that each node is provided with a certain amount of secret bits before communication commences. An eavesdropper with unlimited computing power has access to all communication and can hack a subset of the nodes not known to the rest of the nodes. We investigate the limits on information-theoretic secure communication with end-to-end encryption for this network. We establish a tradeoff between the secure channel rate (for a node pair) and the secure network rate (sum over all node pair rates) and show that information-theoretic secrecy can be achieved asymptotically if and only if the sum rate of any subset of unhacked channels does not exceed the shared unhacked-secret-bit rate of these channels. We also propose a practical scheme that achieves a good balance of network and channel rates with information-theoretic secrecy guarantee. This work has a wide range of potential applications for which strong secrecy is desired, such as cyber-physical systems, distributed-control systems, and ad-hoc networks.
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 propose efficient schemes for information-theoretically secure key exchange in the Bounded Storage Model (BSM), where the adversary is assumed to have limited storage. Our schemes generate a secret One Time Pad (OTP) shared by the sender and the receiver,from a large number of public random bits produced by the sender or by an external source. Our schemes initially generate a small number of shared secret bits, using known techniques. We introduce a new method to expand a small number of shared bits to a much longer, shared key.