Search

Non-orthogonal quantum states pose a fundamental challenge in quantum information processing, as they cannot be distinguished with absolute certainty. Conventionally, the focus has been on minimizing error probability in quantum state discrimination tasks. However, another criterion known as quantum guesswork has emerged as a crucial measure in assessing the distinguishability of non-orthogonal quantum states, when we are allowed to query a sequence of states. In this paper, we generalize well known properties in the classical setting that are relevant for the guessing problem. Specifically, we establish the pre and post Data Processing Inequalities. We also derive a more refined lower bound on quantum guesswork., Comment: 6 pages

We leverage the Gibbs inequality and its natural generalization to R\'enyi entropies to derive closed-form parametric expressions of the optimal lower bounds of $\rho$th-order guessing entropy (guessing moment) of a secret taking values on a finite set, in terms of the R\'enyi-Arimoto $\alpha$-entropy. This is carried out in an non-asymptotic regime when side information may be available. The resulting bounds yield a theoretical solution to a fundamental problem in side-channel analysis: Ensure that an adversary will not gain much guessing advantage when the leakage information is sufficiently weakened by proper countermeasures in a given cryptographic implementation. Practical evaluation for classical leakage models show that the proposed bounds greatly improve previous ones for analyzing the capability of an adversary to perform side-channel attacks.

A new information theoretic condition is presented for reconstructing a discrete random variable $X$ based on the knowledge of a set of discrete functions of $X$. The reconstruction condition is derived from Shannon's 1953 lattice theory with two entropic metrics of Shannon and Rajski. Because such a theoretical material is relatively unknown and appears quite dispersed in different references, we first provide a synthetic description (with complete proofs) of its concepts, such as total, common and complementary informations. Definitions and properties of the two entropic metrics are also fully detailed and shown compatible with the lattice structure. A new geometric interpretation of such a lattice structure is then investigated that leads to a necessary (and sometimes sufficient) condition for reconstructing the discrete random variable $X$ given a set $\{ X_1,\ldots,X_{n} \}$ of elements in the lattice generated by $X$. Finally, this condition is illustrated in five specific examples of perfect reconstruction problems: reconstruction of a symmetric random variable from the knowledge of its sign and absolute value, reconstruction of a word from a set of linear combinations, reconstruction of an integer from its prime signature (fundamental theorem of arithmetic) and from its remainders modulo a set of coprime integers (Chinese remainder theorem), and reconstruction of the sorting permutation of a list from a minimal set of pairwise comparisons., Comment: 27 pages, 9 figures

A common countermeasure against side-channel attacks on secret key cryptographic implementations is $d$th-order masking, which splits each sensitive variable into $d+1$ random shares. In this paper, maximal leakage bounds on the probability of success of any side-channel attack are derived for any masking order. Maximal leakage (Sibson's information of order infinity) is evaluated between the sensitive variable and the noisy leakage, and is related to the conditional ``min-entropy'' (Arimoto's entropy of order infinity) of the sensitive variable given the leakage. The latter conditional entropy is then lower-bounded in terms of the conditional entropies for each share using majorization inequalities. This yields a generalization of Mrs. Gerber's lemma for min-entropy in finite Abelian groups.

Fitts' law is often employed as a predictive model for human movement, especially in the field of human-computer interaction. Models with an assumed Gaussian error structure are usually adequate when applied to data collected from controlled studies. However, observational data (often referred to as data gathered "in the wild") typically display noticeable positive skewness relative to a mean trend as users do not routinely try to minimize their task completion time. As such, the exponentially-modified Gaussian (EMG) regression model has been applied to aimed movements data. However, it is also of interest to reasonably characterize those regions where a user likely was not trying to minimize their task completion time. In this paper, we propose a novel model with a two-component mixture structure -- one Gaussian and one exponential -- on the errors to identify such a region. An expectation-conditional-maximization (ECM) algorithm is developed for estimation of such a model and some properties of the algorithm are established. The efficacy of the proposed model, as well as its ability to inform model-based clustering, are addressed in this work through extensive simulations and an insightful analysis of a human aiming performance study., Comment: 29 pages, 3 figures

