Improving the security of ElGamal-type signatures

We propose a method for modifying ElGamal-type signature schemes (in particular, GOST R 34.10-2012), which improves security in case of their usage in the weakly trusted environments (in the absence of reliable randomness). SUF-CMRA (Strong Unforgeability under Chosen Message and Randomness Attack) security model is introduced for analyzing the security of the modified signature scheme. We provide the security bound of modified scheme in the SUF-CMRA model, which allows us to estimate the security of modified scheme by the SUF-CMA–security of the underlying signature scheme and PRF-security of HMAC function.