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

Cambridge University Press eBooks

Coding for secrecy

Matthieu R. Bloch, João Barros

Published Sep 22, 2011• 3 citations
Publisher

Abstract

In this chapter, we discuss the construction of practical codes for secrecy. The design of codes for the wiretap channel turns out to be surprisingly difficult, and this area of information-theoretic security is still largely in its infancy. To some extent, the major obstacles in the road to secrecy capacity are similar to those that lay in the path to channel capacity: the random-coding arguments used to establish the secrecy capacity do not provide explicit code constructions. However, the design of wiretap codes is further impaired by the absence of a simple metric, such as a bit error rate, which could be evaluated numerically. Unlike codes designed for reliable communication, whose performance is eventually assessed by plotting a bit-error-rate curve, we cannot simulate an eavesdropper with unlimited computational power; hence, wiretap codes must possess enough structure to be provably secure. For certain channels, such as binary erasure wiretap channels, the information-theoretic secrecy constraint can be recast in terms of an algebraic property for a code-generator matrix. Most of the chapter focuses on such cases since this algebraic view of secrecy simplifies the analysis considerably. As seen in Chapter 4, the design of secret-key distillation strategies is a somewhat easier problem insofar as reliability and security can be handled separately by means of information reconciliation and privacy amplification. Essentially, the construction of coding schemes for key agreement reduces to the design of Slepian–Wolf-like codes for information reconciliation, which can be done efficiently with low-density parity-check (LDPC) codes or turbo-codes.

DOI
10.1017/cbo9780511977985.008

Related papers

Wireless Information-Theoretic Security - Part II: Practical Implementation

Matthieu R. Bloch, João Barros, Miguel R. D. Rodrigues +1 more

In Part I of this two-part paper on confidential communication over wireless channels, we studied the fundamental security limits of quasi-static fading channels from the point of view of outage secrecy capacity with perfect and imperfect channel state information. In Part II, we develop a practical secret key agreement protocol for Gaussian and quasi-static fading wiretap channels. The protocol uses a four-step procedure to secure communications: establish common randomness via an opportunistic transmission, perform message reconciliation, establish a common key via privacy amplification, and use of the key. We introduce a new reconciliation procedure that uses multilevel coding and optimized low density parity check codes which in some cases comes close to achieving the secrecy capacity limits established in Part I. Finally, we develop new metrics for assessing average secure key generation rates and show that our protocol is effective in secure key renewal.

arXiv:cs/0611121•Nov 24, 2006•14 citations

Information Theoretic Secrecy

Abbas El Gamal, Young-Han Kim

Confidentiality of information is a key consideration in many networking applications, including e-commerce, online banking, and intelligence operations. How can information be communicated reliably to the legitimate users, while keeping it secret from eavesdroppers? How does such a secrecy constraint on communication affect the limits on information flow in the network? In this chapter, we study these questions under the information theoretic notion of secrecy, which requires each eavesdropper to obtain essentially no information about the messages sent from knowledge of its received sequence, the channel statistics, and the codebooks used. We investigate two approaches to achieve secure communication. The first is to exploit the statistics of the channel from the sender to the legitimate receivers and the eavesdroppers. We introduce the wiretap channel as a 2-receiver broadcast channel with a legitimate receiver and an eavesdropper, and establish its secrecy capacity, which is the highest achievable secret communication rate. The idea is to design the encoder so that the channel from the sender to the receiver becomes effectively stronger than the channel to the eavesdropper; hence the receiver can recover the message but the eavesdropper cannot. This wiretap coding scheme involves multicoding and randomized encoding. If the channel from the sender to the receiver is weaker than that to the eavesdropper, however, secret communication at a positive rate is not possible. This brings us to the second approach to achieve secret communication, which is to use a secret key shared between the sender and the receiver but unknown to the eavesdropper. We show that the rate of such secret key must be at least as high as the rate of the confidential message. This raises the question of how the sender and the receiver can agree on such a long secret key in the first place. After all, if they had a confidential channel with sufficiently high capacity to communicate the key, then why not use it to communicate the message itself! We show that if the sender and the receiver have access to correlated sources (e.g., through a satellite beaming common randomness to them), then they can still agree on a secret key even when the channel has zero secrecy capacity. We first consider the source model for key agreement, where the sender communicates with the receiver over a noiseless public broadcast channel to generate a secret key from their correlated sources.

Cambridge University Press eBooks•Dec 8, 2011•1 citation

Secrecy from Resolvability

Matthieu R. Bloch, J. Nicholas Laneman

