Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Foundations of Mobile Computing

Information security for sensors by overwhelming random sequences and permutations

Shlomi Dolev, Niv Gilboa, Marina Kopeetsky, Giuseppe Persiano, Paul G. Spirakis

Published Sep 16, 2010• 5 citations
Publisher

Abstract

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.

DOI
10.1145/1860684.1860694

Related papers

Information security for sensors by overwhelming random sequences and permutations

Shlomi Dolev, Niv Gilboa, Marina Kopeetsky +2 more

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.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 4, 2010•3 citations

The Bare Bounded-Storage Model: The Tight Bound on the Storage Requirement for Key Agreement

Stefan Dziembowski, Ueli M. Maurer

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.

IEEE Transactions on Information Theory•May 29, 2008•13 citations

Tight security proofs for the bounded-storage model

Stefan Dziembowski, Ueli M. Maurer

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.

ACM Symposium on Theory of Computing (STOC)•May 19, 2002•53 citations

Secure sharing of random bits over the Internet

Geraldo A. Barbosa

Although one-time pad encrypted files can be sent through Internet channels, the need for renewing shared secret keys have made this method unpractical. This work presents a scheme to turn practical the fast sharing of random keys over arbitrary Internet channels. Starting with a shared secret key sequence of length K_0 the users end up with a secure new sequence K >> K_0. Using these sequences for posteriori message encryption the legitimate users have absolute security control without the need for third parties. Additionally, the security level does not depend on the unproven difficulty of factoring numbers in primes. In the proposed scheme a fast optical random source generates random bits and noise for key renewals. The transmitted signals are recorded signals that carries both the random binary signals to be exchanged and physical noise that cannot be eliminated by the attacker. These signals allow amplification over the Internet network without degrading security. The proposed system is also secure against a-posteriori known-plaintext attack on the key. Information-theoretic analysis is presented and bounds for secure operation are quantitatively determined.

arXiv:0705.2243•May 15, 2007•0 citations

A secret key establishment protocol for wireless networks using noisy channels

Albert Guan, Wen-Guey Tzeng

An efficient protocol for establishing secret keys for neighboring nodes in a wireless network is presented in this paper. The security of the key generated by our protocol is based on the unpredictability of the noises in binary symmetric communication channels. The two nodes which try to establish a common secret key receive messages from a common source of random bit strings. Due to noises in the communication channel, the messages received by them, and most importantly the messages received by the eavesdropper, are not the same. We show that the two nodes can modify their messages in an efficient way to obtain a common string which contains enough uncertainty to the eavesdropper. Then, a secure universal hash function is applied to compute a secret key for extracting randomness from the common string. We prove that the probability for the eavesdropper to know the value of the key is negligible. One advantage of our proposed protocol is that the secret key rate is better than the known scheme in other models, such as the bounded storage model. Furthermore, our proposed protocol needs only to perform exclusive-or operations and compute hash values. Thus, it is a computationally light-weight protocol and suitable for devices with limited computing resources, such as sensors in sensor networks.

Journal of Computer Security•Feb 24, 2017•3 citations

Exchanging Secrets without Using Cryptography

Iris Safaka, Siavoshani, Mahdi J., Pulleti, Uday +4 more

We consider the problem where a group of n nodes, connected to the same broadcast channel (e.g., a wireless network), want to generate a common secret bitstream, in the presence of an adversary Eve, who tries to obtain information on the bitstream. We assume that the nodes initially share a (small) piece of information, but do not have access to any out-of-band channel. We ask the question: can this problem be solved without relying on Eve's computational limitations, i.e., without using any form of public-key cryptography? We propose a secret-agreement protocol, where the n nodes of the group keep exchanging bits until they have all agreed on a bit sequence that Eve cannot reconstruct with very high probability. In this task, the nodes are assisted by a small number of interferers, whose role is to create channel noise in a way that bounds the amount of information Eve can overhear. Our protocol has polynomial-time complexity and requires no changes to the physical or MAC layer of network devices. First, we formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure, achieves optimal secret-generation rate for n = 2 nodes, and scales well to an arbitrary number of nodes. Second, we adapt our protocol to a small wireless 14-square-meter testbed; we experimentally show that, if Eve uses a standard wireless physical layer and is not too close to any of the nodes, 8 nodes can achieve a secret-generation rate of 38 Kbps. To the best of our knowledge, ours is the first experimental demonstration of information-theoretic secret exchange on a wireless network at a rate beyond a few tens of bits per second.

arXiv:1105.4991•May 25, 2011•14 citations
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.
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.
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 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.
Although one-time pad encrypted files can be sent through Internet channels, the need for renewing shared secret keys have made this method unpractical. This work presents a scheme to turn practical the fast sharing of random keys over arbitrary Internet channels. Starting with a shared secret key sequence of length K_0 the users end up with a secure new sequence K >> K_0. Using these sequences for posteriori message encryption the legitimate users have absolute security control without the need for third parties. Additionally, the security level does not depend on the unproven difficulty of factoring numbers in primes. In the proposed scheme a fast optical random source generates random bits and noise for key renewals. The transmitted signals are recorded signals that carries both the random binary signals to be exchanged and physical noise that cannot be eliminated by the attacker. These signals allow amplification over the Internet network without degrading security. The proposed system is also secure against a-posteriori known-plaintext attack on the key. Information-theoretic analysis is presented and bounds for secure operation are quantitatively determined.
An efficient protocol for establishing secret keys for neighboring nodes in a wireless network is presented in this paper. The security of the key generated by our protocol is based on the unpredictability of the noises in binary symmetric communication channels. The two nodes which try to establish a common secret key receive messages from a common source of random bit strings. Due to noises in the communication channel, the messages received by them, and most importantly the messages received by the eavesdropper, are not the same. We show that the two nodes can modify their messages in an efficient way to obtain a common string which contains enough uncertainty to the eavesdropper. Then, a secure universal hash function is applied to compute a secret key for extracting randomness from the common string. We prove that the probability for the eavesdropper to know the value of the key is negligible. One advantage of our proposed protocol is that the secret key rate is better than the known scheme in other models, such as the bounded storage model. Furthermore, our proposed protocol needs only to perform exclusive-or operations and compute hash values. Thus, it is a computationally light-weight protocol and suitable for devices with limited computing resources, such as sensors in sensor networks.
We consider the problem where a group of n nodes, connected to the same broadcast channel (e.g., a wireless network), want to generate a common secret bitstream, in the presence of an adversary Eve, who tries to obtain information on the bitstream. We assume that the nodes initially share a (small) piece of information, but do not have access to any out-of-band channel. We ask the question: can this problem be solved without relying on Eve's computational limitations, i.e., without using any form of public-key cryptography? We propose a secret-agreement protocol, where the n nodes of the group keep exchanging bits until they have all agreed on a bit sequence that Eve cannot reconstruct with very high probability. In this task, the nodes are assisted by a small number of interferers, whose role is to create channel noise in a way that bounds the amount of information Eve can overhear. Our protocol has polynomial-time complexity and requires no changes to the physical or MAC layer of network devices. First, we formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure, achieves optimal secret-generation rate for n = 2 nodes, and scales well to an arbitrary number of nodes. Second, we adapt our protocol to a small wireless 14-square-meter testbed; we experimentally show that, if Eve uses a standard wireless physical layer and is not too close to any of the nodes, 8 nodes can achieve a secret-generation rate of 38 Kbps. To the best of our knowledge, ours is the first experimental demonstration of information-theoretic secret exchange on a wireless network at a rate beyond a few tens of bits per second.