Cryptology ePrint Archive: Report 2016/211

Randomness Complexity of Private Circuits for Multiplication

Sonia Belaïd and Fabrice Benhamouda and Alain Passelègue and Emmanuel Prouff and 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 ≤ 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.

Category / Keywords:

Original Publication (with minor differences): IACR-EUROCRYPT-2016

Date: received 26 Feb 2016, last revised 26 Feb 2016

Contact author: sonia belaid at ens fr fabrice benhamouda at ens fr alain passelegue at ens fr adrian thillard at ens fr damien vergnaud at ens fr emmanuel prouff at ssi gouv fr

Available format(s): PDF | BibTeX Citation

Version: 20160229:212833 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]