Paper 2022/250

Private Circuits with Quasilinear Randomness

Vipul Goyal, Yuval Ishai, and Yifan Song

Abstract

A $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 ts)$ random bits, where $s$ is the circuit size of $f$. We improve this to $O(t\cdot \log ts)$, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in Eurocrypt 2022
Keywords
Information-theoretic securityMasking schemesSide channel attacks
Contact author(s)
vipul @ cmu edu
yuvali @ cs technion ac il
yifans2 @ andrew cmu edu
History
2022-03-02: received
Short URL
https://ia.cr/2022/250
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/250,
      author = {Vipul Goyal and Yuval Ishai and Yifan Song},
      title = {Private Circuits with Quasilinear Randomness},
      howpublished = {Cryptology ePrint Archive, Paper 2022/250},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/250}},
      url = {https://eprint.iacr.org/2022/250}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.