We leverage the Gibbs inequality and its natural generalization to Rényi entropies to derive closed-form parametric expressions of the optimal lower bounds of$\rho \text{th}$-order guessing entropy (guessing moment) of a secret taking values on a finite set, in terms of the Rényi-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 common countermeasure against side-channel attacks on secret key cryptographic implementations is $d$ thorder 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.

Embedded cryptographic devices are usually protected against side-channel attacks by masking strategies. In this paper, the security of protected cryptographic implementations is evaluated for any masking order, using alpha-information measures. Universal upper bounds on the probability of success of any type of side-channel attack are derived. These also provide lower bounds on the minimum number of queries required to achieve a given success rate. An important issue, solved in this paper, is to remove the loss factor due to the masking field size.

In a theoretical context of side-channel attacks, optimal bounds between success rate and guessing entropy are derived with a simple majorization (Schur-concavity) argument. They are further theoretically refined for different versions of the classical Hamming weight leakage model, in particular assuming a priori equiprobable secret keys and additive white Gaussian measurement noise. Closed-form expressions and numerical computation are given. A study of the impact of the choice of the substitution box with respect to side-channel resistance reveals that its nonlinearity tends to homogenize the expressivity of success rate and guessing entropy. The intriguing approximate relation$GE=1/SR$is observed in the case of 8-bit bytes and low noise.

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.

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ényi entropy) of an integer-valued variable can be upper bounded using the differential (Rényi) 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ényi entropy (without side information) and conditional entropy or Arimoto conditional entropy (when side information is available).

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.

We study challenge codes for physically unclonable functions (PUFs). Starting from the classical Hadamard challenge code, we augment it by one vector. Numerical values suggest that the optimal choice of this vector for maximizing the entropy is to pick a vector the farthest away from the code formed by the challenges and their binary complements. This leads us to study the covering radius of Hadamard codes. A notion of bent sequence that generalizes the classical notion from Hadamard matrices of Sylvester type to general Hadamard matrices is given. Lower bounds for Paley-type Hadamard matrices are given.

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$.

We use linear programming (LP) to derive upper and lower bounds on the “kissing number” $A_{d}$ of any q-ary linear code C with distance distribution frequencies $A_{i}$, in terms of the given parameters $[n,\ k,\ d]$. In particular, a polynomial method gives explicit analytic bounds in a certain range of parameters, which are sharp for some low-rate codes like the first-order Reed-Muller codes. The general LP bounds are more suited to numerical estimates. Besides the classical estimation of the probability of decoding error and of undetected error, we outline recent applications in hardware protection against side-channel attacks using code-based masking countermeasures, where the protection is all the more efficient a s the kissing number is low.

Hick's law is a key quantitative law in Psychology that relates reaction time to the logarithm of the number of stimulus-response alternatives in a task. Its application to HCI is controversial: Some believe that the law does not apply to HCI tasks, others regard it as the cornerstone of interface design. The law, however, is often misunderstood. We review the choice-reaction time literature and argue that: (1) Hick's law speaks against, not for, the popular principle that 'less is better'; (2) logarithmic growth of observed temporal data is not necessarily interpretable in terms of Hick's law; (3) the stimulus-response paradigm is rarely relevant to HCI tasks, where choice-reaction time can often be assumed to be constant; and (4) for user interface design, a detailed examination of the effects on choice-reaction time of psychological processes such as visual search and decision making is more fruitful than a mere reference to Hick's law.

Using information-theoretic tools, this paper establishes a mathematical link between the probability of success of a side-channel attack and the minimum number of queries to reach a given success rate, valid for any possible distinguishing rule and with the best possible knowledge on the attacker's side. This link is a lower bound on the number of queries, which depends on the mutual information between the traces and the secret key. This leads us to derive upper bounds on the mutual information that are as tight as possible and can be easily calculated. It turns out that, in the case of additive white Gaussian noise, the bound on the probability of success of any attack is directly related to the signal-to-noise ratio (SNR). This leads to easy computations and predictions of the success rate for any leakage model.

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.

The design of Fitts' historical reciprocal tapping experiment gravely confounds index of difficulty ID with target distance D: Summary statistics for the candidate Fitts model and a competing model may appear identical, and the validity of Fitts' model for some tasks can be legitimately questioned. We show that the contamination of ID by either target distance D or width W is due to the common practices of pooling and averaging data belonging to different distance-width (D,W) pairs for the same ID, and taking a geometric progression for values of D and W. We analyze a case study of the validation of Fitts' law in eye-gaze movements, where an unfortunate experimental design has misled researchers into believing that eye-gaze movements are not ballistic. We then provide simple guidelines to prevent confounds: Practitioners should carefully design the experimental conditions of (D,W), fully distinguish data acquired for different conditions, and put less emphasis on r² scores. We also recommend investigating the use of stochastic sampling for D and W.

