Cryptology ePrint Archive: Report 2020/1484

Cryptanalysis of Aggregate $\Gamma$-Signature and Practical Countermeasures in Application to Bitcoin

Goichiro Hanaoka and Kazuo Ohta and Yusuke Sakai and Bagus Santoso and Kaoru Takemure and Yunlei Zhao

Abstract: We present a sub-exponential forger by using a $k$-sum algorithm against the aggregate $\Gamma$-signature, which was proposed at AsiaCCS 2019 by Zhao. Our forger is a universal forger under a key-only attack and effective in the knowledge of secret key model. We also discuss the real impact of this attack in reality with Bitcoin applications. The discussions on the real impact of the attack also highlight the significant differences between the usage of individual signatures like EC-DSA and that of aggregate signatures in the blockchain systems like Bitcoin, which might be of independent interest and could bring forth interesting questions for future investigations.

Category / Keywords: public-key cryptography / k-sum algorithm, aggregate signature, universal forgery, blockchain

Date: received 25 Nov 2020, last revised 15 Dec 2020

Contact author: takemure at uec ac jp,yusuke sakai@aist go jp,santoso bagus@uec ac jp,kazuo ohta@uec ac jp,hanaoka-goichiro@aist go jp,ylzhao@fudan edu cn

Available format(s): PDF | BibTeX Citation

Version: 20201215:085812 (All versions of this report)

Short URL: ia.cr/2020/1484


[ Cryptology ePrint archive ]