Current status

With post-quantum cryptography not having made the transition into a broader market of applications yet, it seems fair to say that the proposed parameter choices deserve to be interpreted with some caution. Dedicated hardware devices can speed up cryptanalytic attacks drastically—not only against symmetric schemes [COPA]: for RSA, one of the most common cryptographic primitives, it turned out that a highly optimized hardware engine, has the potential to jeopardize keys that have been generated with a popular parameter choice (cf. [ShTr03, GeSt07]). Successful distinguishing attacks as in [FGOP+10] also evidence the necessity to carefully evaluate parameter choices for code-based cryptography, when provable security guarantees are required. Discussions in a very recent workshop indicate that quantum algorithms could indeed enable improvements over classical techniques for attacking code-based cryptographic schemes [PQC12]. Consequently, before considering the deployment of post-quantum schemes for mission-critical operations, where the enemy must be assumed to be well-funded, a thorough review of recommended parameter choices is needed. It is interesting to note that for attacks based a quantum computer, even fundamental questions like implementing efficient finite field arithmetic are still at the beginning of their exploration [ARS13], and we hope that his project enables more robust estimates of the cost and the potential of “quantum attacks”—paving the road for a reliable choice of implementation parameters.

A substantial body of work on side-channel attacks against implementations of classical cryptographic schemes is available, and theoretical models to deal with information leakage through side-channels have started to appear in the literature. However, even in this classical setting the theory is not mature enough yet to derive efficient implementations that can be deployed without experimentally verifying the implementation-level security. For post-quantum proposals, the situation is even more unsatisfying. As the algebraic structures used here are different, it is neither from an algorithmic nor from an implementation point of view clear, how resistance against pertinent side-channel attacks should be implemented. The existing literature evidences that side-channel attacks are a relevant concern for post-quantum schemes ([CGP08,CaDu10]), and now systematic experimental work (like [CHP12]) with actual measurements for different implementation platforms and a closer theoretical analysis of the involved computations are urgently needed here. This might in particular offer insight into plausible hardware modifications to protect sensitive (key) material adequately (cf. [BGGF+]).

Each of the involved groups has an established track record in cryptographic research, and the specific types of expertise complement each other, so that all levels of cryptographic system design can be covered:

• The group in France, led by Viktor Fischer, has substantial experience with FPGA implementations, experiments with side-channel attacks and low-level protection of sensitive (key) data. To defend against implementation-level attacks, algorithmic countermeasures alone do not necessarily provide adequate protection, and suitable modifications or extensions of the hardware platform used can be invoked to counter adversarial strategies which aim directly at implementations. This group also has a strong expertise in post-quantum cryptography [CGP08,CaDu10,MCGL11]: as reflected in a literature database maintained by a member of the group [Cay12], this project partner developed various schemes and studied their robustness against side-channel analyses.
• The group in Israel has extensive experience in carrying out architectural attacks on software implementations (exploiting CPU architectural details such as cache attacks), and acoustic attacks exploiting sound emanations from computer power supplies. It also has experience with RF and power emanation analysis, and is working on mathematical modeling of side channels. Moreover, it has worked extensively on the design of special-purpose cryptanalytic hardware. Consequently this group, led by Eran Tromer, plays a key role in the side-channel and hardware-attack analysis of the implementations. Input of this group will be essential when choosing the exact implementation parameters of a scheme which has strong provable guarantees in a theoretical model.
• The group in Slovakia, led by Otokar Grošek is experienced with the theoretical analysis and the design of encryption schemes as well as the efficient software implementation of cryptanalytic attacks. The input of this group will be essential when considering customizations of algorithms, the choice of hardness assumptions in the presence of quantum algorithms, and when selecting concrete parameters of a scheme which has strong asymptotic guarantees in a theoretical model.
• The group in the U.S. is experienced with the cryptanalysis of asymmetric schemes, including proposals based on new hardness assumptions as needed for a post-quantum setting [Ste10, GIMS11, StSu11]. Moreover, this group is familiar with the design of quantum circuits for cryptanalysis [ARS12, ARS13], the use of dedicated cryptanalytic hardware designs [GeSt07, GMS10], and cryptographic security models—including advanced security requirements for signature schemes [BRS06]. The U.S. partner also has experience in the design of cryptographic primitives for a post-quantum setting [StVi08], and in 2011 the co-director of this partner co-organized a Dagstuhl Seminar on the use of quantum computers in cryptanalysis [FMRS11]. He co-organizes a follow-up Dagstuhl seminar on this topic in 2013 [FMRS13], and we expect the proposed project to benefit from discussions with researchers in quantum computing, that are an integral part of this seminar. The U.S. partner is anticipated to carry the main load on the side of the theoretical analysis of the implemented schemes, including aspects specific to quantum computing.

