Showing 1–50 of 62 results for author: Bloch, M

Pilot-Attacks Can Enable Positive-Rate Covert Communications of Wireless Hardware Trojans

Authors: Serhat Bakirtas, Matthieu R. Bloch, Elza Erkip

Abstract: Hardware Trojans can inflict harm on wireless networks by exploiting the link margins inherent in communication systems. We investigate a setting in which, alongside a legitimate communication link, a hardware Trojan embedded in the legitimate transmitter attempts to establish communication with its intended rogue receiver. To illustrate the susceptibility of wireless networks against pilot attack… ▽ More Hardware Trojans can inflict harm on wireless networks by exploiting the link margins inherent in communication systems. We investigate a setting in which, alongside a legitimate communication link, a hardware Trojan embedded in the legitimate transmitter attempts to establish communication with its intended rogue receiver. To illustrate the susceptibility of wireless networks against pilot attacks, we examine a two-phased scenario. In the channel estimation phase, the Trojan carries out a covert pilot scaling attack to corrupt the channel estimation of the legitimate receiver. Subsequently, in the communication phase, the Trojan exploits the ensuing imperfect channel estimation to covertly communicate with its receiver. By analyzing the corresponding hypothesis tests conducted by the legitimate receiver in both phases, we establish that the pilot scaling attack allows the Trojan to operate in the so-called "linear regime" i.e., covertly and reliably transmitting at a positive rate to the rogue receiver. Our results highlight the vulnerability of the channel estimation process in wireless communication systems against hardware Trojans. △ Less

Submitted 23 April, 2024; v1 submitted 15 April, 2024; originally announced April 2024.

Covert Online Decision Making: From Sequential Hypothesis Testing to Stochastic Bandits

Authors: Meng-Che Chang, Matthieu R. Bloch

Abstract: We study the problem of covert online decision-making in which an agent attempts to identify a parameter governing a system by probing the system while escaping detection from an adversary. The system is modeled as a Markov kernel whose input is controlled by the agent and whose two outputs are observed by the agent and the adversary, respectively. This problem is motivated by applications such as… ▽ More We study the problem of covert online decision-making in which an agent attempts to identify a parameter governing a system by probing the system while escaping detection from an adversary. The system is modeled as a Markov kernel whose input is controlled by the agent and whose two outputs are observed by the agent and the adversary, respectively. This problem is motivated by applications such as covert sensing or covert radar, in which one tries to perform a sensing task without arousing suspicion by an adversary monitoring the environment for the presence of sensing signals. Specifically, we consider two situations corresponding to different amounts of knowledge of the system. If the kernel is known but governed by an unknown fixed parameter, we formulate the problem as a sequential hypothesis testing problem. If the kernel determining the observations of the agent is unknown but the kernel determining those of the adversary is known, we formulate the problem as a best-arm identification problem in a bandit setting. In both situations, we characterize the exponent of the probability of identification error. As expected because of the covertness requirement, the probability of identification error decays exponentially with the square root of the blocklength. △ Less

Submitted 20 November, 2023; originally announced November 2023.

Secure Integrated Sensing and Communication

Authors: Onur Günlü, Matthieu R. Bloch, Rafael F. Schaefer, Aylin Yener

Abstract: This work considers the problem of mitigating information leakage between communication and sensing in systems jointly performing both operations. Specifically, a discrete memoryless state-dependent broadcast channel model is studied in which (i) the presence of feedback enables a transmitter to convey information, while simultaneously performing channel state estimation; (ii) one of the receivers… ▽ More This work considers the problem of mitigating information leakage between communication and sensing in systems jointly performing both operations. Specifically, a discrete memoryless state-dependent broadcast channel model is studied in which (i) the presence of feedback enables a transmitter to convey information, while simultaneously performing channel state estimation; (ii) one of the receivers is treated as an eavesdropper whose state should be estimated but which should remain oblivious to part of the transmitted information. The model abstracts the challenges behind security for joint communication and sensing if one views the channel state as a key attribute, e.g., location. For independent and identically distributed states, perfect output feedback, and when part of the transmitted message should be kept secret, a partial characterization of the secrecy-distortion region is developed. The characterization is exact when the broadcast channel is either physically-degraded or reversely-physically-degraded. The partial characterization is also extended to the situation in which the entire transmitted message should be kept secret. The benefits of a joint approach compared to separation-based secure communication and state-sensing methods are illustrated with binary joint communication and sensing models. △ Less

Submitted 20 March, 2023; originally announced March 2023.

Comments: arXiv admin note: substantial text overlap with arXiv:2202.10790

Noise Injection Node Regularization for Robust Learning

Authors: Noam Levi, Itay M. Bloch, Marat Freytsis, Tomer Volansky

Abstract: We introduce Noise Injection Node Regularization (NINR), a method of injecting structured noise into Deep Neural Networks (DNN) during the training stage, resulting in an emergent regularizing effect. We present theoretical and empirical evidence for substantial improvement in robustness against various test data perturbations for feed-forward DNNs when trained under NINR. The novelty in our appro… ▽ More We introduce Noise Injection Node Regularization (NINR), a method of injecting structured noise into Deep Neural Networks (DNN) during the training stage, resulting in an emergent regularizing effect. We present theoretical and empirical evidence for substantial improvement in robustness against various test data perturbations for feed-forward DNNs when trained under NINR. The novelty in our approach comes from the interplay of adaptive noise injection and initialization conditions such that noise is the dominant driver of dynamics at the start of training. As it simply requires the addition of external nodes without altering the existing network structure or optimization algorithms, this method can be easily incorporated into many standard problem specifications. We find improved stability against a number of data perturbations, including domain shifts, with the most dramatic improvement obtained for unstructured noise, where our technique outperforms other existing methods such as Dropout or $L_2$ regularization, in some cases. We further show that desirable generalization properties on clean data are generally maintained. △ Less

Submitted 27 October, 2022; originally announced October 2022.

Comments: 16 pages, 9 figures

Journal ref: Proceedings of the International Conference on Learning Representations (ICLR), 2023

Rate and Detection-Error Exponent Tradeoff for Joint Communication and Sensing of Fixed Channel States

Authors: Meng-Che Chang, Shi-Yuan Wang, Tuna Erdoğan, Matthieu R. Bloch

Abstract: We study the information-theoretic limits of joint communication and sensing when the sensing task is modeled as the estimation of a discrete channel state fixed during the transmission of an entire codeword. This setting captures scenarios in which the time scale over which sensing happens is significantly slower than the time scale over which symbol transmission occurs. The tradeoff between comm… ▽ More We study the information-theoretic limits of joint communication and sensing when the sensing task is modeled as the estimation of a discrete channel state fixed during the transmission of an entire codeword. This setting captures scenarios in which the time scale over which sensing happens is significantly slower than the time scale over which symbol transmission occurs. The tradeoff between communication and sensing then takes the form of a tradeoff region between the rate of reliable communication and the state detection-error exponent. We investigate such tradeoffs for both mono-static and bi-static scenarios, in which the sensing task is performed at the transmitter or receiver, respectively. In the mono-static case, we develop an exact characterization of the tradeoff in open-loop, when the sensing is not used to assist the communication. We also show the strict improvement brought by a closed-loop operation, in which the sensing informs the communication. In the bi-static case, we develop an achievable tradeoff region that highlights the fundamentally different nature of the bi-static scenario. Specifically, the rate of communication plays a key role in the characterization of the tradeoff and we show how joint strategies, which simultaneously estimate message and state, outperform successive strategies, which only estimate the state after decoding the transmitted message. △ Less

Submitted 16 May, 2023; v1 submitted 14 October, 2022; originally announced October 2022.

Comments: 34 pages, 5 figures, accepted to JSAIT

Optimal rate-limited secret key generation from Gaussian sources using lattices

Authors: Laura Luzzi, Cong Ling, Matthieu R. Bloch

Abstract: We propose a lattice-based scheme for secret key generation from Gaussian sources in the presence of an eavesdropper, and show that it achieves the strong secret key capacity in the case of degraded source models, as well as the optimal secret key / public communication rate trade-off. The key ingredients of our scheme are the use of the modulo lattice operation to extract the channel intrinsic ra… ▽ More We propose a lattice-based scheme for secret key generation from Gaussian sources in the presence of an eavesdropper, and show that it achieves the strong secret key capacity in the case of degraded source models, as well as the optimal secret key / public communication rate trade-off. The key ingredients of our scheme are the use of the modulo lattice operation to extract the channel intrinsic randomness, based on the notion of flatness factor, together with a randomized lattice quantization technique to quantize the continuous source. Compared to previous works, we introduce two new notions of flatness factor based on $L^1$ distance and KL divergence, respectively, which might be of independent interest. We prove the existence of secrecy-good lattices under $L^1$ distance and KL divergence, whose $L^1$ and KL flatness factors vanish for volume-to-noise ratios up to $2πe$. This improves upon the volume-to-noise ratio threshold $2π$ of the $L^{\infty}$ flatness factor. △ Less

