On the security of some algorithms over a group of points of elliptic curves

The results of the analysis of the VKO scheme and the combined VKO+GOST signature scheme in “generalized group” and “bijective random oracle” heuristics are presented. Two security models have been introduced. In the model for VKO scheme, the adversary has to tell whether the key that it obtains as a challenge is chosen uniformly random or it is generated via VKO scheme. The adversary has an access to Combine oracle, which takes ephemeral public key $epk$ as an input and returns a shared key obtained via VKO scheme using long-term secret key $sk$. In the model for combined VKO+GOST signature scheme, the adversary has the additional opportunity to obtain GOST signatures on the long-term secret key $sk$ (i.e., the key $sk$ is used as a static component of VKO scheme and as a long-term secret key for the signature scheme). It has been shown that in the generic group heuristic the advantage of the adversary making at most $q_\text{com}$ queries to the Combine oracle and at most $q_\text{group}$ queries to the group oracle can be upper bounded by $2 q^{-1} (q_\text{group} + q_\text{comb})^2$ (plus a minor summand responsible for the possibility of attacks on the hash function used in the scheme), where $q$ is the base group order. The result is tight due to the existence of discrete-log finding algorithms with the $\mathcal{O}(\sqrt{q})$ complexity. For the combined VKO+GOST scheme, it has been shown that in the Bijective Random Oracle heuristic the problem can be reduced to the model for VKO scheme without signing oracle (i.e., GOST signatures do not leak any useful information).