Cryptology ePrint Archive: Report 2018/1141

Fast Authentication from Aggregate Signatures with Improved Security

Muslum Ozgur Ozmen and Rouzbeh Behnia and Attila A. Yavuz

Abstract: 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.

Category / Keywords: public-key cryptography / Authentication, Digital signatures, Universal forgery, NTRU-based signatures

Original Publication (in the same form): Financial Cryptography and Data Security 2019 (FC'19)

Date: received 22 Nov 2018

Contact author: ozmenmu at oregonstate edu

Available format(s): PDF | BibTeX Citation

Version: 20181129:151138 (All versions of this report)

Short URL: ia.cr/2018/1141


[ Cryptology ePrint archive ]