Submitted 12 April, 2023; v1 submitted 21 June, 2022; originally announced June 2022.

Comments: 17 pages, 3 figures, accepted for publication in IEEE Trans. Inf. Theory

Secure Joint Communication and Sensing

Authors: Onur Günlü, Matthieu Bloch, Rafael F. Schaefer, Aylin Yener

Abstract: This work considers the problem of mitigating information leakage between communication and sensing in systems jointly performing both operations. Specifically, a discrete memoryless state-dependent broadcast channel model is studied in which (i) the presence of feedback enables a transmitter to convey information, while simultaneously performing channel state estimation; (ii) one of the receivers… ▽ More This work considers the problem of mitigating information leakage between communication and sensing in systems jointly performing both operations. Specifically, a discrete memoryless state-dependent broadcast channel model is studied in which (i) the presence of feedback enables a transmitter to convey information, while simultaneously performing channel state estimation; (ii) one of the receivers is treated as an eavesdropper whose state should be estimated but which should remain oblivious to part of the transmitted information. The model abstracts the challenges behind security for joint communication and sensing if one views the channel state as a sensitive attribute, e.g., location. For independent and identically distributed states, perfect output feedback, and when part of the transmitted message should be kept secret, a partial characterization of the secrecy-distortion region is developed. The characterization is exact when the broadcast channel is either physically-degraded or reversely-physically-degraded. The partial characterization is also extended to the situation in which the entire transmitted message should be kept secret. The benefits of a joint approach compared to separation-based secure communication and state-sensing methods are illustrated with a binary joint communication and sensing model. △ Less

Submitted 15 August, 2022; v1 submitted 22 February, 2022; originally announced February 2022.

Comments: Shorter version to appear in the 2022 IEEE International Symposium on Information Theory

Secure Multi-Function Computation with Private Remote Sources

Authors: Onur Günlü, Matthieu Bloch, Rafael F. Schaefer

Abstract: We consider a distributed function computation problem in which parties observing noisy versions of a remote source facilitate the computation of a function of their observations at a fusion center through public communication. The distributed function computation is subject to constraints, including not only reliability and storage but also privacy and secrecy. Specifically, 1) the remote source… ▽ More We consider a distributed function computation problem in which parties observing noisy versions of a remote source facilitate the computation of a function of their observations at a fusion center through public communication. The distributed function computation is subject to constraints, including not only reliability and storage but also privacy and secrecy. Specifically, 1) the remote source should remain private from an eavesdropper and the fusion center, measured in terms of the information leaked about the remote source; 2) the function computed should remain secret from the eavesdropper, measured in terms of the information leaked about the arguments of the function, to ensure secrecy regardless of the exact function used. We derive the exact rate regions for lossless and lossy single-function computation and illustrate the lossy single-function computation rate region for an information bottleneck example, in which the optimal auxiliary random variables are characterized for binary-input symmetric-output channels. We extend the approach to lossless and lossy asynchronous multiple-function computations with joint secrecy and privacy constraints, in which case inner and outer bounds for the rate regions differing only in the Markov chain conditions imposed are characterized. △ Less

Submitted 29 March, 2022; v1 submitted 17 June, 2021; originally announced June 2021.

Comments: Shorter version appeared in the IEEE International Symposium on Information Theory 2021

Key Assistance, Key Agreement, and Layered Secrecy for Bosonic Broadcast Channels

Authors: Uzi Pereg, Roberto Ferrara, Matthieu R. Bloch

Abstract: Secret-sharing building blocks based on quantum broadcast communication are studied. The confidential capacity region of the pure-loss bosonic broadcast channel is determined, both with and without key assistance, and an achievable region is established for the lossy bosonic broadcast channel. If the main receiver has a transmissivity of η<1/2, then confidentiality solely relies on the key-assiste… ▽ More Secret-sharing building blocks based on quantum broadcast communication are studied. The confidential capacity region of the pure-loss bosonic broadcast channel is determined, both with and without key assistance, and an achievable region is established for the lossy bosonic broadcast channel. If the main receiver has a transmissivity of η<1/2, then confidentiality solely relies on the key-assisted encryption of the one-time pad. We also address conference key agreement for the distillation of two keys, a public key and a secret key. A regularized formula is derived for the key-agreement capacity region in finite dimensions. In the bosonic case, the key-agreement region is included within the capacity region of the corresponding broadcast channel with confidential messages. We then consider a network with layered secrecy, where three users with different security ranks communicate over the same broadcast network. We derive an achievable layered-secrecy region for a pure-loss bosonic channel that is formed by the concatenation of two beam splitters. △ Less

Submitted 13 September, 2021; v1 submitted 9 May, 2021; originally announced May 2021.

Feedback Coding for Active Learning

Authors: Gregory Canal, Matthieu Bloch, Christopher Rozell

Abstract: The iterative selection of examples for labeling in active machine learning is conceptually similar to feedback channel coding in information theory: in both tasks, the objective is to seek a minimal sequence of actions to encode information in the presence of noise. While this high-level overlap has been previously noted, there remain open questions on how to best formulate active learning as a c… ▽ More The iterative selection of examples for labeling in active machine learning is conceptually similar to feedback channel coding in information theory: in both tasks, the objective is to seek a minimal sequence of actions to encode information in the presence of noise. While this high-level overlap has been previously noted, there remain open questions on how to best formulate active learning as a communications system to leverage existing analysis and algorithms in feedback coding. In this work, we formally identify and leverage the structural commonalities between the two problems, including the characterization of encoder and noisy channel components, to design a new algorithm. Specifically, we develop an optimal transport-based feedback coding scheme called Approximate Posterior Matching (APM) for the task of active example selection and explore its application to Bayesian logistic regression, a popular model in active learning. We evaluate APM on a variety of datasets and demonstrate learning performance comparable to existing active learning methods, at a reduced computational cost. These results demonstrate the potential of directly deploying concepts from feedback channel coding to design efficient active learning strategies. △ Less

Submitted 28 February, 2021; originally announced March 2021.

Comments: AISTATS 2021

Covert MIMO Communications under Variational Distance Constraint

Authors: Shi-Yuan Wang, Matthieu R. Bloch

Abstract: The problem of covert communication over Multiple-Input Multiple-Output (MIMO) Additive White Gaussian Noise (AWGN) channels is investigated, in which a transmitter attempts to reliably communicate with a legitimate receiver while avoiding detection by a passive adversary. The covert capacity of the MIMO AWGN is characterized under a variational distance covertness constraint when the MIMO channel… ▽ More The problem of covert communication over Multiple-Input Multiple-Output (MIMO) Additive White Gaussian Noise (AWGN) channels is investigated, in which a transmitter attempts to reliably communicate with a legitimate receiver while avoiding detection by a passive adversary. The covert capacity of the MIMO AWGN is characterized under a variational distance covertness constraint when the MIMO channel matrices are static and known. The characterization of the covert capacity is also extended to a class of channels in which the legitimate channel matrix is known but the adversary's channel matrix is only known up to a rank and a spectral norm constraint. △ Less

Submitted 3 September, 2021; v1 submitted 22 February, 2021; originally announced February 2021.

Comments: 22 pages, 1 figure, accepted to Transactions on Information Forensics & Security

On Covert Quantum Sensing and the Benefits of Entanglement

Authors: Mehrdad Tahmasbi, Matthieu Bloch

Abstract: Motivated by applications to covert quantum radar, we analyze a covert quantum sensing problem, in which a legitimate user aims at estimating an unknown parameter taking finitely many values by probing a quantum channel while remaining undetectable from an adversary receiving the probing signals through another quantum channel. When channels are classical-quantum, we characterize the optimal error… ▽ More Motivated by applications to covert quantum radar, we analyze a covert quantum sensing problem, in which a legitimate user aims at estimating an unknown parameter taking finitely many values by probing a quantum channel while remaining undetectable from an adversary receiving the probing signals through another quantum channel. When channels are classical-quantum, we characterize the optimal error exponent under a covertness constraint for sensing strategies in which probing signals do not depend on past observations. When the legitimate user's channel is a unitary depending on the unknown parameter, we provide achievability and converse results that show how one can significantly improve covertness using an entangled input state. △ Less

