RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography]

Mat. Vopr. Kriptogr., 2021, Volume 12, Issue 2, Pages 75–91 (Mi mvk367)

On methods of shortening ElGamal-type signatures
L. R. Akhmetzyanova, E. K. Alekseev, A. A. Babueva, S. V. Smyshlyaev

References

1. Rescorla E., The Transport Layer Security (TLS) Protocol Version 1.3, RFC 8446, 2018 https://www.rfc-editor.org/info/rfc8446  crossref
2. Kaufman C., Hoffman P., Nir Y., Eronen P., Kivinen T., Internet Key Exchange Protocol Version 2 (IKEv2), RFC 7296, 2014 https://www.rfc-editor.org/info/rfc7296  crossref
3. Boneh D., Lynn B., Shacham H., “Short signatures from the Weil pairing”, ASIACRYPT 2001, Lect. Note Comput. Sci., 2248, 2001, 514–532
4. Patarin J., Courtois N., Goubin L., “FLASH, a fast multivariate signature algorithm”, CT-RSA 2001, Lect. Note Comput. Sci., 2020, 2001, 298–307
5. Patarin J., Courtois N., Goubin L., “QUARTZ, 128-bit long digital signatures”, CT-RSA 2001, Lect. Note Comput. Sci., 2020, 2001, 282–297
6. Dubois V., Fouque PA., Shamir A., Stern J., “Practical cryptanalysis of SFLASH”, CRYPTO 2007, Lect. Note Comput. Sci., 4622, 2007, 1–12
7. Courtois N.T., Daum M., Felke P., “On the security of HFE, HFEv- and Quartz”, PKC 2003, Lect. Note Comput. Sci., 2567, 2003, 337–350
8. Petzoldt A., Chen MS., Yang BY., Tao C., Ding J., “Design principles for HFEv-based multivariate signature schemes”, ASIACRYPT 2015, Lect. Note Comput. Sci., 9452, 2015, 311–334
9. Mohamed M.S.E., Petzoldt A., “The shortest signatures ever”, INDOCRYPT 2016, Lect. Note Comput. Sci., 10095, 2016, 61–77
10. Kipnis A., Patarin J., Goubin L., “Unbalanced Oil and Vinegar signature schemes”, EUROCRYPT'99, Lect. Note Comput. Sci., 1592, 1999, 206–222
11. Ding J., Schmidt D., “Rainbow, a new multivariable polynomial sgnature scheme”, ACNS 2005, Lect. Note Comput. Sci., 3531, 2005, 164–175
12. Fersch M., Kiltz E., Poettering B., “On the one-per-message unforgeability of (EC)DSA and its variants”, TCC 2017, Lect. Note Comput. Sci., 10678, 2017, 519–534
13. Fersch M., Kiltz E., Poettering B., “On the provable security of (EC) DSA signatures”, Proc. 2016 ACM SIGSAC Conf. Comput. and Communic. Security, 2016, 1651–1662
14. Fersch M., The Provable Security of Elgamal-type Signature Schemes, Diss., Bochum, 2018
15. Chevalier C., Fouque PA., Pointcheval D., Zimmer S., “Optimal randomness extraction from a Diffie-Hellman element”, EUROCRYPT 2009, Lect. Note Comput. Sci., 5479, 2009, 572–589
16. 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, 2012 (In Russian)
17. GOST 34.10-2018. Information technology. Cryptographic data security. Signature and verification processes of electronic digital signature. Interstate standard, Interstate Council for Standardization, Metrology and Certification (ISC), 2018 (in Russian)
18. ISO/IEC 14888-3:2018, IT Security techniques – Digital signatures with appendix – Part 3: Discrete logarithm based mechanisms – Section 6: Certificate-based mechanisms – 6.9: ECRDSA, 2018
19. Dolmatov V., Degtyarev A., GOST R 34.10-2012: Digital Signature Algorithm, RFC 7091, 2013 https://www.rfc-editor.org/info/rfc7091  crossref
20. Inoue A., Iwata T., Minematsu K., Poettering B., “Cryptanalysis of OCB2: attacks on authenticity and confidentiality”, CRYPTO 2019, Lect. Note Comput. Sci., 11692, 2019, 3–31
21. Koblitz N., Menezes A., Critical perspectives on provable security: fifteen years of "Another Look" papers, Cryptology ePrint Archive, Report 2019/1336, https://eprint.iacr.org/2019/1336.pdf, 2019
22. Paillier P., Vergnaud D., “Discrete-log-based signatures may not be equivalent to discrete log”, ASIACRYPT 2005, Lect. Note Comput. Sci., 3788, 2005, 1–20
23. Savage J.E., Models of Computation: Exploring the Power of Computing, Addison-Wesley Longman Publishing Co, Boston, 1998
24. Bellare M., Rogaway P., “Random oracles are practical: A paradigm for designing efficient protocols”, Proc. 1st ACM conf. Comput. and communic. security, 1993, 62–73
25. Pollard, J.M., “A Monte Carlo method for factorization”, BIT, 15 (1975), 331–334
26. Zheng Y., “Digital signcryption or how to achieve cost(signature & encryption) $\ll$ cost(signature) + cost(encryption)”, CRYPTO'97, Lect. Note Comput. Sci., 1294, 1997, 165–179
27. Akhmetzyanova A., Alekseev E., Babueva A., Smyshlyaev S., On methods of shortening ElGamal-type signatures (full version), IACR Cryptology ePrint Archive, 2021/148, https://eprint.iacr.org/2021/148.pdf, 2021


© Steklov Math. Inst. of RAS, 2025