MQIBS: An Efficient Post-Quantum Identity-based Signature from Multivariate Polynomials
Abstract
Identity-based signature (IBS) is an important cryptographic primitive which allows authentication of a party’s public key without the need for certificates. In this paper, we construct a post-quantum provable identity-based signature scheme from multivariate polynomials. Our scheme is constructed from the sigma protocols with helper by Beullens at Eurocrypt 2020 and the Fiat-Shamir paradigm. Concrete choice of parameters shows that our scheme is more efficient than existing multivariate IBS schemes in terms of public key/signature sizes.References
National Institute of Standards and Technology additional post-quantum signatures.
https://csrc.nist.gov/projects/pqc-dig-sig/round-1-additional-signatures.
Accessed: 2024-07-24.
National Institute of Standards and Technology post-quantum cryptography.
https://csrc.nist.gov/projects/post-quantum-cryptography.
Accessed: 2024-07-24.
Sedat Akleylek and Meryem Soysaldi.
A novel 3-pass identification scheme and signature scheme based on multivariate quadratic polynomials.
Turkish Journal of Mathematics, 43:241--257, 2019.
Ward Beullens.
Sigma Protocols for MQ, PKP and SIS, and Fishy Signature Schemes. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part III, volume 12107 of Lecture Notes in Computer Science, pages 183--211. Springer, 2020.
Ward Beullens.
Breaking rainbow takes a weekend on a laptop.
In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in
Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference,CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part II, volume 13508 of Lecture Notes in Computer Science, pages 464--479. Springer, 2022.
Andrey Bogdanov, Thomas Eisenbarth, Andy Rupp, and Christopher Wolf.
Time-area optimized public-key engines: Mq-cryptosystems as
replacement for elliptic curves? IACR Cryptol. ePrint Arch., page 349, 2008.
Anna Inn-Tung Chen, Ming-Shing Chen, Tien-Ren Chen, Chen-Mou Cheng, Jintai Ding, Eric Li-Hsiang Kuo, Frost Yu-Shuang Lee, and Bo-Yin Yang.
SSE implementation of multivariate pkcs on modern x86 cpus.
In Christophe Clavier and Kris Gaj, editors, Cryptographic
Hardware and Embedded Systems - CHES 2009, 11th International Workshop, Lausanne, Switzerland, September 6-9, 2009, Proceedings, volume 5747 of Lecture Notes in Computer Science, pages 33--48. Springer, 2009.
Jiahui Chen, Jie Ling, Jianting Ning, and Jintai Ding.
Identity-based signature schemes for multivariate public key
cryptosystems.
Comput. J., 62(8):1132--1147, 2019.
Ming-Shing Chen, Andreas H lsing, Joost Rijneveld, Simona Samardjiska, and
Peter Schwabe.
MQDSS submission to the NIST post-quantum cryptography project.
In NIST Post-quantum Cryptography, 2017.
Ming-Shing Chen, Andreas H"ulsing, Joost Rijneveld, Simona Samardjiska, and Peter Schwabe.
From 5-pass phMQ -based identification tophMQ -based
signatures.
In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in
Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part II, volume 10032 of Lecture Notes in Computer Science, pages 135--165, 2016.
Sumit Kumar Debnath, Sihem Mesnager, Vikas Srivastava, Saibal Kumar Pal, and Nibedita Kundu.
Mul-ibs: a multivariate identity-based signature scheme compatible with iot-based NDN architecture.
J. Cryptogr. Eng., 13(2):187--199, 2023.
Jintai Ding and Dieter Schmidt.
Rainbow, a new multivariable polynomial signature scheme.In John Ioannidis, Angelos D. Keromytis, and Moti Yung, editors,
Applied Cryptography and Network Security, Third International Conference, ACNS 2005, New York, NY, USA, June 7-10, 2005, Proceedings, volume 3531 of Lecture Notes in Computer Science, pages 164--175, 2005.
Amos Fiat and Adi Shamir.
How to prove yourself: Practical solutions to identification and
signature problems. In Andrew M. Odlyzko, editor, Advances in Cryptology - CRYPTO '86, Santa Barbara, California, USA, 1986, Proceedings, volume 263 of Lecture Notes in Computer Science, pages 186--194. Springer, 1986.
Hiroki Furue, Dung Hoang Duong, and Tsuyoshi Takagi.
An efficient mq-based signature in the QROM.
In 2019 Seventh International Symposium on Computing and
Networking, CANDAR 2019, Nagasaki, Japan, November 25-28, 2019, pages 10--17. IEEE, 2019.
M R Garey and D S Johnson.
Computers and Intractability: A Guide to the Theory of Np-Completeness. W. H. Freeman, 1979.
Daniel Kales and Greg Zaverucha.
An attack on some signature schemes constructed from five-pass
identification schemes.
In Stephan Krenn, Haya Schulmann, and Serge Vaudenay, editors, Cryptology and Network Security - 19th International Conference, CANS 2020, Vienna, Austria, December 14-16, 2020, Proceedings, volume 12579 of Lecture Notes in Computer Science, pages 3--22. Springer, 2020.
Jonathan Katz, Vladimir Kolesnikov, and Xiao Wang.
Improved Non-Interactive Zero Knowledge with Applications to
Post-Quantum Signatures.
In CCS '18: Proceedings of the 2018 ACM SIGSAC Conference on
Computer and Communications Security, pages 525 -- 537. ACM, 2017.
Eike Kiltz and Gregory Neven.
Identity-based signatures. In Marc Joye and Gregory Neven, editors, Identity-Based
Cryptography, volume 2 of Cryptology and Information Security Series, pages 31--44. IOS Press, 2009.
Aviad Kipnis, Jacques Patarin, and Louis Goubin.
Unbalanced oil and vinegar signature schemes.
In Jacques Stern, editor, Advances in Cryptology - EUROCRYPT
'99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, volume 1592 of Lecture Notes in Computer Science, pages 206--222. Springer, 1999.
Le Van Luyen.
An improved identity-based multivariate signature scheme based on rainbow. Cryptogr., 3(1):8, 2019.
Jacques Patarin.
Cryptanalysis of the Matsumoto and Imai public key scheme of
eurocrypt'88.
In Don Coppersmith, editor, Advances in Cryptology - CRYPTO
'95, 15th Annual International Cryptology Conference, Santa Barbara, California, USA, August 27-31, 1995, Proceedings, volume 963 of Lecture Notes in Computer Science, pages 248--261. Springer, 1995.
Albrecht Petzoldt, Stanislav Bulygin, and Johannes Buchmann.
Cyclicrainbow - A multivariate signature scheme with a partially
cyclic public key.
In Guang Gong and Kishan Chand Gupta, editors, Progress in
Cryptology - INDOCRYPT 2010 - 11th International Conference on Cryptology in India, Hyderabad, India, December 12-15, 2010. Proceedings, volume 6498 of Lecture Notes in Computer Science, pages 33--48. Springer, 2010.
Koichi Sakumoto, Taizo Shirai, and Harunaga Hiwatari.
Public-key identification schemes based on multivariate quadratic
polynomials.
In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO
- 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 706--723. Springer, 2011.
Adi Shamir.
Identity-based cryptosystems and signature schemes.
In G. R. Blakley and David Chaum, editors, Advances in
Cryptology, Proceedings of CRYPTO '84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings, volume 196 of Lecture Notes in Computer Science, pages 47--53. Springer, 1984.
Adi Shamir.
Public quadratic polynomial-tuples for efficient
signature-verification and message-encryption.
In G. R. Blakley and David Chaum, editors, Advances in
Cryptology, Proceedings of EUROCRYPT '88, Davos, Switzerland, May 25-27, 1988, Proceedings, volume 330 of Lecture Notes in Computer Science, pages 419--553. Springer, 1988.
Wuqiang Shen, Shaohua Tang, and Lingling Xu.
Ibuov, A provably secure identity-based UOV signature scheme.
In 16th IEEE International Conference on Computational Science
and Engineering, CSE 2013, December 3-5, 2013, Sydney, Australia, pages 388--395. IEEE Computer Society, 2013.
DOI:
https://doi.org/10.31449/inf.v49i11.7089Downloads
Additional Files
Published
How to Cite
Issue
Section
License
I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.
I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.
In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.
I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal. The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.
Copyright © Slovenian Society Informatika
