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

Classical Fault Attacks often require the ability to encrypt twice the same plaintext, in order to get one or several pairs of correct and faulty cipher texts corresponding to the same message. This observation led some designers to think that a randomized mode of operation may be sufficient to protect block cipher encryption against this kind of threat. In this paper, we consider the case where the adversary neither chooses nor knows the input messages, and has only access to the faulty cipher texts. In this context, we are able to describe several attacks against AES-128 by using non uniform fault models. Our attacks target the last 4 rounds and allow to recover the correct key with practical time complexity, using a limited number of faulty cipher texts. This work highlights the need for dedicated fault attack countermeasures in secure embedded systems.

Recent works show that a combination of perturbation and observation attacks on symmetric ciphers thwarts state-of-the-art countermeasures. In this paper, we first propose a new way - to our knowledge - to classify fault attacks against block ciphers, allowing us to exhibit their capacity to be combined with observation attacks. We then present a set of common protections against side-channel and fault attacks, namely higher-order masking schemes, detection and infection countermeasures, and how they can be combined. We show that the combination of a higher-order masking scheme and a detection countermeasure can actually be defeated by a slight variant of the combined attack of Roche et al., even if one applies their patch. Furthermore, we also demonstrate that none of the published infection countermeasures is robust against fault attacks. Finally, using randomness, we propose a set of enhanced countermeasures that thwart considered threats.