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.
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.
This paper studies the problem of optimal channel design. For a given input probability distribution and for hard and soft design constraints, the aim here is to design a (probabilistic) channel whose output leaks minimally from its input. To analyse this problem, general notions of entropy and information leakage are introduced. It can be shown that, for all notions of leakage here defined, the optimal channel design problem can be solved using convex programming with zero duality gap. Subsequently, the optimal channel design problem is studied in a game-theoretical framework: games allow for analysis of optimal strategies of both the defender and the adversary. It is shown that all channel design problems can be studied in this game-theoretical framework, and that the defender's Bayes-Nash equilibrium strategies are equivalent to the solutions of the convex programming problem. Moreover, the adversary's equilibrium strategies correspond to a robust inference problem.
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.
This monograph studies the theory of information through the multiuser secret key agreement problem. A general notion of mutual dependence is established for the secrecy capacity, as a natural generalization of Shannon's mutual information to the multivariate case. Under linear-type source models, this capacity can be achieved practically by linear network codes. In addition to being an unusual application of the network coding solution to a secrecy problem, it gives secrecy capacity an interpretation of network information flow and partition connectivity, further confirming the intuitive meaning of secrecy capacity as mutual dependence. New identities in submodular function optimization and matroid theory are discovered in proving these results. A framework is also developed to view matroids as graphs, allowing certain theory on graphs to generalize to matroids.
In order to study cooperation schemes in a network, a general channel model with multiple inputs is formulated. Single-letter secrecy capacity upper bounds are derived using the Shearer-type lemma. Lower bounds are obtained with a new cooperation scheme called the mixed source emulation. In the same way that mixed strategies may surpass pure strategies in zero-sum games, mixed source emulation outperforms the conventional pure source emulation approach in terms of the achievable key rate. Necessary and sufficient conditions are derived for tightness of these secrecy bounds, which shows that secrecy capacity can be characterized for a larger class of channels than the broadcast-type channels considered in previous work. The mixed source emulation scheme is also shown to be unnecessary for some channels while insufficient for others. The possibility of a better cooperative scheme becomes apparent, but a general scheme remains to be found. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
In this paper without tailoring to any physical channel condition or any restriction on adversary's computational resources we design a secrecy scheme with information leakage that decays at an exponential rate. The only advantage for legitimate users over eavesdropper is existence of a key source that is partially known by Eve. A key extractor based on a sampler and a Renyi extractor derives secret keys with the required entropy from this source. Encryption using this key with a general cipher maps Eve's uncertainty about the key to uncertainty about the plaintext that can also be interpreted as degradation in her channel. Using privacy amplification on top of this cipher based on inverse universal2 hashing results in information leakage with decreasing exponent that can be optimized to guarantee a higher level of secrecy.
Abstract. In this paper, information theoretic cryptography is discussed based on conditional Rényi entropies. Our discussion focuses not only on cryptography but also on the definitions of conditional Rényi entropies and the related information theoretic inequalities. First, we revisit conditional Rényi entropies, and clarify what kind of properties are required and actually satisfied. Then, we propose security criteria based on Rényi entropies, which suggests us deep relations between (conditional) Rényi entropies and error probabilities by using several guessing strategies. Based on these results, unified proof of impossibility, namely, the lower bounds of key sizes is derived based on conditional Rényi entropies. Our model and lower bounds include the Shannon’s perfect secrecy, and the minentropy based encryption presented by Dodis, and Alimomeni and Safavi-Naini. Finally, new optimal symmetric key cryptography and almost optimal secret sharing schemes are proposed which achieve our lower bounds.
In a secret sharing scheme, a secret s is divided into multiple shares and distributed among n participants. As more shares are collected, the mutual information between the secret and the shares increases monotonically. In the perfect case, the best known explicit lower bound on the share size is given by k2k−1⋅H(s), where H(s) is the entropy of the secret and k is the largest integer such that n ≥ 2k+k−2. This paper considers the non-perfect case, in which each share reveals at most a L1 fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of kL2k−1⋅H(s), under the condition n ≥ 2k+k+L−3. We provide a new lower bound that approaches the perfect-case bound, namely k2k−2+1/L⋅H(s), which holds under the condition n ≥ 2k+k+2L−4. The proof generalizes perfect-case techniques by increasing the number of participants by 2(L−1). These results refine our understanding of the trade-off between share size and information leakage in non-perfect secret sharing. In particular, we construct non-perfect access structures that nearly attain the perfect lower bound with fewer participants than previous non-perfect bounds, thus complementing and extending prior work.