We consider multiparty information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of private protocols is of interest both because random bits are considered a scarce resource and because of the relation between that complexity measure and other complexity measures of boolean functions such as the circuit size or the sensitivity of the function being computed [Kushilevitz, Ostrovsky, and Rosén, J. Comput. Syst. Sci., 58 (1999), pp. 129--136] and [Gál and Rosén, SIAM J. Comput., 31 (2002), pp. 1424--1437]. More concretely, we consider the randomness complexity of the basic Boolean function \tt and, that serves as a building block in the design of many private protocols. We show that \tt and cannot be privately computed using a single random bit, thus giving the first nontrivial lower bound on the 1-private randomness complexity of an explicit Boolean function, $f: \{0,1\}^n \rightarrow \{0,1\}$. We further show that and, on any number of inputs $n$ (one input bit per player), can be privately computed using 8 random bits (and 7 random bits in the special case of $n=3$ players), improving the upper bound of 73 random bits implicit in [Kushilevitz, Ostrovsky, and Rosén, J. Comput. Syst. Sci., 58 (1999), pp. 129--136]. Together with our lower bound, we thus approach the exact determination of the randomness complexity of \tt and. To the best of our knowledge, the exact randomness complexity of private computation is not known for any explicit function (except for \tt xor, which is 1-random, and for several degenerate functions).

Masking is a class of well-known countermeasure against side-channel analysis by employing the idea of secret sharing. The theoretical security proof model of higher-order masking was initiated by Ishai, Sahai, and Wagner, and Barthe et al. pushed forward it by proposing a more refine security definition named as t-SNI security. In CHES 2016, a new attack called horizontal side-channel attacks (HSCAs) came forward and successfully broke the Rivain-Prouff countermeasure, which has been proved to satisfy the t-SNI security. It presents a dilemma: instead of more secure, masking with higher-order may be more vulnerable due to the HSCA. Although there already exists an effective countermeasure for the Rivain-Prouff scheme, it is quite difficult to apply this method in the table recomputation-based higher-order masking schemes, such as the scheme introduced by Coron in EUROCRYPT 2014. To fill this gap, we propose a new table recomputation-based higher-order masking scheme, named as table compression masking (TCM) scheme. While meeting the t-SNI security, our new countermeasure is also secure against the HSCA. We give the formal security proof under the t-SNI security definition, as well as a heuristic security analysis considering the HSCA. Our analysis shows that, by dividing the full lookup table into many distinct parts and shifting them by refreshed shares, the same share will never be manipulated for more than twice in TCM scheme. This feature gives a heuristic security against HSCA. To our best knowledge, our countermeasure is the first solution for table recomputation-based higher-order masking to resist HSCA.

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.

Since the preliminary works of Kocher et al. in the nineties, studying and enforcing the resistance of cryptographic implementations against side channel analysis (SCA) is became a dynamic and prolific area of embedded security. Stochastic attacks, introduced by Schindler et al., form one of the main families of SCA and they offer a valuable alternative to template attacks which are known to be among the most efficient ones. However, stochastic attacks, as long as template attacks, have been initially designed for adversaries with a perfect copy of the target device in hand. Such a prerequisite makes them a pertinent tool when studying the implementations resistance against the most powerful adversaries, but it limits their pertinence as a cryptanalytic technique. Indeed, getting open access to a copy of the device under attack is difficult in practice and, even when possible, it remains difficult to exploit templates acquired on one device to attack another one. In light of this observation, several papers have been published to adapt stochastic attacks for contexts where the above prerequisite is no longer needed. They succeeded in defining practical attacks against unprotected implementations but no work was published until now to explain how stochastic attacks can be applied against secure implementations. In this paper, we deal with this issue. We first extend the previous analyses of stochastic attacks to highlight their core foundations. Then, we explain how they can be generalized to defeat first-order masking techniques, which are the main SCA countermeasures. Eventually, we illustrate the interest of the new attack by a series of experiments on simulated and real curves.

On smart card environment, speed and memory optimization of cryptographic algorithms are an ongoing preoccupation. In addition, there is the necessity to protect the device against various attacks. In this paper we present a fault attack detection scheme for the AES using digest values. They are deduced from the mathematical description of each AES individual transformation. The security of our countermeasure is proved in a realistic fault model. Moreover we show that it can be combined with data masking to thwart efficiently both FA and DPA. Eventually, implementations of our method are presented, showing that it can be an interesting alternative to the traditional doubling countermeasure method.

Second order Differential Power Analysis (2O-DPA) is a powerful side-channel attack that allows an attacker to bypass the widely used masking countermeasure. To thwart 2O-DPA, higher order masking may be employed but it implies a nonnegligible overhead. In this context, there is a need to know how efficient a 2O-DPA can be, in order to evaluate the resistance of an implementation that uses first order masking and, possibly, some hardware countermeasures. Different methods of mounting a practical 2O-DPA attack have been proposed in the literature. However, it is not yet clear which of these methods is the most efficient. In this paper, we give a formal description of the higher order DPA that are mounted against software implementations. We then introduce a framework in which the attack efficiencies may be compared. The attacks we focus on involve the combining of several leakage signals and the computation of correlation coefficients to discriminate the wrong key hypotheses. In the second part of this paper, we pay particular attention to 2O-DPA that involves the product combining or the absolute difference combining. We study them under the assumption that the device leaks the Hamming weight of the processed data together with an independent Gaussian noise. After showing a way to improve the product combining, we argue that in this model, the product combining is more efficient not only than absolute difference combining, but also than all the other combining techniques proposed in the literature.