Randomness Complexity of Private Circuits for Multiplication

par Dr Damien Vergnaud (ENS)

mardi 26 janv. 2016, 14:00 → 15:00 Europe/Paris

XR203 (FST)

Many cryptographic algorithms appear to be vulnerable to side channel analysis and several leakage models have been introduced to better understand these analyses. 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.