User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

An Analysis of the Learning Parity with Noise Assumption Against Fault Attacks

Primary tabs

download
  • Open access
  • PDF
  • 529.73 K
Berti, Francesco [UCL] Standaert, François-Xavier [UCL]

We provide a rst security evaluation of LPN-based implementations against fault attacks. Our main result is to show that such implementations inherently have good features to resist these attacks. First, some prominent fault models (e.g. where an adversary flips bits in an implementation) are ineffective against LPN. Second, attacks taking advantage of more advanced fault models (e.g. where an adversary sets bits in an implementation) require significantly more samples than against standard symmetric cryptographic primitives such as block ciphers. Furthermore, the sampling complexity of these attacks strongly suers from inaccurate fault insertion. Combined with the previous observation that the inner products computed in LPN implementations have an interesting algebraic structure for side-channel resistance via masking, these results therefore suggest LPN-based primitives as interesting candidates for physically secure implementations.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès libre
Publication date 2016
Language Anglais
Conference "15th International Conference on Smart Card Research and Advanced Applications (CARDIS 2016)", Cannes (France) (du 07/11/2016 au 09/11/2016)
Peer reviewed yes
Host document Kerstin Lemke-Rust, Michael Tunstall ; "Proceedings of the 15th International Conference on Smart Card Research and Advanced Applications (CARDIS 2016)"- p. 245-264 (ISBN : 978-3-319-54668-1)
Collection Lecture Notes in Computer Science - 10146
Publisher Springer (Trier)
Publication status Publié
Affiliation UCL - SST/ICTM/ELEN - Pôle en ingénierie électrique
Keywords Fault attacks
Links
  1. Balasch Josep, Faust Sebastian, Gierlichs Benedikt, Inner Product Masking Revisited, Advances in Cryptology -- EUROCRYPT 2015 (2015) ISBN:9783662467992 p.486-510, 10.1007/978-3-662-46800-5_19
  2. Banerjee Abhishek, Peikert Chris, Rosen Alon, Pseudorandom Functions and Lattices, Advances in Cryptology – EUROCRYPT 2012 (2012) ISBN:9783642290107 p.719-737, 10.1007/978-3-642-29011-4_42
  3. Barenghi Alessandro, Breveglieri Luca, Koren Israel, Naccache David, Fault Injection Attacks on Cryptographic Devices: Theory, Practice, and Countermeasures, 10.1109/jproc.2012.2188769
  4. Biham Eli, Shamir Adi, Differential fault analysis of secret key cryptosystems, Advances in Cryptology — CRYPTO '97 (1997) ISBN:9783540633846 p.513-525, 10.1007/bfb0052259
  5. Blum Avrim, Furst Merrick, Kearns Michael, Lipton Richard J., Cryptographic Primitives Based on Hard Learning Problems, Advances in Cryptology — CRYPTO’ 93 ISBN:9783540577669 p.278-291, 10.1007/3-540-48329-2_24
  6. Blum Avrim, Kalai Adam, Wasserman Hal, Noise-tolerant learning, the parity problem, and the statistical query model, 10.1145/335305.335355
  7. Bogos, S., Tramèr, F., Vaudenay, S.: On solving lPN using BKW and variants. IACR Cryptology ePrint Archive 2015:49 (2015)
  8. Bringer, J., Chabanne, H., Dottax, E.: Hb $${}^{\text{++}}$$ : a lightweight authentication protocol secure against some attacks. In: Second International Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2006), 29 June 2006, Lyon, France, pp. 28–33 (2006)
  9. Chari Suresh, Rao Josyula R., Rohatgi Pankaj, Template Attacks, Cryptographic Hardware and Embedded Systems - CHES 2002 (2003) ISBN:9783540004097 p.13-28, 10.1007/3-540-36400-5_3
  10. Dodis Yevgeniy, Kiltz Eike, Pietrzak Krzysztof, Wichs Daniel, Message Authentication, Revisited, Advances in Cryptology – EUROCRYPT 2012 (2012) ISBN:9783642290107 p.355-374, 10.1007/978-3-642-29011-4_22
  11. Duc Alexandre, Vaudenay Serge, HELEN: A Public-Key Cryptosystem Based on the LPN and the Decisional Minimal Distance Problems, Progress in Cryptology – AFRICACRYPT 2013 (2013) ISBN:9783642385520 p.107-126, 10.1007/978-3-642-38553-7_6
  12. Dziembowski Stefan, Faust Sebastian, Leakage-Resilient Cryptography from the Inner-Product Extractor, Lecture Notes in Computer Science (2011) ISBN:9783642253843 p.702-721, 10.1007/978-3-642-25385-0_38
  13. Gaspar Lubos, Leurent Gaëtan, Standaert François-Xavier, Hardware Implementation and Side-Channel Analysis of Lapin, Topics in Cryptology – CT-RSA 2014 (2014) ISBN:9783319048512 p.206-226, 10.1007/978-3-319-04852-9_11
  14. Gilbert H., Robshaw M., Sibert H., Active attack against HB+: a provably secure lightweight authentication protocol, 10.1049/el:20052622
  15. Gilbert Henri, Robshaw Matthew J. B., Seurin Yannick, : Increasing the Security and Efficiency of, Advances in Cryptology – EUROCRYPT 2008 ISBN:9783540789666 p.361-378, 10.1007/978-3-540-78967-3_21
  16. Gilbert Henri, Robshaw Matthew J. B., Seurin Yannick, How to Encrypt with the LPN Problem, Automata, Languages and Programming ISBN:9783540705826 p.679-690, 10.1007/978-3-540-70583-3_55
  17. Giraud Christophe, Thiebeauld Hugues, A Survey on Fault Attacks, IFIP International Federation for Information Processing (2004) ISBN:9781402081460 p.159-176, 10.1007/1-4020-8147-2_11
  18. Grosso Vincent, Standaert François-Xavier, Faust Sebastian, Masking vs. multiparty computation: how large is the gap for AES?, 10.1007/s13389-014-0073-y
  19. Guo Qian, Johansson Thomas, Löndahl Carl, Solving LPN Using Covering Codes, Lecture Notes in Computer Science (2014) ISBN:9783662456101 p.1-20, 10.1007/978-3-662-45611-8_1
  20. Heyse Stefan, Kiltz Eike, Lyubashevsky Vadim, Paar Christof, Pietrzak Krzysztof, Lapin: An Efficient Authentication Protocol Based on Ring-LPN, Fast Software Encryption (2012) ISBN:9783642340468 p.346-365, 10.1007/978-3-642-34047-5_20
  21. Hopper Nicholas J., Blum Manuel, Secure Human Identification Protocols, Advances in Cryptology — ASIACRYPT 2001 (2001) ISBN:9783540429876 p.52-66, 10.1007/3-540-45682-1_4
  22. Joye, M., Tunstall, M. (eds.): Fault Analysis in Cryptography. Information Security and Cryptography. Springer, Heidelberg (2012)
  23. Juels Ari, Weis Stephen A., Authenticating Pervasive Devices with Human Protocols, Advances in Cryptology – CRYPTO 2005 (2005) ISBN:9783540281146 p.293-308, 10.1007/11535218_18
  24. Kiltz Eike, Pietrzak Krzysztof, Cash David, Jain Abhishek, Venturi Daniele, Efficient Authentication from Hard Learning Problems, Advances in Cryptology – EUROCRYPT 2011 (2011) ISBN:9783642204647 p.7-26, 10.1007/978-3-642-20465-4_3
  25. Levieil Éric, Fouque Pierre-Alain, An Improved LPN Algorithm, Lecture Notes in Computer Science (2006) ISBN:9783540380801 p.348-359, 10.1007/11832072_24
  26. Medwed Marcel, Standaert François-Xavier, Extractors against side-channel attacks: weak or strong?, 10.1007/s13389-011-0014-y
  27. Pietrzak Krzysztof, Cryptography from Learning Parity with Noise, SOFSEM 2012: Theory and Practice of Computer Science (2012) ISBN:9783642276590 p.99-114, 10.1007/978-3-642-27660-6_9
  28. Piret Gilles, Quisquater Jean-Jacques, A Differential Fault Attack Technique against SPN Structures, with Application to the AES and Khazad, Lecture Notes in Computer Science (2003) ISBN:9783540408338 p.77-88, 10.1007/978-3-540-45238-6_7
  29. Pointcheval, D., Johansson, T. (eds.): EUROCRYPT 2012. LNCS, vol. 7237. Springer, Heidelberg (2012)
  30. Regev Oded, On lattices, learning with errors, random linear codes, and cryptography, 10.1145/1060590.1060603
  31. Veyrat-Charvillon Nicolas, Gérard Benoît, Renauld Mathieu, Standaert François-Xavier, An Optimal Key Enumeration Algorithm and Its Application to Side-Channel Attacks, Selected Areas in Cryptography (2013) ISBN:9783642359989 p.390-406, 10.1007/978-3-642-35999-6_25
Bibliographic reference Berti, Francesco ; Standaert, François-Xavier. An Analysis of the Learning Parity with Noise Assumption Against Fault Attacks.15th International Conference on Smart Card Research and Advanced Applications (CARDIS 2016) (Cannes (France), du 07/11/2016 au 09/11/2016). In: Kerstin Lemke-Rust, Michael Tunstall, Proceedings of the 15th International Conference on Smart Card Research and Advanced Applications (CARDIS 2016), Springer : Trier2016, p. 245-264
Permanent URL http://hdl.handle.net/2078.1/187154