Quantum-Safe Group Key Establishment Protocol from Lattice Trapdoors

Teklay Gebremichael, Mikael Gidlund, Gerhard P. Hancke, Ulf Jennehag

TL;DR

This paper introduces a novel quantum-safe group key establishment protocol for IoT devices, leveraging lattice-based cryptography. It addresses the critical need for secure communication in resource-constrained environments, offering a method to establish shared secret keys resistant to future quantum computer attacks.

What Problem Does This Paper Address?

The Internet of Things (IoT) is rapidly expanding, necessitating secure communication channels, especially for group communication where multiple devices need to share a secret key to encrypt/decrypt messages. Traditional cryptographic methods are vulnerable to quantum computers, posing a significant future threat. Existing quantum-resistant solutions are often too computationally intensive or resource-demanding for typical IoT devices. This paper tackles the challenge of creating a group key establishment protocol that is both quantum-safe and lightweight enough for resource-constrained IoT environments, while also supporting dynamic group membership with forward and backward secrecy.

Methods

The core of the proposed protocol relies on lattice trapdoors. A lattice trapdoor is a piece of information that allows for the efficient inversion of a one-way function defined on a lattice, a task that is otherwise computationally hard. The authors utilize the Learning With Errors (LWE) problem, a well-studied hard lattice problem, as the basis for their one-way function.

Here's a breakdown of the key methodological aspects:

  • Lattice Trapdoor Setup: Each user in the group is provisioned with a unique "short basis" for a specific lattice. This basis acts as their trapdoor. The process involves generating a series of related lattices, where each user's lattice is intersected with the previous one, ensuring a chain of related trapdoors. The final public parameter is a "bad basis" lattice that is hard to work with directly.
  • Group Key Generation: The group key is derived from the secret component 's' of the LWE problem. This 's' is generated randomly for each session and is used as a seed for a pseudo-random function to derive the actual session key.
  • One-Way Function: The protocol uses a lattice-based one-way function $g_A(s, e) = s^T A + e \pmod{q}$, where 's' is the secret, 'e' is an error term, and 'A' is a public matrix. Inverting this function (recovering 's') is equivalent to solving the Search-LWE problem, which is hard without the trapdoor.
  • Encryption/Decryption: Encryption involves using the derived session key to encrypt the message and then appending the output of the one-way function. Decryption requires a user to use their trapdoor (short basis) to invert the one-way function, recover 's', and then derive the session key to decrypt the message.
  • Dynamic Group Management: The protocol supports adding new nodes to the group while maintaining forward and backward secrecy. This is achieved by updating the public lattice parameter, forcing all members to re-establish their trapdoors with respect to the new parameter.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Lattice Trapdoors as a Versatile Primitive: The paper demonstrates the power of lattice trapdoors beyond their typical applications, showing their suitability for constructing complex cryptographic protocols like group key establishment.
  • Quantum-Safe IoT Security: By grounding the protocol in lattice-based cryptography, the authors provide a pathway to secure IoT communications against future quantum computing threats, a critical concern for long-term security.
  • Lightweight and Efficient Operations: The use of simple linear-algebra operations for key establishment, encryption, and decryption makes the protocol suitable for resource-constrained IoT devices, where computational power and memory are limited.
  • Decentralized Key Management: The protocol avoids a central authority for key management, distributing the responsibility and enhancing resilience.
  • Session Key Independence: Deriving session keys from randomly generated secrets for each round ensures forward and backward secrecy, meaning compromise of one session key does not affect others.

Key Results

  • Constant Time Operations: After the initial trapdoor setup (which takes O(n) time, where n is the number of users), encryption, decryption, session key generation, and node addition are all performed in constant time (O(1)). This is a significant advantage for large-scale IoT deployments.
  • Performance: In a simulated IoT network with 10 nodes and a 300x300 lattice, trapdoor setup took approximately 4.94 seconds. Encryption averaged 0.023 seconds, and decryption averaged 3.04 seconds.
  • Error Rate: The protocol exhibits an average recovery rate of 92% for the secret 's', with a 8% error rate. The authors suggest using reconciliation techniques to handle these discrepancies.
  • Quantum Resistance: The security is based on the conjectured hardness of lattice problems (like LWE and SVP), which are believed to be resistant to quantum attacks.

Limitations and Future Work

  • Active Adversary: The security analysis primarily considers passive adversaries. The paper acknowledges that extending the security model to include active adversaries is a direction for future work.
  • Node Removal: The current method for removing a node is inefficient, requiring a re-run of the entire protocol. An improved solution is left for future research.
  • Parameter Size: For a robust security level (e.g., 128-bit), the dimension of the lattice can be large (over 500), leading to significant storage requirements for matrices. The authors suggest optimizations like using the Hermite normal form (HNF) or ring-LWE to mitigate this.
  • Implementation Optimization: While a proof-of-concept was implemented, further optimization is needed to improve performance.
  • Parallelization: The trapdoor setup is currently sequential but could be parallelized for further speedup.

Summary updated

Abstract

Group communication enables Internet of Things (IoT) devices to communicate in an efficient and fast manner. In most instances, a group message needs to be encrypted using a cryptographic key that only devices in the group know. In this paper, we address the problem of establishing such a key using a lattice-based one-way function, which can easily be inverted using a suitably designed lattice trapdoor. Using the notion of a bad/good basis, we present a new method of coupling multiple private keys into a single public key, which is then used for encrypting a group message. The protocol has the apparent advantage of having a conjectured resistance against potential quantum-computer-based attacks. All functions—key establishment, session key update, node addition, encryption, and decryption—are effected in constant time, using simple linear-algebra operations, making the protocol suitable for resource-constrained IoT networks. We show how a cryptographic session group key can be constructed on the fly by a user with legitimate credentials, making node-capture-type attacks impractical. The protocol also incorporates a mechanism for node addition and session-key generation in a forward- and backward-secrecy-preserving manner.
BibTeX
@inproceedings{gebremichael2022quantum,
  author = {Teklay Gebremichael and Mikael Gidlund and Gerhard P. Hancke and Ulf Jennehag},
  title = {{Quantum-Safe Group Key Establishment Protocol from Lattice Trapdoors}},
  booktitle = {Sensors},
  year = {2022},
  url = {https://openreview.net/forum?id=4_Z_Efa-vVg},
}

Loading related content...

Figure