Measuring the information leakage is critical for evaluating the practical security of cryptographic devices against side-channel analysis. Information-theoretic measures can be used (along with Fano's inequality) to derive upper bounds on the success rate of any possible attack in terms of the number of side-channel measurements. Equivalently, this gives lower bounds on the number of queries for a given success probability of attack. In this paper, we consider cryptographic implementations protected by (first-order) masking schemes, and derive several information-theoretic bounds on the efficiency of any (second-order) attack. The obtained bounds are generic in that they do not depend on a specific attack but only on the leakage and masking models, through the mutual information between side-channel measurements and the secret key. Numerical evaluations confirm that our bounds reflect the practical performance of optimal maximum likelihood attacks., Comment: The revised version will appear in ISIT 2022

A conditional version of Sibson's $\alpha$-information is defined using a simple closed-form "log-expectation" expression, which satisfies important properties such as consistency, uniform expansion, and data processing inequalities. This definition is compared to previous ones, which in contrast do not satisfy all of these properties. Based on our proposal and on a generalized Fano inequality, we extend the case $\alpha = 1$ of previous works to obtain sharp universal upper bounds for the probability of success of any type side-channel attack, particularly when $\alpha = 2$.

A Massey-like inequality is any useful lower bound on guessing entropy in terms of the computationally scalable Shannon entropy. The asymptotically optimal Massey-like inequality is determined and further refined for finite-support distributions. The impact of these results are highlighted for side-channel attack evaluation where guessing entropy is a key metric. In this context, the obtained bounds are compared to the state of the art.

A finite metric space is called here distance degree regular if its distance degree sequence is the same for every vertex. A notion of designs in such spaces is introduced that generalizes that of designs in $Q$-polynomial distance-regular graphs. An approximation of their cumulative distribution function, based on the notion of Christoffel function in approximation theory is given. As an application we derive limit laws on the weight distributions of binary orthogonal arrays of strength going to infinity. An analogous result for combinatorial designs of strength going to infinity is given., Comment: 18 pages

In 1994, Jim Massey proposed the guessing entropy as a measure of the difficulty that an attacker has to guess a secret used in a cryptographic system, and established a well-known inequality between entropy and guessing entropy. Over 15 years before, in an unpublished work, he also established a well-known inequality for the entropy of an integer-valued random variable of given variance. In this paper, we establish a link between the two works by Massey in the more general framework of the relationship between discrete (absolute) entropy and continuous (differential) entropy. Two approaches are given in which the discrete entropy (or R\'enyi entropy) of an integer-valued variable can be upper bounded using the differential (R\'enyi) entropy of some suitably chosen continuous random variable. As an application, lower bounds on guessing entropy and guessing moments are derived in terms of entropy or R\'enyi entropy (without side information) and conditional entropy or Arimoto conditional entropy (when side information is available)., Comment: 16 pages, 4 figures

The information leakage of a cryptographic implementation with a given degree of protection is evaluated in a typical situation when the signal-to-noise ratio is small. This is solved by expanding Kullback-Leibler divergence, entropy, and mutual information in terms of moments/cumulants.

A physically unclonable function (PUF) is an electronic circuit that produces an intrinsic identifier in response to a challenge. These identifiers depend on uncontrollable variations of the manufacturing process, which make them hard to predict or to replicate. Various security protocols leverage on such intrinsic randomness for authentification, cryptographic key generation, anti-counterfeiting, etc. Evaluating the entropy of PUFs (for all possible challenges) allows one to assess the security properties of such protocols. In this paper, we estimate the probability distribution of certain kinds of PUFs composed of $n$ delay elements. This is used to evaluate relevant R\'enyi entropies and determine how they increase with $n$. Such a problem was known to have extremely high complexity (in the order of $2^{2^n}$) and previous entropy estimations were carried out up to $n=7$. Making the link with the theory of Boolean threshold functions, we leverage on the representation by Chow parameters to estimate probability distributions up to $n=10$. The resulting Shannon entropy of the PUF is close to the max-entropy, which is asymptotically quadratic in $n$., Comment: 7 pages, 1 figure

A framework for deriving R\'enyi entropy-power inequalities (EPIs) is presented that uses linearization and an inequality of Dembo, Cover, and Thomas. Simple arguments are given to recover the previously known R\'enyi EPIs and derive new ones, by unifying a multiplicative form with constant c and a modification with exponent $\alpha$ of previous works. An information-theoretic proof of the Dembo-Cover-Thomas inequality---equivalent to Young's convolutional inequality with optimal constants---is provided, based on properties of R\'enyi conditional and relative entropies and using transportation arguments from Gaussian densities. For log-concave densities, a transportation proof of a sharp varentropy bound is presented., Comment: arXiv admin note: text overlap with arXiv:1807.02622

The usability of small devices such as smartphones or interactive watches is often hampered by the limited size of command vocabularies. This paper is an attempt at better understanding how finger identification may help users invoke commands on touch screens, even without recourse to multi-touch input. We describe how finger identification can increase the size of input vocabularies under the constraint of limited real estate, and we discuss some visual cues to communicate this novel modality to novice users. We report a controlled experiment that evaluated, over a large range of input-vocabulary sizes, the efficiency of single-touch command selections with vs. without finger identification. We analyzed the data not only in terms of traditional time and error metrics, but also in terms of a throughput measure based on Shannon's theory, which we show offers a synthetic and parsimonious account of users' performance. The results show that the larger the input vocabulary needed by the designer, the more promising the identification of individual fingers.

The matrix version of the entropy-power inequality for real or complex coefficients and variables is proved using a transportation argument that easily settles the equality case. An application to blind source extraction is given., Comment: 5 pages, in Proc. 2019 IEEE International Symposium on Information Theory (ISIT 2019), Paris, France, July 7-12, 2019

Following a recent proof of Shannon's entropy power inequality (EPI), a comprehensive framework for deriving various EPIs for the R\'enyi entropy is presented that uses transport arguments from normal densities and a change of variable by rotation. Simple arguments are given to recover the previously known R\'enyi EPIs and derive new ones, by unifying a multiplicative form with constant c and a modification with exponent {\alpha} of previous works. In particular, for log-concave densities, we obtain a simple transportation proof of a sharp varentropy bound., Comment: 17 page. Entropy Journal, to appear

Trajectories in human aimed movements are inherently variable. Using the concept of positional variance profiles, such trajectories are shown to be decomposable into two phases: In a first phase, the variance of the limb position over many trajectories increases rapidly; in a second phase, it then decreases steadily. A new theoretical model, where the aiming task is seen as a Shannon-like communication problem, is developed to describe the second phase: Information is transmitted from a source (determined by the position at the end of the first phase), to a destination (the movement's end-point) over a channel perturbed by Gaussian noise, with the presence of a noiseless feedback link. Information-theoretic considerations show that the positional variance decreases exponentially with a rate equal to the channel capacity C. Two existing datasets for simple pointing tasks are re-analyzed and observations on real data confirm our model. The first phase has constant duration and C is found constant across instructions and task parameters, which thus characterizes the participant's performance. Our model provides a clear understanding of the speed-accuracy tradeoff in aimed movements: Since the participant's capacity is fixed, a higher prescribed accuracy necessarily requires a longer second phase resulting in an increased overall movement time. The well-known Fitts' law is also recovered using this approach.

We present a simple proof of the entropy-power inequality using an optimal transportation argument which takes the form of a simple change of variables. The same argument yields a reverse inequality involving a conditional differential entropy which has its own interest. It can also be generalized in various ways. The equality case is easily captured by this method and the proof is formally identical in one and several dimensions., Comment: IEEE Information Theory and Applications Workshop (ITA 2017), San Diego, USA, Feb. 12-17, 2017

The corner points of the capacity region of the two-user Gaussian interference channel under strong or weak interference are determined using the notions of almost Gaussian random vectors, almost lossless addition of random vectors, and almost linearly dependent random vectors. In particular, the "missing" corner point problem is solved in a manner that differs from previous works in that it avoids the use of integration over a continuum of SNR values or of Monge-Kantorovitch transportation problems.

Yet another simple proof of the entropy power inequality is given, which avoids both the integration over a path of Gaussian perturbation and the use of Young's inequality with sharp constant or R\'enyi entropies. The proof is based on a simple change of variables, is formally identical in one and several dimensions, and easily settles the equality case.

-DVB-T2 was the first industrial standard deploying rotated and cyclic Q delayed (RCQD)modulation to improve performance over fading channels. This enablesimportantgains compared toconventional quadrature amplitude modulations(QAM) under severe channel conditions.However, the corresponding demodulation complexitystill prevents its use forwider applications. This paper proposes several rotation angles for different QAM constellations anda corresponding low-complexity detection method. Results show that the proposed solution simplifies both the transmitter and the receiver with often betterperformancethan the proposed angles in DVB-T2. Compared with the lowest complexity demappers currently used in DVB-T2, the proposed solution achieves an additional reduction bymore than 60%. Index Terms- DVB-T2, Rotated and Cyclic Q Delayed (RCQD) Modulations, Signal Space Diversity (SSD), Fading Channel, Quadrature Amplitude Modulations (QAM), Max-Log, ComputationalComplexity.

While most useful information theoretic inequalities can be deduced from the basic properties of entropy or mutual information, up to now Shannon's entropy power inequality (EPI) is an exception: Existing information theoretic proofs of the EPI hinge on representations of differential entropy using either Fisher information or minimum mean-square error (MMSE), which are derived from de Bruijn's identity. In this paper, we first present an unified view of these proofs, showing that they share two essential ingredients: 1) a data processing argument applied to a covariance-preserving linear transformation; 2) an integration over a path of a continuous Gaussian perturbation. Using these ingredients, we develop a new and brief proof of the EPI through a mutual information inequality, which replaces Stam and Blachman's Fisher information inequality (FII) and an inequality for MMSE by Guo, Shamai and Verd\'u used in earlier proofs. The result has the advantage of being very simple in that it relies only on the basic properties of mutual information. These ideas are then generalized to various extended versions of the EPI: Zamir and Feder's generalized EPI for linear transformations of the random variables, Takano and Johnson's EPI for dependent variables, Liu and Viswanath's covariance-constrained EPI, and Costa's concavity inequality for the entropy power., Comment: submitted for publication in the IEEE Transactions on Information Theory, revised version

While most useful information theoretic inequalities can be deduced from the basic properties of entropy or mutual information, Shannon's entropy power inequality (EPI) seems to be an exception: available information theoretic proofs of the EPI hinge on integral representations of differential entropy using either Fisher's information (FI) or minimum mean-square error (MMSE). In this paper, we first present a unified view of proofs via FI and MMSE, showing that they are essentially dual versions of the same proof, and then fill the gap by providing a new, simple proof of the EPI, which is solely based on the properties of mutual information and sidesteps both FI or MMSE representations., Comment: 5 pages, accepted for presentation at the IEEE International Symposium on Information Theory 2007