We introduce BIGFile, a new fast file retrieval technique based on the Bayesian Information Gain framework. BIGFile provides interface shortcuts to assist the user in navigating to a desired target (file or folder). BIGFile's split interface combines a traditional list view with an adaptive area that displays shortcuts to the set of file paths estimated by our computationally efficient algorithm. Users can navigate the list as usual, or select any part of the paths in the adaptive area. A pilot study of 15 users informed the design of BIGFile, revealing the size and structure of their file systems and their file retrieval practices. Our simulations show that BIGFile outperforms Fitchett et al.'s AccessRank, a best-of-breed prediction algorithm. We conducted an experiment to compare BIGFile with ARFile (AccessRank instantiated in a split interface) and with a Finder-like list view as baseline. BIGFile was by far the most efficient technique (up to 44% faster than ARFile and 64% faster than Finder), and participants unanimously preferred the split interfaces to the Finder.

Physicallyunclonable functions(PUF) have been used in various applications, such as device authentication, secure storage of sensitive data, and anti-counterfeiting. Different applications require various levels of reliability from the PUF. However, as of today, nopredictivemodel to characterize the PUF reliability has been developed. This is particularly a problem for PUFs with low error rates, because the lower the error rate, the larger the number of measurements required to obtain a good estimate. In this paper, we develop a predictive framework, which enables us to derive a closed-form expression of bothentropyandreliabilityfor several families of delay PUFs: the ring oscillator (RO) PUF, the RO sum PUF as well as the Loop PUF. Improving reliability with bit-filtering, we provide an explicit tradeoff between complexity, reliability and entropy. Error rates as low as 10-9or even lower can be achieved. Our theoretical results are validated by experiments on Loop PUFs implemented in 65 nm CMOS ASIC technology, also used to simulate the behavior of the RO PUF and the RO sum PUF.

Human movements are inherently variable and involve some feedback mechanism. A study of the positional variance in a tapping task reveals that the variance profiles are unimodal in time. In the variance-decreasing phase, the aiming task can be modeled by a Shannon-like communication scheme where information is transmitted from a "source" - determined by the distance to the target at maximum variance - to a "destination" - the movement endpoint - over a "channel" with feedback perturbed by Gaussian noise. Thanks to the feedback link, we show that the variance decreases exponentially at a rate given by the channel capacity. This is confirmed on real data. The proposed information-theoretic model has promise to improve our understanding of human aimed movements.

The rationale for Fitts’ law is that pointing tasks have the information-theoretic analogy of sending a signal over a noisy channel, thereby matching Shannon’s capacity formula. Yet, the currently received analysis is incomplete and unsatisfactory: There is no explicit communication model for pointing; there is a confusion between central concepts of capacity (a mathematical limit), throughput (an average performance measure), and bandwidth (a physical quantity); and there is also a confusion between source and channel coding so that Shannon’s Theorem 17 can be misinterpreted. We develop an information-theoretic model for pointing tasks where the index of difficulty (ID) is the expression of both a source entropy and a zero-error channel capacity. Then, we extend the model to include misses at rate ε and prove that ID should be adjusted to (1−ε)ID. Finally, we reflect on Shannon’s channel coding theorem and argue that only minimum movement times, not performance averages, should be considered.

In usual Fitts' law experiments the outcome of a pointing act can be either measured as an error, i.e., a distance from endpoint to target center, or categorized in an all-or-none way as a hit versus a miss. Information theory offers a useful distinction between transmission errors (the received symbol is wrong) and erasures (the received symbol is empty). Although Fitts' law research has been very much inspired by the information theoretic rationale, the error/erasure distinction has escaped attention so far: Target misses have always been treated as normally-distributed errors, through the effective index of difficulty IDe. The paper introduces a new index of difficulty based on the simple observation that a target miss conveys zero bit of information, i.e., it is an erasure. Not only is the new index more consistent with the fundamentals of information theory, it is much simpler to derive than the ISO-recommended IDe.

