Paper 2018/1141

Fast Authentication from Aggregate Signatures with Improved Security

Muslum Ozgur Ozmen, Rouzbeh Behnia, and Attila A. Yavuz


An attempt to derive signer-efficient digital signatures from aggregate signatures was made in a signature scheme referred to as Structure-free Compact Rapid Authentication (SCRA) (IEEE TIFS 2017). In this paper, we first mount a practical universal forgery attack against the NTRU instantiation of SCRA by observing only 8161 signatures. Second, we propose a new signature scheme (FAAS), which transforms any single-signer aggregate signature scheme into a signer-efficient scheme. We show two efficient instantiations of FAAS, namely, FAAS-NTRU and FAAS-RSA, both of which achieve high computational efficiency. Our experiments confirmed that FAAS schemes achieve up to 100x faster signature generation compared to their underlying schemes. Moreover, FAAS schemes eliminate some of the costly operations such as Gaussian sampling, rejection sampling, and exponentiation at the signature generation that are shown to be susceptible to side-channel attacks. This enables FAAS schemes to enhance the security and efficiency of their underlying schemes. Finally, we prove that FAAS schemes are secure (in random oracle model), and open-source both our attack and FAAS implementations for public testing purposes.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Financial Cryptography and Data Security 2019 (FC'19)
AuthenticationDigital signaturesUniversal forgeryNTRU-based signatures
Contact author(s)
ozmenmu @ oregonstate edu
2018-11-29: received
Short URL
Creative Commons Attribution


      author = {Muslum Ozgur Ozmen and Rouzbeh Behnia and Attila A.  Yavuz},
      title = {Fast Authentication from Aggregate Signatures with Improved Security},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1141},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.