Post-quantum algebraic signature algorithms with a hidden group

Abstract

Introduction: The development of post-quantum standards on digital signature algorithms is one of the current challenges faced by the global cryptographic community. Recently, two types of algebraic signature schemes with a hidden group have been proposed, in which the finite non-commutative associative algebras set over the field GF(p) are used as an algebraic support. The design of that type of signature algorithms on the algebras set over the finite fields of Characteristic two represent significant interest for improving the performance and reducing the hardware implementation cost. Purpose: To develop post-quantum algebraic signature algorithms in which computations in a finite field of Characteristic two are used. Results: Several 4-dimensional finite non-commutative algebras set over the GF(2^z) fields are proposed as algebraic support of the signature schemes with a hidden group. We suggest some recommendations for choosing the value of the extension degree z. In particular cases the value of z represents a Mersenne degree. Compared with the signature algorithms which are based on the hidden logarithm problem, the algebraic signature algorithms based on the computational complexity of solving systems of many quadratic equations with many variables are considered to be a preferable type of cryptoschemes with a hidden group. We have introduced new practical signature algorithms with a hidden group. In two of the developed algorithms the signature (e, S) represents an integer e and a 4-dimensional vector S and is verified with vector equations with three and four entries of the signature element S. Practical relevance: Like other known signature schemes with a hidden group, the proposed two schemes have sufficiently small size of signature and public key. Due to comparatively small hardware implementation cost and high performance, the introduced candidates for post-quantum signature algorithms represent practical interest and are attractive as a potential prototype of a post-quantum digital signature standard.