Submitted 3 August, 2020; originally announced August 2020.

Keyless Covert Communication via Channel State Information

Authors: Hassan ZivariFard, Matthieu R. Bloch, Aria Nosratinia

Abstract: We consider the problem of covert communication over a state-dependent channel when the channel state is available either non-causally, causally, or strictly causally, either at the transmitter alone or at both transmitter and receiver. Covert communication with respect to an adversary, called "warden," is one in which, despite communication over the channel, the warden's observation remains indis… ▽ More We consider the problem of covert communication over a state-dependent channel when the channel state is available either non-causally, causally, or strictly causally, either at the transmitter alone or at both transmitter and receiver. Covert communication with respect to an adversary, called "warden," is one in which, despite communication over the channel, the warden's observation remains indistinguishable from an output induced by innocent channel-input symbols. Covert communication involves fooling an adversary in part by a proliferation of codebooks; for reliable decoding at the legitimate receiver, the codebook uncertainty is typically removed via a shared secret key that is unavailable to the warden. In contrast to previous work, we do not assume the availability of a shared key at the transmitter and legitimate receiver. Instead, shared randomness is extracted from the channel state in a manner that keeps it secret from the warden, despite the influence of the channel state on the warden's output. When channel state is available at the transmitter and receiver, we derive the covert capacity region. When channel state is only available at the transmitter, we derive inner and outer bounds on the covert capacity. We provide examples for which the covert capacity is positive with knowledge of channel state information but is zero without it. △ Less

Submitted 21 May, 2021; v1 submitted 6 March, 2020; originally announced March 2020.

Undetectable Radios: Covert Communication under Spectral Mask Constraints

Authors: Qiaosheng, Zhang, Matthieu R. Bloch, Mayank Bakshi, Sidharth Jaggi

Abstract: We consider the problem of covert communication over continuous-time additive white Gaussian noise (AWGN) channels under spectral mask constraints, wherein two legitimate parties attempt to communicate reliably in the presence of an eavesdropper that should be unable to estimate if communication takes place. The spectral mask constraint is imposed to restrict excessive radiation beyond the bandwid… ▽ More We consider the problem of covert communication over continuous-time additive white Gaussian noise (AWGN) channels under spectral mask constraints, wherein two legitimate parties attempt to communicate reliably in the presence of an eavesdropper that should be unable to estimate if communication takes place. The spectral mask constraint is imposed to restrict excessive radiation beyond the bandwidth of interest. We develop a communication scheme with theoretical reliability and covertness guarantees based on pulse amplitude modulation (PAM) with Binary Phase Shift Keying (BPSK) and root raised cosine (RRC) carrier pulses. Given a fixed transmission duration T and a spectral mask with bandwidth parameter W, we show that one can reliably and covertly transmit $O(\sqrt{WT})$ bits of information. We characterize the constant behind the $O$ and show that it is tight under some conditions. △ Less

Submitted 5 January, 2020; originally announced January 2020.

Steganography Protocols for Quantum Channels

Authors: Mehrdad Tahmasbi, Matthieu Bloch

Abstract: We study several versions of a quantum steganography problem, in which two legitimate parties attempt to conceal a cypher in a quantum cover transmitted over a quantum channel without arising suspicion from a warden who intercepts the cover. In all our models, we assume that the warden has an inaccurate knowledge of the quantum channel and we formulate several variations of the steganography probl… ▽ More We study several versions of a quantum steganography problem, in which two legitimate parties attempt to conceal a cypher in a quantum cover transmitted over a quantum channel without arising suspicion from a warden who intercepts the cover. In all our models, we assume that the warden has an inaccurate knowledge of the quantum channel and we formulate several variations of the steganography problem depending on the tasks used as the cover and the cypher task. In particular, when the cover task is classical communication, we show that the cypher task can be classical communication or entanglement sharing; when the cover task is entanglement sharing and the main channel is noiseless, we show that the cypher task can be randomness sharing; when the cover task is quantum communication and the main channel is noiseless, we show that the cypher task can be classical communication. In the latter case, our results improve earlier ones by relaxing the need for a shared key between the transmitter and the receiver and hold under milder assumptions on the cover quantum communication code. △ Less

Submitted 22 July, 2019; originally announced July 2019.

Toward Undetectable Quantum Key Distribution over Bosonic Channels

Authors: Mehrdad Tahmasbi, Matthieu R. Bloch

Abstract: We show that covert secret key expansion is possible using a public authenticated classical channel and a quantum channel largely under control of an adversary, which we precisely define. We also prove a converse result showing that, under the golden standard of quantum key distribution by which the adversary completely controls the quantum channel, no covert key generation is possible. We propose… ▽ More We show that covert secret key expansion is possible using a public authenticated classical channel and a quantum channel largely under control of an adversary, which we precisely define. We also prove a converse result showing that, under the golden standard of quantum key distribution by which the adversary completely controls the quantum channel, no covert key generation is possible. We propose a protocol based on pulse-position modulation and multi-level coding that allows one to use traditional quantum key distribution (QKD) protocols while ensuring covertness, in the sense that no statistical test by the adversary can detect the presence of communication better than a random guess. When run over a bosonic channel, our protocol can leverage existing discrete-modulated continuous variable protocols. Since existing techniques to bound Eve's information do not directly apply, we develop a new bound that results in positive throughput for a range of channel parameters. △ Less

Submitted 8 November, 2019; v1 submitted 28 April, 2019; originally announced April 2019.

Two-Multicast Channel with Confidential Messages

Authors: Hassan ZivariFard, Matthieu Bloch, Aria Nosratinia

Abstract: Motivated in part by the problem of secure multicast distributed storage, we analyze secrecy rates for a channel in which two transmitters simultaneously multicast to two receivers in the presence of an eavesdropper. Achievable rates are calculated via extensions of a technique due to Chia and El Gamal and the method of output statistics of random binning. Outer bounds are derived for both the deg… ▽ More Motivated in part by the problem of secure multicast distributed storage, we analyze secrecy rates for a channel in which two transmitters simultaneously multicast to two receivers in the presence of an eavesdropper. Achievable rates are calculated via extensions of a technique due to Chia and El Gamal and the method of output statistics of random binning. Outer bounds are derived for both the degraded and non-degraded versions of the channel, and examples are provided in which the inner and outer bounds meet. The inner bounds recover known results for the multiple-access wiretap channel, broadcast channel with confidential messages, and the compound MAC channel. An auxiliary result is also produced that derives an inner bound on the minimal randomness necessary to achieve secrecy in multiple-access wiretap channels. △ Less

Submitted 3 August, 2020; v1 submitted 22 February, 2019; originally announced February 2019.

Covert Secret Key Generation with an Active Warden

Authors: Mehrdad Tahmasbi, Matthieu Bloch

Abstract: We investigate the problem of covert and secret key generation over a state-dependent discrete memoryless channel with one-way public discussion in which an adversary, the warden, may arbitrarily choose the channel state. We develop an adaptive protocol that, under conditions that we explicitly specify, not only allows the transmitter and the legitimate receiver to exchange a secret key but also c… ▽ More We investigate the problem of covert and secret key generation over a state-dependent discrete memoryless channel with one-way public discussion in which an adversary, the warden, may arbitrarily choose the channel state. We develop an adaptive protocol that, under conditions that we explicitly specify, not only allows the transmitter and the legitimate receiver to exchange a secret key but also conceals from the active warden whether the protocol is being run. When specialized to passive adversaries that do not control the channel state, we partially characterize the covert secret key capacity. In particular, the covert secret key capacity is sometimes equal to the covert capacity of the channel, so that secrecy comes "for free." △ Less

Submitted 8 November, 2019; v1 submitted 7 January, 2019; originally announced January 2019.

Journal ref: in IEEE Transactions on Information Forensics and Security, vol. 15, pp. 1026-1039, 2020

State Leakage and Coordination with Causal State Knowledge at the Encoder

Authors: Mael Le Treust, Matthieu Bloch

Abstract: We revisit the problems of state masking and state amplification through the lens of empirical coordination. Specifically, we characterize the rate-equivocation-coordination trade-offs regions of a state-dependent channel in which the encoder has causal and strictly causal state knowledge. We also extend this characterization to the cases of two-sided state information and noisy channel feedback.… ▽ More We revisit the problems of state masking and state amplification through the lens of empirical coordination. Specifically, we characterize the rate-equivocation-coordination trade-offs regions of a state-dependent channel in which the encoder has causal and strictly causal state knowledge. We also extend this characterization to the cases of two-sided state information and noisy channel feedback. Our approach is based on the notion of core of the receiver's knowledge, which we introduce to capture what the decoder can infer about all the signals involved in the model. Finally, we exploit the aforementioned results to solve a channel state estimation zero-sum game in which the encoder prevents the decoder to estimate the channel state accurately. △ Less

