Problem and Proposed Solution

The Problem

Establishing a shared secret key among a group of participants over an insecure network is one of the most fundamental cryptographic tasks. Once such a (high entropy) secret has been established, well-understood symmetric cryptographic solutions for authentication, integrity, and confidentiality can be deployed, and establishing secure communication channels among the parties becomes fairly routine. Impressive experimental progress in the experimental realization of quantum computers (Lee 2017)  raises the question for quantum safe key establishment solutions. The efficient solutions available today -- even when restricting to only two parties -- become insecure, once scalable quantum computers are available. When looking at groups of n ≥ 2 participants, the problem affects pretty much all layers of the cryptographic design process:

  1. The main building blocks (including in particular the ubiquitous 2-party Diffie-Hellman protocol (Diffie and Hellman 1976)) require a discrete logarithm assumption, which is not quantum-safe.
  2. Established security models for group key establishment ((Bellare, Pointcheval, and Rogaway 2000) ) and established protocol compilers (such as (Katz and Yung, n.d.)) have not been designed with quantum attacks in mind.
  3. Fixing secure parameters for quantum-safe hardness assumptions is challenging, as the security margins are less understood. Thus communication and computation complexity tend to be high.
  4. There is a lack of tools to protect implementations -- modifications of code at runtime is an attack vector outside the common cryptographic security models. Regrettably, Rowhammer attacks (Kim et al. 2014) are one example showing that we cannot ignore fault induction, even in software implementations.

 

Proposed Solution

To address this problem, contributions at at various levels are needed.

  • For the basic building blocks we will start out with lattice-based constructions (the New Hope 2-party protocol (“Post-Quantum Key Exchange—A New Hope | USENIX” 2017) is a natural starting point) and with constructions using coding theory. Due to their 2-round structure, neither of these approaches is suitable for a simple drop-in for Diffie-Hellman, but these are currently nonetheless the most promising available starting points. Due to their experimental nature, we plan to use these building blocks initially in a hybrid form, i.e., we will make sure that our protocols still have a “pre-quantum” fallback. To increase confidence in specific parameter sets, we plan on experiments with state-of-the-art lattice reduction and information set-decoding against the underlying hardness assumptions. For signatures, which (apart from password-based settings) are the standard tool for authentication, the exact choice of scheme will require some exploration -- hash-based constructions (“Literature” 2014) tend to suffer from a large signature size, which can be more burdensome than a slower alternative with larger key. The team in the US offers the necessary expertise on lattice reduction and code-based cryptography as well as quantum cryptanalysis
  • On the protocol level, an adequate security model to capture quantum attacks needs to be chosen. In particular, we intend to look into the quantum random oracle model and into the feasibility of working models where the adversary is allowed to make use of superpositions of protocol executions. However, when exploring the latter type of attacks, we intend to focus on scenarios where we still have practical AGKE solutions available: As mounting superposition attacks requires strong assumptions on the implementation and is not feasible on fully classical implementations, it is for most use cases not worthwhile to impose a high performance punishment to achieve extreme security guarantees.
    For the protocol design, we intend to pursue two lines, as ensuring authentication with signatures is expected to be a critical parameter for the communication complexity:
    • Explore adjustments of generic protocol compilers for adding authentication (such as (Tang and Mitchell 2005)), so that they can be used efficiently in a post-quantum scenario.
    • Design optimized scalable AGKE protocols that maximize the protocol benefits and minimize resources needed to recover from failure -- making partitioned AGKE constructions (such as (“Cryptology ePrint Archive: Report 2017/141” 2017a)) quantum-safe is a natural starting point.
  • To protect actual protocol implementations against a wide class of attacks, through the partner in Malta we will integrate state-of-the-art runtime verification into the cryptographic protocol implementation. Deploying software monitors with the AGKE solution using a minimally intrusive approach should keep overheads low and offer a robust mitigation layer against, e.g., Rowhammer attacks. Traditional side-channel protection will nonetheless be needed as well, and the team in Slovakia will help to ensure that the new primitives that we implement will be protected adequately. Combining all of the above, we anticipate to obtain a full quantum-safe solution for authenticated group key establishment.