Post-quantum signature algorithms with a hidden group and doubled verification equation

Abstract

Introduction: One of the current topical problems of cryptography is the development of post-quantum digital signature algorithms with relatively small sizes of the public key and signature. Purpose: To develop a new method for designing post-quantum algebraic signature algorithms with a hidden group, based on the computational complexity of solving large systems of quadratic multivariate equations, which allows to reduce the size of the public key and signature as compared to the known analogues. Results: We propose a new method for designing digital signature algorithms with a signature of the form (e, S), where e is a natural number (randomization parameter) and S is a vector (fitting parameter. The method makes it possible to reduce the dimension of finite non-commutative associative algebras used as an algebraic support. The method is distinguished by the use of the technique of doubling the verification equation for fixing the hidden group, which allows one to set the formation of the vector S depending on the random reversible vector and thereby eliminates the influence of the number of signed documents on the security, which is typical of the known analogous algorithms. The method has been tested by the development of a specific post-quantum signature algorithm, various modifications of which use algebras of different dimensions. A preliminary security assessment of the proposed algorithm has been performed. Practical relevance: Due to comparatively small sizes of signature and public key, the introduced signature algorithm represents significant practical interest as a prototype of a post-quantum signature standard.