Submitted 6 November, 2020; v1 submitted 17 December, 2018; originally announced December 2018.

Comments: accepted in IEEE Transactions on Information Theory

Cooperative Resolvability and Secrecy in the Cribbing Multiple-Access Channel

Authors: Noha Helal, Matthieu Bloch, Aria Nosratinia

Abstract: We study channel resolvability for the discrete memoryless multiple-access channel with cribbing, i.e., the characterization of the amount of randomness required at the inputs to approximately produce a chosen i.i.d. output distribution according to KL divergence. We analyze resolvability rates when one encoder cribs (i) the input of the other encoder; or the output of the other encoder, (ii) non-… ▽ More We study channel resolvability for the discrete memoryless multiple-access channel with cribbing, i.e., the characterization of the amount of randomness required at the inputs to approximately produce a chosen i.i.d. output distribution according to KL divergence. We analyze resolvability rates when one encoder cribs (i) the input of the other encoder; or the output of the other encoder, (ii) non-causally, (iii) causally, or (iv) strictly-causally. For scenarios (i)-(iii), we exactly characterize the channel resolvability region. For (iv), we provide inner and outer bounds for the channel resolvability region; the crux of our achievability result is to handle the strict causality constraint with a block-Markov coding scheme in which dependencies across blocks are suitably hidden. Finally, we leverage the channel resolvability results to derive achievable secrecy rate regions for each of the cribbing scenarios under strong secrecy constraints. △ Less

Submitted 28 November, 2018; originally announced November 2018.

Multilevel-Coded Pulse-Position Modulation for Covert Communications over Binary-Input Discrete Memoryless Channels

Authors: Ishaque Ashar Kadampot, Mehrdad Tahmasbi, Matthieu R Bloch

Abstract: We develop a low-complexity coding scheme to achieve covert communications over binary-input discrete memoryless channels (BI-DMCs). We circumvent the impossibility of covert communication with linear codes by introducing non-linearity through the use of pulse position modulation (PPM) and multilevel coding (MLC). We show that the MLC-PPM scheme exhibits many appealing properties; in particular, t… ▽ More We develop a low-complexity coding scheme to achieve covert communications over binary-input discrete memoryless channels (BI-DMCs). We circumvent the impossibility of covert communication with linear codes by introducing non-linearity through the use of pulse position modulation (PPM) and multilevel coding (MLC). We show that the MLC-PPM scheme exhibits many appealing properties; in particular, the channel at a given index level remains stationary as the number of level increases, which allows one to use families of channel capacity- and channel resolvability-achieving codes to concretely instantiate the covert communication scheme. △ Less

Submitted 23 November, 2018; originally announced November 2018.

A framework for covert and secret key expansion over quantum channels

Authors: Mehrdad Tahmasbi, Matthieu R. Bloch

Abstract: Covert and secret quantum key distribution aims at generating information-theoretically secret bits between distant legitimate parties in a manner that remains provably undetectable by an adversary. We propose a framework in which to precisely define and analyze such an operation, and we show that covert and secret key expansion is possible. For fixed and known classical-quantum channels, we devel… ▽ More Covert and secret quantum key distribution aims at generating information-theoretically secret bits between distant legitimate parties in a manner that remains provably undetectable by an adversary. We propose a framework in which to precisely define and analyze such an operation, and we show that covert and secret key expansion is possible. For fixed and known classical-quantum channels, we develop and analyze protocols based on forward and reverse reconciliation. When the adversary applies the same quantum channel independently on each transmitted quantum state, akin to a collective attack in the quantum key distribution literature, we propose a protocol that achieves covert and secret key expansion under mild restrictions. The crux of our approach is the use of information reconciliation and privacy amplification techniques that are able to process the sparse signals required for covert operation and whose Shannon entropy scales as the square root of their length. % diffuse information content quantified through Shannon entropy induced by the sparse signaling required for covert operation. In particular, our results show that the coordination required between legitimate parties to achieve covert communication can be achieved with a negligible number of secret key bits. △ Less

Submitted 24 November, 2018; v1 submitted 13 November, 2018; originally announced November 2018.

Journal ref: Phys. Rev. A 99, 052329 (2019)

Covert Capacity of Non-Coherent Rayleigh-Fading Channels

Authors: Mehrdad Tahmasbi, Anne Savard, Matthieu R. Bloch

Abstract: The covert capacity is characterized for a non-coherent fast Rayleigh-fading wireless channel, in which a legitimate user wishes to communicate reliably with a legitimate receiver while escaping detection from a warden. It is shown that the covert capacity is achieved with an amplitude-constrained input distribution that consists of a finite number of mass points including one at zero and numerica… ▽ More The covert capacity is characterized for a non-coherent fast Rayleigh-fading wireless channel, in which a legitimate user wishes to communicate reliably with a legitimate receiver while escaping detection from a warden. It is shown that the covert capacity is achieved with an amplitude-constrained input distribution that consists of a finite number of mass points including one at zero and numerically tractable bounds are provided. It is also conjectured that distributions with two mass points in fixed locations are optimal. △ Less

Submitted 8 November, 2019; v1 submitted 17 October, 2018; originally announced October 2018.

Strong Coordination over Noisy Channels with Strictly Causal Encoding

Authors: Giulia Cervia, Laura Luzzi, Maël Le Treust, Matthieu R. Bloch

Abstract: We consider a network of two nodes separated by a noisy channel, in which the input and output signals have to be coordinated with the source and its reconstruction. In the case of strictly causal encoding and non-causal decoding, we prove inner and outer bounds for the strong coordination region and show that the inner bound is achievable with polar codes. We consider a network of two nodes separated by a noisy channel, in which the input and output signals have to be coordinated with the source and its reconstruction. In the case of strictly causal encoding and non-causal decoding, we prove inner and outer bounds for the strong coordination region and show that the inner bound is achievable with polar codes. △ Less

Submitted 28 September, 2018; originally announced September 2018.

Comments: 10 pages, 3 figures, conference paper

Journal ref: Proceedings of Allerton Conference on Communication, Control and Computing 2018

Embedding Covert Information in Broadcast Communications

Authors: Keerthi Suria Kumar Arumugam, Matthieu R. Bloch

Abstract: We analyze a two-receiver binary-input discrete memoryless broadcast channel, in which the transmitter communicates a common message simultaneously to both receivers and a covert message to only one of them. The unintended recipient of the covert message is treated as an adversary who attempts to detect the covert transmission. This model captures the problem of embedding covert messages in an inn… ▽ More We analyze a two-receiver binary-input discrete memoryless broadcast channel, in which the transmitter communicates a common message simultaneously to both receivers and a covert message to only one of them. The unintended recipient of the covert message is treated as an adversary who attempts to detect the covert transmission. This model captures the problem of embedding covert messages in an innocent codebook and generalizes previous covert communication models in which the innocent behavior corresponds to the absence of communication between legitimate users. We identify the exact asymptotic behavior of the number of covert bits that can be transmitted when the rate of the innocent codebook is close to the capacity of the channel to the adversary. Our results also identify the dependence of the number of covert bits on the channel parameters and the characteristics of the innocent codebook. △ Less

Submitted 28 August, 2018; originally announced August 2018.

Universal Covertness for Discrete Memoryless Sources

Authors: Remi A. Chou, Matthieu R. Bloch, Aylin Yener

Abstract: Consider a sequence $X^n$ of length $n$ emitted by a Discrete Memoryless Source (DMS) with unknown distribution $p_X$. The objective is to construct a lossless source code that maps $X^n$ to a sequence $\widehat{Y}^m$ of length $m$ that is indistinguishable, in terms of Kullback-Leibler divergence, from a sequence emitted by another DMS with known distribution $p_Y$. The main result is the existen… ▽ More Consider a sequence $X^n$ of length $n$ emitted by a Discrete Memoryless Source (DMS) with unknown distribution $p_X$. The objective is to construct a lossless source code that maps $X^n$ to a sequence $\widehat{Y}^m$ of length $m$ that is indistinguishable, in terms of Kullback-Leibler divergence, from a sequence emitted by another DMS with known distribution $p_Y$. The main result is the existence of a coding scheme that performs this task with an optimal ratio $m/n$ equal to $H(X)/H(Y)$, the ratio of the Shannon entropies of the two distributions, as $n$ goes to infinity. The coding scheme overcomes the challenges created by the lack of knowledge about $p_X$ by a type-based universal lossless source coding scheme that produces as output an almost uniformly distributed sequence, followed by another type-based coding scheme that jointly performs source resolvability and universal lossless source coding. The result recovers and extends previous results that either assume $p_X$ or $p_Y$ uniform, or $p_X$ known. The price paid for these generalizations is the use of common randomness with vanishing rate, whose length scales as the logarithm of $n$. By allowing common randomness larger than the logarithm of $n$ but still negligible compared to $n$, a constructive low-complexity encoding and decoding counterpart to the main result is also provided for binary sources by means of polar codes. △ Less

