The Shortest Signatures Ever

Mohamed Saied Emam Mohamed; Albrecht Petzoldt

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Post Quantum Cryptography Multivariate Cryptography Digital Signatures Signature Size
Contact author(s): mohamed @ cdc informatik tu-darmstadt de
History: 2016-09-19: received
Short URL: https://ia.cr/2016/911
License: CC BY

BibTeX

@misc{cryptoeprint:2016/911,
      author = {Mohamed Saied Emam Mohamed and Albrecht Petzoldt},
      title = {The Shortest Signatures Ever},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/911},
      year = {2016},
      url = {https://eprint.iacr.org/2016/911}
}