Current status

For the 2-party case, the search for a possible quantum-safe standard receives much public attention (“ - Computer Security Division - Computer Security Resource Center” 2017) for an unauthenticated solution is the New Hope algorithm, and an authenticated 2-party solution has been proposed in 2016 (“Cryptology ePrint Archive: Report 2016/435” 2017). A main challenge is the efficient authentication, as popular quantum-safe large signature suffer from large signature sizes. In theory, one can try to bootstrap an authenticated 2-party solution from an unauthenticated one (Neupane 2012) without introducing additional assumptions, but this is mainly a theoretical result -- the resulting protocol complexity is prohibitive for most applications.

For group communication scenarios, i.e., user groups with n ≥ 2 users, systematic constructions for quantum-safe AGKE are lacking. Even ignoring the question of how the security model should best be adjusted, a performance problem with existing protocol compilers becomes immediately clear -- a standard design technique is to start with an unauthenticated protocol and then add some overhead, including signatures on (almost) all messages (Bresson, Manulis, and Schwenk, n.d.) -- in view of post-quantum signatures which are slow or have large signature sizes, this design approach creates a non-trivial performance challenge. We expect that with the current state of quantum-safe signatures it is worthwhile to look into alternative compiler designs, where the signing of messages is centralized to a few (late) messages in the protocol. At a more fundamental level, the use of random oracles -- which is fairly standard in AGKE when emphasizing efficiency over conceptual purity -- is known to be problematic in a quantum setting. Even for basic padding schemes, subtle adjustments can be needed to ensure provable guarantees (Targhi and Unruh 2016).

The proposing team has substantial experience with constructing AGKE solutions -- including the design of efficient, scalable solutions ((Bohli, Vasco, and Steinwandt 2007),   (Gao, Neupane, and Steinwandt 2014)) and protocol compilers ((Abdalla et al., n.d.), (Neupane, Steinwandt, and Corona 2012)). Moreover, the Spanish team has recently shown, in a collaboration with one of our experts, how to efficiently recover from a situation where authentication is not successful for all participants in an AGKE (“Cryptology ePrint Archive: Report 2017/141” 2017b). While not being quantum-safe, the design principle of this protocol is of interest for the project scope, as in the quantum-safe setting we likely face situations where restarting a protocol execution from scratch imposes a high communication cost. The Spanish team has also experience in modeling advanced security guarantees in group key establishment (“Cryptology ePrint Archive: Report 2016/1166” 2017). The US team complements the necessary expertise for modeling quantum cryptanalytic attacks. In addition to direct scientific contributions ((Roetteler and Steinwandt 2015), (Grassl et al. 2016)), the US partner regularly organizes pertinent workshops   (Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH 2017)the US co-director will be program co-chair and general chair for PQCrypto 2018, the leading publication venue for post-quantum cryptography. Dedicated experts in the project team for both relevant mathematical platforms -- code-based ((Cayrel et al. 2017), (Buchmann et al. 2017)) and lattice-based ((Bai, Laarhoven, and Stehlé 2016), (Albrecht, Bai, and Ducas 2016)) -- ensure that our solutions will work with state-of-the-art parameter choices.

Passing from the theoretical protocol description of an AGKE to a secure implementation is still an area relying mostly on good engineering practices rather than proofs. So-called leakage-resilient cryptography (see, e.g., (Andrychowicz, Masny, and Persichetti 2015)) tries to tackle side-channel attacks from a conceptual level, but the existing theory is not advanced enough to provide sufficient guidance for efficient implementations. For the major post-quantum platforms, the development of side-channel countermeasures is still at an early stage, but one can expect activity in this field to pick up quickly. With Infineon, now a major industry player with expertise in side-channels has presented a lattice-based 2-party key establishment solution (Ag 2017), which should stimulate research on side-channel attacks in the community. Pertinent techniques for countermeasures  that will will appear in the literature in the upcoming months will of course be taken into account for the implementation work in the project. The project partner in Slovakia has many years of experience with securing cryptographic hardware implementations against side-channels. In fact, the NPD of this proposal just completed successfully a NATO SPS funded project dealing with side-channels in a code-based encryption scheme (“Workshop on Secure Implementation of Post-Quantum Cryptography | Secure Implementation of Post-Quantum Cryptography” 2017, “Introduction | Secure Implementation of Post-Quantum Cryptography” 2017), and the expertise built up therein will be of great help when using code-based primitives in our AGKE designs.

Interestingly, there appears to be no systematic consideration in the literature on protecting AGKE implementations in a traditional software implementation against manipulation at runtime. For instance, if an adversary manages to manipulate the code in such a way that signature verifications are not properly executed, this would be devastating from a security perspective. And with Rowhammer attacks having been demonstrated, such code manipulation is regrettably no longer utopian. Work by Bauer and Juerjens shows that techniques from runtime verification can be used to strengthen the security of cryptographic implementations (Bauer and Juerjens 2010), but there appears to be no documented experience with securing AGKEs, which is fundamental for secure group communication. The project partner in Malta has an established track record in all pertinent areas of runtime verification ((Azzopardi, Colombo, and Pace 2016), (Colombo and Falcone 2016)), in particular the team in Malta is experienced with the deployment (Colombo and Pace 2013) and rigorous testing of monitoring techniques (Colombo, Mizzi, and Pace 2013) at runtime that are minimally intrusive. The latter is crucial for our purposes, as large overhead could imply serious performance drawbacks, thereby making an AGKE solution unusable. The experience accumulated from years of work with partners from the financial transaction industry (Colombo, Pace, and Abela 2012) is key. Similar to the monitoring of cryptographic implementations, financial transaction systems are also sensitive to overheads introduced.