Tightly Secure Non-Interactive Multisignatures in the Plain Public Key Model

Article type: Research Article

Authors: Qian, Haifeng^; | Li, Xiangxue^; | Huang, Xinli

Affiliations: Department of Computer Science and Technology, East China Normal University, Shanghai 200241, China. E-mail: {hfqian, xxli}@cs.ecnu.edu.cn | Hangzhou Key Lab of E-business and Information Security, Hangzhou Normal University, Hangzhou 310036, China

Note: [] Corresponding author.

Abstract: Multisignature scheme allows a group of signers to generate a compact signature on a common document that certifies they endorsed the message. However, the existing state of the art multisignatures often suffers from the following problems: impractical key setup assumptions, loose security reductions and inefficient signature verification. In this paper, we propose a non-interactive multisignature scheme with tight security reduction in the random oracle model. Our proposed multisignatures address the above three problems by achieving: provable security in the plain public key model; tight security reduction under the standard Computational Diffie–Hellman (CDH) assumption and 𝒪(1) computational time for signature verification through pre-computation. Hence, our non-interactive multisignatures are of great use in routing authentication of networks.

Keywords: rogue key attacks, plain public key model, provable security, multisignatures, tight security

Journal: Informatica, vol. 23, no. 3, pp. 443-460, 2012