Paper 2016/503

MQSAS - A Multivariate Sequential Aggregate Signature Scheme

Rachid El Bansarkhani, Mohamed Saied Emam Mohamed, and Albrecht Petzoldt

Abstract

(Sequential) Aggregate signature schemes enable a group of users $u_1,\dots ,u_k$ with messages $m_1,\dots ,m_k$ to produce a single signature $\mathrm{\Sigma }$ which states the integrity and authenticity of all the messages $m_1,\dots ,m_k$. The length of the signature $\mathrm{\Sigma }$ is thereby significantly shorter than a concatenation of individual signatures. Therefore, aggregate signatures can improve the efficiency of numerous applications, e.g. the BGPsec protocol of Internet routing and the development of new efficient aggregate signature schemes is an important task for cryptographic research. On the other hand, multivariate cryptography offers a huge variety of practical signature schemes. However, there is a lack of multivariate signature schemes with special properties such as aggregate signature schemes. In this paper, we propose a technique to extend the HFEv- signature scheme to a sequential aggregate signature scheme. By doing so, we create the first multivariate signature scheme of this kind. Our scheme is very efficient and offers compression rates that outperform current lattice-based constructions for practical parameters.