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

IEEE Information Theory Workshop (ITW)

Privacy amplification theorem for bounded storage eavesdropper

Shun Watanabe, Yasutada Oohama

Published Sep 1, 2012• 6 citations
Publisher

Abstract

In this paper, we consider a situation such that legitimate parties, Alice and Bob, share an identical source to generate a secret key, and an eavesdropper, Eve, can access a correlated data that is stored in a storage with bounded size. Then, Alice and Bob want to extract a secret as long as possible. We show a privacy amplification theorem for this problem, i.e., we clarify the rate of key generation for given rate of Eve's storage. The problem can be regarded as a dual randomness generation problem of the Wyner-Ahlswede-Körner type source coding system, and the techniques used in the proof are exchanged, i.e., the so-called Markov lemma is used in the converse part, and the so-called image size characterization is used in the direct part.

DOI
10.1109/itw.2012.6404652

Related papers

Amplifying Privacy in Privacy Amplification.

Divesh Aggarwal, Yevgeniy Dodis, Zahra Jafargholi +2 more

We study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key R of length m over a public communication channel completely controlled by a computationally unbounded attacker Eve. Despite being extensively studied in the literature, the problem of designing “optimal ” efficient privacy amplification protocols is still open, because there are several optimization goals. The first of them is (1) minimizing the entropy loss L = k−m (it is known that the optimal value for L = O(λ), where ε = 2−λ is the desired security of the protocol). Other important considerations include (2) minimizing the number of communication rounds, (3) maintaining security even after the secret key is used (this is called post-application robustness), and (4) ensuring that the protocol P does not leak some “useful information ” about the source X (this is called source privacy). Additionally, when dealing with a very long source X, as happens in the so-called Bounded Retrieval Model (BRM), extracting as long a key as possible is no longer the goal. Instead, the goals are (5) to touch as little of X as possible (for efficiency), and (6) to be able to run the protocol many times on the same X, extracting multiple secure keys.

•Jan 1, 2013•0 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

Secrecy via Sources and Channels

Vinod M. Prabhakaran, Krishnan Eswaran, Kannan Ramchandran

Alice and Bob want to share a secret key and to communicate an independent message, both of which they desire to be kept secret from an eavesdropper Eve. This problem of secret communication and secret-key generation when two resources are available-correlated sources at Alice, Bob, and Eve, and a noisy broadcast channel from Alice to Bob and Eve which is independent of the sources is studied. The goal is to characterize the fundamental tradeoff between the rates of the secret message and secret key. An achievable solution and proof of its optimality for the parallel channels and sources case when each subchannel and source component satisfies a degradation order (either in favor of the legitimate receiver or the eavesdropper) is presented. This includes the case of jointly Gaussian sources and an additive Gaussian channel, for which the secrecy region is evaluated.

arXiv:0807.0942•IEEE Transactions on Information Theory•Jul 13, 2012•31 citations

Physical Layer Secret Key Generation in Static Environments

Nasser Aldaghri, Hessam Mahdavifar

Two legitimate parties, referred to as Alice and Bob, wish to generate secret keys from the wireless channel in the presence of an eavesdropper, referred to as Eve, in order to use such keys for encryption and decryption. In general, the secret key rate highly depends on the coherence time of the channel. In particular, a straightforward method of generating secret keys in static environments results in ultra-low rates. In order to resolve this problem, we introduce a low-complexity method called induced randomness. In this method, Alice and Bob independently generate local randomness to be used together with the uniqueness of the wireless channel coefficients in order to enable high-rate secret key generation. In this work, two scenarios are considered: first, when Alice and Bob share a direct communication channel, and second, when Alice and Bob do not have a direct link and communicate through an untrusted relay. After exchanging the induced randomness, post-processing is done by Alice and Bob to generate highly-correlated samples that are used for the key generation. Such samples are then converted into bits, disparities between the sequences generated by Alice and Bob are mitigated, and the resulting sequences are then hashed to compensate for the information leakage to the eavesdropper and to allow consistency checking of the generated key bit sequences. We utilize semantic security measures and information-theoretic inequalities to upper bound the probability of successful eavesdropping attack in terms of the mutual information measures that can be numerically computed. Given certain reasonable system parameters this bound is numerically evaluated to be 2-31and 2-10.57in the first and the second scenario, respectively.

