Linear and Lossy Identification Schemes Derive Tightly Secure Multisignatures

Masayuki Fukumitsu,
Shingo Hasegawa,


For the multisignature schemes, the tight security in the plain public key (PPK) model is considered as one of the desirable features. In this paper, we give a generic construction of multisignature schemes which is tightly secure in the PPK and random oracle model. Our construction can capture the known tightly secure multisignature schemes. The generic construction is derived from the identification (ID) scheme which has two properties called the linearity and the lossiness. Thus, we can obtain new tightly secure multisignature schemes by applying our construction to existing linear and lossy ID schemes. Moreover, we consider the relationship between these two properties to shrink the conditions required for our generic construction. We propose a new property of ID schemes, called the difference soundness, and show that the combination of the linearity and the difference soundness implies the lossiness.

Citation Format:
Masayuki Fukumitsu, Shingo Hasegawa, "Linear and Lossy Identification Schemes Derive Tightly Secure Multisignatures," Journal of Internet Technology, vol. 22, no. 5 , pp. 1159-1170, Sep. 2021.

Full Text:



  • There are currently no refbacks.

Published by Executive Committee, Taiwan Academic Network, Ministry of Education, Taipei, Taiwan, R.O.C
JIT Editorial Office, Office of Library and Information Services, National Dong Hwa University
No. 1, Sec. 2, Da Hsueh Rd., Shoufeng, Hualien 974301, Taiwan, R.O.C.
Tel: +886-3-931-7314  E-mail: