Field lifting for smaller UOV public keys

Ward Beullens; Bart Preneel

Paper 2017/776

Field lifting for smaller UOV public keys

Ward Beullens and Bart Preneel

Abstract

Most Multivariate Quadratic (MQ) signature schemes have a very large public key, which makes them unsuitable for many applications, despite attractive features such as speed and small signature sizes. In this paper we introduce a modification of the Unbalanced Oil and Vinegar (UOV) signature scheme that has public keys which are an order of magnitude smaller than other MQ signature schemes. The main idea is to choose UOV keys over the smallest field F2 in order to achieve small keys, but to lift the keys to a large extension field, where solving the MQ problem is harder. The resulting Lifted UOV signature scheme is very competitive with other post-quantum signature schemes in terms of key sizes, signature sizes and speed.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Post-Quantum Cryptography Multivariate Cryptography Signature Schemes Unbalanced Oil and Vinegar Key Size Reduction
Contact author(s): ward beullens @ esat kuleuven be
History: 2017-08-16: received
Short URL: https://ia.cr/2017/776
License: CC BY

BibTeX

@misc{cryptoeprint:2017/776,
      author = {Ward Beullens and Bart Preneel},
      title = {Field lifting for smaller UOV public keys},
      howpublished = {Cryptology ePrint Archive, Paper 2017/776},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/776}},
      url = {https://eprint.iacr.org/2017/776}
}