TL;DR
This paper introduces SPDH-Sign, a novel class of post-quantum digital signature schemes based on group actions. By leveraging the semidirect product of groups and their automorphism groups, they construct efficient and secure signature schemes that are resistant to quantum attacks, addressing the urgent need for post-quantum cryptography.
What Problem Does This Paper Address?
The advent of quantum computers poses a significant threat to current public-key cryptography, including digital signature schemes (DSS). Shor's algorithm can efficiently break many widely used cryptographic systems. This has spurred the field of Post-Quantum Cryptography (PQC), aiming to develop quantum-resistant alternatives. While several PQC schemes exist, there's a call for diversity, particularly for efficient schemes not based on lattices. Group-based cryptography offers a promising avenue, but existing group-action based schemes have faced challenges with efficiency and scalability. This paper tackles the problem of constructing efficient and secure post-quantum group-based digital signature schemes by exploring a new class of group actions derived from semidirect products.
Methods
The core of this work lies in constructing a new class of group actions based on the semidirect product of a finite group $G$ and its automorphism group $Aut(G)$. Specifically, they define a group action of $G \times Aut(G)$ on a set derived from $G$. This construction allows for the definition of a Semidirect Discrete Logarithm Problem (SDLP), which is believed to be quantum-hard.
The authors then leverage this group action to build an honest-verifier identification scheme, SPDH-ID. This scheme is then transformed into a digital signature scheme, SPDH-Sign, using the standard Fiat-Shamir heuristic. A key contribution is demonstrating that for any finite group, a group action can be constructed, and importantly, that the size of the acting cyclic group is restricted, making uniform sampling efficient. They also provide a specific example of a group that allows for efficient sampling while maintaining resistance to cryptanalysis.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- General Construction for Group Actions: The paper shows that every finite group can define a group action suitable for cryptography, significantly broadening the scope of group-action based cryptography.
- Efficient Sampling via Semidirect Products: By utilizing the semidirect product structure, the authors demonstrate that the size of the cyclic group involved in the action is restricted, enabling efficient uniform sampling without expensive offline computations or redundancy.
- SDLP as the Security Foundation: The security of the proposed SPDH-Sign scheme is directly tied to the difficulty of the Semidirect Discrete Logarithm Problem (SDLP), a problem believed to be quantum-resistant.
- Bridging Group Theory and Cryptography: The work explicitly connects abstract group-theoretic concepts (semidirect products) to practical cryptographic constructions (digital signatures), highlighting the rich potential of group theory in PQC.
- A Concrete Example for Efficiency: The paper provides a specific group example ($G_p$) that allows for efficient computation of the group action and sampling, demonstrating the practical feasibility of their approach.
Key Results
- SPDH-Sign Scheme: The paper proposes a new family of post-quantum digital signature schemes, SPDH-Sign, based on group actions derived from semidirect products.
- Security Bounds: The security of SPDH-Sign is proven in the random oracle model and is shown to be bounded by the difficulty of the Semidirect Discrete Logarithm Problem (SDLP).
- Efficient Sampling: Theorem 4 establishes that the period $n$ (related to the cyclic group size) divides the order of the pair $(g, \phi)$ in $G \times Aut(G)$, and Theorem 9 shows that for a specific group $G_p$, $n$ is one of only 12 possible values, enabling efficient computation of $n$ and thus efficient sampling.
- Quantum Resistance: The security relies on the presumed quantum hardness of SDLP, making SPDH-Sign a candidate for post-quantum cryptography.
Limitations and Future Work
- Concrete Security Estimates: The paper acknowledges that it does not provide concrete security parameters or specific parameter sizes for a signature scheme. This requires further research into the constants in asymptotic security estimates and implementation details.
- Quantum-Accessible Random Oracle Model: While the security is proven in the random oracle model, the paper notes that for post-quantum security, the quantum-accessible random oracle model is required, with references to existing work in this area.
- Further Study of Group Choices: The authors suggest that more research is needed to explore the relative merits of different finite non-abelian groups for use in their scheme to fully realize its potential.
- Implementation: The paper mentions that providing an implementation of the scheme would merit a separate paper.
- Addressing Recent Work: The authors note that at a late stage, they became aware of work [13] discussing the security of group action-induced computational problems, particularly in a quantum sense, which should be addressed in future work concerning the difficulty of SDLP.
Summary updated