To reach the project goals, a wide spectrum of cryptographic expertise, including techniques from computer science, engineering, mathematics, and quantum computing is necessary. We believe that this particular project team is in an excellent position to live up to this challenge. With the presence of multidisciplinary experts in the field with significant practical and theoretical knowledge for the scope of this project, innovative solutions can be expected which enhance NATO’s capabilities to secure its communication and defend against terrorist threats.

Literature

[ACDG03] M-L. Akkat, N. T. Courtois, R. Duteuil, L. Goubin: A Fast and Secure Implementation of SFLASH, Public Key Cryptography – PKC 2003, vol. 2567 of Lecture Notes in Computer Science, pp. 267-278, Springer, 2002.

[ARS12] B. Amento, M. Rötteler and R. Steinwandt: Efficient quantum circuits for binary elliptic curve arithmetic: reducing T-gate complexity, Quantum Information & Computation (to appear), preprint available at quant-ph: http://arxiv.org/abs/1209.5491.

[ARS13] B. Amento, M. Rötteler and R. Steinwandt: Quantum Binary Field Inversion: Improved Circuit Depth via Choice of Basis Representation, Quantum Information & Computation 13, 2013 (to appear).

[BCM09] S.R. Blackburn, C. Cid and C. Mullan: Cryptanalysis of the MST3 public key cryptosystem, Journal of Mathematical Cryptology, vol. 3: 321-338, 2009.

[BRS06] J.-M. Bohli, S. Röhrich and R. Steinwandt: Key substitution attacks revisited: taking into account malicious signers, International Journal of Information Security vol. 5, pp. 30-36, 2006.

[BGGF+] L. Bossuet, M. Grand, L. Gaspar, V. Fischer and G. Gogniat, Architectures of Flexible Symmetric Key Crypto-engines – A Survey: from Hardware Coprocessor to Multi-crypto-processor System on Chip. Accepted for publication in ACM Computing Surveys.

[Cay12] P.-L. Cayrel: Code-based cryptography: publications, http://www.cayrel.net/research/code-based-cryptography/article/code-based-cryptography, 2012

[CaDu10] P.-L. Cayrel end P. Dusart : McEliece/Niederreiter PKC : sensitivity to fault injection, Proceedings of FEAS 2010, IEEE, pages 1 - 6, 2010

[CGP08] P.-L. Cayrel, P. Gaborit and E. Prouff :Secure Implementation of the Stern Authentication and Signature Scheme for Low-Resource Devices, Eighth Smart Card Research and Advanced Application Conference CARDIS 2008 In G. Grimaud and F.-X. Standaert, editors, Lecture Notes in Computer Science, volume 5189, pp. 191-205, Springer, 2008.

[CPH12] P.-L. Cayrel, G. Hoffmann and E. Persichetti : Efficient implementation of a CCA2-secure variant of McEliece using generalized Srivastava codes, Proceedings of PKC 2012, Lecture Notes in Computer Science, volume, 7293, pp. 138-155, Springer, 2012.

[CaSt10] P.-L. Cayrel and F. Strenzke: Side channel attacks in code-based cryptography, COSADE 2010 - First International Workshop on Constructive Side-Channel Analysis and Secure Design, 2010.

[COPA] COPACOBANA. A Codebreaker for DES and other Ciphers, www.copacobana.org/ .

[DFSS07] V. Dubois, P-A. Fouque, A. Shamir and J. Stern: Practical Cryptanalysis of SFLASH, Advances in Cryptology – CRYPTO 2007, vol. 4622 of Lecture Notes in Computer Science, pp. 1-12, Springer, 2007.

[FGOP+10] J.-C. Faugère, V. Gauthier, A. Otmani, L. Perret and J.-P.Tillich,A Distinguisher for High Rate McEliece Cryptosystems, Cryptology ePrint Archive Report 2010/331, 2010. Available at http://eprint.iacr.org/2010/331.

[FPS12] S. Faust, K. Pietrzak and J. Schipper: Practical Leakage-Resilient Symmetric Cryptography, Cryptographuc Hardware and Embeddes Systems – CHES 2012, vol. 7428 of Lecture Notes in Computer science, pp. 213-232, Springer, 2012.

[FRR+10] S. Faust, T. Rabin, L. Reyzin, E. Tromer and V. Vaikuntanathan: Protecting Circuits from Leakage: the Computationally-Bounded and Noisy Cases, Advances in Cryptology – Eurocrypt 2010, vol. 6110 of Lecture Notes in Computer Science, pp. 135-136, Springer, 2010.

