Unconditionally Secure Computation Against Low-Complexity Leakage

Andrej Bogdanov; Yuval Ishai; Akshayaram Srinivasan

Paper 2019/627

Unconditionally Secure Computation Against Low-Complexity Leakage

Andrej Bogdanov, Yuval Ishai, and Akshayaram Srinivasan

Abstract

We consider the problem of constructing leakage-resilient circuit compilers that are secure against global leakage functions with bounded output length. By global, we mean that the leakage can depend on all circuit wires and output a low-complexity function (represented as a multi-output Boolean circuit) applied on these wires. In this work, we design compilers both in the stateless (a.k.a. single-shot leakage) setting and the stateful (a.k.a. continuous leakage) setting that are unconditionally secure against AC0 leakage and similar low-complexity classes. In the stateless case, we show that the original private circuits construction of Ishai, Sahai, and Wagner (Crypto 2003) is actually secure against AC0 leakage. In the stateful case, we modify the construction of Rothblum (Crypto 2012), obtaining a simple construction with unconditional security. Prior works that designed leakage-resilient circuit compilers against AC0 leakage had to rely either on secure hardware components (Faust et al., Eurocrypt 2010, Miles-Viola, STOC 2013) or on (unproven) complexity-theoretic assumptions (Rothblum, Crypto 2012).

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in CRYPTO 2019
Contact author(s): andrejb @ gmail com
yuval ishai @ gmail com
akshayaram @ berkeley edu
History: 2021-08-27: revised; 2019-06-03: received; See all versions
Short URL: https://ia.cr/2019/627
License: CC BY

BibTeX

@misc{cryptoeprint:2019/627,
      author = {Andrej Bogdanov and Yuval Ishai and Akshayaram Srinivasan},
      title = {Unconditionally Secure Computation Against Low-Complexity Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2019/627},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/627}},
      url = {https://eprint.iacr.org/2019/627}
}