This paper introduces BIGnav, a new multiscale navigation technique based on Bayesian Experimental Design where the criterion is to maximize the information-theoretic concept of mutual information, also known as information gain. Rather than simply executing user navigation commands, BIGnav interprets user input to update its knowledge about the user's intended target. Then it navigates to a new view that maximizes the information gain provided by the user's expected subsequent input. We conducted a controlled experiment demonstrating that BIGnav is significantly faster than conventional pan and zoom and requires fewer commands for distant targets, especially in non-uniform information spaces. We also applied BIGnav to a realistic application and showed that users can navigate to highly probable points of interest on a map with only a few steps. We then discuss the tradeoffs of BIGnav--including efficiency vs. increased cognitive load--and its application to other interaction tasks.

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.

On the one hand, collision attacks have been introduced in the context of side-channel analysis for attackers who exploit repeated code with the same data without having any knowledge of the leakage model. On the other hand, stochastic attacks have been introduced to recover leakage models of internally processed intermediate secret variables. Both techniques have shown advantages and intrinsic limitations. Most collision attacks, for instance, fail in exploiting all the leakages (e.g., only a subset of matching samples are analyzed), whereas stochastic attacks cannot involve linear regression with the full basis (while the latter basis is the most informative one). In this paper, we present an innovative attacking approach, which combines the flavors of stochastic and collision attacks. Importantly, our attack is derived from the optimal distinguisher, which maximizes the success rate when the model is known. Notably, we develop an original closed-form expression, which shows many benefits by using the full algebraic description of the leakage model. Using simulated data, we show in the unprotected case that, for low noise, the stochastic collision attack is superior to the state of the art, whereas asymptotically and thus, for higher noise, it becomes equivalent to the correlation-enhanced collision attack. Our so-called stochastic collision attack is extended to the scenario where the implementation is protected by masking. In this case, our new stochastic collision attack is more efficient in all scenarios and, remarkably, tends to the optimal distinguisher. We confirm the practicability of the stochastic collision attack thanks to experiments against a public data set (DPA contest v4). Furthermore, we derive the stochastic collision attack in case of zero-offset leakage that occurs in protected hardware implementations and use simulated data for comparison. Eventually, we underline the capability of the new distinguisher to improve its efficiency when the attack multiplicity increases.

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ényi 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.

A novel “interclass information” side-channel distinguisher is compared to mutual information analysis. Interclass information possesses properties similar to mutual information but uses a different comparing strategy between the underlying conditional distributions. It is shown that interclass information can outperform mutual information in side-channel analysis, especially under low noise. The theoretical comparison is confirmed by simulations.

A physically unclonable function (PUF) is a hardware device that can generate intrinsic responses from challenges. The responses serve as unique identifiers and it is required that they be as little predictable as possible. A loop-PUF is an architecture where n single-bit delay elements are chained. Each PUF generates one bit response per challenge. We model the relationship between responses and challenges in a loop-PUF using Gaussian random variables and give a closed-form expression of the total entropy of the responses. It is shown that n bits of entropy can be obtained with n challenges if and only if the challenges constitute a Hadamard code. Contrary to a previous belief, it is shown that adding more challenges results in an entropy strictly greater than n bits. A greedy code construction is provided for this purpose.

International audience

DVB-T2 was the first industrial standard deploying rotated and cyclic Q delayed (RCQD) modulation to improve performance over fading channels. This enables important gains compared to conventional quadrature amplitude modulations (QAM) under severe channel conditions. However, the corresponding demodulation complexity still prevents its use for wider applications. This paper proposes several rotation angles for different QAM constellations and a corresponding low-complexity detection method. Results show that the proposed solution simplifies both the transmitter and the receiver with often better performance than the proposed angles in DVB-T2. Compared with the lowest complexity demappers currently used in DVB-T2, the proposed solution achieves an additional reduction by more than 60%.

In this paper, we consider a dual-hop Multiple Input Multiple Output (MIMO) wireless multi-relay network, in which a source-destination pair both equipped with multiple antennas communicates through multiple half-duplex amplify-and-forward (AF) relay terminals which are also with multiple antennas. Imperfect channel estimations for all nodes are considered. We propose a novel robust linear beamforming at the relays, based on the QR decomposition filter at the destination node which performs successive interference cancellation (SIC). Using Law of Large Number, we obtain the asymptotic rate, upon which the proposed relay beamforming is optimized. Simulation results show that the asymptotic rate matches with the ergodic rate well. Analysis and simulation results demonstrate that the proposed beamforming outperforms the conventional beamforming schemes.

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ú 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.

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.