Submitted 17 June, 2021; v1 submitted 16 August, 2018; originally announced August 2018.

Comments: 11 pages, two-column, 2 figures, accepted to IEEE Transactions on Information Theory

Learning an Adversary's Actions for Secret Communication

Authors: Mehrdad Tahmasbi, Matthieu R. Bloch, Aylin Yener

Abstract: Secure communication over a wiretap channel is investigated, in which an active adversary modifies the state of the channel and the legitimate transmitter has the opportunity to sense and learn the adversary's actions. The adversary has the ability to switch the channel state and observe the corresponding output at every channel use while the encoder has causal access to observations that depend o… ▽ More Secure communication over a wiretap channel is investigated, in which an active adversary modifies the state of the channel and the legitimate transmitter has the opportunity to sense and learn the adversary's actions. The adversary has the ability to switch the channel state and observe the corresponding output at every channel use while the encoder has causal access to observations that depend on the adversary's actions. A joint learning/transmission scheme is developed in which the legitimate users learn and adapt to the adversary's actions. For some channel models, it is shown that the achievable rates, defined precisely for the problem, are arbitrarily close to those obtained with hindsight, had the transmitter known the actions ahead of time. This initial study suggests that there is much to exploit and gain in physical-layer security by learning the adversary, e.g., monitoring the environment. △ Less

Submitted 8 November, 2019; v1 submitted 23 July, 2018; originally announced July 2018.

Covert Communication over a K-User Multiple Access Channel

Authors: Keerthi Suria Kumar Arumugam, Matthieu R. Bloch

Abstract: We consider a scenario in which $K$ transmitters attempt to communicate covert messages reliably to a legitimate receiver over a discrete memoryless MAC while simultaneously escaping detection from an adversary who observes their communication through another discrete memoryless MAC. We assume that each transmitter may use a secret key that is shared only between itself and the legitimate receiver… ▽ More We consider a scenario in which $K$ transmitters attempt to communicate covert messages reliably to a legitimate receiver over a discrete memoryless MAC while simultaneously escaping detection from an adversary who observes their communication through another discrete memoryless MAC. We assume that each transmitter may use a secret key that is shared only between itself and the legitimate receiver. We show that each of the $K$ transmitters can transmit on the order of $\sqrt{n}$ reliable and covert bits per $n$ channel uses, exceeding which, the warden will be able to detect the communication. We identify the optimal pre-constants of the scaling, which leads to a complete characterization of the covert capacity region of the $K$-user binary-input MAC. We show that, asymptotically, all sum-rate constraints are inactive unlike the traditional MAC capacity region. We also characterize the channel conditions that have to be satisfied for the transmitters to operate without a secret key. △ Less

Submitted 7 June, 2019; v1 submitted 15 March, 2018; originally announced March 2018.

Polar codes for empirical coordination over noisy channels with strictly causal encoding

Authors: Giulia Cervia, Laura Luzzi, Maël Le Treust, Matthieu R. Bloch

Abstract: In this paper, we propose a coding scheme based on polar codes for empirical coordination of autonomous devices. We consider a two-node network with a noisy link in which the input and output signals have to be coordinated with the source and the reconstruction. In the case of strictly causal encoding, we show that polar codes achieve the empirical coordination region, provided that a vanishing ra… ▽ More In this paper, we propose a coding scheme based on polar codes for empirical coordination of autonomous devices. We consider a two-node network with a noisy link in which the input and output signals have to be coordinated with the source and the reconstruction. In the case of strictly causal encoding, we show that polar codes achieve the empirical coordination region, provided that a vanishing rate of common randomness is available. △ Less

Submitted 27 February, 2018; originally announced February 2018.

Comments: 4 pages, 1 figure, conference paper presented at XXVIème colloque GRETSI (2017)

Strong coordination of signals and actions over noisy channels with two-sided state information

Authors: Giulia Cervia, Laura Luzzi, Maël Le Treust, Matthieu R. Bloch

Abstract: We consider a network of two nodes separated by a noisy channel with two-sided state information, in which the input and output signals have to be coordinated with the source and its reconstruction. In the case of non-causal encoding and decoding, we propose a joint source-channel coding scheme and develop inner and outer bounds for the strong coordination region. While the inner and outer bounds… ▽ More We consider a network of two nodes separated by a noisy channel with two-sided state information, in which the input and output signals have to be coordinated with the source and its reconstruction. In the case of non-causal encoding and decoding, we propose a joint source-channel coding scheme and develop inner and outer bounds for the strong coordination region. While the inner and outer bounds do not match in general, we provide a complete characterization of the strong coordination region in three particular cases: i) when the channel is perfect; ii) when the decoder is lossless; and iii) when the random variables of the channel are independent from the random variables of the source. Through the study of these special cases, we prove that the separation principle does not hold for joint source-channel strong coordination. Finally, in the absence of state information, we show that polar codes achieve the best known inner bound for the strong coordination region, which therefore offers a constructive alternative to random binning and coding proofs. △ Less

Submitted 8 March, 2018; v1 submitted 31 January, 2018; originally announced January 2018.

Journal ref: IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 66, NO. 8, AUGUST 2020

Smart Wireless Communication is the Cornerstone of Smart Infrastructures

Authors: Mary Ann Weitnauer, Jennifer Rexford, Nicholas Laneman, Matthieu Bloch, Santiago Griljava, Catherine Ross, Gee-Kung Chang

Abstract: Emerging smart infrastructures, such as Smart City, Smart Grid, Smart Health, and Smart Transportation, need smart wireless connectivity. However, the requirements of these smart infrastructures cannot be met with today's wireless networks. A new wireless infrastructure is needed to meet unprecedented needs in terms of agility, reliability, security, scalability, and partnerships. We are at the… ▽ More Emerging smart infrastructures, such as Smart City, Smart Grid, Smart Health, and Smart Transportation, need smart wireless connectivity. However, the requirements of these smart infrastructures cannot be met with today's wireless networks. A new wireless infrastructure is needed to meet unprecedented needs in terms of agility, reliability, security, scalability, and partnerships. We are at the beginning of a revolution in how we live with technology, resulting from a convergence of machine learning (ML), the Internet-of-Things (IoT), and robotics. A smart infrastructure monitors and processes a vast amount of data, collected from a dense and wide distribution of heterogeneous sensors (e.g., the IoT), as well as from web applications like social media. In real time, using machine learning, patterns and relationships in the data over space, time, and application can be detected and predictions can be made; on the basis of these, resources can be managed, decisions can be made, and devices can be actuated to optimize metrics, such as cost, health, safety, and convenience. △ Less

Submitted 22 June, 2017; originally announced June 2017.

Comments: A Computing Community Consortium (CCC) white paper, 5 pages

Strong Coordination of Signals and Actions over Noisy Channels

Authors: Giulia Cervia, Laura Luzzi, Maël Le Treust, Matthieu Bloch

Abstract: -We develop a random binning scheme for strong coordination in a network of two nodes separated by a noisy channel, in which the input and output signals have to be coordinated with the source and its reconstruction. In the case of non-causal encoding and decoding, we propose a joint source-channel coding scheme and develop inner and outer bounds for the strong coordination region. While the set o… ▽ More -We develop a random binning scheme for strong coordination in a network of two nodes separated by a noisy channel, in which the input and output signals have to be coordinated with the source and its reconstruction. In the case of non-causal encoding and decoding, we propose a joint source-channel coding scheme and develop inner and outer bounds for the strong coordination region. While the set of achievable target distributions is the same as for empirical coordination, we characterize the rate of common randomness required for strong coordination. △ Less

Submitted 16 May, 2017; originally announced May 2017.

Journal ref: IEEE International Symposium on Information Theory, Jun 2017, Aachen, Germany

