Geodesic
On methods of shortening ElGamal-type signatures
Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 2, pp. 75-91 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Development of signature schemes with short signatures is a quite relevant non-trivial challenge. The most perspective existing schemes are multivariate schemes and schemes based on Weil pairing. But the cryptographic tools used in these schemes are still not supported by most cryptographic software, this complicates their use in practice. We propose three methods of shortening standard ElGamal-type signatures and analyze how these methods affect the security. Applying all three methods to the GOST signature scheme with elliptic curve subgroup of order $q\in(2^{255},2^{256})$ may reduce the signature size from $512$ to $320$ bits providing sufficient security and acceptable (for non-interactive protocols) signing and verifying time. 
@article{MVK_2021_12_2_a5,
     author = {L. R. Akhmetzyanova and E. K. Alekseev and A. A. Babueva and S. V. Smyshlyaev},
     title = {On methods of shortening {ElGamal-type} signatures},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {75--91},
     year = {2021},
     volume = {12},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a5/}
}
TY  - JOUR
AU  - L. R. Akhmetzyanova
AU  - E. K. Alekseev
AU  - A. A. Babueva
AU  - S. V. Smyshlyaev
TI  - On methods of shortening ElGamal-type signatures
JO  - Matematičeskie voprosy kriptografii
PY  - 2021
SP  - 75
EP  - 91
VL  - 12
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a5/
LA  - en
ID  - MVK_2021_12_2_a5
ER  - 
%0 Journal Article
%A L. R. Akhmetzyanova
%A E. K. Alekseev
%A A. A. Babueva
%A S. V. Smyshlyaev
%T On methods of shortening ElGamal-type signatures
%J Matematičeskie voprosy kriptografii
%D 2021
%P 75-91
%V 12
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a5/
%G en
%F MVK_2021_12_2_a5
L. R. Akhmetzyanova; E. K. Alekseev; A. A. Babueva; S. V. Smyshlyaev. On methods of shortening ElGamal-type signatures. Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 2, pp. 75-91. http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a5/

[1] Rescorla E., The Transport Layer Security (TLS) Protocol Version 1.3, RFC 8446, 2018 https://www.rfc-editor.org/info/rfc8446 | DOI

[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 | DOI

[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 | DOI

[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, , 2019 https://eprint.iacr.org/2019/1336.pdf

[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, , 2021 https://eprint.iacr.org/2021/148.pdf