We study the asymptotic behaviour of (a) information leakage and (b) adversary's error probability in information hiding systems modelled as noisy channels. Specifically, we assume the attacker can make a single guess after observing n independent executions of the system, throughout which the secret information is kept fixed. We show that the asymptotic behaviour of quantities (a) and (b) can be determined in a simple way from the channel matrix. Moreover, simple and tight bounds on them as functions of n show that the convergence is exponential. We also discuss feasible methods to evaluate the rate of convergence. Our results cover both the Bayesian case, where an a priori probability distribution on the secrets is assumed known to the attacker, and the maximum-likelihood case, where the attacker does not know such distribution. In the Bayesian case, we identify the distributions that maximize leakage. We consider both the min-entropy setting studied by Smith and the additive form recently proposed by Braun et al. and show the two forms do agree asymptotically. Next, we extend these results to a more sophisticated eavesdropping scenario, where the attacker can perform a (noisy) observation at each state of the computation and the systems are modelled as hidden Markov models.
We study the asymptotic behaviour of (a) information leakage and (b) adversary's error probability in information hiding systems modelled as noisy channels. Specifically, we assume the attacker can make a single guess after observing n independent executions of the system, throughout which the secret information is kept fixed. We show that the asymptotic behaviour of quantities (a) and (b) can be determined in a simple way from the channel matrix. Moreover, simple and tight bounds on them as functions of n show that the convergence is exponential. We also discuss feasible methods to evaluate the rate of convergence. Our results cover both the Bayesian case, where an a priori probability distribution on the secrets is assumed known to the attacker, and the maximum-likelihood case, where the attacker does not know such distribution. In the Bayesian case, we identify the distributions that maximize leakage. We consider both the min-entropy setting studied by Smith and the additive form recently proposed by Braun et al. and show the two forms do agree asymptotically. Next, we extend these results to a more sophisticated eavesdropping scenario, where the attacker can perform a (noisy) observation at each state of the computation and the systems are modelled as hidden Markov models.
In information-hiding, an adversary that tries to infer the secret information has a higher probability of success if it knows the distribution on the secrets. We show that if the system leaks probabilistically some information about the secrets, (that is, if there is a probabilistic correlation between the secrets and some observables) then the adversary can approximate such distribution by repeating the observations. More precisely, it can approximate the distribution on the observables by computing their frequencies, and then derive the distribution on the secrets by using the correlation in the inverse direction. We illustrate this method, and then we study the bounds on the approximation error associated with it, for various natural notions of error. As a case study, we apply our results to Crowds, a protocol for anonymous communication.
Secret key establishment from common randomness has been traditionally investigated under cartain limiting assumptions, of which the most ubiquitous appears to be that the information available to all parties comes in the form of independent and identically distributed (i.i.d.) samples of some correlated random variables. Unfortunately, models employing the i.i.d assumption are often not accurate representations of real scenarios. A more capable model would represent the available information as correlated hidden Markov models (HMMs), based on the same underlying Markov chain. Such a model accurately reflects the scenario where all parties have access to imperfect observations of the same source random process, exhibiting a certain time dependency. In this paper, we derive a computationally-efficient asymptotic converse bound for the secret key capacity of the correlated-HMM scenario. The main obstacle, not only for our model, but also for other non-i.i.d cases, is the computational complexity. We address this by converting the initial bound to a product of Markov random matrices, and using recent results regarding its convergence to a Lyapunov exponent. The methods developed in the paper are easily extensible to derive a secret-key capacity lower bound.
This paper introduces g-leakage, a rich generalization of the min-entropy model of quantitative information flow. In g-leakage, the benefit that an adversary derives from a certain guess about a secret is specified using a gain function g. Gain functions allow a wide variety of operational scenarios to be modeled, including those where the adversary benefits from guessing a value close to the secret, guessing a part of the secret, guessing a property of the secret, or guessing the secret within some number of tries. We prove important properties of g-leakage, including bounds between min-capacity, g-capacity, and Shannon capacity. We also show a deep connection between a strong leakage ordering on two channels, C1and C2, and the possibility of factoring C1into C2C3, for some C3. Based on this connection, we propose a generalization of the Lattice of Information from deterministic to probabilistic channels.
Physical-layer security aims to exploit the randomness inherent in communication channels in order to guarantee confidentiality even against computationally unlimited attackers. In this thesis, we focus on covert communication, also known as “communication with low probability of detection”. This is a scenario where a transmitter and receiver try to prevent an eavesdropper from making a good guess on whether a communication is ongoing or not. We assume that the receiver and the eavesdropper share the same channel and therefore see the same outputs. In this scenario, the transmitter shares a key with the legitimate receiver to provide the necessary advantage to detect the communication and reliably decode the message. Asymptotically, the amount of information that can be sent reliably and covertly scales like the square root of the number of channel uses; this is known as the square root law of covert communication.We study the corresponding scaling constant of the square root law for general memoryless channels including non-Gaussian additive noise, as well as Gaussian channels with memory. In the latter case, we show that the scaling constant is the same as over the memoryless Gaussian channel. For continuous memoryless channels, under mild integrability conditions, we show that the scaling constant is upper bounded by a simple expression which only involves the variance of the logarithm of the probability density function of the noise. Moreover, we show that under some additional assumptions, this upper bound is tight. Furthermore, we provide upper bounds on the length of the secret key required to achieve covertness.The second objective of this work is to investigate the limits of covert communication over continuous memoryless channels in the finite blocklength regime. We provide bounds for the first and second-order asymptotics for covert communication over an AWGN channel under a maximal error probability criterion and for the first-order asymptotics under an average error probability criterion.
Secret sharing is an instrumental tool for sharing secret keys in distributed systems. In a classical threshold setting, this involves a dealer who has a secret/key, a set of parties/users to which shares of the secret are sent, and a threshold on the number of users whose presence is needed in order to recover the secret. In secret sharing, secure links with no leakage are often assumed between the involved parties. However, when the users are nodes in a communication network and all the links are physical links, e.g., wireless, such assumptions are not valid anymore. In order to study this critical problem, we propose a statistical leakage model of secret sharing, where some noisy versions of all the secret shares might be independently leaked to an adversary. We then study the resilience of the seminal Shamir's secret sharing scheme with statistical leakage, and bound certain measures of security (i.e., semantic security, mutual information security), given other parameters of the system including the amount of leakage from each secret share. We show that for an extreme scenario of Shamir's scheme, in particular when the underlying field characteristic is 2, the security of each bit of the secret against leakage improves exponentially with the number of users. To the best of our knowledge, this is the first attempt towards understanding secret sharing under general statistical noisy leakage.
A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1 - e-1)-approximation of the maximum success probability. Moreover, for this problem it is NP-hard to obtain an approximation ratio strictly better than (1 - e-1). 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most 1/1-e-1. In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú.