Secrecy by design is examined as an approach to information-theoretic secrecy. The main idea behind this approach is to design an information processing system from the ground up to be perfectly secure with respect to an explicit secrecy constraint. The principal technical contributions are decomposition bounds that allow the representation of a random variable$X$as a deterministic function of$({S},{Z})$, where$S$is a given fixed random variable and$Z$is constructed to be independent of$S$. Using the problems of privacy and lossless compression as examples, the utility cost of applying secrecy by design is investigated. Privacy is studied in the setting of the privacy funnel function previously introduced in the literature and new bounds for the regime of zero information leakage are derived. For the problem of lossless compression, it is shown that strong information-theoretic guarantees can be achieved using a reduced secret key size and a quantifiable penalty on the compression rate. The fundamental limits for both problems are characterized with matching lower and upper bounds when the secret$S$is a deterministic function of the information source$X$.
Secrecy by design is examined as an approach to information-theoretic secrecy. The main idea behind this approach is to design an information processing system from the ground up to be perfectly secure with respect to an explicit secrecy constraint. The principal technical contributions are decomposition bounds that allow the representation of a random variableXas a deterministic function of(S,Z), whereSis a given fixed random variable andZis constructed to be independent ofS. Using the problems of privacy and lossless compression as examples, the utility cost of applying secrecy by design is investigated. Privacy is studied in the setting of the privacy funnel function previously introduced in the literature and new bounds for the regime of zero information leakage are derived. For the problem of lossless compression, it is shown that strong information-theoretic guarantees can be achieved using a reduced secret key size and a quantifiable penalty on the compression rate. The fundamental limits for both problems are characterized with matching lower and upper bounds when the secretSis a deterministic function of the information sourceX.
Randomness plays a central role in computer science, in particular cryptography. Almost all cryptographic primitives depend crucially on randomness because randomness and unpredictability in secret keys provides the means for security. Usually one assumes that perfect randomness, a sequence of independently and uniformly distributed bits, are accessible to algorithms. This is a strong assumption. Physical sources of randomness are neither uniformly random, nor produce necessarily independent bits. Therefore, the aim of this thesis is to start from a realistic model of randomness, investigate notions of secrecy and their randomness requirements and finally find practical methods for generation of randomness that matches the requirements of cryptographic primitives. We consider a model of random source where the source output follows one distribution from a set of possible distributions, each with the property that the maximum probability of symbols is bounded and can not be arbitrarily close to 1. This model does not assume independence or uniformity of the output symbols, and is considered to be a realistic model of randomness. From this point, the thesis can be divided into two main parts: In the first part, considering various notions of information theoretic secrecy, a fundamental problem is to find the properties of randomness needed to achieve security in these notions. Traditional cryptographic protocols simply assume perfect randomness and build on this assumption. We explore the results that show secrecy can not be based on imperfect randomness that is not uniform or independent. Thus a line of work attempts to relax notions of secrecy in such a way that they can be constructed with non-perfect sources, and possibly require smaller key sizes. Yet they should match real life applications. An important work in this context is entropic security where the key size could be smaller than the message depending on message distribution. Inspired by this, we propose two relaxed notions of secrecy that are motivated by practical applications. In the first notion, motivated by an application in biometrics authentication, we propose guessing secrecy where the probability of guessing the message for a computational unbounded adversary with the best strategy remains the same when a ciphertext is given or when it is not. We compare the randomness requirements of guessing secrecy with stronger notions and show that in some cases such as key length, the requirements are the same. For key distribution however, we found a family of distributions that provide guessing secrecy but not perfect secrecy. In the second notion, we investigate randomness requirements of multiple message encryption. Considering a natural extension of secrecy definition to multiple messages, we show that independent keys are needed to encrypt each message. We then propose a relaxed notion in which the security of last message is more important than past messages, although the leakage of past messages is bounded using entropic security. By this assumption, we achieve smaller key length compared to indistinguishability, and comparable to key length for entropic security. This notion has applications such as location privacy. In the second part of the thesis, since secrecy crucially depends on perfect randomness, we investigate how perfect randomness can be practically generated, specifically from human game-play. Unlike many random number generators that assume independent or uniform random bits in the random source, we base our work on the realistic model of randomness. Our main observation is that human game-play has an element of randomness coming from the errors in their game-play which is the main entertaining factor of the game. We also observed that this game-play can distinguish among a group of people if the right features are collected from the game-play. We incrementally changed our game design until the distinguishability among a small population is maximized, and then run the experiments required to show the viability of this approach over a larger population. This approach can also provide a hard to delegate authentication property where a human could not emulate the behavior of another human even given statistical information about their game-play.
The aim of information-theoretic secrecy is to ensure that an eavesdropper who listens to the wireless transmission of a message can only collect an arbitrarily small number of information bits about this message. In contrast to cryptography, there are no assumptions on the computational power of the eavesdropper. Information-theoretically secret communication has been studied for many particular wireless network topologies. In the main part of this thesis, we consider such communication for arbitrary acyclic wireless network topologies. We provide lower and upper bounds on the strong perfect secrecy capacity for the case when the channels of the network are either Gaussian or deterministic. These results are based on the recent understanding of the capacity of wireless networks (without secrecy constraints) by Avestimehr, Diggavi and Tse. As a side result, we give inner and outer bounds on the capacity region for the multisource problem in arbitrary wireless networks with Gaussian or deterministic signal interaction. For linear deterministic signal interaction, we find the exact capacity region. For Gaussian signal interaction, we are able to bound the gap between the two bounds on the capacity region. This gap depends only on the network topology, but not on the signal-to-noise ratio (SNR), which leads to an approximation of the capacity region for the high SNR regime. We further consider a particular network topology, called the fan-network, in which we assume that an eavesdropper has physical access to every node in a subset of the relay nodes. We give a general upper bound on the perfect secrecy capacity, and we characterize the perfect secrecy capacity for two special cases. In the second part of the thesis, we consider interactive secrecy, i.e., secrecy in the presence of a public feedback link from the destination to the source. We focus on the problem of secret key generation rather than secret communication. The benefit of public discussion for secret key generation in a broadcast channel was first shown by Maurer. We extend his ideas to a relay network called the line network, leading to a lower bound on the strongly secret key capacity for this network topology. Finally, we introduce a new channel coding setup called the interference-multiple access (IMA) channel. This channel is a variant of the interference channel where one of the receivers is required to decode the messages from both transmitters. We derive an inner bound on the capacity region of the IMA channel, as well as an outer bound for the so-called structured IMA channel. In a semi-deterministic version of the structured IMA channel, the bounds match, providing a characterization of the capacity region. In the Gaussian case, we obtain a 1 bit-approximation of the capacity region. We also show an inner bound on the equivocation-capacity region for the IMA channel, where we require that part of the private message for one receiver is kept information-theoretically secret from the other receiver.
Perfect secrecy describes cases where an adversary cannot learn anything about the secret beyond its prior distribution. A classical result by Shannon shows that a necessary condition for perfect secrecy is that the adversary should not be able to eliminate any of the possible secrets. In this paper we answer the following fundamental question: What is the lowest leakage of information that can be achieved when some of the secrets have to be eliminated? We address this question by deriving the minimum leakage in closed-form, and explicitly providing "universally optimal" randomized strategies, in the sense that they guarantee the minimum leakage irrespective of the measure of entropy used to quantify the leakage. We then introduce a generalization of Rényi family of asymmetric measures of leakage which generalizes the g-leakage and show that a slight modification of our strategies are optimal with respect to an important class of such measures. Subsequently, we show that our schemes constitute the Nash Equilibria of closely related two-person zero sum games. This game perspective provides implicit solutions for a wider set of structural constraints and asymmetric entropies. Finally we demonstrate how this work can also be seen as designing a universally optimal channel given a specified prior.
In this chapter, we discuss the construction of practical codes for secrecy. The design of codes for the wiretap channel turns out to be surprisingly difficult, and this area of information-theoretic security is still largely in its infancy. To some extent, the major obstacles in the road to secrecy capacity are similar to those that lay in the path to channel capacity: the random-coding arguments used to establish the secrecy capacity do not provide explicit code constructions. However, the design of wiretap codes is further impaired by the absence of a simple metric, such as a bit error rate, which could be evaluated numerically. Unlike codes designed for reliable communication, whose performance is eventually assessed by plotting a bit-error-rate curve, we cannot simulate an eavesdropper with unlimited computational power; hence, wiretap codes must possess enough structure to be provably secure. For certain channels, such as binary erasure wiretap channels, the information-theoretic secrecy constraint can be recast in terms of an algebraic property for a code-generator matrix. Most of the chapter focuses on such cases since this algebraic view of secrecy simplifies the analysis considerably. As seen in Chapter 4, the design of secret-key distillation strategies is a somewhat easier problem insofar as reliability and security can be handled separately by means of information reconciliation and privacy amplification. Essentially, the construction of coding schemes for key agreement reduces to the design of Slepian–Wolf-like codes for information reconciliation, which can be done efficiently with low-density parity-check (LDPC) codes or turbo-codes.
We investigate an approach to physical-layer security based on the premise that the coding mechanism for secrecy over noisy channels is fundamentally tied to the notion of resolvability. Instead of considering capacity-based constructions, which associate to each message a sub-code whose rate approaches the capacity of the eavesdropper’s channel, we consider resolvability-based constructions, which associate to each message a sub-code whose rate is beyond the resolvability of the eavesdropper’s channel. We provide evidence that resolvability is a more powerful and perhaps more fundamental coding mechanism for secrecy by developing results that hold for strong secrecy metrics and arbitrary channels. Specifically, we show that, at least for binary symmetric wiretap channels, random capacity-based constructions fail to approach the strong secrecy capacity while resolvability-based constructions achieve it. We then obtain the secrecy-capacity region of arbitrary broadcast channels with confidential messages and a cost constraint for strong secrecy metrics, which generalizes existing results. Finally, we specialize our results to study the secrecy capacity of wireless channels with perfect channel state information, compound and mixed channels, as well as the secret-key capacity of source models for secret-key agreement. By tying secrecy to resolvability, we obtain achievable rates for stronger secrecy metrics and with simpler proofs than previously derived. Index Terms information-theoretic security, wiretap channel, secret-key agreement, information-spectrum, resolv-ability, wireless channels.
This paper addresses privacy leakage in biometric secrecy systems. Four settings are investigated. The first one is the standard Ahlswede-Csiszar secret-generation setting in which two terminals observe two correlated sequences. They form a common secret by interchanging a public message. This message should only contain a negligible amount of information about the secret, but here, in addition, we require it to leak as little information as possible about the biometric data. For this first case, the fundamental tradeoff between secret-key and privacy-leakage rates is determined. Also for the second setting, in which the secret is not generated but independently chosen, the fundamental secret-key versus privacy-leakage rate balance is found. Settings three and four focus on zero-leakage systems. Here the public message should only contain a negligible amount of information on both the secret and the biometric sequence. To achieve this, a private key is needed, which can only be observed by the terminals. For both the generated-secret and the chosen-secret model, the regions of achievable secret-key versus private-key rate pairs are determined. For all four settings, the fundamental balance is determined for both unconditional and conditional privacy leakage.