Officical thesis title: "Development of a Post-Quantum Digital Signature Scheme Based on the Hidden Discrete Logarithm and the Multivariate Quadratic Problem"
Major: Computer Science Code: 9 48 01 01
Full name: DUONG THU MAY
Supervisors:
1: Prof. Dr. Nguyễn Hiếu Minh
2: Dr. Đỗ Thị Bắc
Training Institution: University of Information and Communication Technology, Thai Nguyen University.
NEW RESULTS ACHIEVED BY THE DISSERTATION
The dissertation proposes a novel approach to designing post-quantum digital signature schemes (Post-Quantum Digital Signature Scheme – PQDSS) by jointly exploiting the algebraic structure of Finite Non-commutative Associative Algebras (FNAA) and the computational complexity of two hard problems: the Hidden Discrete Logarithm Problem (HDLP) and the Multivariate Quadratic Problem (MQ).
- The schemes PQDSS₁–PQDSS₃ demonstrate the feasibility and security of this method. Specifically, PQDSS₁, built on a 4-dimensional FNAA with a global two-sided unit and a sparse Basis Vector Multiplication Table (BVMT) over GF(2ᶻ), optimizes implementation cost while generating complex MQ systems resistant to quantum attacks. PQDSS₂ and PQDSS₃ extend the approach by transforming the HDLP into an MQ-solving model over 4- and 6-dimensional FNAAs, where the public key is represented as a product of secret vectors, and the signature vector S is reused three times in the verification equations to enhance security.
- Building on this foundation, the dissertation further expands the FNAA structure and hidden group space to propose two higher-security schemes: PQDSS₄ and PQDSS₅. PQDSS₄, based on a 6-dimensional FNAA with p² global right-sided units (GRS), prevents degradation of hidden group cycles and avoids isomorphic mappings to simpler commutative algebras. PQDSS₅, developed on Quaternion-type Algebras (QTA), employs two distinct non-commuting commutative hidden groups and applies two hash-derived exponents to S to effectively conceal the group’s cyclic structure.
The PQDSS₁–PQDSS₅ schemes provide parameter recommendations-including the FNAA dimension m, finite-field size |p| bits, BVMT structure, and hash output length-to achieve NIST post-quantum security levels I/III/V, ensuring suitability for resource-constrained environments while optimizing key size, signature length, and quantum resistance.
APPLICATIONS AND PRACTICAL IMPLEMENTATION POTENTIAL
- Education & Research: The research results have been directly applied to postgraduate education and PhD supervision, contributing to the enhancement of research capacity.
- Information Security: The proposed solutions utilize post-quantum mathematical foundations to protect data integrity and authenticate information sources, even in the era of quantum computing.
- Optimization for Resource-Constrained Environments: With compact key and signature sizes, low memory and bandwidth requirements, the schemes are well-suited for IoT devices, sensors, microcontrollers, and low-speed communication systems.
OPEN ISSUES AND FUTURE RESEARCH DIRECTIONS
Building on the achieved results, the dissertation outlines several directions for further research and development as follows:
First, the PQDSS schemes based on FNAAs should be further extended and diversified by combining multiple hard computational problems such as HDLP, MQ, and dynamic hidden group structures to enhance quantum resistance.
Additionally, optimization through reducing key and signature sizes and refining algorithmic structures is essential to improve performance. Another important direction involves the study of fully randomized signature generation techniques to counter structural analysis attacks. At the same time, practical deployment should be promoted on resource-limited platforms such as IoT devices, sensors, and Industry 4.0 systems.
Finally, expanding the algebraic space using new structures and sparse multiplication tables will improve flexibility, security, and practical applicability of PQDSS schemes in the future.
