Geodesic
On the security of some algorithms over a group of points of elliptic curves
Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 63-70.

Voir la notice de l'article provenant de la source Math-Net.Ru

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).
Keywords: provable security, VKO, signature scheme, joint security. 
@article{PDMA_2024_17_a14,
     author = {A. O. Bakharev and K. D. Tsaregorodtsev},
     title = {On the security of some algorithms over a group of points of elliptic curves},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {63--70},
     publisher = {mathdoc},
     number = {17},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2024_17_a14/}
}
TY  - JOUR
AU  - A. O. Bakharev
AU  - K. D. Tsaregorodtsev
TI  - On the security of some algorithms over a group of points of elliptic curves
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2024
SP  - 63
EP  - 70
IS  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2024_17_a14/
LA  - ru
ID  - PDMA_2024_17_a14
ER  - 
%0 Journal Article
%A A. O. Bakharev
%A K. D. Tsaregorodtsev
%T On the security of some algorithms over a group of points of elliptic curves
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2024
%P 63-70
%N 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2024_17_a14/
%G ru
%F PDMA_2024_17_a14
A. O. Bakharev; K. D. Tsaregorodtsev. On the security of some algorithms over a group of points of elliptic curves. Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 63-70. http://geodesic.mathdoc.fr/item/PDMA_2024_17_a14/

[1] Pankratova I. A., Teoretiko-chislovye metody kriptografii, Ucheb. posobie, Tomskii gosudarstvennyi universitet, Tomsk, 2009, 120 pp.

[2] Adleman L., “A subexponential algorithm for the discrete logarithm problem with applications to cryptography”, Proc. 20th Ann. Symp. Found. Comput. Sci. (San Juan, PR, USA), 1979, 55–60

[3] Menezes A., Vanstone S., and Okamoto T., “Reducing elliptic curve logarithms to logarithms in a finite field”, Proc. 23th Ann. ACM Symp. Theory Comput. (New Orleans, Louisiana, USA), 1991, 80–89 | MR

[4] Alekseev E. K., Oshkin I. B., Popov V. O., Smyshlyaev S. V., “O kriptograficheskikh svoistvakh algoritmov, soputstvuyuschikh primeneniyu standartov GOST R 34.11-2012 i GOST R 34.10-2012”, Matem. vopr. kriptogr., 7:1 (2016), 5–38 | DOI | MR | Zbl

[5] Bellare M. and Rogaway P., “Random oracles are practical: A paradigm for designing efficient protocols”, Proc. CCS'93 (Fairfax, Virginia, USA), 1993, 62–73

[6] Fersch M., Kiltz E., and Poettering B., “On the provable security of (EC)DSA signatures”, Proc. CCS'16 (Vienna, Austria), 2016, 1651–1662

[7] Fersch M., The Provable Security of ElGamal-type Signature Schemes, Doctoral dissertation, Ruhr University Bochum, 2018

[8] Nechaev V. I., “K voprosu o slozhnosti determinirovannogo algoritma dlya diskretnogo logarifma”, Matem. zametki, 55:2 (1994), 91–101 | Zbl

[9] Shoup V., “Lower bounds for discrete logarithms and related problems”, LNCS, 1233, 1997, 256–266 | MR

[10] Rekomendatsii po standartizatsii R 50.1.113-2016. Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Kriptograficheskie algoritmy, soputstvuyuschie primeneniyu algoritmov elektronnoi tsifrovoi podpisi i funktsii kheshirovaniya, Standartinform, M., 2016

[11] Mezhgosudarstvennyi standart GOST 34.10.2018. Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Protsessy formirovaniya i proverki elektronnoi tsifrovoi podpisi, Standartinform, M., 2018

[12] Paterson K. G., Schuldt J., Stam M., Thomson S., “On the joint security of encryption and signature, revisited”, LNCS, 7073, 2011, 161–178 | MR | Zbl

[13] Babueva A. A, Bozhko A. A., and Kyazhin S. N., “Joint security of encryption and signature in RuCMS: Two keys are better, but one is also fine”, Proc. CTCrypt'24, 2024 | Zbl

[14] Sipser M., Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2012