MQ Signature and Proxy Signature Schemes with Exact Security Based on UOV Signature

Shaohua Tang; Jiahui Chen; Lingling Xu; Xiaoyu Li

Paper 2013/877

MQ Signature and Proxy Signature Schemes with Exact Security Based on UOV Signature

Shaohua Tang, Jiahui Chen, Lingling Xu, and Xiaoyu Li

Abstract

Multivariate public key cryptography which relies on MQ (Multivariate Quadratic) problems is one of the main approaches to guarantee the security of communication in the post-quantum world. In this paper, we propose a combined MQ signature scheme based on the yet unbroken UOV (Unbalanced Oil and Vinegar) signature if parameters are properly chosen. Our scheme can not only reduce the public key size of the UOV signature, but also provide more tighter bound of security against chosen-message attack in the random oracle model. On the other hand, we propose a proxy signature scheme based on our proposed combined signature scheme. Additionally, we give a strict security proof for our proxy signature scheme. Finally, we present experiments for all of our proposed schemes and the baseline schemes. Comparisons with related schemes show that our work has some advantages on performance along with more strict security.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Multivariate Quadratic Problem Multivariate Public Key Cryptography UOV Signature Exact Security Proxy Signature
Contact author(s): csshtang @ scut edu cn
History: 2013-12-30: received
Short URL: https://ia.cr/2013/877
License: CC BY

BibTeX

@misc{cryptoeprint:2013/877,
      author = {Shaohua Tang and Jiahui Chen and Lingling Xu and Xiaoyu Li},
      title = {{MQ} Signature and Proxy Signature Schemes with Exact Security Based on {UOV} Signature},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/877},
      year = {2013},
      url = {https://eprint.iacr.org/2013/877}
}