First and Second Order Asymptotics in Covert Communication

Authors: Mehrdad Tahmasbi, Matthieu R. Bloch

Abstract: We study the first- and second-order asymptotics of covert communication over binary-input DMC for three different covertness metrics and under maximum probability of error constraint. When covertness is measured in terms of the relative entropy between the channel output distributions induced with and without communication, we characterize the exact first- and second-order asymptotics of the numb… ▽ More We study the first- and second-order asymptotics of covert communication over binary-input DMC for three different covertness metrics and under maximum probability of error constraint. When covertness is measured in terms of the relative entropy between the channel output distributions induced with and without communication, we characterize the exact first- and second-order asymptotics of the number of bits that can be reliably transmitted with a maximum probability of error less than $ε$ and a relative entropy less than $δ$. When covertness is measured in terms of the variational distance between the channel output distributions or in terms of the probability of missed detection for fixed probability of false alarm, we establish the exact first-order asymptotics and bound the second-order asymptotics. PPM achieves the optimal first-order asymptotics for all three metrics, as well as the optimal second-order asymptotics for relative entropy. The main conceptual contribution of this paper is to clarify how the choice of a covertness metric impacts the information-theoretic limits of covert communications. The main technical contribution underlying our results is a detailed expurgation argument to show the existence of a code satisfying the reliability and covertness criteria. △ Less

Submitted 3 July, 2018; v1 submitted 3 March, 2017; originally announced March 2017.

Polar Coding for Empirical Coordination of Signals and Actions over Noisy Channels

Authors: Giulia Cervia, Laura Luzzi, Matthieu Bloch, Maël Le Treust

Abstract: -We develop a polar coding scheme for empirical coordination in a two-node network with a noisy link in which the input and output signals have to be coordinated with the source and the reconstruction. In the case of non-causal encoding and decoding, we show that polar codes achieve the best known inner bound for the empirical coordination region, provided that a vanishing rate of common randomnes… ▽ More -We develop a polar coding scheme for empirical coordination in a two-node network with a noisy link in which the input and output signals have to be coordinated with the source and the reconstruction. In the case of non-causal encoding and decoding, we show that polar codes achieve the best known inner bound for the empirical coordination region, provided that a vanishing rate of common randomness is available. This scheme provides a constructive alternative to random binning and coding proofs. △ Less

Submitted 21 September, 2016; originally announced September 2016.

Journal ref: Information Theory Workshop 2016, Sep 2016, Cambridge, United Kingdom

Empirical and Strong Coordination via Soft Covering with Polar Codes

Authors: Remi A. Chou, Matthieu Bloch, Joerg Kliewer

Abstract: We design polar codes for empirical coordination and strong coordination in two-node networks. Our constructions hinge on the fact that polar codes enable explicit low-complexity schemes for soft covering. We leverage this property to propose explicit and low-complexity coding schemes that achieve the capacity regions of both empirical coordination and strong coordination for sequences of actions… ▽ More We design polar codes for empirical coordination and strong coordination in two-node networks. Our constructions hinge on the fact that polar codes enable explicit low-complexity schemes for soft covering. We leverage this property to propose explicit and low-complexity coding schemes that achieve the capacity regions of both empirical coordination and strong coordination for sequences of actions taking value in an alphabet of prime cardinality. Our results improve previously known polar coding schemes, which (i) were restricted to uniform distributions and to actions obtained via binary symmetric channels for strong coordination, (ii) required a non-negligible amount of common randomness for empirical coordination, and (iii) assumed that the simulation of discrete memoryless channels could be perfectly implemented. As a by-product of our results, we obtain a polar coding scheme that achieves channel resolvability for an arbitrary discrete memoryless channel whose input alphabet has prime cardinality. △ Less

Submitted 6 June, 2018; v1 submitted 30 August, 2016; originally announced August 2016.

Comments: 14 pages, two-column, 5 figures, accepted to IEEE Transactions on Information Theory

Strong Secrecy in Pairwise Key Agreement over a Generalized Multiple Access Channel

Authors: Somayeh Salimi, Matthieu Bloch, Frederic Gabry, Mikael Skoglund, Panos Papadimitratos

Abstract: This paper considers the problem of pairwise key agreement without public communication between three users connected through a generalized multiple access channel (MAC). While two users control the channel inputs, all three users observe noisy outputs from the channel and each pair of users wishes to agree on a secret key hidden from the remaining user. We first develop a "pre-generated" key-agre… ▽ More This paper considers the problem of pairwise key agreement without public communication between three users connected through a generalized multiple access channel (MAC). While two users control the channel inputs, all three users observe noisy outputs from the channel and each pair of users wishes to agree on a secret key hidden from the remaining user. We first develop a "pre-generated" key-agreement scheme based on secrecy codes for the generalized MAC, in which the channel is only used to distribute pre-generated secret keys. We then extend this scheme to include an additional layer of rate-limited secret-key generation by treating the observed channel outputs as induced sources. We characterize inner and outer bounds on the strong secret-key capacity region for both schemes. For a special case of the "pre-generated" scheme, we obtain an exact characterization. We also illustrate with some binary examples that exploiting the generalized nature of the generalized MAC may lead to significantly larger key-agreement rates. △ Less

Submitted 17 March, 2016; originally announced March 2016.

Comments: 45 pages, 11 figures, Submitted to the IEEE Transactions on Information Theory

Strong Coordination over Multi-hop Line Networks

Authors: Badri N Vellambi, Joerg Kliewer, Matthieu Bloch

Abstract: We analyze the problem of strong coordination over a multi-hop line network in which the node initiating the coordination is a terminal network node. We assume that each node has access to a certain amount of randomness that is local to the node, and that the nodes share some common randomness, which are used together with explicit hop-by-hop communication to achieve strong coordination. We derive… ▽ More We analyze the problem of strong coordination over a multi-hop line network in which the node initiating the coordination is a terminal network node. We assume that each node has access to a certain amount of randomness that is local to the node, and that the nodes share some common randomness, which are used together with explicit hop-by-hop communication to achieve strong coordination. We derive the trade-offs among the required rates of communication on the network links, the rates of local randomness available to network nodes, and the rate of common randomness to realize strong coordination. We present an achievable coding scheme built using multiple layers of channel resolvability codes, and establish several settings in which this scheme is proven to offer the best possible trade-offs. △ Less

Submitted 8 April, 2016; v1 submitted 29 February, 2016; originally announced February 2016.

Comments: 35 pages, 9 Figures, 4 Tables. A part of this work were published in the 2015 IEEE Information Theory Workshop, and a part was accepted for publication in the 50th Annual Conference on Information Sciences and Systems

Lossy Compression with Near-uniform Encoder Outputs

Authors: Badri N Vellambi, Joerg Kliewer, Matthieu Bloch

Abstract: It is well known that lossless compression of a discrete memoryless source with near-uniform encoder output is possible at a rate above its entropy if and only if the encoder is randomized. This work focuses on deriving conditions for near-uniform encoder output(s) in the Wyner-Ziv and the distributed lossy compression problems. We show that in the Wyner-Ziv problem, near-uniform encoder output an… ▽ More It is well known that lossless compression of a discrete memoryless source with near-uniform encoder output is possible at a rate above its entropy if and only if the encoder is randomized. This work focuses on deriving conditions for near-uniform encoder output(s) in the Wyner-Ziv and the distributed lossy compression problems. We show that in the Wyner-Ziv problem, near-uniform encoder output and operation close to the WZ-rate limit is simultaneously possible, whereas in the distributed lossy compression problem, jointly near-uniform outputs is achievable in the interior of the distributed lossy compression rate region if the sources share non-trivial Gács-Körner common information. △ Less

Submitted 9 July, 2016; v1 submitted 22 February, 2016; originally announced February 2016.

Comments: Submitted to the 2016 IEEE International Symposium on Information Theory (11 Pages, 3 Figures)

Coding Schemes for Achieving Strong Secrecy at Negligible Cost

Authors: Remi A. Chou, Badri Vellambi, Matthieu Bloch, Joerg Kliewer

