Cryptology ePrint Archive: Report 2021/148

On methods of shortening ElGamal-type signatures

Liliya Akhmetzyanova and Evgeny Alekseev and Alexandra Babueva and Stanislav Smyshlyaev

Abstract: Development of signature schemes providing short signatures is a quite relevant non-trivial challenge for cryptographers. Since the late 1980ís many short signature schemes have been proposed. The most perspective schemes are multivariate schemes and schemes based on Weil pairing. Unfortunately, the cryptographic tools used in these schemes are still not supported by most cryptographic software that complicates their effortless use in practice.

In the current paper we investigate the opportunity of shortening the standard ElGamal-type signatures. We propose three methods of shortening signatures (for any ElGamal-type schemes such as ECDSA, GOST and SM2) and analyze how applying these methods affects the security. Applying all three methods to the GOST signature scheme with elliptic curve subgroup order $q$, $2^{255} < q < 2^{256}$, can reduce the signature size from $512$ to $320$ bits. The modified scheme provides sufficient security and acceptable (for non-interactive protocols) signing and verifying time.

Category / Keywords: public-key cryptography / short signature scheme, ElGamal-type signature scheme, GOST, provable security

Date: received 11 Feb 2021

Contact author: babueva at cryptopro ru

Available format(s): PDF | BibTeX Citation

Version: 20210212:073726 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]