General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography

Zhengfeng Ji, Youming Qiao, Fang Song, Aaram Yun

Introduction

The impending arrival of the "quantum era" poses a fundamental threat to modern digital security. Current cryptographic standards, such as RSA and Elliptic Curve Cryptography (ECC), rely on the computational hardness of integer factorization and discrete logarithms. Shor’s algorithm demonstrates that a sufficiently powerful quantum computer could solve these problems in polynomial time, rendering existing public-key infrastructures obsolete.

In response, researchers are exploring mathematical structures that are resistant to both classical and quantum attacks. One promising avenue is group action-based cryptography. While early candidates like Graph Isomorphism (GI) were found to be vulnerable to specific quantum techniques, this paper proposes a more resilient alternative: the General Linear Group Action on Tensors (GLAT). By formalizing the Pseudorandom Group Action (PRA) assumption, the authors provide a robust framework for building quantum-safe cryptographic primitives.

The GLAT Framework

The core of the proposed system lies in the interaction between linear algebra and group theory. The authors focus on 3-tensors, which can be visualized as three-dimensional arrays of numbers over a finite field.

The Mathematical Object and Action

In this framework, the set $S$ consists of 3-tensors. The group $G$ is a product of general linear groups (e.g., $GL_n(\mathbb{F}) \times GL_n(\mathbb{F}) \times GL_n(\mathbb{F})$). The group action involves changing the basis along each of the three dimensions of the tensor.

The Hard Problem

The security of GLAT is rooted in the Tensor Isomorphism (TI) problem. Specifically, given two tensors, the challenge is to determine if one can be transformed into the other via the defined group action. This problem is widely considered a "bottleneck" in complexity theory; while many well-known isomorphism problems (like Graph Isomorphism or Linear Code Equivalence) can be reduced to 3-tensor isomorphism, the reverse is not true. This suggests that 3TI is a fundamentally harder problem.

Security Assumptions: OWA and PRA

To build practical cryptographic tools, the authors introduce two formal hardness assumptions:

  1. One-Way Group Action (OWA): Given a tensor $s$ and the result of a group action $g \cdot s$, it is computationally infeasible to find the group element $g$. This is the group-action equivalent of the One-Way Function (OWF) assumption.
  2. Pseudorandom Group Action (PRA): Given a pair of tensors $(s, t)$, it is hard to distinguish whether $t$ was generated by a random group action ($t = g \cdot s$) or if $t$ is simply a random element sampled from the set $S$.

The PRA assumption is particularly significant as it serves as a direct, quantum-safe analogue to the Decisional Diffie-Hellman (DDH) assumption used in classical cryptography. By establishing PRA, the authors move group-action cryptography beyond simple identification schemes and into the realm of Minicrypt, enabling the construction of more complex tools.

Cryptographic Constructions

Using these assumptions, the paper provides formal proofs for several essential cryptographic primitives, ensuring they remain secure even against quantum adversaries capable of making queries in superposition:

  • Digital Signatures: Constructed using the OWA assumption and the Unruh transformation, which adapts identification schemes into signatures that are secure in the Quantum Random Oracle Model (QROM).
  • Pseudorandom Functions (PRFs): Built using the GGM construction tailored for group actions. The PRA assumption allows for the creation of functions that are indistinguishable from truly random functions to any polynomial-time observer.
  • Bit Commitments: Established as a fundamental building block for more complex protocols.

Why GLAT is Quantum-Resistant

GLAT offers several advantages over previous algebraic candidates for post-quantum cryptography:

  • Non-Commutativity: Unlike the cyclic groups used in RSA or ECC, the general linear group is non-abelian (non-commutative). This prevents the application of standard quantum Fourier sampling, the primary mechanism used by Shor’s algorithm to break classical systems.
  • Resistance to Geometric Attacks: The authors demonstrate that GLAT is resistant to "supergroup attacks" and other geometric heuristics that have compromised other algebraic structures in the past.
  • Complexity Bottleneck: Because 3TI is a maximal isomorphism problem, it provides a high security margin against future algorithmic breakthroughs in isomorphism testing.

Challenges and Future Outlook

While GLAT provides a strong theoretical foundation for PQC, several hurdles remain for practical implementation:

  1. Computational Efficiency: Performing group actions on large tensors is computationally expensive. Future work must focus on optimizing the representation of these tensors and the speed of the group action operations.
  2. Public-Key Encryption (PKE): Currently, the framework focuses on "Minicrypt" (signatures and PRFs). Developing a full Public-Key Encryption or Key Exchange protocol from GLAT remains an open challenge.
  3. Average-Case Hardness: While 3TI is hard in the worst case, cryptography requires hardness in the average case. Further research into the "orbit closure" of these actions is needed to ensure that randomly generated instances are consistently difficult to solve.

In conclusion, the General Linear Group Action on Tensors represents a significant step forward in the search for quantum-safe mathematical foundations, bridging the gap between abstract group theory and practical cryptographic security.

Summary updated

Abstract

Starting from the one-way group action framework of Brassard and Yung (Crypto’90), we revisit building cryptography based on group actions. Several previous candidates for one-way group actions no longer stand, due to progress both on classical algorithms (e.g., graph isomorphism) and quantum algorithms (e.g., discrete logarithm). We propose the general linear group action on tensors as a new candidate to build cryptography based on group actions. Recent works (Futorny–Grochow–Sergeichuk Lin. Alg. Appl., 2019) suggest that the underlying algorithmic problem, the tensor isomorphism problem, is the hardest one among several isomorphism testing problems arising from areas including coding theory, computational group theory, and multivariate cryptography. We present evidence to justify the viability of this proposal from comprehensive study of the state-of-art heuristic algorithms, theoretical algorithms, hardness results, as well as quantum algorithms. We then introduce a new notion called pseudorandom group actions to further develop group-action based cryptography. Briefly speaking, given a group G acting on a set S, we assume that it is hard to distinguish two distributions of (s, t) either uniformly chosen from $$S\times S$$, or where s is randomly chosen from S and t is the result of applying a random group action of $$g\in G$$ on s. This subsumes the classical Decisional Diffie-Hellman assumption when specialized to a particular group action. We carefully analyze various attack strategies that support instantiating this assumption by the general linear group action on tensors. Finally, we construct several cryptographic primitives such as digital signatures and pseudorandom functions. We give quantum security proofs based on the one-way group action assumption and the pseudorandom group action assumption.
BibTeX
@inproceedings{ji2019general,
  author = {Zhengfeng Ji and Youming Qiao and Fang Song and Aaram Yun},
  title = {{General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography}},
  booktitle = {TCC},
  year = {2019},
  doi = {10.1007/978-3-030-36030-6\_11},
}
Figure