Correction to: Unconditionally Secure Computation Against Low-Complexity Leakage
Tóm tắt
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
$$\mathsf {AC}^0$$
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
$${\mathsf {AC}}^{0}$$
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
$$\mathsf {AC}^0$$
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).
Tài liệu tham khảo
A. Akavia, A. Bogdanov, S. Guo, A. Kamath, A. Rosen, Candidate weak pseudorandom functions in AC\(^0\)\(o\) MOD\(_2\), in Moni Naor, editor, ITCS 2014, ACM, (January 2014), pp. 251–260
P. Ananth, Y. Ishai, A. Sahai, Private circuits: A modular approach, in Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part III, pp. 427–455 (2018)
M. Ajtai, Secure computation with information leaking to an adversary, in Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6–8 June 2011, pp. 715–724 (2011)
S. Belaïd, F. Benhamouda, A. Passelègue, E. Prouff, A. Thillard, and D. Vergnaud. Randomness complexity of private circuits for multiplication, in Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, (Springer, Heidelberg, May 2016), pp. 616–648
N. Bitansky, R. Canetti, S. Halevi, Leakage-tolerant interactive protocols, in Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings, pp. 266–284 (2012)
A. Battistello, J.-S. Coron, E. Prouff, R. Zeitoun, Horizontal side-channel attacks and countermeasures on the ISW masking scheme, in Benedikt Gierlichs and Axel Y. Poschmann, editors, CHES 2016, volume 9813 of LNCS, (Springer, Heidelberg, August 2016), pp. 23–39
F. Benhamouda, A. Degwekar, Y. Ishai, T. Rabin, On the local leakage resilience of linear secret sharing schemes, in Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part I, pp. 531–561 (2018)
N. Bitansky, D. Dachman-Soled, H. Lin, Leakage-tolerant computation with input-independent preprocessing, in CRYPTO, pp. 146–163 (2014)
E. Boyle, S. Garg, A. Jain, Y.T. Kalai, A. Sahai, Secure computation against adaptive auxiliary information, in Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2013. Proceedings, Part I, pp. 316–334 (2013)
E. Boyle, S. Goldwasser, Abhishek Jain, Yael Tauman Kalai, Multiparty computation secure against continual memory leakage, in Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pp. 1235–1254 (2012)
M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in STOC, pp. 1–10 (1988)
A. Bogdanov, Y. Ishai, A. Srinivasan, Unconditionally secure computation against low-complexity leakage, in Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II, volume 11693 of Lecture Notes in Computer Science, (Springer, 2019), pp. 387–416
A. Bogdanov, Y. Ishai, E. Viola, C. Williamson, Bounded indistinguishability and the complexity of recovering secrets, in Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, (Springer, Heidelberg, August 2016), pp. 593–618
M. Bun, R. Kothari, J. Thaler, Quantum algorithms and approximating polynomials for composed functions with shared inputs, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019, pp. 662–678 (2019)
J. Van Bulck, M. Minkin, O. Weisse, D. Genkin, B. Kasikci, F. Piessens, M. Silberstein, T.F. Wenisch, Y. Yarom, R. Strackx, Foreshadow: Extracting the keys to the intel SGX kingdom with transient out-of-order execution, in 27th USENIX Security Symposium, USENIX Security 2018, Baltimore, MD, USA, August 15–17, 2018, pp. 991–1008, (2018)
D. Chaum, C. Crépeau, I. Damgård, Multiparty unconditionally secure protocols (extended abstract), in STOC, pp. 11–19 (1988)
J.-S. Coron, Higher order masking of look-up tables, in Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, (Springer, Heidelberg, May 2014), pp. 441–458
J.-S. Coron, E. Prouff, M. Rivain, T. Roche, Higher-order side channel security and mask refreshing, in Fast Software Encryption - 20th International Workshop, FSE 2013, Singapore, March 11–13, 2013. Revised Selected Papers, pp. 410–424 (2013)
A. Duc, S. Dziembowski, S. Faust, Unifying leakage models: From probing attacks to noisy leakage, in Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, (Springer, Heidelberg, May 2014), pp. 423–440
S. Dziembowski, S. Faust, Leakage-resilient circuits without computational assumptions, in TCC 2012, pp. 230–247 (2012)
S. Dziembowski, S. Faust, M. Skorski, Noisy leakage revisited, in Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, (Springer, Heidelberg, April 2015), pp. 159–188
I. Damgård, Y. Ishai, M. Krøigaard, Perfectly secure multiparty computation and the computational overhead of cryptography, in Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, (Springer, Heidelberg, May 2010), pp. 445–465
D. Dachman-Soled, F.-H. Liu, H.-S. Zhou, Leakage-resilient circuits revisited - optimal number of computing components without leak-free hardware, in EUROCRYPT 2015, pp. 131–158 (2015)
Y. Filmus, Y. Ishai, A. Kaplan, G. Kindler, Limits of preprocessing. in Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pp. 17:1–17:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
S. Faust, C. Paglialonga, T. Schneider, Amortizing randomness complexity in private circuits, in Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, (Springer, Heidelberg, December 2017), pp. 781–810
S. Faust, T. Rabin, L. Reyzin, E. Tromer, V. Vaikuntanathan, Protecting circuits from leakage: the computationally-bounded and noisy cases, in Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, (Springer, Heidelberg, May 2010), pp. 135–156
S. Faust, T. Rabin, L. Reyzin, E. Tromer, V. Vaikuntanathan, Protecting circuits from computationally bounded and noisy leakage. SIAM J. Comput., 43(5), 1564–1614, (2014) Extended abstract in Eurocrypt 2010
V. Goyal, Y. Ishai, H.K. Maji, A. Sahai, A.A. Sherstov, Bounded-communication leakage resilience via parity-resilient circuits, in FOCS 2016, pp. 1–10 (2016)
D. Genkin, Y. Ishai, M. Weiss, How to construct a leakage-resilient (stateless) trusted party, in Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12–15, 2017, Proceedings, Part II, pp. 209–244 (2017)
S. Garg, A. Jain, A. Sahai, Leakage-resilient zero knowledge. in Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, (Springer, Heidelberg, August 2011), pp. 297–315
O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or A completeness theorem for protocols with honest majority, in Alfred Aho, editor, 19th ACM STOC, (ACM Press, 1987), pp. 218–229
S. Goldwasser, G.N. Rothblum, Securing computation against continuous leakage. in CRYPTO 2010, pp. 59–79 (2010)
S. Goldwasser, G.N. Rothblum, How to compute in the presence of leakage, in 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20–23, 2012, pp. 31–40 (2012)
J. Håstad, On the correlation of parity and small-depth circuits. SIAM J. Comput., 43(5), 1699–1708 (2014)
Y. Ishai, A. Sahai, D. Wagner, Private circuits: Securing hardware against probing attacks, in Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, (Springer, Heidelberg, August 2003), pp. 463–481
Y. Ishai, M. Weiss, G. Yang, Making the best of a leaky situation: Zero-knowledge pcps from leakage-resilient circuits, in Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10–13, 2016, Proceedings, Part II, pp. 3–32 (2016)
A. Juma, Y. Vahlis, Protecting cryptographic keys against continual leakage, in CRYPTO 2010, pp. 41–58 (2010)
P. Kocher, D. Genkin, D. Gruss, W. Haas, M. Hamburg, M. Lipp, S. Mangard, T. Prescher, M. Schwarz, Y. Yarom, Spectre attacks: Exploiting speculative execution. CoRR, arXiv:1801.01203 (2018)
P.C. Kocher, J. Jaffe, B. Jun, Differential power analysis, in Michael J. Wiener, editor, CRYPTO’99, volume 1666 of LNCS, (Springer, Heidelberg, August 1999), pp. 388–397
P.C. Kocher, Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, in Neal Koblitz, editor, CRYPTO’96, volume 1109 of LNCS, (Springer, Heidelberg, August 1996), pp. 104–113
M. Lipp, M. Schwarz, D. Gruss, T. Prescher, W. Haas, A. Fogh, J. Horn, S. Mangard, P. Kocher, D. Genkin, Y. Yarom, M. Hamburg, Meltdown: Reading kernel memory from user space, in 27th USENIX Security Symposium, USENIX Security 2018, Baltimore, MD, USA, August 15–17, 2018, pp. 973–990 (2018)
E. Miles, Iterated group products and leakage resilience against NC1, in Moni Naor, editor, ITCS 2014, pp. 261–268. ACM (January 2014)
S. Micali, L. Reyzin, Physically observable cryptography (extended abstract), in Moni Naor, editor, TCC 2004, volume 2951 of LNCS, (Springer, Heidelberg, February 2004), pp. 278–296
E. Miles, E. Viola, Shielding circuits with groups, in Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, (ACM Press, 2013), pp. 251–260
G.N. Rothblum, How to compute under \({\cal{AC}}^{\sf 0}\) leakage without secure hardware, in Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, (Springer, Heidelberg, August 2012), pp. 552–569
M. Rivain, E. Prouff, Provably secure higher-order masking of AES, in Stefan Mangard and François-Xavier Standaert, editors, CHES 2010, volume 6225 of Lecture Notes in Computer Science, (Springer, 2010), pp. 413–427
M. Weiss, Zero-knowledge PCPs from leakage-resilient circuits, revisited, in CFAIL 2019 (2019). https://sites.google.com/site/morweissmor/.
A.C.-C. Yao, How to generate and exchange secrets (extended abstract), in 27th FOCS, (IEEE Computer Society Press, October 1986), pp. 162–167