[FMRS11] S. Fehr, M. Mosca, M. Rötteler, R. Steinwandt (eds.): Quantum Cryptanalysis (Dagstuhl Seminar 11381), Dagstuhl Reports 1(9): 58-75, 2011.

[FMRS13] S. Fehr, M. Mosca, M. Rötteler, R. Steinwandt (organizers): Quantum Cryptanalysis (Dagstuhl Seminar 13371), Sep. 8-Sep.13, 2013, http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=13371.

[FiSe09] M.Finiasz and N.Sendrier: Security Bounds for the Design of Code-Based Cryptosystems, in Advances in Cryptology – ASIACRYPT 2009, vol. 5912 of Lecture Notes in Computer Science, pp. 88-105, Springer, 2009.

[GMS10] W. Geiselmann, K. Matheis and R. Steinwandt: PET SNAKE: A Special Purpose Architecture to Implement an Algebraic Attack in Hardware, Transactions on Computational Science 10: 298-328, 2010.

[GeSt07] W. Geiselmann and R. Steinwandt: Non-Wafer-Scale Sieving Hardware for the NFS: Another Attempt to Cope with 1024-bit, in Advances in Cryptology - EUROCRYPT 2007, vol. 4515 of Lecture Notes in Computer Science, pp. 466-481, Springer, 2007.

[GKST05] W. Geiselmann, H. Köpfer, R. Steinwandt, and E. Tromer: Improved Routing-Based Linear Algebra for the Number Field Sieve, in Proceedings of ITCC 2005 - Track on Embedded Cryptographic Systems, IEEE Computer Society, pp. 636-641, 2005.

[GSST05] W. Geiselmann, A. Shamir, R. Steinwandt, and E. Tromer: Scalable Hardware for Sparse Systems of Linear Equations, with Applications to Integer Factorization, in Workshop on Cryptographic Hardware and Embedded Systems 2005, CHES 2005 Proceedings, vol. 3659 of Lecture Notes in Computer Science, pp. 131-146, Springer, 2005.

[GIMS11] M. Grassl, I. Ilic, S.S. Magliveras and R. Steinwandt: Cryptanalysis of the Tillich-Zémor Hash Function, Journal of Cryptology 24(1): 148-156, 2011.

[Gro10] O. Grošek (coordinator): Cryptographic algorithms and primitives with increased resistance against side-channel attack, Development of France-Slovak cooperation in cryptology, http://147.175.106.2/kaivt/Projekty/Projekty/spolupracaFrancuzkoEn

[HoSt02] D. Hofheinz and R. Steinwandt: A Practical Attack on Some Braid Group Based Cryptographic Primitives, Public Key Cryptography – PKC 2003, vol. 2567 of Lecture Notes in Computer Science, pp. 187-198, Springer, 2002.

[MCGL11] C. Aguilar Melchor, P.-L. Cayrel, P. Gaborit and F. Laguillaumie: A New Efficient Threshold Ring Signature Scheme based on Coding Theory IEEE Trans. Inf. Theory, number 57(7), pages 4833-4842, 2011.

[PQC12] Post-Quantum Cryptography and Quantum Algorithms, Workshop at Lorentz Center, Leiden, Netherlands, Nov 5-Nov 9, 2012, https://wiki.pqcrypto.org/mediawiki/index.php/Working_group:_Quantum_attacks_on_code-based_cryptography

[QuKo02] J.-J. Quisquater, F. Koeune: State-of-the-art regarding side channel attacks, CRYPTREC Technical Rep., www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1047_Side_Channel_report.pdf , October 2002.

[ShTr04] A. Shamir and E. Tromer: Acoustic cryptanalysis. On noisy people and noisy machines, available electronically at tau.ac.il/~tromer/acoustic/ , presented at EURCORYPT 2004.

[ShTr03] A. Shamir and E. Tromer: Factoring Large Numbers with the TWIRL Device, in Advances in Cryptology – CRYPTO 2003, vol. 2729 of Lecture Notes in Computer Science, pp. 1-26, Springer, 2003.

[Ste10] R. Steinwandt: A ciphertext-only attack on Polly Two, Applicable Algebra in Engineering Communication and Computing 21(2): 89-92, 2010.

[StSu11] R. Steinwandt and A. Suárez Corona: Cryptanalysis of a 2-party key establishment based on a semigroup action problem, Advances in Mathematics of Communications 5(1): 87-92, 2011.

[StVi08] R. Steinwandt and V. I. Villányi: A one-time signature using run-length encoding, Information Processing Letters 108(4): 179-185, 2008.

[TOS10] E. Tromer, D. A. Osvik, A. Shamir: Efficient cache attacks on AES, and countermeasures, Journal of Cryptology, 23(1): 37-71, 2010.