Abstract: We study the problem of achieving strong secrecy over wiretap channels at negligible cost, in the sense of maintaining the overall communication rate of the same channel without secrecy constraints. Specifically, we propose and analyze two source-channel coding architectures, in which secrecy is achieved by multiplexing public and confidential messages. In both cases, our main contribution is to s… ▽ More We study the problem of achieving strong secrecy over wiretap channels at negligible cost, in the sense of maintaining the overall communication rate of the same channel without secrecy constraints. Specifically, we propose and analyze two source-channel coding architectures, in which secrecy is achieved by multiplexing public and confidential messages. In both cases, our main contribution is to show that secrecy can be achieved without compromising communication rate and by requiring only randomness of asymptotically vanishing rate. Our first source-channel coding architecture relies on a modified wiretap channel code, in which randomization is performed using the output of a source code. In contrast, our second architecture relies on a standard wiretap code combined with a modified source code termed uniform compression code, in which a small shared secret seed is used to enhance the uniformity of the source code output. We carry out a detailed analysis of uniform compression codes and characterize the optimal size of the shared seed. △ Less

Submitted 5 December, 2016; v1 submitted 31 August, 2015; originally announced August 2015.

Comments: 15 pages, two-column, 5 figures, accepted to IEEE Transactions on Information Theory

Covert Communication over Noisy Channels: A Resolvability Perspective

Authors: Matthieu R. Bloch

Abstract: We consider the situation in which a transmitter attempts to communicate reliably over a discrete memoryless channel while simultaneously ensuring covertness (low probability of detection) with respect to a warden, who observes the signals through another discrete memoryless channel. We develop a coding scheme based on the principle of channel resolvability, which generalizes and extends prior wor… ▽ More We consider the situation in which a transmitter attempts to communicate reliably over a discrete memoryless channel while simultaneously ensuring covertness (low probability of detection) with respect to a warden, who observes the signals through another discrete memoryless channel. We develop a coding scheme based on the principle of channel resolvability, which generalizes and extends prior work in several directions. First, it shows that, irrespective of the quality of the channels, it is possible to communicate on the order of $\sqrt{n}$ reliable and covert bits over $n$ channel uses if the transmitter and the receiver share on the order of $\sqrt{n}$ key bits; this improves upon earlier results requiring on the order of $\sqrt{n}\log n$ key bits. Second, it proves that, if the receiver's channel is "better" than the warden's channel in a sense that we make precise, it is possible to communicate on the order of $\sqrt{n}$ reliable and covert bits over $n$ channel uses without a secret key; this generalizes earlier results established for binary symmetric channels. We also identify the fundamental limits of covert and secret communications in terms of the optimal asymptotic scaling of the message size and key size, and we extend the analysis to Gaussian channels. The main technical problem that we address is how to develop concentration inequalities for "low-weight" sequences; the crux of our approach is to define suitably modified typical sets that are amenable to concentration inequalities. △ Less

Submitted 28 January, 2016; v1 submitted 30 March, 2015; originally announced March 2015.

Comments: 30 pages, 4 figures, accepted to IEEE Transactions on Information Theory

Coordination in distributed networks via coded actions with application to power control

Authors: Benjamin Larrousse, Samson Lasaulce, Matthieu Bloch

Abstract: This paper investigates the problem of coordinating several agents through their actions. Although the methodology applies to general scenarios, the present work focuses on a situation with an asymmetric observation structure that only involves two agents. More precisely, one of the agents knows the past, present, and future realizations of a state (the system state) that affects the common payoff… ▽ More This paper investigates the problem of coordinating several agents through their actions. Although the methodology applies to general scenarios, the present work focuses on a situation with an asymmetric observation structure that only involves two agents. More precisely, one of the agents knows the past, present, and future realizations of a state (the system state) that affects the common payoff function of the agents; in contrast, the second agent is assumed either to know the past realizations of the system state or to have no knowledge of it. In both cases, the second agent has access to some strictly causal observations of the first agent's actions, which enables the two agents to coordinate. These scenarios are applied to the problem of distributed power control; the key idea is that a transmitter may embed information about the wireless channel state into its transmit power levels so that an observation of these levels, e.g. the signal-to-interference plus noise ratio, allows the other transmitter to coordinate its power levels. The main contributions of this paper are twofold. First, we provide a characterization of the set of feasible average payoffs when the agents repeatedly take long sequences of actions and the realizations of the system state are \acs{iid}. Second, we exploit these results in the context of distributed power control and introduce the concept of coded power control. We carry out an extensive numerical analysis of the benefits of coded power control over alternative power control policies, and highlight a simple yet non-trivial example of a power control code. △ Less

Submitted 14 August, 2017; v1 submitted 15 January, 2015; originally announced January 2015.

Comments: Submitted to ieee transactions on information theory. Some results partly published in references [1-3]

Polar Coding for the Broadcast Channel with Confidential Messages: A Random Binning Analogy

Authors: Remi A. Chou, Matthieu R. Bloch

Abstract: We develop a low-complexity polar coding scheme for the discrete memoryless broadcast channel with confidential messages under strong secrecy and randomness constraints. Our scheme extends previous work by using an optimal rate of uniform randomness in the stochastic encoder, and avoiding assumptions regarding the symmetry or degraded nature of the channels. The price paid for these extensions is… ▽ More We develop a low-complexity polar coding scheme for the discrete memoryless broadcast channel with confidential messages under strong secrecy and randomness constraints. Our scheme extends previous work by using an optimal rate of uniform randomness in the stochastic encoder, and avoiding assumptions regarding the symmetry or degraded nature of the channels. The price paid for these extensions is that the encoder and decoders are required to share a secret seed of negligible size and to increase the block length through chaining. We also highlight a close conceptual connection between the proposed polar coding scheme and a random binning proof of the secrecy capacity region. △ Less

Submitted 4 March, 2016; v1 submitted 2 November, 2014; originally announced November 2014.

Comments: 20 pages, two-column, 6 figures, accepted to IEEE Transactions on Information Theory; parts of the results were presented at the 2015 IEEE Information Theory Workshop; minor change in title

Restricted Discrete Invariance and Self-Synchronization For Stable Walking of Bipedal Robots

Authors: Hamed Razavi, Anthony M. Bloch, Christine Chevallereau, J. W. Grizzle

Abstract: Models of bipedal locomotion are hybrid, with a continuous component often generated by a Lagrangian plus actuators, and a discrete component where leg transfer takes place. The discrete component typically consists of a locally embedded co-dimension one submanifold in the continuous state space of the robot, called the switching surface, and a reset map that provides a new initial condition when… ▽ More Models of bipedal locomotion are hybrid, with a continuous component often generated by a Lagrangian plus actuators, and a discrete component where leg transfer takes place. The discrete component typically consists of a locally embedded co-dimension one submanifold in the continuous state space of the robot, called the switching surface, and a reset map that provides a new initial condition when a solution of the continuous component intersects the switching surface. The aim of this paper is to identify a low-dimensional submanifold of the switching surface, which, when it can be rendered invariant by the closed-loop dynamics, leads to asymptotically stable periodic gaits. The paper begins this process by studying the well-known 3D Linear Inverted Pendulum (LIP) model, where analytical results are much easier to obtain. A key contribution here is the notion of \textit{self-synchronization}, which refers to the periods of the pendular motions in the sagittal and frontal planes tending to a common period. The notion of invariance resulting from the study of the 3D LIP model is then extended to a 9-DOF 3D biped. A numerical study is performed to illustrate that asymptotically stable walking may be obtained. △ Less

Submitted 9 June, 2016; v1 submitted 1 November, 2014; originally announced November 2014.

Comments: Conference

Information Spectrum Approach to Strong Converse Theorems for Degraded Wiretap Channels

Authors: Vincent Y. F. Tan, Matthieu R. Bloch

Abstract: We consider block codes for degraded wiretap channels in which the legitimate receiver decodes the message with an asymptotic error probability no larger than $\varepsilon$ but the leakage to the eavesdropper vanishes. For discrete memoryless and Gaussian wiretap channels, we show that the maximum rate of transmission does not depend on $\varepsilon\in [0,1)$, i.e., such channels possess the parti… ▽ More We consider block codes for degraded wiretap channels in which the legitimate receiver decodes the message with an asymptotic error probability no larger than $\varepsilon$ but the leakage to the eavesdropper vanishes. For discrete memoryless and Gaussian wiretap channels, we show that the maximum rate of transmission does not depend on $\varepsilon\in [0,1)$, i.e., such channels possess the partial strong converse property. Furthermore, we derive sufficient conditions for the partial strong converse property to hold for memoryless but non-stationary symmetric and degraded wiretap channels. Our proof techniques leverage the information spectrum method, which allows us to establish a necessary and sufficient condition for the partial strong converse to hold for general wiretap channels without any information stability assumptions. △ Less

Submitted 26 September, 2014; v1 submitted 25 June, 2014; originally announced June 2014.

Comments: Presented at Allerton Conference 2014; Submitted to the IEEE Journal of Selected Topics in Signal Processing; v2 corrected typos and strengthened Theorem 4