We investigate an approach to physical-layer security based on the premise that the coding mechanism for secrecy over noisy channels is fundamentally tied to the notion of resolvability. Instead of considering capacity-based constructions, which associate to each message a sub-code whose rate approaches the capacity of the eavesdropper’s channel, we consider resolvability-based constructions, which associate to each message a sub-code whose rate is beyond the resolvability of the eavesdropper’s channel. We provide evidence that resolvability is a more powerful and perhaps more fundamental coding mechanism for secrecy by developing results that hold for strong secrecy metrics and arbitrary channels. Specifically, we show that, at least for binary symmetric wiretap channels, random capacity-based constructions fail to approach the strong secrecy capacity while resolvability-based constructions achieve it. We then obtain the secrecy-capacity region of arbitrary broadcast channels with confidential messages and a cost constraint for strong secrecy metrics, which generalizes existing results. Finally, we specialize our results to study the secrecy capacity of wireless channels with perfect channel state information, compound and mixed channels, as well as the secret-key capacity of source models for secret-key agreement. By tying secrecy to resolvability, we obtain achievable rates for stronger secrecy metrics and with simpler proofs than previously derived. Index Terms information-theoretic security, wiretap channel, secret-key agreement, information-spectrum, resolv-ability, wireless channels.

•May 26, 2011•19 citations

On the application of LDPC codes to a novel wiretap channel inspired by quantum key distribution

Andrew Thangaraj, Souvik Dihidar, A.R. Calderbank +2 more

