Paper 2022/339

New Digital Signature Algorithm EHT

Abstract

Every public-key encryption/decryption algorithm where the set of possible plain-texts is identical to the set of possible cipher-texts may be converted into a digital signature algorithm. That is quite different in the lattice (code)-based public-key cryptography. The decryption algorithm on a random input produces a valid plain-text, that is a signature, with a negligible probability. That explains why it is so difficult to construct a new secure and efficient lattice-based digital signature system. Though several solutions are known and taking part in the NIST Post Quantum Standardisation Process there is still a need to construct digital signature algorithms based on new principles. In this work, a new and efficient digital signature algorithm is suggested. Its design is simple and transparent. Its security is based on the hardness of an approximate closest vector problem in the maximum norm for some $q$-ary lattices. The signature is shorter than that provided by the NIST Selected Digital Signature Algorithms with a comparable security level, while the public key size is larger.

Note: The efficiency of the signature(signature size and public key size) was improved in this revision by using composite moduli. Besides, the parameters of the algorithm were proposed for two security levels: 120 and 240 bits. For the 120-bit security level, the parameters were compared with those of the NIST Selected Digital Signature Algorithms.