MQIBS: An Efficient Post-Quantum Identity-based Signature from Multivariate Polynomials

Le Van Luyen

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.

Full Text:

PDF

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.7089

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.