The Effect of Eavesdropper's Statistics in Experimental Wireless Secret-Key Generation

Authors: Alexandre J. Pierrot, Rémi A. Chou, Matthieu R. Bloch

Abstract: This paper investigates the role of the eavesdropper's statistics in the implementation of a practical secret-key generation system. We carefully conduct the information-theoretic analysis of a secret-key generation system from wireless channel gains measured with software-defined radios. In particular, we show that it is inaccurate to assume that the eavesdropper gets no information because of de… ▽ More This paper investigates the role of the eavesdropper's statistics in the implementation of a practical secret-key generation system. We carefully conduct the information-theoretic analysis of a secret-key generation system from wireless channel gains measured with software-defined radios. In particular, we show that it is inaccurate to assume that the eavesdropper gets no information because of decorrelation with distance. We also provide a bound for the achievable secret-key rate in the finite key-length regime that takes into account the presence of correlated eavesdropper's observations. We evaluate this bound with our experimental gain measurements to show that operating with a finite number of samples incurs a loss in secret-key rate on the order of 20%. △ Less

Submitted 17 June, 2014; v1 submitted 11 December, 2013; originally announced December 2013.

Comments: Submitted to the IEEE Transactions on Information Forensics and Security

Secret key generation from Gaussian sources using lattice hashing

Authors: Cong Ling, Laura Luzzi, Matthieu R. Bloch

Abstract: We propose a simple yet complete lattice-based scheme for secret key generation from Gaussian sources in the presence of an eavesdropper, and show that it achieves strong secret key rates up to 1/2 nat from the optimal in the case of "degraded" source models. The novel ingredient of our scheme is a lattice-hashing technique, based on the notions of flatness factor and channel intrinsic randomness.… ▽ More We propose a simple yet complete lattice-based scheme for secret key generation from Gaussian sources in the presence of an eavesdropper, and show that it achieves strong secret key rates up to 1/2 nat from the optimal in the case of "degraded" source models. The novel ingredient of our scheme is a lattice-hashing technique, based on the notions of flatness factor and channel intrinsic randomness. The proposed scheme does not require dithering. △ Less

Submitted 22 June, 2013; originally announced June 2013.

Comments: 5 pages, Conference (ISIT 2013)

Strong Coordination over a Line Network

Authors: Matthieu R. Bloch, Joerg Kliewer

Abstract: We study the problem of strong coordination in a three-terminal line network, in which agents use common randomness and communicate over a line network to ensure that their actions follow a prescribed behavior, modeled by a target joint distribution of actions. We provide inner and outer bounds to the coordination capacity region, and show that these bounds are partially optimal. We leverage this… ▽ More We study the problem of strong coordination in a three-terminal line network, in which agents use common randomness and communicate over a line network to ensure that their actions follow a prescribed behavior, modeled by a target joint distribution of actions. We provide inner and outer bounds to the coordination capacity region, and show that these bounds are partially optimal. We leverage this characterization to develop insight into the interplay between communication and coordination. Specifically, we show that common randomness helps to achieve optimal communication rates between agents, and that matching the network topology to the behavior structure may reduce inter-agent communication rates. △ Less

Submitted 26 May, 2013; originally announced May 2013.

Comments: To be presented at ISIT 2013, Istanbul, Turkey

Polar Coding for Secret-Key Generation

Authors: Remi A. Chou, Matthieu R. Bloch, Emmanuel Abbe

Abstract: Practical implementations of secret-key generation are often based on sequential strategies, which handle reliability and secrecy in two successive steps, called reconciliation and privacy amplification. In this paper, we propose an alternative approach based on polar codes that jointly deals with reliability and secrecy. Specifically, we propose secret-key capacity-achieving polar coding schemes… ▽ More Practical implementations of secret-key generation are often based on sequential strategies, which handle reliability and secrecy in two successive steps, called reconciliation and privacy amplification. In this paper, we propose an alternative approach based on polar codes that jointly deals with reliability and secrecy. Specifically, we propose secret-key capacity-achieving polar coding schemes for the following models: (i) the degraded binary memoryless source (DBMS) model with rate-unlimited public communication, (ii) the DBMS model with one-way rate-limited public communication, (iii) the 1-to-m broadcast model and (iv) the Markov tree model with uniform marginals. For models (i) and (ii) our coding schemes remain valid for non-degraded sources, although they may not achieve the secret-key capacity. For models (i), (ii) and (iii), our schemes rely on pre-shared secret seed of negligible rate; however, we provide special cases of these models for which no seed is required. Finally, we show an application of our results to secrecy and privacy for biometric systems. We thus provide the first examples of low-complexity secret-key capacity-achieving schemes that are able to handle vector quantization for model (ii), or multiterminal communication for models (iii) and (iv). △ Less

Submitted 6 August, 2015; v1 submitted 21 May, 2013; originally announced May 2013.

Comments: 26 pages, 9 figures, accepted to IEEE Transactions on Information Theory; parts of the results were presented at the 2013 IEEE Information Theory Workshop

Low-power Secret-key Agreement over OFDM

Authors: Francesco Renna, Nicola Laurenti, Stefano Tomasin, Marco Baldi, Nicola Maturo, Marco Bianchi, Franco Chiaraluce, Matthieu Bloch

Abstract: Information-theoretic secret-key agreement is perhaps the most practically feasible mechanism that provides unconditional security at the physical layer to date. In this paper, we consider the problem of secret-key agreement by sharing randomness at low power over an orthogonal frequency division multiplexing (OFDM) link, in the presence of an eavesdropper. The low power assumption greatly simplif… ▽ More Information-theoretic secret-key agreement is perhaps the most practically feasible mechanism that provides unconditional security at the physical layer to date. In this paper, we consider the problem of secret-key agreement by sharing randomness at low power over an orthogonal frequency division multiplexing (OFDM) link, in the presence of an eavesdropper. The low power assumption greatly simplifies the design of the randomness sharing scheme, even in a fading channel scenario. We assess the performance of the proposed system in terms of secrecy key rate and show that a practical approach to key sharing is obtained by using low-density parity check (LDPC) codes for information reconciliation. Numerical results confirm the merits of the proposed approach as a feasible and practical solution. Moreover, the outage formulation allows to implement secret-key agreement even when only statistical knowledge of the eavesdropper channel is available. △ Less

Submitted 19 February, 2013; originally announced February 2013.

Comments: 9 pages, 4 figures; this is the authors prepared version of the paper with the same name accepted for HotWiSec 2013, the Second ACM Workshop on Hot Topics on Wireless Network Security and Privacy, Budapest, Hungary 17-19 April 2013

Separation of Reliability and Secrecy in Rate-Limited Secret-Key Generation

Authors: Remi A. Chou, Matthieu R. Bloch

Abstract: For a discrete or a continuous source model, we study the problem of secret-key generation with one round of rate-limited public communication between two legitimate users. Although we do not provide new bounds on the wiretap secret-key (WSK) capacity for the discrete source model, we use an alternative achievability scheme that may be useful for practical applications. As a side result, we conven… ▽ More For a discrete or a continuous source model, we study the problem of secret-key generation with one round of rate-limited public communication between two legitimate users. Although we do not provide new bounds on the wiretap secret-key (WSK) capacity for the discrete source model, we use an alternative achievability scheme that may be useful for practical applications. As a side result, we conveniently extend known bounds to the case of a continuous source model. Specifically, we consider a sequential key-generation strategy, that implements a rate-limited reconciliation step to handle reliability, followed by a privacy amplification step performed with extractors to handle secrecy. We prove that such a sequential strategy achieves the best known bounds for the rate-limited WSK capacity (under the assumption of degraded sources in the case of two-way communication). However, we show that, unlike the case of rate-unlimited public communication, achieving the reconciliation capacity in a sequential strategy does not necessarily lead to achieving the best known bounds for the WSK capacity. Consequently, reliability and secrecy can be treated successively but not independently, thereby exhibiting a limitation of sequential strategies for rate-limited public communication. Nevertheless, we provide scenarios for which reliability and secrecy can be treated successively and independently, such as the two-way rate-limited SK capacity, the one-way rate-limited WSK capacity for degraded binary symmetric sources, and the one-way rate-limited WSK capacity for Gaussian degraded sources. △ Less

Submitted 16 May, 2014; v1 submitted 16 October, 2012; originally announced October 2012.

Comments: 18 pages, two-column, 9 figures, accepted to IEEE Transactions on Information Theory; corrected typos; updated references; minor change in title