Geodesic
On the (im)possibility of secure ElGamal blind signatures
Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 25-42 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In the current paper we investigate the possibility of designing secure blind signature scheme based on ElGamal signature equation. We define the generalized construction and analyze its security. We consider two types of schemes with the proposed construction, that cover all existing schemes. For schemes of the first type we provide generic ROS-style attack that violates unforgeability in the parallel setting. For schemes of the second type we prove that they do not provide either blindness, or unforgeability. As the result, we prove that all known ElGamal blind signature schemes are not secure. Moreover, these results show that the existence of secure ElGamal blind signature scheme is potentially possible only for small set of signature equations and requires the non-standard way of generating the first component of the signature. 
@article{MVK_2023_14_2_a1,
     author = {L. R. Akhmetzyanova and E. K. Alekseev and A. A. Babueva and S. V. Smyshlyaev},
     title = {On the (im)possibility of secure {ElGamal} blind signatures},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {25--42},
     year = {2023},
     volume = {14},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a1/}
}
TY  - JOUR
AU  - L. R. Akhmetzyanova
AU  - E. K. Alekseev
AU  - A. A. Babueva
AU  - S. V. Smyshlyaev
TI  - On the (im)possibility of secure ElGamal blind signatures
JO  - Matematičeskie voprosy kriptografii
PY  - 2023
SP  - 25
EP  - 42
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a1/
LA  - en
ID  - MVK_2023_14_2_a1
ER  - 
%0 Journal Article
%A L. R. Akhmetzyanova
%A E. K. Alekseev
%A A. A. Babueva
%A S. V. Smyshlyaev
%T On the (im)possibility of secure ElGamal blind signatures
%J Matematičeskie voprosy kriptografii
%D 2023
%P 25-42
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a1/
%G en
%F MVK_2023_14_2_a1
L. R. Akhmetzyanova; E. K. Alekseev; A. A. Babueva; S. V. Smyshlyaev. On the (im)possibility of secure ElGamal blind signatures. Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 25-42. http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a1/

[1] Abe M., Okamoto T., “Provably secure partially blind signatures”, CRYPTO 2000, Lect. Notes Comput. Sci., 1880, 2000, 271–286 | DOI | MR | Zbl

[2] Babueva A. A., Akhmetzyanova L. R., Alekseev E. K., Taraskin O. G., On blindness of several ElGamal-type blind signatures, Cryptology ePrint Archive, Paper 2022/1739, 2022 | Zbl

[3] Benhamouda F., Lepoint T., Los J., Orru M., Raykova M., “On the (in)security of ROS”, EUROCRYPT 2021, Lect. Notes Comput. Sci., 12696, 2021, 33–53 | DOI | MR | Zbl

[4] Chaum D., “Blind signatures for untraceable payments”, Proc. CRYPTO'82, Springer, Boston, MA, 1983, 199–203

[5] Camenisch J. L., Piveteau J. M., Stadler M. A., “Blind signatures based on the discrete logarithm problem”, Advances in Cryptology - EUROCRYPT'94, Lect. Notes Comput. Sci., 950, 1994, 428–432 | DOI | MR

[6] ElGamal T., “A public key cryptosystem and a signature scheme based on discrete logarithms”, CRYPTO'84, Lect. Notes Comput. Sci., 196, 1985, 10–18 | DOI | MR | Zbl

[7] Fersch M., The provable security of Elgamal-type signature schemes, Diss., Ruhr-Universität Bochum, Bochum, 2018

[8] Fujioka A., Okamoto T., Ohta K., “A practical secret voting scheme for large scale elections”, AUSCRYPT'92, Lect. Notes Comput. Sci., 718, 1992, 244–251 | DOI

[9] Fuchsbauer G., Plouviez A., Seurin Y., “Blind Schnorr signatures and signed ElGamal encryption in the algebraic group model”, EUROCRYPT 2020, Lect. Notes Comput. Sci., 12106, 2020, 63–95 | DOI | MR | Zbl

[10] Gorbenko I., Yesina M., Ponomar V., “Anonymous electronic signature method”, 2016 Third Int. Sci.-Pract. Conf. Problems of Infocommunic. Sci. and Technology, PIC S, IEEE, 2016, 47–50 | DOI

[11] Harn L., Xu Y., “Design of generalised ElGamal type digital signature schemes based on discrete logarithm”, Electr. Lett., 30:24 (1994), 2025–2026 | DOI

[12] Jena D., Panigrahy S. K., Acharya B., Jena S. K., “A novel ECDLP-based blind signature scheme”, Nat. Conf. Inf. Security – Issues Challenges, NCISIC 08, 2008, 37–40

[13] Khater M. M., Al-Ahwal A., Selim M. M., Zayed H. H., “New blind signature scheme based on modified ElGamal signature for secure electronic voting”, Int. J. Sci. Eng. Research, 9:3 (2018), 917–921

[14] Moldovyan N. A., “Blind signature protocols from digital signature standards”, Int. J. Netw. Secur., 13:1 (2011), 22–30 | MR

[15] Pointcheval D., Stern J., “Security arguments for digital signatures and blind signatures”, J. Cryptology, 13:3 (2000), 361–396 | DOI | Zbl

[16] Qin X., Cai C., Yuen T.H., “One-more unforgeability of blind ECDSA”, ESORICS 2021, Lect. Notes Comput. Sci., 12973, 2021, 313–331 | DOI | Zbl

[17] Rostovtsev A. G., “Blind signature on elliptic curve for e-cash”, Probl. informacionnoj bezopasnosti. Kompyuternye sistemy, 1 (2000), 40–45 (In Russian)

[18] Schnorr C. P., “Security of blind discrete log signatures against interactive attacks”, Int. Conf. Inf. Communic. Security, Lect. Notes Comput. Sci., 2229, 2001, 1–12 | DOI | Zbl

[19] Shen V. R., Chung Y. F., Chen T. S., Lin Y. A., “A blind signature based on discrete logarithm problem”, Int. J. Innovat. Computing, Inf. and Control, 7:9 (2011), 5403–5416

[20] Tan D. N., Nam H. N., Van H. N., Thi L. T., Hieu M. N., “New blind mutisignature schemes based on signature standards”, 2017 Int. Conf. Adv. Comput. Appl., ACOMP, IEEE, 2017, 23–27 | DOI | MR

[21] Tan D. N., Nam H. N., Hieu M. N., Van H. N., “New blind multi-signature schemes based on ECDLP”, Int. J. Electr. Computer Eng., 8:2 (2018), 1074–1083

[22] Vinberg E. B., A course in algebra, Graduate Studies in Mathematics, 56, Amer. Math. Soc., 2003, 511 pp. | DOI | MR | Zbl

[23] Wagner D., “A generalized birthday problem”, CRYPTO 2002, Lect. Notes Comput. Sci., 2442, 2002, 288–304 | DOI | MR

[24] Yi X., Lam K. Y., “A new blind ECDSA scheme for bitcoin transaction anonymity”, Proc. 2019 ACM Asia Conf. Computer and Communic. Security, 2019, 613–620

[25] Zhang Y., He D., Zhang F., Huang X., Li D., “An efficient blind signature scheme based on SM2 signature algorithm”, Int. Conf. Inf. Secur. Cryptology, Lect. Notes Comput. Sci., 12612, 2020, 368–384 | DOI | MR

[26] GOST R 34.10-2012. Information technology. Cryptographic data security. Signature and verification processes of electronic digital signature, National standard of the Russian Federation, STANDARTINFORM, M., 2012 (In Russian)