This paper proposes a new joint source and channel coder based on real-valued BCH codes, in which the signal protection (analogous to a signal interpolation) is performed before compression. This allows a better tradeoff in high accuracy compression, since part of the distortion introduced by the compression can be corrected by the "channel decoder". Furthermore, we propose an optimal code allocation procedure, which also allows a good robustness to be obtained when the errors introduced by the channel increase. The resulting rate/distortion curves outperform those obtained by a separate system on the whole range of operation. Although presented in the context of image transmission through a binary symmetric channel, the resulting codes may be employed on a wide range of transmission schemes with significant performance benefits.

In this paper, a Bose-Chaudhuri-Hocquenghem (BCH) coder in the field of the real numbers is investigated for simultaneous source coding and impulse noise cancellation of satellite images. Our channel is a binary symmetric channel (BSC). Our approach is to make a carefully designed interpolation of the subband images prior to quantization and transmission. Compared to a classical tandem source and channel coding (TSC) scheme, in which a binary BCH coder would take place after quantization, our approach makes use of BCH coding prior to quantization, thus, allowing joint source and channel decoding. We also examine the issue of robust transmission of wavelet compressed images through the noisy channel: simulations show that we obtain a 3.7 dB improvement in PSNR over the classical entropy coder for a global rate of 3.25 transmitted bits per pixel and small BSC crossover probability.

A new image coding technique based on an Linfinity-norm criterion and exploiting statistical properties of the reconstruction error is investigated. The original image is preprocessed, quantized, encoded, and reconstructed within a given confidence interval. Two important classes of preprocessing, namely linear prediction and iterated filterbanks, are used. The approach is also shown to be compatible with previous techniques. The approach allows a great flexibility in that it can perform lossless coding as well as a controlled lossy one: specifications are typically that only p% the reconstructed pixels are different from the original ones.

In the context of subband processing of finite-length signals using FIR filter banks, a new technique is derived for achieving exact reconstruction when subband signals are truncated to the same number of samples as the original signal. Using a delayed truncation method in the subbands, it is shown that the missing samples can be recovered exactly by inverting small linear systems. Our approach also applies to time-varying filter banks or wavelet transforms where filters are switched between consecutive input blocks.>

A new image coding technique using statistical properties of quantization errors and L/sup /spl infin//-norm criterion is investigated. The original image is preprocessed, quantized, encoded and reconstructed within a given confidence interval. We focus on iterated filter banks as a preprocessing technique, and provide a comparison with linear prediction in the case of very good quality (almost lossless) image coding.>

Several algorithms are reviewed for computing various types of wavelet transforms: the Mallat algorithm (1989), the 'a trous' algorithm, and their generalizations by Shensa. The goal of this work is to develop guidelines for implementing discrete and continuous wavelet transforms efficiently, and to compare the various algorithms obtained and give an idea of possible gains by providing operation counts. Most wavelet transform algorithms compute sampled coefficients of the continuous wavelet transform using the filter bank structure of the discrete wavelet transform. Although this general method is already efficient, it is shown that noticeable computational savings can be obtained by applying known fast convolution techniques, such as the FFT (fast Fourier transform), in a suitable manner. The modified algorithms are termed 'fast' because of their ability to reduce the computational complexity per computed coefficient from L to log L (within a small constant factor) for large filter lengths L. For short filters, smaller gains are obtained: 'fast running FIR (finite impulse response) filtering' techniques allow one to achieve typically 30% savings in computations.>

It is shown that filter banks arise naturally when implementing the continuous wavelet transform (CWT). The conditions under which the CWT can be computed exactly using discrete filter banks are determined, and fast CWT algorithms are derived. The complexity of the resulting algorithms increases linearly with the number of octaves. They are easily implemented by repetitive application of identical cells, to which various methods are applied for reducing the number of operations: FFT (fast Fourier transform) algorithms are most efficient for large filter lengths; for small lengths, fast running FIR (finite impulse response) algorithms are preferred.>

A formalism of signal energy representations depending on time and scale is presented. Precise links between time-frequency and time-scale energy distributions are provided. It is known that a full description of the former is given by Cohen's class, which can be described as a generalization of the spectrogram appropriately parameterized by a smoothing function acting on the Wigner-Ville distribution. A full description of the latter is given, resulting in a class of representations in which the smoothing of the Wigner-Ville distribution is scale-dependent. Through proper choice of the smoothing function, interesting properties may be imposed on the representation, which makes it a versatile tool for the analysis of nonstationary signals. Also, specific choices allow known definitions to be recovered (including the Bertrands' and the energetic version of the wavelet transform, referred to as the scalogram). Another very flexible choice uses separable smoothing functions. It is shown, in particular, that Gaussian kernels provide a continuous transition between spectrograms and scalograms by means of the Wigner-Ville distribution.>