Cryptology ePrint Archive: Report 2016/911

The Shortest Signatures Ever

Mohamed Saied Emam Mohamed and Albrecht Petzoldt

Abstract: Multivariate Cryptography is one of the main candidates for creating post quantum public key cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. In this paper we present a general technique to reduce the signature size of multivariate schemes. Our technique enables us to reduce the signature size of nearly all multivariate signature schemes by 10 to 15 % without slowing down the scheme significantly. We can prove that the security of the underlying scheme is not weakened by this modification. Furthermore, the technique enables a further reduction of the signature size when accepting a slightly more costly verification process. This trade off between signature size and complexity of the verification process can not be observed for any other class of digital signature schemes. By applying our technique to the Gui signature scheme, we obtain the shortest signatures of all existing digital signature schemes.

Category / Keywords: public-key cryptography / Post Quantum Cryptography, Multivariate Cryptography, Digital Signatures, Signature Size

Date: received 19 Sep 2016, last revised 19 Sep 2016

Contact author: mohamed at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20160919:150204 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]