Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Post-Quantum Cryptography, Multivariate Cryptography, Signature Schemes, Unbalanced Oil and Vinegar, Key Size Reduction

Date: received 14 Aug 2017

Contact author: ward beullens at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20170816:122600 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]