Alain Passelègue (ENS/UCLA)
Monday, May 22, 2017, 2:00pm
Title: Private circuits for multiplication
Abstract:
We study the randomness and arithmetic complexities of private multiplication. The talk will be composed of 2 parts. First, we study the randomness complexity of private multiplication over GF(2). We introduce an algebraic characterization of privacy and use this characterization to prove a linear lower bound and a (non-constructive) quasilinear upper bound for the randomness complexity. We also propose a generic construction with better complexity than previous known constructions, specific constructions for practical cases that reach our lower bound, and a dedicated verification tool that aims at finding attacks against candidate schemes at a low computational cost.
The second part of the talk extends the study to finite fields. We extend our algebraic characterization to any finite field and also propose a characterization of non-interference. We then propose two generic constructions achieving non-interference: the first one has better arithmetic complexity (linear number of bilinear multiplications) while the second one only has linear randomness complexity. The latter construction is asymptotically optimal as we also prove a linear lower bound for randomness complexity of non-interfering multiplication over finite fields.
Joint works with Sonia Belaïd, Fabrice Benhamouda, Emmanuel Prouff, Adrian Thillard, and Damien Vergnaud.
Paper link