arXiv:1908.03637•IEEE Transactions on Information Forensics and Security•Jan 1, 2020•202 citations

On the secret-key rate of binary random variables

Martin J. Gander, Ueli M. Maurer

Consider a scenario in which two parties Alice and Bob as well as an opponent Eve receive the output of a binary symmetric source (e,g. installed in a satellite) over individual, not necessarily independent binary symmetric channels. Alice and Bob share no secret key initially and can only communicate over a public channel completely accessible to Eve. The authors derive a lower bound on the rate at which Alice and Bob can generate secret-key bits about which Eve has arbitrarily little information, This lower bound is strictly positive as long as Eve's binary symmetric channel is not perfect, even if Alice's and Bob's channels are by orders of magnitude less reliable than Eve's channel.>

IEEE International Symposium on Information Theory (ISIT)•Dec 17, 2002•30 citations

Secure Multiterminal Source Coding With Side Information at the Eavesdropper

Joffrey Villard, Pablo Piantanida

The problem of secure multiterminal source coding with side information at the eavesdropper is investigated. This scenario consists of a main encoder (referred to as Alice) that wishes to compress a single source but simultaneously satisfying the desired requirements on the distortion level at a legitimate receiver (referred to as Bob) and the equivocation rate—average uncertainty—at an eavesdropper (referred to as Eve). It is further assumed the presence of a (public) rate-limited link between Alice and Bob. In this setting, Eve perfectly observes the information bits sent by Alice to Bob and has also access to a correlated source which can be used as side information. A second encoder (referred to as Charlie) helps Bob in estimating Alice's source by sending a compressed version of its own correlated observation via a (private) rate-limited link, which is only observed by Bob. For instance, the problem at hands can be seen as the unification between the Berger–Tung and the secure source coding setups. Inner and outer bounds on the so-called rate-distortion-equivocation region are derived. The inner region turns to be tight for two cases: 1) uncoded side information at Bob and 2) lossless reconstruction of both sources at Bob—secure distributed lossless compression. Application examples to secure lossy source coding of Gaussian and binary sources in the presence of Gaussian and binary/ternary (respectively) side informations are also considered. Optimal coding schemes are characterized for some cases of interest where the statistical differences between the side information at the decoders and the presence of a nonzero distortion at Bob can be fully exploited to guarantee secrecy.

