International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Private Circuits with Quasilinear Randomness

Vipul Goyal , CMU and NTT Research
Yuval Ishai , Technion
Yifan Song , Carnegie Mellon University
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: A {\em $t$-private} circuit for a function $f$ is a randomized Boolean circuit $C$ that maps a randomized encoding of an input $x$ to an encoding of the output $f(x)$, such that probing $t$ wires anywhere in $C$ reveals nothing about $x$. Private circuits can be used to protect embedded devices against side-channel attacks. Motivated by the high cost of generating fresh randomness in such devices, several works have studied the question of minimizing the randomness complexity of private circuits. The best known upper bound, due to Coron et al. (Eurocrypt 2020), is $O(t^2\cdot\log s)$ random bits, where $s$ is the circuit size of $f$. We improve this to $O(t\cdot \log s)$, including the randomness used by the input encoder, and extend this bound to the stateful variant of private circuits. Our constructions are semi-explicit in the sense that there is an efficient randomized algorithm that generates the private circuit $C$ from a circuit for $f$ with negligible failure probability.
Video from EUROCRYPT 2022
  title={Private Circuits with Quasilinear Randomness},
  author={Vipul Goyal and Yuval Ishai and Yifan Song},