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:
- 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.
- 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:
- 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.
- 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.
- 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