1,720,969 research outputs found
Equivalent models for multi-terminal channels
Get PDFThe recently introduced network equivalence results are used to create bit-pipe models that can replace multi-terminal channels within a discrete memoryless network. The goal is to create a set of simple “components” or “blocks” that can be substituted for the channel in such a way that the resulting network is capable of emulating the operation of the original one. We develop general upper and lower bounding models for the multiple access channel and for a class of broadcast channels. These bounds are sharp in the sense that there exists networks where the original channel can achieve the maximum sum rate permissible through the upper or lower bounding models. This approach provides a simple method for analyzing the capacity of large networks, which we illustrate with an example
Forgot your password: Correlation dilution
No full textWe consider the problem of diluting common randomness from correlated observations by separated agents. This problem creates a new framework to study statistical privacy, in which a legitimate party, Alice, has access to a random variable X, whereas an attacker, Bob, has access to a random variable Y dependent on X drawn from a joint distribution p[subscript X,Y]. Alice's goal is to produce a non-trivial function of her available information that is uncorrelated with (has small correlation with) any function that Bob can produce based on his available information. This problem naturally admits a minimax formulation where Alice plays first and Bob follows her. We define dilution coefficient as the smallest value of correlation achieved by the best strategy available to Alice, and characterize it in terms of the minimum principal inertia components of the joint probability distribution p[subscript X,Y]. We then explicitly find the optimal function that Alice must choose to achieve this limit. We also establish a connection between differential privacy and dilution coefficient and show that if Y is ε-differentially private from X, then dilution coefficient can be upper bounded in terms of ε. Finally, we extend to the setting where Alice and Bob have access to i.i.d. copies of (X[subscript i], Y[subscript i]), i = 1, ..., n and show that the dilution coefficient vanishes exponentially with n. In other words, Alice can achieve better privacy as the number of her observations grows
Multi-User Guesswork and Brute Force Security
Get PDFThe guesswork problem was originally motivated by a desire to quantify computational security for single user systems. Leveraging recent results from its analysis, we extend the remit and utility of the framework to the quantification of the computational security of multi-user systems. In particular, assume that V users independently select strings stochastically from a finite, but potentially large, list. An inquisitor who does not know which strings have been selected wishes to identify U of them. The inquisitor knows the selection probabilities of each user and is equipped with a method that enables the testing of each (user, string) pair, one at a time, for whether that string had been selected by that user. Here, we establish that, unless U=V, there is no general strategy that minimizes the distribution of the number of guesses, but in the asymptote as the strings become long we prove the following: by construction, there is an asymptotically optimal class of strategies; the number of guesses required in an asymptotically optimal strategy satisfies a large deviation principle with a rate function, which is not necessarily convex, that can be determined from the rate functions of optimally guessing individual users' strings; if all users' selection statistics are identical, the exponential growth rate of the average guesswork as the string-length increases is determined by the specific Rényi entropy of the string-source with parameter (V-U+1)/(V-U+2), generalizing the known V=U=1 case; and that the Shannon entropy of the source is a lower bound on the average guesswork growth rate for all U and V, thus providing a bound on computational security for multi-user systems. Examples are presented to illustrate these results and their ramifications for systems design
Fundamental limits of perfect privacy
Get PDFWe investigate the problem of intentionally disclosing information about a set of measurement points X (useful information), while guaranteeing that little or no information is revealed about a private variable S (private information). Given that S and X are drawn from a finite set with joint distribution pS,X, we prove that a non-trivial amount of useful information can be disclosed while not disclosing any private information if and only if the smallest principal inertia component of the joint distribution of S and X is 0. This fundamental result characterizes when useful information can be privately disclosed for any privacy metric based on statistical dependence. We derive sharp bounds for the tradeoff between disclosure of useful and private information, and provide explicit constructions of privacy-assuring mappings that achieve these bounds
Recommended from our members
Machine Learning for Flavor Development
No full textCurrently, most flavor development is performed by chemists who experimentally iterate many times to find flavors that best fit specified requirements. In this study, three potential algorithms for automating and accelerating this process are examined and implemented, and the results are analyzed. The apriori algorithm, which generates probabilistic association rules, fails because it only predicts the coexistence of high-frequency features. The generative adversarial network (GAN) fails because the generator only exploits a small part of the solution space. However, the variational autoencoder (VAE) successfully recovers purposely omitted features 95.6% of the time, making it the most promising algorithm
Brute force searching, the typical set and Guesswork
Get PDFConsider the situation where a word is chosen probabilistically from a finite list. If an attacker knows the list and can inquire about each word in turn, then selecting the word via the uniform distribution maximizes the attacker's difficulty, its Guesswork, in identifying the chosen word. It is tempting to use this property in cryptanalysis of computationally secure ciphers by assuming coded words are drawn from a source's typical set and so, for all intents and purposes, uniformly distributed within it. By applying recent results on Guesswork, for i.i.d. sources it is this equipartition ansatz that we investigate here. In particular, we demonstrate that the expected Guesswork for a source conditioned to create words in the typical set grows, with word length, at a lower exponential rate than that of the uniform approximation, suggesting use of the approximation is ill-advised.United States. Dept. of Defense (Air Force Contract FA8721-05-C-0002
Guessing a password over a wireless channel (on the effect of noise non-uniformity)
Get PDFA string is sent over a noisy channel that erases some of its characters. Knowing the statistical properties of the string's source and which characters were erased, a listener that is equipped with an ability to test the veracity of a string, one string at a time, wishes to fill in the missing pieces. Here we characterize the influence of the stochastic properties of both the string's source and the noise on the channel on the distribution of the number of attempts required to identify the string, its guesswork. In particular, we establish that the average noise on the channel is not a determining factor for the average guesswork and illustrate simple settings where one recipient with, on average, a better channel than another recipient, has higher average guesswork. These results stand in contrast to those for the capacity of wiretap channels and suggest the use of techniques such as friendly jamming with pseudo-random sequences to exploit this guesswork behavior.United States. Dept. of Defense (Air Force Contract FA8721-05-C-0002
General exact formulations for the outage probability and for the performance of a hybrid combining method in wireless communication systems
Get PDFOrientador: Michel Daoud YacoubDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de ComputaçãoResumo: Este trabalho propõe uma formulação nova e prática para a probabilidade de outage em sistemas de comunicação sem fio, denominada Probabilidade de Outage Conjunta (JOP, do inglês Joint Outage Probability). Dado um conjunto de restrições para as razões sinal-interferência-mais-ruído de sinais mutuamentente interferentes, a JOP corresponde à probabilidade de que pelo menos uma dessas restrições não seja atendida. Uma solução exata e geral para a JOP é demonstrada, junto com uma condição necessária e suficiente para que ela seja não-trivial. Ademais, uma expressão fechada paraa JOP em um ambiente Rayleigh onde os sinais são independentes é apresentada. As formulações obtidas são ilustradas através de um exemplo em alocação de potência. Além disso, este trabalho introduz e investiga um esquema geral de combinação de diversidade, denominado MRCS, baseado na seleção de sinais combinados por razão máxima. Este método de combinação possui uma implementação simples e uma formulação analítica matematicamente tratável, podendo ser diretamente aplicada a situações onde existe seleção de sítio. Uma análise geral da distribuição de probabilidade (confiabilidade), taxa de cruzamento de nível e duração média de desvanecimento na saída do combinador é apresentada, além de exemplos para um ambiente de desvanecimento Nakagami-m. No entanto, o principal resultado da análise do MRCS é a demonstração de uma expressão fechada, exata e simples de implementar computacionalmente para a razão sinalruído média da saída do combinador. Esta expressão pode ser utilizada quando o produto entre o número de ramos combinados por razão máxima e o parâmetro de Nakagami-mé inteiro, generalizando um resultado já apresentado na literatura. As formulações introduzidas aqui podem ser diretamente aplicadas ao dimensionamento de redes sem fio.Abstract: This work presents a useful, novel formulation for the outage probability in wireless communication systems, here named Joint Outage Probability (JOP). Given a set of signal-to-interferenceplus-noise ratio restrictions for mutually interfering signals, the JOP corresponds to the probability that at least one of the restrictions is not satisfied. A general exact solution for the JOP is derived, along with a necessary and sufficient condition for a non-trivial solution. In addition, a closed-form expression for the JOP in an independent non-identically distributed Rayleigh scenario is obtained. An application example of the formulations is presented by a power allocation problem. In addition, this work also introduces and investigates a general diversity combining scheme, here named MRCS, in which maximal-ratio combined signals are chosen on a selection combining basis. This combining method has a simple implementation and a tractable analytical formulation that can be directly applied to situations in which site selection exists. A general analysis of the probability distribution (reliability), level crossing rate, and average fade duration at the output of the combiner is provided, along with examples for a Nakagami-m fading environment. The main result of the MRCS analysis, however, is the derivation of an exact, easy-to-evaluate closed-form expression for the mean signal-to-noise ratio at the output of the combiner. Such an expression is applicable for conditions in which the product of the number of maximal ratio combining branches and the Nakagami-m parameter is an integer and it generalizes a result presented elsewhere in the literature. The formulations derived here find a direct applicability in the dimensioning of practical wireless networks.MestradoTelecomunicações e TelemáticaMestre em Engenharia Elétric
Information-theoretic metrics for security and privacy
No full textThesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.Cataloged from PDF version of thesis.Includes bibliographical references (pages 143-150).In this thesis, we study problems in cryptography, privacy and estimation through the information-theoretic lens. We introduce information-theoretic metrics and associated results that shed light on the fundamental limits of what can be learned from noisy data. These metrics and results, in turn, are used to evaluate and design both symmetric-key encryption schemes and privacy-assuring mappings with provable information-theoretic security guarantees. We start by studying information-theoretic properties of symmetric-key encryption in the "small key" regime (i.e. when the key rate is smaller than the entropy rate of the message source). It is well known that security against computationally unbounded adversaries in such settings can only be achieved when the communicating parties share a key that is at least as long as the secret message (i.e. plaintext) being communicated, which is infeasible in practice. Nevertheless, even with short keys, we show that a certain level of security can be guaranteed, albeit not perfect secrecy. In order to quantify exactly how much security can be provided with short keys, we propose a new security metric, called symbol secrecy, that measures how much an adversary that observes only the encrypted message learns about individual symbols of the plaintext. Unlike most traditional rate-based information-theoretic metrics for security, symbol secrecy is non-asymptotic. Furthermore, we demonstrate how fundamental symbol secrecy performance bounds can be achieved through standard code constructions (e.g. Reed-Solomon codes). While much of information-theoretic security has considered the hiding of the plaintext, cryptographic metrics of security seek to hide functions thereof. Consequently, we extend the definition of symbol secrecy to quantify the information leaked about certain classes of functions of the plaintext. This analysis leads to a more general question: can security claims based on information metrics be translated into guarantees on what an adversary can reliably infer from the output of a security system? On the one hand, information metrics usually quantify how far the probability distribution between the secret and the disclosed information is from the ideal case where independence is achieved. On the other hand, estimation guarantees seek to assure that an adversary cannot significantly improve his estimate of the secret given the information disclosed by the system. We answer this question in the positive, and present formulations based on rate-distortion theory that allow security bounds given in terms of information metrics to be transformed into bounds on how well an adversary can estimate functions of secret variable. We do this by solving a convex program that minimizes the average estimation error over all possible distributions that satisfy the bound on the information metric. Using this approach, we are able to derive a set of general sharp bounds on how well certain classes of functions of a hidden variable can(not) be estimated from a noisy observation in terms of different information metrics. These bounds provide converse (negative) results: If an information metric is small, then any non-trivial function of the hidden variable cannot be estimated with probability of error or mean-squared error smaller than a certain threshold. The main tool used to derive the converse bounds is a set of statistics known as the Principal Inertia Components (PICs). The PICs provide a fine-grained decomposition of the dependence between two random variables. Since there are well-studied statistical methods for estimating the PICs, we can then determine the (im)possibility of estimating large classes of functions by using the bounds derived in this thesis and standard statistical tests. The PICs are of independent interest, and are applicable to problems in information theory, statistics, learning theory, and beyond. In the security and privacy setting, the PICs fulfill the dual goal of providing (i) a measure of (in)dependence between the secret and disclosed information of a security system, and (ii) a complete characterization of the functions of the secret information that can or cannot be reliably inferred given the disclosed information. We study the information-theoretic properties of the PICs, and show how they characterize the fundamental limits of perfect privacy. The results presented in this thesis are applicable to estimation, security and privacy. For estimation and statistical learning theory, they shed light on the fundamental limits of learning from noisy data, and can help guide the design of practical learning algorithms. Furthermore, as illustrated in this thesis, the proposed converse bounds are particularly useful for creating security and privacy metrics, and characterize the inherent trade-off between privacy and utility in statistical data disclosure problems. The study of security systems through the information-theoretic lens adds a new dimension for understanding and quantifying security against very powerful adversaries. Furthermore, the framework and metrics discussed here provide practical insight on how to design and improve security systems using well-known coding and optimization techniques. We conclude the thesis by presenting several promising future research directions.by Flavio du Pin Calmon.Ph. D
Lists that are smaller than their parts: A coding approach to tunable secrecy
Get PDFWe present a new information-theoretic definition and associated results, based on list decoding in a source coding setting. We begin by presenting list-source codes, which naturally map a key length (entropy) to list size. We then show that such codes can be analyzed in the context of a novel information-theoretic metric, ϵ-symbol secrecy, that encompasses both the one-time pad and traditional rate-based asymptotic metrics, but, like most cryptographic constructs, can be applied in non-aymptotic settings. We derive fundamental bounds for ϵ-symbol secrecy and demonstrate how these bounds can be achieved with MDS codes when the source is uniformly distributed. We discuss applications and implementation issues of our codes.United States. Dept. of Defense (Air Force Contract FA8721-05-C-0002
- …