arXiv:1105.1658•IEEE Transactions on Information Theory•Feb 6, 2013•78 citations
In this paper, we consider a situation such that legitimate parties, Alice and Bob, share an identical source to generate a secret key, and an eavesdropper, Eve, can access a correlated data that is stored in a storage with bounded size. Then, Alice and Bob want to extract a secret as long as possible. We show a privacy amplification theorem for this problem, i.e., we clarify the rate of key generation for given rate of Eve's storage. The problem can be regarded as a dual randomness generation problem of the Wyner-Ahlswede-Körner type source coding system, and the techniques used in the proof are exchanged, i.e., the so-called Markov lemma is used in the converse part, and the so-called image size characterization is used in the direct part.
We study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key R of length m over a public communication channel completely controlled by a computationally unbounded attacker Eve. Despite being extensively studied in the literature, the problem of designing “optimal ” efficient privacy amplification protocols is still open, because there are several optimization goals. The first of them is (1) minimizing the entropy loss L = k−m (it is known that the optimal value for L = O(λ), where ε = 2−λ is the desired security of the protocol). Other important considerations include (2) minimizing the number of communication rounds, (3) maintaining security even after the secret key is used (this is called post-application robustness), and (4) ensuring that the protocol P does not leak some “useful information ” about the source X (this is called source privacy). Additionally, when dealing with a very long source X, as happens in the so-called Bounded Retrieval Model (BRM), extracting as long a key as possible is no longer the goal. Instead, the goals are (5) to touch as little of X as possible (for efficiency), and (6) to be able to run the protocol many times on the same X, extracting multiple secure keys.
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.
Alice and Bob want to share a secret key and to communicate an independent message, both of which they desire to be kept secret from an eavesdropper Eve. This problem of secret communication and secret-key generation when two resources are available-correlated sources at Alice, Bob, and Eve, and a noisy broadcast channel from Alice to Bob and Eve which is independent of the sources is studied. The goal is to characterize the fundamental tradeoff between the rates of the secret message and secret key. An achievable solution and proof of its optimality for the parallel channels and sources case when each subchannel and source component satisfies a degradation order (either in favor of the legitimate receiver or the eavesdropper) is presented. This includes the case of jointly Gaussian sources and an additive Gaussian channel, for which the secrecy region is evaluated.
Two legitimate parties, referred to as Alice and Bob, wish to generate secret keys from the wireless channel in the presence of an eavesdropper, referred to as Eve, in order to use such keys for encryption and decryption. In general, the secret key rate highly depends on the coherence time of the channel. In particular, a straightforward method of generating secret keys in static environments results in ultra-low rates. In order to resolve this problem, we introduce a low-complexity method called induced randomness. In this method, Alice and Bob independently generate local randomness to be used together with the uniqueness of the wireless channel coefficients in order to enable high-rate secret key generation. In this work, two scenarios are considered: first, when Alice and Bob share a direct communication channel, and second, when Alice and Bob do not have a direct link and communicate through an untrusted relay. After exchanging the induced randomness, post-processing is done by Alice and Bob to generate highly-correlated samples that are used for the key generation. Such samples are then converted into bits, disparities between the sequences generated by Alice and Bob are mitigated, and the resulting sequences are then hashed to compensate for the information leakage to the eavesdropper and to allow consistency checking of the generated key bit sequences. We utilize semantic security measures and information-theoretic inequalities to upper bound the probability of successful eavesdropping attack in terms of the mutual information measures that can be numerically computed. Given certain reasonable system parameters this bound is numerically evaluated to be 2-31and 2-10.57in the first and the second scenario, respectively.
Consider a scenario in which two parties Alice and Bob as well as an opponent Eve receive the output of a binary symmetric source (e,g. installed in a satellite) over individual, not necessarily independent binary symmetric channels. Alice and Bob share no secret key initially and can only communicate over a public channel completely accessible to Eve. The authors derive a lower bound on the rate at which Alice and Bob can generate secret-key bits about which Eve has arbitrarily little information, This lower bound is strictly positive as long as Eve's binary symmetric channel is not perfect, even if Alice's and Bob's channels are by orders of magnitude less reliable than Eve's channel.>
The problem of secure multiterminal source coding with side information at the eavesdropper is investigated. This scenario consists of a main encoder (referred to as Alice) that wishes to compress a single source but simultaneously satisfying the desired requirements on the distortion level at a legitimate receiver (referred to as Bob) and the equivocation rate—average uncertainty—at an eavesdropper (referred to as Eve). It is further assumed the presence of a (public) rate-limited link between Alice and Bob. In this setting, Eve perfectly observes the information bits sent by Alice to Bob and has also access to a correlated source which can be used as side information. A second encoder (referred to as Charlie) helps Bob in estimating Alice's source by sending a compressed version of its own correlated observation via a (private) rate-limited link, which is only observed by Bob. For instance, the problem at hands can be seen as the unification between the Berger–Tung and the secure source coding setups. Inner and outer bounds on the so-called rate-distortion-equivocation region are derived. The inner region turns to be tight for two cases: 1) uncoded side information at Bob and 2) lossless reconstruction of both sources at Bob—secure distributed lossless compression. Application examples to secure lossy source coding of Gaussian and binary sources in the presence of Gaussian and binary/ternary (respectively) side informations are also considered. Optimal coding schemes are characterized for some cases of interest where the statistical differences between the side information at the decoders and the presence of a nonzero distortion at Bob can be fully exploited to guarantee secrecy.