On methods of shortening ElGamal-type signatures

Development of signature schemes with short signatures is a quite relevant non-trivial challenge. The most perspective existing schemes are multivariate schemes and schemes based on Weil pairing. But the cryptographic tools used in these schemes are still not supported by most cryptographic software, this complicates their use in practice. We propose three methods of shortening standard ElGamal-type signatures and analyze how these methods affect the security. Applying all three methods to the GOST signature scheme with elliptic curve subgroup of order $q\in(2^{255},2^{256})$ may reduce the signature size from $512$ to $320$ bits providing sufficient security and acceptable (for non-interactive protocols) signing and verifying time.