With the advent of quantum key distribution (QKD) systems, perfect (i.e. information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical errorcorrecting codes for both error correction (for the honest p arties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model for such a setting is the wire tap channel introduced by Wyner in 1975. In this paper, we study fundamental limits and coding methods for wire tap channels. We provide a novel proof for the secrecy capacity theorem for wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide complete security at rates below secrecy capacity in some specific cases.

•Jan 1, 2005•8 citations

Capacity Achieving Codes for the Wire Tap Channel with Applications to Quantum Key Distribution

Andrew Thangaraj, Souvik Dihidar, A.R. Calderbank +2 more

With the advent of quantum key distribution (QKD) systems, perfect (i.e. information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical error-correcting codes for both error correction (for the honest parties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model for such a setting is the wire tap channel system introduced by Wyner in 1975. In this paper, we study fundamental limits and coding methods for wire tap channel systems. We provide a novel proof for the secrecy capacity theorem for wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel system and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide complete security at rates below secrecy capacity in some specific cases.

•Nov 2, 2004•15 citations

Secrecy capacity

Matthieu R. Bloch, João Barros

In this chapter, we develop the notion of secrecy capacity , which plays a central role in physical-layer security. The secrecy capacity characterizes the fundamental limit of secure communications over noisy channels, and it is essentially the counterpart to the usual point-to-point channel capacity when communications are subject not only to reliability constraints but also to an information-theoretic secrecy requirement. It is inherently associated with a channel model called the wiretap channel , which is a broadcast channel in which one of the receivers is treated as an adversary. This adversarial receiver, which we call the eavesdropper to emphasize its passiveness, should remain ignorant of the messages transmitted over the channel. The mathematical tools, and especially the random-coding argument, presented in this chapter are the basis for most of the theoretical research in physical-layer security, and we use them extensively in subsequent chapters. We start with a review of Shannon's model of secure communications (Section 3.1), and then we informally discuss the problem of secure communications over noisy channels (Section 3.2). The intuition we develop from loose arguments is useful to grasp the concepts underlying the proofs of the secrecy capacity and motivates a discussion of the choice of an information-theoretic secrecy metric (Section 3.3). We then study in detail the fundamental limits of secure communication over degraded wiretap channels (Section 3.4) and broadcast channels with confidential messages (Section 3.5).

Cambridge University Press eBooks•Sep 22, 2011•3 citations
In this chapter, we discuss the construction of practical codes for secrecy. The design of codes for the wiretap channel turns out to be surprisingly difficult, and this area of information-theoretic security is still largely in its infancy. To some extent, the major obstacles in the road to secrecy capacity are similar to those that lay in the path to channel capacity: the random-coding arguments used to establish the secrecy capacity do not provide explicit code constructions. However, the design of wiretap codes is further impaired by the absence of a simple metric, such as a bit error rate, which could be evaluated numerically. Unlike codes designed for reliable communication, whose performance is eventually assessed by plotting a bit-error-rate curve, we cannot simulate an eavesdropper with unlimited computational power; hence, wiretap codes must possess enough structure to be provably secure. For certain channels, such as binary erasure wiretap channels, the information-theoretic secrecy constraint can be recast in terms of an algebraic property for a code-generator matrix. Most of the chapter focuses on such cases since this algebraic view of secrecy simplifies the analysis considerably. As seen in Chapter 4, the design of secret-key distillation strategies is a somewhat easier problem insofar as reliability and security can be handled separately by means of information reconciliation and privacy amplification. Essentially, the construction of coding schemes for key agreement reduces to the design of Slepian–Wolf-like codes for information reconciliation, which can be done efficiently with low-density parity-check (LDPC) codes or turbo-codes.
In Part I of this two-part paper on confidential communication over wireless channels, we studied the fundamental security limits of quasi-static fading channels from the point of view of outage secrecy capacity with perfect and imperfect channel state information. In Part II, we develop a practical secret key agreement protocol for Gaussian and quasi-static fading wiretap channels. The protocol uses a four-step procedure to secure communications: establish common randomness via an opportunistic transmission, perform message reconciliation, establish a common key via privacy amplification, and use of the key. We introduce a new reconciliation procedure that uses multilevel coding and optimized low density parity check codes which in some cases comes close to achieving the secrecy capacity limits established in Part I. Finally, we develop new metrics for assessing average secure key generation rates and show that our protocol is effective in secure key renewal.
Confidentiality of information is a key consideration in many networking applications, including e-commerce, online banking, and intelligence operations. How can information be communicated reliably to the legitimate users, while keeping it secret from eavesdroppers? How does such a secrecy constraint on communication affect the limits on information flow in the network? In this chapter, we study these questions under the information theoretic notion of secrecy, which requires each eavesdropper to obtain essentially no information about the messages sent from knowledge of its received sequence, the channel statistics, and the codebooks used. We investigate two approaches to achieve secure communication. The first is to exploit the statistics of the channel from the sender to the legitimate receivers and the eavesdroppers. We introduce the wiretap channel as a 2-receiver broadcast channel with a legitimate receiver and an eavesdropper, and establish its secrecy capacity, which is the highest achievable secret communication rate. The idea is to design the encoder so that the channel from the sender to the receiver becomes effectively stronger than the channel to the eavesdropper; hence the receiver can recover the message but the eavesdropper cannot. This wiretap coding scheme involves multicoding and randomized encoding. If the channel from the sender to the receiver is weaker than that to the eavesdropper, however, secret communication at a positive rate is not possible. This brings us to the second approach to achieve secret communication, which is to use a secret key shared between the sender and the receiver but unknown to the eavesdropper. We show that the rate of such secret key must be at least as high as the rate of the confidential message. This raises the question of how the sender and the receiver can agree on such a long secret key in the first place. After all, if they had a confidential channel with sufficiently high capacity to communicate the key, then why not use it to communicate the message itself! We show that if the sender and the receiver have access to correlated sources (e.g., through a satellite beaming common randomness to them), then they can still agree on a secret key even when the channel has zero secrecy capacity. We first consider the source model for key agreement, where the sender communicates with the receiver over a noiseless public broadcast channel to generate a secret key from their correlated sources.
We investigate an approach to physical-layer security based on the premise that the coding mechanism for secrecy over noisy channels is fundamentally tied to the notion of resolvability. Instead of considering capacity-based constructions, which associate to each message a sub-code whose rate approaches the capacity of the eavesdropper’s channel, we consider resolvability-based constructions, which associate to each message a sub-code whose rate is beyond the resolvability of the eavesdropper’s channel. We provide evidence that resolvability is a more powerful and perhaps more fundamental coding mechanism for secrecy by developing results that hold for strong secrecy metrics and arbitrary channels. Specifically, we show that, at least for binary symmetric wiretap channels, random capacity-based constructions fail to approach the strong secrecy capacity while resolvability-based constructions achieve it. We then obtain the secrecy-capacity region of arbitrary broadcast channels with confidential messages and a cost constraint for strong secrecy metrics, which generalizes existing results. Finally, we specialize our results to study the secrecy capacity of wireless channels with perfect channel state information, compound and mixed channels, as well as the secret-key capacity of source models for secret-key agreement. By tying secrecy to resolvability, we obtain achievable rates for stronger secrecy metrics and with simpler proofs than previously derived. Index Terms information-theoretic security, wiretap channel, secret-key agreement, information-spectrum, resolv-ability, wireless channels.
With the advent of quantum key distribution (QKD) systems, perfect (i.e. information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical errorcorrecting codes for both error correction (for the honest p arties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model for such a setting is the wire tap channel introduced by Wyner in 1975. In this paper, we study fundamental limits and coding methods for wire tap channels. We provide a novel proof for the secrecy capacity theorem for wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide complete security at rates below secrecy capacity in some specific cases.
With the advent of quantum key distribution (QKD) systems, perfect (i.e. information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical error-correcting codes for both error correction (for the honest parties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model for such a setting is the wire tap channel system introduced by Wyner in 1975. In this paper, we study fundamental limits and coding methods for wire tap channel systems. We provide a novel proof for the secrecy capacity theorem for wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel system and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide complete security at rates below secrecy capacity in some specific cases.
In this chapter, we develop the notion of secrecy capacity , which plays a central role in physical-layer security. The secrecy capacity characterizes the fundamental limit of secure communications over noisy channels, and it is essentially the counterpart to the usual point-to-point channel capacity when communications are subject not only to reliability constraints but also to an information-theoretic secrecy requirement. It is inherently associated with a channel model called the wiretap channel , which is a broadcast channel in which one of the receivers is treated as an adversary. This adversarial receiver, which we call the eavesdropper to emphasize its passiveness, should remain ignorant of the messages transmitted over the channel. The mathematical tools, and especially the random-coding argument, presented in this chapter are the basis for most of the theoretical research in physical-layer security, and we use them extensively in subsequent chapters. We start with a review of Shannon's model of secure communications (Section 3.1), and then we informally discuss the problem of secure communications over noisy channels (Section 3.2). The intuition we develop from loose arguments is useful to grasp the concepts underlying the proofs of the secrecy capacity and motivates a discussion of the choice of an information-theoretic secrecy metric (Section 3.3). We then study in detail the fundamental limits of secure communication over degraded wiretap channels (Section 3.4) and broadcast channels with confidential messages (Section 3.5).