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: ia.cr/2016/211
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]