Paper 2018/566
Private Circuits: A Modular Approach
Prabhanjan Ananth, Yuval Ishai, and Amit Sahai
Abstract
We consider the problem of protecting general computations against constantrate random leakage. That is, the computation is performed by a randomized boolean circuit that maps a randomly encoded input to a randomly encoded output, such that even if the value of every wire is independently leaked with some constant probability $p > 0$, the leakage reveals essentially nothing about the input. In this work we provide a conceptually simple, modular approach for solving the above problem, providing a simpler and selfcontained alternative to previous constructions of Ajtai (STOC 2011) and Andrychowicz et al.\ (Eurocrypt 2016). We also obtain several extensions and generalizations of this result. In particular, we show that for every leakage probability $p<1$, there is a finite basis $\mathbb{B}$ such that leakageresilient computation with leakage probability $p$ can be realized using circuits over the basis $\mathbb{B}$. We obtain similar positive results for the stronger notion of leakage tolerance, where the input is not encoded, but the leakage from the entire computation can be simulated given random $p'$leakage of input values alone, for any $p<p'<1$. Finally, we complement this by a negative result, showing that for every basis $\mathbb{B}$ there is some leakage probability $p<1$ such that for any $p'<1$, leakage tolerance as above cannot be achieved in general.
Metadata
 Available format(s)
 Publication info
 A minor revision of an IACR publication in CRYPTO 2018
 Contact author(s)

prabhanjan va @ gmail com
yuval ishai @ gmail com
amitsahai @ gmail com  History
 20190921: revised
 20180605: received
 See all versions
 Short URL
 https://ia.cr/2018/566
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/566, author = {Prabhanjan Ananth and Yuval Ishai and Amit Sahai}, title = {Private Circuits: A Modular Approach}, howpublished = {Cryptology ePrint Archive, Paper 2018/566}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/566}}, url = {https://eprint.iacr.org/2018/566} }