### Randomness Complexity of Private Circuits for Multiplication

Sonia Belaïd, Fabrice Benhamouda, Alain Passelègue, Emmanuel Prouff, Adrian Thillard, and Damien Vergnaud

##### Abstract

Many cryptographic algorithms are vulnerable to side channel analysis and several leakage models have been introduced to better understand these flaws. In 2003, Ishai, Sahai and Wagner introduced the d-probing security model, in which an attacker can observe at most d intermediate values during a processing. They also proposed an algorithm that securely performs the multiplication of 2 bits in this model, using only d(d + 1)/2 random bits to protect the computation. We study the randomness complexity of multiplication algorithms secure in the d-probing model. We propose several contributions: we provide new theoretical characterizations and constructions, new practical constructions and a new efficient algorithmic tool to analyze the security of such schemes. We start with a theoretical treatment of the subject: we propose an algebraic model for multiplication algorithms and exhibit an algebraic characterization of the security in the d-probing model. Using this characterization, we prove a linear (in d) lower bound and a quasi-linear (non-constructive) upper bound for this randomness cost. Then, we construct a new generic algorithm to perform secure multiplication in the d-probing model that only uses d + d^2 /4 random bits. From a practical point of view, we consider the important cases d &#8804; 4 that are actually used in current real-life implementations and we build algorithms with a randomness complexity matching our theoretical lower bound for these small-order cases. Finally, still using our algebraic characterization, we provide a new dedicated verification tool, based on information set decoding, which aims at finding attacks on algorithms for fixed order d at a very low computational cost.

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2016
Contact author(s)
sonia belaid @ ens fr
alain passelegue @ ens fr
emmanuel prouff @ ssi gouv fr
History
Short URL
https://ia.cr/2016/211

CC BY

BibTeX

@misc{cryptoeprint:2016/211,
author = {Sonia Belaïd and Fabrice Benhamouda and Alain Passelègue and Emmanuel Prouff and Adrian Thillard and Damien Vergnaud},
title = {Randomness Complexity of Private Circuits for Multiplication},
howpublished = {Cryptology ePrint Archive, Paper 2016/211},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/211}},
url = {https://eprint.iacr.org/2016/211}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.