Two-party GOST signature scheme

In this paper, we investigate the possibility of designing a secure two-party GOST signature scheme. This is a two-party interactive signing protocol that adheres to the signature equation and verification algorithm of the Russian standard signature scheme (GOST scheme) with the signing key distributed between the two parties involved. We had solve this problem in two stages. The first stage was a (fruitless) search for an appropriate scheme in the literature. It turned out that all existing schemes are insecure in the strong security models. The second stage was a synthesis of a new two-party GOST signature scheme. We had solve this problem guided by the features of the GOST signature scheme, as well as the known attacks on existing two-party schemes. The proposed signature scheme additionally uses the $\mathrm{HMAC}$ algorithm. We prove that this scheme is secure (neither party can create a correct signature without interacting with the other party) under the assumption that the classical GOST scheme is unforgeable. The proof is carried under the assumption that the $\mathrm{HMAC}$ algorithm and a certain operation in the GOST signature are modeled as random oracles.