Efficient Leakage Resilient Circuit Compilers

详细信息    查看全文

• 作者：Marcin Andrychowicz (16)
  Ivan Damg氓rd (14)
  Stefan Dziembowski (16)
  Sebastian Faust (15)
  Antigoni Polychroniadou (14)
  
  16. Warsaw University ; Warsaw ; Poland
  14. Aarhus University ; Aarhus ; Denmark
  15. EPFL ; Lausanne ; Switzerland
  
• 关键词：Leakage resilience ; Multi ; party computation ; Split ; state model ; $$\mathsf {AC}^{0}$$ ; Side channel attacks
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9048
• 期：1
• 页码：311-329
• 全文大小：453 KB
• 参考文献：1. Bitansky, N, Dachman-Soled, D, Lin, H Leakage-tolerant computation with input-independent preprocessing. In: Garay, JA, Gennaro, R eds. (2014) Advances in Cryptology 鈥?CRYPTO 2014. Springer, Heidelberg, pp. 146-163 CrossRef
  2. Castagnos, G, Renner, S, Z茅mor, G High-order masking by using coding聽theory and its application to AES. In: Stam, M eds. (2013) Cryptography and Coding. Springer, Heidelberg, pp. 193-212 CrossRef
  3. Chari, S, Jutla, CS, Rao, JR, Rohatgi, P Towards sound approaches to counteract power-analysis attacks. In: Wiener, M eds. (1999) Advances in Cryptology - CRYPTO 鈥?9. Springer, Heidelberg, pp. 398-412 CrossRef
  4. Cramer, R, Damg氓rd, I, Pastro, V On the amortized complexity of zero knowledge protocols for multiplicative relations. In: Smith, A eds. (2012) Information Theoretic Security. Springer, Heidelberg, pp. 62-79 CrossRef
  5. Damg氓rd, I, Ishai, Y, Kr酶igaard, M Perfectly secure multiparty computation and the computational overhead of cryptography. In: Gilbert, H eds. (2010) Advances in Cryptology 鈥?EUROCRYPT 2010. Springer, Heidelberg, pp. 445-465 CrossRef
  6. Davi, F., Dziembowski, S., Venturi, D.: Leakage-resilient storage. Cryptology ePrint Archive, Report 2009/399 (2009)
  7. Dav矛, F, Dziembowski, S, Venturi, D Leakage-resilient storage. In: Garay, JA, Prisco, R eds. (2010) Security and Cryptography for Networks. Springer, Heidelberg, pp. 121-137 CrossRef
  8. Duc, A, Dziembowski, S, Faust, S Unifying leakage models: from probing attacks to noisy leakage. In: Nguyen, PQ, Oswald, E eds. (2014) Advances in Cryptology 鈥?EUROCRYPT 2014. Springer, Heidelberg, pp. 423-440 CrossRef
  9. Dziembowski, S, Faust, S Leakage-resilient cryptography from the inner-product extractor. In: Lee, DH, Wang, X eds. (2011) Advances in Cryptology 鈥?ASIACRYPT 2011. Springer, Heidelberg, pp. 702-721 CrossRef
  10. Dziembowski, S, Faust, S Leakage-resilient circuits without computational assumptions. In: Cramer, R eds. (2012) Theory of Cryptography. Springer, Heidelberg, pp. 230-247 CrossRef
  11. Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 293鈥?02 (2008)
  12. Faust, S, Rabin, T, Reyzin, L, Tromer, E, Vaikuntanathan, V Protecting circuits from leakage: The computationally-bounded and noisy cases. In: Gilbert, H eds. (2010) Advances in Cryptology 鈥?EUROCRYPT 2010. Springer, Heidelberg, pp. 135-156 CrossRef
  13. Franklin, M., Yung, M.: Communication complexity of secure computation (extended abstract). In: STOC, pp. 699鈥?10. ACM, New York (1992)
  14. Genkin, D, Pipman, I, Tromer, E Get your hands off my laptop: Physical side-channel key-extraction attacks on PCs. In: Batina, L, Robshaw, M eds. (2014) Cryptographic Hardware and Embedded Systems 鈥?CHES 2014. Springer, Heidelberg, pp. 242-260 CrossRef
  15. Genkin, D, Shamir, A, Tromer, E RSA key extraction via low-bandwidth acoustic cryptanalysis. In: Garay, JA, Gennaro, R eds. (2014) Advances in Cryptology 鈥?CRYPTO 2014. Springer, Heidelberg, pp. 444-461 CrossRef
  16. Goldwasser, S, Rothblum, GN Securing computation against continuous leakage. In: Rabin, T eds. (2010) Advances in Cryptology 鈥?CRYPTO 2010. Springer, Heidelberg, pp. 59-79 CrossRef
  17. Goldwasser, S., Rothblum, G.N.: How to compute in the presence of leakage. Tech. Rep. TR12-010, Electronic Colloquium on Computational Complexity (2012)
  18. Grosso, V, Standaert, F-X, Faust, S Masking vs. multiparty computation: How large is the gap for AES?. In: Bertoni, G, Coron, J-S eds. (2013) Cryptographic Hardware and Embedded Systems - CHES 2013. Springer, Heidelberg, pp. 400-416 CrossRef
  19. Ishai, Y, Sahai, A, Wagner, D Private circuits: Securing hardware against probing attacks. In: Boneh, D eds. (2003) Advances in Cryptology - CRYPTO 2003. Springer, Heidelberg, pp. 463-481 CrossRef
  20. Ishai, Y., Sahai, A., Wagner, D.: Private circuits: Securing hardware against probing attacks (2003). Unpublished manuscript ([19] is a revised and abbreviated version)
  21. Juma, A, Vahlis, Y Protecting cryptographic keys against continual leakage. In: Rabin, T eds. (2010) Advances in Cryptology 鈥?CRYPTO 2010. Springer, Heidelberg, pp. 41-58 CrossRef
  22. Kocher, PC Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N eds. (1996) Advances in Cryptology - CRYPTO 鈥?6. Springer, Heidelberg, pp. 104-113
  23. Kocher, PC, Jaffe, J, Jun, B Differential power analysis. In: Wiener, M eds. (1999) Advances in Cryptology - CRYPTO 鈥?9. Springer, Heidelberg, pp. 388-397 CrossRef
  24. Micali, S, Reyzin, L Physically observable cryptography. In: Naor, M eds. (2004) Theory of Cryptography. Springer, Heidelberg, pp. 278-296 CrossRef
  25. Miles, E., Viola, E.: Shielding circuits with groups. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC 2013, pp. 251鈥?60. ACM, New York (2013)
  26. Prouff, E, Rivain, M Masking against side-channel attacks: A formal security proof. In: Johansson, T, Nguyen, PQ eds. (2013) Advances in Cryptology 鈥?EUROCRYPT 2013. Springer, Heidelberg, pp. 142-159 CrossRef
  27. Prouff, E, Roche, T Higher-order glitches free implementation of the AES using secure multi-party computation protocols. In: Preneel, B, Takagi, T eds. (2011) Cryptographic Hardware and Embedded Systems 鈥?CHES 2011. Springer, Heidelberg, pp. 63-78 CrossRef
  28. Quisquater, J-J, Samyde, D ElectroMagnetic analysis (EMA): Measures and counter-measures for smart cards. In: Attali, S, Jensen, T eds. (2001) Smart Card Programming and Security. Springer, Heidelberg, pp. 200-210 CrossRef
  29. Rivain, M, Prouff, E Provably secure higher-order masking of AES. In: Mangard, S, Standaert, F-X eds. (2010) Cryptographic Hardware and Embedded Systems, CHES 2010. Springer, Heidelberg, pp. 413-427 CrossRef
  30. Rothblum, GN How to compute under $${\cal {AC}}^{\sf 0}$$ leakage without secure hardware. In: Safavi-Naini, R, Canetti, R eds. (2012) Advances in Cryptology 鈥?CRYPTO 2012. Springer, Heidelberg, pp. 552-569 CrossRef
  31. Sch枚nhage, A (1977) Schnelle multiplikation von polynomen 眉ber k枚rpern der charakteristik 2. Acta Informatica 7: pp. 395-398 CrossRef
  32. Shamir, A (1979) How to share a secret. Commun. ACM 22: pp. 612-613 CrossRef
  
• 作者单位：Topics in Cryptology 篓C- CT-RSA 2015
• 丛书名：978-3-319-16714-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In this paper, we revisit the problem of constructing general leakage resilient compilers that can transform any (Boolean) circuit \(C\) into a protected circuit \(C'\) computing the same functionality as \(C\) , which additionally is resilient to certain classes of leakage functions. An important problem that has been neglected in most works on leakage resilient circuits is to minimize the overhead induced by the compiler. In particular, in earlier works for a circuit \(C\) of size \(s\) , the transformed circuit \(C'\) has size at least \(\mathcal {O}(sk^2)\) , where \(k\) is the security parameter. In this work, using techniques from secure Multi-Party Computation, we show that in important leakage models such as bounded independent leakage and leakage from weak complexity classes the size of the transformed circuit can be reduced to \(\mathcal {O}(sk)\) .