International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Side-channel Masking with Pseudo-Random Generator

Authors:
Jean-Sébastien Coron , University of Luxembourg
Aurélien Greuet , IDEMIA, France
Rina Zeitoun , IDEMIA, France
Download:
DOI: 10.1007/978-3-030-45727-3_12 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2020
Abstract: High-order masking countermeasures against side-channel attacks usually require plenty of randomness during their execution. For security against t probes, the classical ISW countermeasure requires O(t^2 s) random bits, where s is the circuit size. However running a True Random Number Generator (TRNG) can be costly in practice and become a bottleneck on embedded devices. In [IKL+13] the authors introduced the notion of robust pseudo-random number generator (PRG), which must remain secure even against an adversary who can probe at most t wires. They showed that when embedding a robust PRG within a private circuit, the number of random bits can be reduced to O(t^4), that is independent of the circuit size s (up to a logarithmic factor). Using bipartite expander graphs, this can be further reduced to O(t^(3+eps)); however the resulting construction is unpractical. In this paper we describe a practical construction where the number of random bits is only O(t^2) for security against t probes, without expander graphs; moreover the running time of each pseudo-random generation goes down from O(t^4) to O(t). Our technique consists in using multiple independent PRGs instead of a single one. We show that for ISW circuits, the robustness property of the PRG is not required anymore, which leads to simple and efficient constructions. For example, for AES we only need 48 bytes of randomness to get second-order security (t=2), instead of 2880 in the original Rivain-Prouff countermeasure; when implemented on an ARM-based embedded device with a relatively slow TRNG, we obtain a 50% speed-up compared to Rivain-Prouff.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30180,
  title={Side-channel Masking with Pseudo-Random Generator},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Side-channel countermeasure;high-order masking;ISW security proof;randomness complexity.},
  volume={12105},
  doi={10.1007/978-3-030-45727-3_12},
  author={Jean-Sébastien Coron and Aurélien Greuet and Rina Zeitoun},
  year=2020
}