key: cord-0047005-xxt7nc2w
authors: Kansal, Meenakshi; Dutta, Ratna
title: Round Optimal Secure Multisignature Schemes from Lattice with Public Key Aggregation and Signature Compression
date: 2020-06-06
journal: Progress in Cryptology - AFRICACRYPT 2020
DOI: 10.1007/978-3-030-51938-4_14
sha: 52c521094664882f70bc620bb470b1fab80cd316
doc_id: 47005
cord_uid: xxt7nc2w

This paper presents the first construction for an efficient multisignature (MS) in the lattice setting, achieving signature compression and public key aggregation simultaneously with single round signature generation. The multisignature size in our construction is the same as that of a single signature. The verification of a multisignature can be performed with the aggregated public key and the verifier gets convinced that the message has been signed by all the signers. More positively, our aggregated public key size is also the same as that of a single signer. Additionally, we extend our multisignature to an accountable subgroup multisignature (ASM) that permits any subset of potential signers to sign a common message with the property that the signature reveals the identities of the signers to any verifier. Our ASM scheme enjoys the same efficiency as that of our MS scheme without incurring any loss in the security reduction. We design our schemes in the plain public key model where there is no need to verify individual public keys. Our constructions are built in the standard lattice and are proven to be secure under the hardness of the short integer solution (SIS) problem in the random oracle model.

Multisignature. In today's digital world, reducing bandwidth is a desirable and challenging task, especially for low energy devices. For instance, sensors and cell phones have restricted battery life. Multisignature is a powerful cryptographic primitive that helps to reduce the bandwidth taken by N signatures from O(N ) to O (1) . A multisignature scheme provides a group of signers the ability to sign collaboratively a common message in such a way that the size of the multisignature remains the same as that of a single signature and the verifier gets convinced that the message has been signed by all the signers. Multisignature becomes more efficient when the public keys can be aggregated to have size asymptotically equivalent to that of the public key of an individual signer and can be verified with the aggregated public key.

Accountable Subgroup Multisignature. Accountable subgroup multisignature, introduced by Micali et al. [17] , enables a subset S of a set of potential signers G to jointly produce a multisignature on a given message such that it satisfies flexibility and accountability. Flexibility means that any subset S of G can sign the document and the verification is then upto the verifier whether the subset S is sufficient to approve the document (message) which is signed jointly by the signers in S. For instance, consider a case as taken in [17] , when a company X signs a contract of a company Y. Suppose a subset S of X containing chief operating officer, chief financial officer and chief marketing officer sign the contract and sends the signature to Y. If Y prefers to have the signature of the chief executive officer then Y may reject the signature. Accountability refers to the fact that the set S is known to the verifier.

Multisignatures find applications in areas where storage and bandwidth costs are subject to minimization. Recently, multisignature has gained attention due to the popularity of the distributed applications that supports decentralize trust such as blockchain. Blockchain is a promising technology in the new financial era where digital currency like Bitcoin is the central currency with no intermediaries trusted parties such as bank to process transactions. Multisignature can reduce the size of blockchains [16] . In blockchain, a number of users agree (sign) on a specific message and put the signature to a block. It is desirable to aggregate these signatures into a single signature to reduce the size of the block. Furthermore, since all the public keys need to be written to the blockchain, it is also required to aggregate all the public keys into a single public key such that the aggregated public key has the same size as that of a single public key.

In Bitcoin, multisig is the hash of l public keys and a number k with 1 ≤ k ≤ l. Multisignature can reduce the multisig Bitcoin address. The multisig in real life offers a feature that participation of all the l signers is not required to spend funds from the multisig address, but a sufficient number k of participation is sufficient. Accountable subgroup multisignature is a solution that allows a subset S of k signers take part in the signature generation instead of all l signers where l k is large [4] . The subset S may be decided by the verifier from the flexibility property of the accountable subgroup multisignature [17] .

Our Contribution. As pointed by Micali et al. [17] , many proposed multisignature schemes are vulnerable to rogue key attacks (for instance Harn [10] , Li et al. [14] ) or their security requires trusted generation of each key (for instance Ohta et al. [19] , Ohta et al. [20] ). They constructed the first multisignature scheme in [17] without trusted key generation. However, it requires an interactive initialization session among all the signers where each signer proves to the other signers that it possesses the secret key for the given public key. This model does not support dynamic setting and is not suited for large groups. Later, Boldyreva [3] introduced the concept of knowledge of secret key (KOSK) to overcome the interactive initialization round in the key registration process. The KOSK assumption utilizes non-interactive zero knowledge proof of knowledge (ZKPoK) involving heavy computation. Consequently, it is highly desirable to construct multisignature scheme in the plain public key model where the special registration of public key is not required. This paper constructs the first lattice based multisignature scheme supporting public key aggregation in the plain public key model. Specifically, we design a multisignature scheme MS and an accountable subgroup multisignature scheme ASM that exhibit signature compression as well as public key aggregation. The verifier only requires an aggregated public key instead of all the public keys to verify a multisignature. Each signer in MS takes part in the multisignature generation and uses public keys of all the participating signers. On the other hand, each signer in our ASM uses aggregated public key along with a group membership key to issue a multisignature. We require only a single round interactive protocol among all the participating signers in a group G to generate a group membership key which can be used to issue an accountable subgroup multisignature for any subset of signers S ⊆ G. Both our constructions achieve simulation based security in the plain public key model against adversaries making bounded number of queries to signatures and hashes. The security of our MS and ASM is derived under the hardness of short integer solution (SIS) problem following the security model of Boneh et al. [4] .

As shown in Table 1 , 2, our MS and ASM schemes are computationally efficient as we have used matrix addition and multiplication. These are linear operations and are very efficient compared to exponentiations and pairings used in [4] [5] [6] 16] . Our construction enjoys the same round complexity as in the work of Boneh et al. [4] . Similar to the existing works, the multisignature size in our designs are independent of the number of signers involved. Since, our designs are based on lattice, the storage and communication overheads are more (see Table 1 , 2) compared to the pairing based multisignature schemes [4] [5] [6] 16] .

The only lattice based multisignature scheme is by Bansarkhani et al. [7] which compresses signature but does not support public key aggregation. It is based on the signature scheme of Guneysu et al. [8, 9] . The verifier requires public keys of all the signers. The scheme uses ideal lattice and chooses secret keys from polynomial rings where coefficients are bounded. The scheme is secure under the hardness of ring-SIS problem. It involves three rounds of communication between a signer and cosigner to generate a multisignature. In contrast, our scheme requires only one round of communication between a signer and the designated signer, is built on standard lattice, the verifier requires only an aggregated public key instead of public keys of all the signers and is proven to be secure under the hardness of SIS problem. : ||M|| ≤ σ √ k}. Each user generates its own publicsecret key pair (pk, sk). The signer i chooses a short matrix V i ∈ Z m×m q with ||V i || ≤ σ √ m as its secret key sk i and sets its own public key as pk i = Y i = A · V i ∈ Z n×m q where σ is specified in the public parameter set Y. Note that finding sk i = V i from pk i = Y i is the SIS problem. As each signer generates its own public-secret key pair, the adversary is allowed to generate public and secret keys of users in the security game except for the challenged signer i * . The adversary is given access to the signing oracle corresponding to the signer i * ∈ G. Let G be a group of signers involved in generating a multisignature on a message M and PK is the set of public key of the signers in G who have participated in this multisignature generation. Each signer i ∈ G uses its secret key sk i together with the public keys of all the signers in G to generate a signature T i,M = H 0 (M, PK) + sk i · H 1 (pk i , PK) · Anyone can aggregate the public keys in PK into an aggregated public key pkag PK = i∈G pk i · H 1 (pk i , PK) ∈ Z n×n q . A verifier verifies a multisignature msig PK,M = (T M , pkag PK , G, M) using the aggregated public key pkag PK . It outputs 1 if A · T M = A · |G| · H 0 (M, PK) + pkag PK · H 2 (M ) and ||T M || ≤ |G| · (||H 0 (M, PK)|| + σ 3 m √ n). Otherwise, it outputs 0. While the adversary makes a signature generation query, the simulator simulates the signature for the challenged signer i * . The ranges of H 1 and H 2 have been specified with bounds to preserve the security. While simulating the signature T i * ,M for i * without knowing its secret key, the simulator calls for H 1 (pk i * , PK) query, H 2 (M ) query, chooses T i * ,M ∈ Z n×m q and finds the value of H 0 (M, PK) satisfying the equation A · T i * ,M = A · H 0 (M, PK) + pk i * · H 1 (pk i * , PK) · H 2 (M ). As there is no bound restriction on the range of H 0 , one can find H 0 (M, PK) using the Gauss elimination method or any other linear algebra method. Using the generalized forking lemma, we finally show that if the adversary is able to forge a multisignature, then the simulator finds V * ∈ Z m×m q satisfying A · V * = 0 mod q with ||V * || ≤ σ √ m. Thus the simulator solves an instance of SIS problem and we have the following theorem.

The public parameter set Y in our ASM scheme uses a matrix A ∈ Z n×m q and hash functions H 0 :

Zq,σ where H 0 , H 1 , H 2 are modeled as random oracles in the security proof. The key generation and the key aggregation are performed as in our MS scheme. All the members in a group of signers G take part in the group membership key protocol. Let PK be the set of public keys of the signers in G. Each member i ∈ G uses its secret key sk i together with the public keys of other signers in G, computes M j,i = H 2 (pkag PK , j) + sk i · H 1 (pk i , PK) · H 3 (j) for all j ∈ G and sends M j,i to all j ∈ G parallely where pkag PK = i∈G pk i · H 1 (pk i , PK) ∈ Z n×n q . After receiving M i,j from all signers j ∈ G, the i-th signer generates its group membership key mk i,PK = j∈G M i,j . Let S be a subset of G and L be the set of all public keys in S. Each signer i ∈ S using its secret key sk i together with the public keys of all the signers in G computes T i,M = sk i · H 0 (pkag PK , M) + mk i,PK and sends T i,M to the designated signer. The designated signer aggregates all the received sig-

is the aggregated subgroup public key. The verifier using the aggregated public key pkag PK and aggregated subgroup public key spkag L , outputs 1 if

The adversary is given access to the group membership key query for the challenged signer i * ∈ G. The simulator and the adversary take part in the group membership key generation protocol where the simulator simulates the group membership key for the challenged signer i * . The ranges of H 1 and H 3 have been specified with bounds to preserve the security. While simulating M j,i * for i * without knowing its secret key, the simulator chooses M j,i * such that

There is no bound on the range of H 2 and thus can be found using any linear algebra method. The adversary is also given signature oracle to query for the challenged signer i * ∈ G. The simulator models the random oracle H 0 to simulate the signature for the challenged signer i * . Finally, we apply generalized forking lemma to show that forging an accountable subgroup multisignature yields a solution to an SIS instance and proved the following theorem.

Related Work. The first construction of multisignature was presented by Itakura and Nakamura [12] . Multisignature schemes require homomorphic properties of arithmetic operations involved in standard signatures. Unfortunately, the same homomorphic properties that permits aggregation of signatures into multisignatures can enable a rogue key attack on such schemes. Infact, the multisignature schemes in early literature [10, 11, 13, 14, [18] [19] [20] were broken mostly by mounting a rogue-key-attack. In this attack, a cheating group member sets its public key as a function of the public key of an honest signer of the group enabling it to forge multisignature easily. Many solutions were proposed to prevent rogue key attack like key registration model, knowledge of secret key (KOSK) assumption, proof of possession (PoP) assumption etc. These approaches have higher complexity and are unrealistic assumptions on the public key infrastructure (PKI). The key registration model is parameterized by the key registration and the adversarial behaviour is restricted by the security game based on the successful or unsuccessful registration. In this model, the client registers with the certifying authority through the key registration protocol and the adversary can access the key registration oracle. Okamoto [19] and Micali [17] developed proper security framework for multisignature. They also built constructions for multisignatures and analyzed the security in the respective proposed models. In contrast to [19] , the security model of [17] addresses attacks in the key generation phase. To prevent rogue key attack, Micali et al. [17] allows all the signers to engage in an interactive protocol to generate public and secret keys. This scheme is not dynamic in the sense that all the signers require to be fixed at the setup phase.

The constructions in Boldyreva et al. [3] , Lu et al. [15] , on the other hand, use KOSK assumption to achieve security against rogue key attack. When the adversary provides a public key for a signer, it is required to provide a matching secret key. In KOSK setting, a user has to prove the knowledge of secret key to the certifying authority during public key registration. However, PKI has yet not realized the KOSK assumption. Bellare and Neven [2] pointed out that a scheme is secure under the KOSK assumption face the upgradation of existing PKI as it would require client and certifying authority to possess zero knowledge proof of knowledge (ZKPoK) with extraction guarantees in fully concurrent settings. The utilization of non interactive zero knowledge proof of knowledge requires heavy computation.

To avoid the KOSK assumption for preventing rogue key attack, Ristenpart and Yilek [21] modified the multisignature scheme of Boldyreva et al. [3] and proved it is secure under the PoP assumption. Unlike KOSK, the PoP setting does not ask to prove the knowledge of secret key, but it attests that a client has the access to the public and secret key pair. One of the simplest ways to achieve PoP in signature schemes is by sending the signature on the message requested by the certifying authority.

Bellare and Neven [2] had overcome the KOSK assumption and proposed a multisignature scheme in the plain public key model. In plain public key model, the users do not need to prove the knowledge or possession of their secret keys. The multisignature scheme of Micali et al. [17] is the first scheme that is secure in the plain public key model. Downfall of this scheme is that the set of the potential signers becomes static once the key setup phase is done. On the other hand, the multisignature of Bellare and Neven [2] does not require a dedicated key setup algorithm and is secure in the plain public key model. However, this scheme requires several rounds of communication between the signers.

Recently, many multisignature schemes [4] [5] [6] 16] have been proposed. The scheme by Boneh et al. [4] is the first compact multisignature scheme secure under the computational co-Diffie-Hellman problem with both signature compression and public key aggregation. Further, they have constructed the first short accountable subgroup multisignature scheme under the hardness of computational Ψ -co-Diffie-Hellman problem in the random oracle model (ROM). Drijvers et al. [6] proposed a construction for pairing based multisignature secure under a variant of the bilinear Diffie-Hellman inversion problem in the ROM. The work in Drijvers et al. [5] pointed out serious issues in the two round multisignature schemes without pairings and presented a variant of Bagherzandi et al. [1] scheme secure under the discrete logarithm assumption in the ROM. Maxwell [16] gave the first multisignature scheme secure in the palin public key model. It is based on Schnorr signature and is secure under the hardness of discrete logarithm problem. All the aforementioned schemes are secure only on the classical machine and are not quantum computer resistant. The construction of Bansarkhani et al. [7] is the only multisignature scheme that is secure under the hardness of computational problems from lattice that are not succeptiable to quantum attacks. The scheme is secure in the ROM under the ring-SIS problem. However, the scheme is interactive involving three rounds during the signature generation and does not support public key aggregation.

Drijvers et al. [6] proposed a multisignature scheme with forward secrecy to address adaptive corruption. The adversary can corrupt committee members after they have certified (signed) a message and use their signing keys to certify (sign) a different message. Forward secure multisignatures prevent this attack and enables signers to update their secret keys over time without changing their respective verification keys.

Notation. We provide below some of the notation that will be used: a ∈ Δ n means that a is a column vector of dimension n × 1 with elements from the set Δ. For a vector (1) . 

7:

for t = 1 to n do 8:

repeat 10:

r ∈ Ω such that r |i t = r|i t ;

Let r = (r, h1, h2, . . . , hi t −1, h i t , . . . , h q H ); (Note that h j = hj for j = it to qH ) 12:

Aux ← Aux ∪ aux;

if (h i t = hi t and I = ∅ and it ∈ I ) then 15: 

Syntax of Multisignature. The multisignature scheme allows a group of signers with public keys {pk i1 , pk i2 , . . . , pk i l } to issue a multisignature 'msig' on a message M in such a way that the verifier agrees that all the N signers have signed the message M . Let there be a designated signer who combines all the signatures of the signers into a single multisignature. The designated signer may be one of the signers or an external party. At high level, we define a multisignature scheme MS = {pg, kg, kag, sg, vrf} as consisting of parameter generation algorithm pg, key generation algorithm kg and key aggregation algorithm kag together with an interactive signature generation protocol sg and a deterministic verification algorithm vrf. A trusted third party, called the key generation center (KGC), generates the public parameter set Y ← MS.pg. A user generates its public-secret key pair (pk, sk)←MS.kg. The public keys are made public while the secret keys are kept secret to the users. The signer i uses secret key sk i to generate signature T i,M on a message M and sends T i,M to the "designated signer ". The designated signer aggregates all the received signatures T i,M on the message M into a multisignature msig PK,M . Here PK is the set of public key of the signers participated in this multisignature generation.

The key aggregation algorithm MS.kag can be run by anyone to aggregate the public keys in a set PK into a single public key pkag PK . The verifier using the aggregated public key pkag PK , runs the algorithm MS.vrf and returns 0, indicating the multisignature msig PK,M is not properly generated or 1, assuring that msig PK,M is correct. More concretely, we have the following.

• MS.pg(1 λ ) → Y. It is a probabilistic polynomial time (PPT) algorithm run on a security parameter λ and outputs the public parameter set Y. • MS.kg(Y, i) → (pk i , sk i ). For each user i, this PPT algorithm returns the public and secret key pair (pk i , sk i ) on input the user i and the public parameter set Y. The public key pk i is made public while the secret key sk i is kept secret to the user. • MS.kag(Y, PK) → pkag PK . Let PK be the set of public keys of signers. This is a deterministic algorithm and it aggregates the public keys in PK into a single public key pkag PK . It outputs the aggregated public key pkag PK which asymptotically has the same size as a single public key. Security Under Unforgeability. The unforgeability experiment Exp unforg F (λ) between a simulator S and a forger F is described in Fig. 1 following the model of Boneh et al. [4] that considers the infeasibility to forge multisignature with atleast one honest signer. The forger has given polynomially many access to the signature queries on any message M with any set of public keys PK. Fig. 1 where negl(λ) is a negligible function in λ.

unforg F (λ) = Pr[Exp unforg F (λ) = 1] ≤ negl(λ) for every PPT adversary F in the experiment Exp unforg F (λ) defined in

Our multisignature MS = (pg, kg, kag, sg, vrf) works as follows.

• MS.pg(1 λ ) → Y. A trusted third party, called key generation center (KGC),

generates the system parameters Y ← (n, q, m, σ, H 0 , H 1 , H 2 , A) .

-choose n of size O(λ), q of size O(n 3 ) and m ≥ 2n log q , -pick the standard deviation σ of the discrete Gaussian distribution D Λ,σ of size Ω( √ n log q log n), 1 . The simulator S generates system parameters Y and a challenge public key pk i * for user i * . The simulator S runs the forger on (Y, pk i * ).

is allowed to make signature queries to S on (M l , PK l ), 1 ≤ l ≤ qs where M l is a message and PK l is a set of public keys with pk i * ∈ PK l i.e., has access to the oracle O (Y,·,·,·) that simulates the honest signer i * with the public keys in PK l and produce a signature T i * ,M on M . 

The signer i runs this algorithm using Y to generate its own public and secret key pair (pk i , sk i ) by performing the following steps.

-choose a short matrix V i ∈ D m×m Zq,σ and compute

Zq,σ . The public key pk i is made public and the secret key sk i is kept secret to the signer i. • MS.kag(Y, PK) → pkag PK . This deterministic algorithm outputs the aggregated public key pkag PK = i∈IPK pk i · H 1 (pk i , PK) ∈ Z n×n q by extracting H 1 from Y where PK = {pk i1 , pk i2 , . . . , pk i l } and I PK = {i 1 , i 2 , . . . , i l } is the index set of PK. • MS.sg(Y, PK, SK, M) → msig PK,M . It is an interactive protocol among the signers i ∈ I PK where PK = {pk i1 , pk i2 , . . . , pk i l } is the set of public keys of the signers with 

In other words, suppose that there exists a forger F running in time t F can break the security under unforgeability of our scheme MS with non-negligible advantage F making q s signature queries and q H hash queries. Then there exists an algorithm S running in time

and P · V = 0 mod q with non negligible advantage F 8qH . Here m ≥ 2n log q , σ is of size Ω( √ n log q log n), q is of size O(n 3 ), t qH , t qs respectively denote the time taken to answer hash and signature queries and t extra is extra time taken by the algorithm S.

Proof. We assume that there exists a forger F that wins the unforgeability game played with a simulator S given in Definition 4 with probability F . 1. Given an SIS instance P ∈ Z n×m q with m ≥ 2n log q , q is of size O(n 3 ), σ is of size Ω( √ n log q log n), the simulator S sets Y = (n, q, m, σ, H 0 , H 1 , H 2 , A) by setting A = P and H 0 :

Zq,σ and H 2 :

Zq,σ for i = 1, 2, . . . , q H . The simulator S speculates a random index k ∈ {1, 2, . . . , q H }. More precisely, S guesses that F makes k-th H 2 query on a message that is used by F to output a valid forgery. It then runs F on input pk i * ∈ Z n×m q , randomness ρ and system parameters Y = (n, q, m, σ, H 0 , H 1 , H 2 , A) . 2. The forger F is allowed to make q H many hash and q s many signature queries which are simulated as follows. H 1 (x) ). If the tuple x = (pk i , PK l ), 1 ≤ l ≤ q H is already answered then S returns from the list L H1 . If it is queried for the first time, S chooses a random value from the set {C 1 , C 2 , . . . , C qH } for H 1 (pk i , PK) for pk i * ∈ PK if pk i * ∈ PK and i = i * . Otherwise, it returns random value from D m×n Zq,σ . Finally, the simulator stores ((pk i , PK), H 1 (pk i , PK)) in the list L H1 . H 0 Query. The simulator maintains a list L H0 containing elements of the form (x, H 0 (x)) where x = (M l , PK l ). If the message has already been queried then it returns from the list L H0 . Otherwise, the simulator performs the following steps to answer H 0 query on any message M l .

Zq,σ uniformly, -query H 1 (pk i * , PK l ) and H 2 (M ) to the random oracles H 1 and H 2 respectively, -find B ∈ Z m×n q (using Gauss elimination method or any linear algebra method) satisfying the equation The distribution of T i * ,M l is identical to the real protocol. Note that in the real protocol, ||T i,M l || ≤ σ 3 m √ n and as we have chosen T i * ,M l ∈ D m×n Zq,σ giving

Signature Generation Query. When F makes a signature query on a message M l , with signers PK l , 1 ≤ l ≤ q s the simulator firstly checks whether pk i * ∈ PK l . If not, it aborts. Otherwise, S checks whether (M l , H 2 (M l )) ∈ L H2 with l = k where k ∈ {1, 2, . . . , q H } is fixed at the beginning of the game. If yes, it aborts. Otherwise, S checks whether ((M l , PK l ), T i * ,M l ) ∈ L good . If yes, then return T i * ,M l . If not, then S calls H 0 query on (M l , PK l ) and return T i * ,M l .

3. With the above knowledge, the forger F outputs a forgery msig * PK,M = (T * M , pkag PK , I PK , M) on a message M . If it is a valid forgery then A · T * M = A · |I PK | · H 0 (M, PK) + i∈PK pk i · H 1 (pk i , PK) · H 2 (M ). As pk i * ∈ PK for a valid forgery, H 1 (pk i * , PK) = C t for some t, 1 ≤ t ≤ q H . The simulator S computes pkag PK = i∈IPK pk i · H 1 (pk i , PK) where pk i is the public key corresponding to the signer i ∈ I PK and H 1 (pk i , PK) are simulated as in the H 1 query for each pk i ∈ PK. Let E j = H 1 (pk j , PK) for pk j ∈ PK.

Then the algorithm S F (in S = P, ρ) outputs ({t}, {(msig PK,M , PK, pkag PK , E 1 , · · · , E |IPK| )}) where ρ = (ξ, C 1 , C 2 , . . . , C qH ).

We prove the theorem by constructing an algorithm B that, on input an SIS instance A ∈ Z n×m q and the above constructed simulator S, solves the SIS problem. Particularly, B runs the generalized forking lemma FL S on S F (in S = P, ρ) given in Sect. PK ,M , PK , E 1 , . . . , E |I PK | )}) with msig * PK,M = (T * M , pkag PK , I PK , M) and msig PK,M = (T M , pkag PK , I PK , M) are obtained from two executions of S with randomness ρ and ρ such that ρ| t = ρ | t i.e., ρ = (ξ, C 1 , C 2 , . . ., C t−1 , C t , . . ., C qH ) and ρ = (ξ, C 1 , C 2 , . . . , C t−1 , C t , . . . , C qH ) . In other words, the arguments of this query are identical (PK = PK ) but E i * = H 1 (pk i * , PK) = C t and E i * = H 1 (pk i * , PK ) = C t with E i * = E i * . Also pkag PK = i∈IPK pk i · E i and pkag PK = i∈IPK pk i · E i . Since E j = E j for all j ∈ I PK except j = i * before the forking point and therefore pkag PK − pkag PK = pk i * E i * − pk i * E i * .

B extracts T * M and T M from msig * PK,M and msig PK,M respectively, sets

The probability of success of S is the probability that (i) F succeeds to output a valid forgery with probability F and (ii) (M k , H 2 (M k )) ∈ L H2 with M k = M i.e., F has asked the k-th H 2 query on M . Here the index k is guessed at prior by S before H 2 queries are made. The algorithm S chooses the correct index with probability 1 qH . Thus the success probability of S is F qH . The running time of S is that of F plus the time taken to answer the queries and the additional computation S makes. Let t qH , t qs be the time taken to answer hash and sign queries. Let t extra be extra time taken by S. Therefore, the run time of S is t F + t qH + t qs + t extra . By the generalized forking lemma, if q > 8qH F , the running time of B is (t F + t qH + t qs + t extra ) · 8q 2 H / F · ln( 8qH F ) and the success probability of B is atleast F 8qH .

Syntax of Accountable Subgroup Multisignature. Let PK = {pk 1 , pk 2 , . . ., pk l } denotes the set of public keys of a group of signers I PK = {1, 2, . . . , l} and SK PK = {sk 1 , sk 2 , . . . , sk l } be the set of corresponding secret keys of the set PK. Let L = {pk i1 , pk i2 , . . . , pk i k } be the set of public keys of a subgroup of signers I L = {i 1 , i 2 , . . . , i k } and SK L = {sk i1 , sk i2 , . . . , sk i k } be the set of corresponding secret keys of the set L. The accountable subgroup multisignature scheme allows a subgroup I L ⊆ I PK to issue an accountable subgroup multisignature accmsig on a message M in such a way that the verifier agrees that all the k signers in I L have signed the message M . Let there be a designated signer who combines all the signatures of signers into a single accountable subgroup multisignature. The designated signer may be one of the signers or an external party. An accountable subgroup multisignature scheme ASM = {pg, kg, kag, gmk, sg, vrf} consists of parameter generation algorithm pg, key generation algorithm kg and key aggregation algorithm kag together with an interactive group membership key protocol gmk, signature generation protocol sg and a deterministic verification algorithm vrf. A trusted third party, called the key generation center (KGC), generates the public parameter set Y ← AMS.pg. A user generates its public-secret key pair (pk, sk)←ASM.kg. The public keys are made public while the secret keys are kept secret to the users. All signer i ∈ I PK with its own secret key sk i execute the protocol ASM.gmk among themselves and generates a group membership key mk i,PK i ∈ I PK . In signature generation protocol ASM.sg, each signer i ∈ I L ⊆ I PK uses its secret key sk i and group membership key mk i,PK to generate signature T i,M on a message M and sends T i,M to the designated signer. The designated signer aggregates all the received signatures T i,M for i ∈ I L on the message M into an accountable subgroup multisignature accmsig PK,L,M . The key aggregation algorithm ASM.kag can be run by anyone to aggregate the public keys in a set PK into a single public key pkag PK . The verifier runs the algorithm ASM.vrf and returns 0, if the multisignature accmsig PK,L,M is not properly generated or 1 if accmsig PK,L,M is correct. More concretely, description of these algorithms are given below.

• ASM.pg(1 λ ) → Y. It is a PPT algorithm run by a KGC on a security parameter λ to generate the public parameter set Y. • ASM.kg(Y, i) → (pk i , sk i ). Each user i runs this algorithm with input the public parameter set Y to generate the public and secret key pair (pk i , sk i ). The secret key sk i is kept secret to the user i while the public key pk i is made publicly available. • ASM.kag(Y, PK) → pkag PK . This is a deterministic algorithm and it aggregates the public keys in PK into a single public key pkag PK . It outputs the aggregated public key pkag PK which asymptotically has the same size as a single public key. • ASM.gmk(Y, PK, SK PK ) → mk i,PK . With input the public parameter set Y, the set of public keys PK of the signers, the set of secret keys SK PK of the signers in I PK , this interactive protocol runs among all signers in I PK and generates group membership key mk i,PK for each i ∈ I PK . • ASM.vrf(Y, accmsig PK,L,M ) → (0 or 1). On input the public parameter set Y and an accountable subgroup multisignature accmsig PK,L,M , this deterministic algorithm returns 1 if the accountable subgroup multisignature accmsig PK,L,M is valid. Otherwise, it returns 0.

1. The simulator S generates system parameters Y and a challenge public key pk i * . The simulator S runs the forger on (Y, pk i * ). 2a. The forger is allowed to make group membership key queries on a set of public keys PK l , 1 ≤ l ≤ qm where PK l is a set of public keys with pk i * ∈ PK l i.e., has access to the oracle O (Y,PK l ,·) in which S plays the role of the honest signer i * . The simulator stores the resulting membership key mk i * ,PK l but does not return it to . 2b. The forger is allowed to make signature queries on (M l , PK l ) where M l is a message and PK l is a set of public keys with pk i * ∈ PK l , 1 ≤ l ≤ qs. That is, has access to the oracle O (Y,·,PK l ,·,·,M l ) . The simulator plays the role of the honest signer i * and produce a signature T i * ,M l on M l . 3. Finally, outputs a forgery accmsig * PK,L,M on a message M for L ⊆ PK where PK is a set of public keys of a group of signers. Completeness. An accountable subgroup multisignature scheme should satisfy completeness. That is, for any Y ← ASM.pg(1 λ ), (pk i , sk i ) ← ASM.kg(Y, i) with i ∈ I PK where I PK is the index set for the set of public keys PK, SK PK is the corresponding set of secret keys, any message M , any subset L ⊂ PK with the set of secret keys SK L , group membership keys G L = {mk i,PK |i ∈ I L ⊆ I PK } where mk i,PK ← ASM.gmk(Y, PK, SK PK ), if accmsig PK,L,M ← ASM.sg(Y, L, PK, SK L , G L , M) then ASM.vrf(Y, accmsig PK,L,M ) outputs 1.

We consider the infeasibility to forge accountable subgroup multisignature with atleast one honest signer following the security model of Boneh et al. [4] . The forger has given access to q g many group membership key queries along with q s many signature queries on any message with any set of public keys PK and any subgroup of signers I L ⊆ I PK . The unforgeability game Exp unf F (λ) between a forger F and a simulator L is described in Fig. 2 Fig. 2 where negl(λ) is a negligible function in λ.

We describe our accountable subgroup multisignature ASM = {pg, kg, kag, gmk, sg, vrf} below.

The key generation center (KGC) generates the system parameters Y ← (n, q, m, σ, H 0 , H 1 , H 2 , H 3 , A) 

The signer i generates its own public and secret key pair (pk i , sk i ) same as in the algorithm MS.kg(Y, i) of Sect. 3. The secret key sk i = V i ∈ D m×m Zq,σ is kept secret to the signer i and the public key

• ASM.kag(Y, PK) → pkag PK . This deterministic algorithm outputs the aggregated public key pkag PK = i∈IPK pk i · H 1 (pk i , PK) ∈ Z n×n q .

• ASM.gmk(Y, PK, SK PK ) → mk i,PK . It is a single round protocol between the signers in I PK where PK = {pk i1 , pk i2 , . . . , pk i l } is a set of public keys with pk i = Y i and SK PK = {sk i1 , sk i2 , . . . , sk i l } is the collection of corresponding secret keys with sk i = V i . All signers i ∈ I PK utilize the public parameter set Y = (n, q, m, σ, H 0 , H 1 , H 2 , H 3 , A) and parallely execute the following.

-generate pkag PK ← ASM.kag(Y, PK) where pkag PK = i∈IPK pk i · H 1 (pk i , PK), -compute M j,i = H 2 (pkag PK , j) + sk i · H 1 (pk i , PK) · H 3 (j) for all j ∈ I PK , -send M j,i to signer j with ||M j,i || ≤ ||H 2 (pkag PK , j)|| + σ 3 m √ n. -On receiving M i,j \ {i} from all signers j ∈ I PK , the i-th signer verifies ||M i,j || ≤ ||H 2 (pkag PK , i)|| + σ 3 m √ n. If the verification fails, it returns ⊥. Otherwise, it computes the group membership key mk i,PK = j∈IPK M i,j = j∈IPK H 2 (pkag PK , i) + sk j · H 1 (pk j , PK) · H 3 (i)

• ASM.sg(Y, L, PK, SK L , G L , M) → accmsig PK,L,M . It is a one round protocol run between the members of the set I L where L ⊆ PK = {pk i1 , pk i2 , . . . , pk i l } is the set of public keys of the signers in I L with pk i = Y i . The set SK L is the collection of corresponding secret keys of the signers in I L with sk i = V i . Each signer i ∈ I L performs the following steps by extracting (n, q, m, σ, H 0 , H 1 , H 2 , H 3 , A) from Y.

-generate pkag PK ← ASM.kag(Y, PK) where pkag PK = i∈IPK pk i · H 1 (pk i , PK), -compute T i,M = sk i · H 0 (pkag PK , M) + mk i,PK with ||T i,M || ≤ σ √ m · H 0 (pkag PK , M ) + |I PK | · ||H 2 (pkag PK , i)|| + |I PK | · σ 3 m √ n,

-send T i,M to the designated signer.

Note that ||T i,M || ≤ σ √ m · H 0 (pkag PK , M)+|I PK |·||H 2 (pkag PK , i)|| + |I PK |· σ 3 m √ n. The designated signer verifies whether ||T i,M || ≤ σ √ m · H 0 (pkag PK , M) + |I PK | · ||H 2 (pkag PK , i)|| + |I PK | · σ 3 m √ n. If not, it aborts and returns ⊥. Otherwise, the designated signer combines all the signatures T i,M , i ∈ I L to produce T M = i∈IL T i,M with ||T M || ≤ |I L | · σ √ m · H 0 (pkag PK , M) + |I PK | · max i∈IL ||H 2 (pkag PK , i)|| + |I L | · |I PK | · σ 3 m √ n. The designated combiner also aggregates the public keys in L and generates aggregated subgroup public key spkag L = i∈IL pk i . It finally returns the accountable subgroup multisignature accmsig PK,L,M = (T M , spkag L , pkag PK , I PK , I L , M). • ASM.vrf(Y, accmsig PK,L,M ) → (0 or 1). On receiving an accountable subgroup multisignature accmsig PK,L,M = (T M , spkag L , pkag PK , I PK , I L , M), a verifier runs this deterministic algorithm using the public parameter set Y and returns 1 if -A·T M = spkag L ·H 0 (pkag PK , M) + |I PK |· i∈IL A·H 2 (pkag PK , i) + pkag PK · i∈IL H 3 (i) where spkag L = i∈IL pk i and pkag PK = i∈IPK pk i · H 1 (pk i , PK)

-||T M || ≤ |I L | · σ √ m · H 0 (pkag PK , M) + |I PK | · max i∈IL ||H 2 (pkag PK , i)|| + |I L | · |I PK | · σ 3 m √ n. Otherwise, the verifier returns 0.

The proof of the following theorem is immediate from the construction.

Theorem 5. The scheme ASM described above is complete.

The scheme ASM is unforgeable in the random oracle model if the SIS problem is hard.

Proof (Sketch). We assume that there exists a forger F that wins the unforgeability game played with a simulator S given in Definition 5 with probability F .

1. This step is similar to the step 1 of the Theorem 4 in Sect. 3.1. 2. We give the hints of the simulation of H 0 , H 1 and group membership key queries. The H 1 -query on x = (pk i , PK) is simulated from the already chosen random values {C 1 , C 2 , . . . , C qH }. for pk i ∈ PK if i = i * . Otherwise a random value is returned. Let bad 1 be the event that a query to random oracles H 0 or H 2 is made involving pkag PK before making H 1 query on (pk i , PK) for some pk i . The simulator S aborts when the event bad 1 occurs as it cannot simulate the queries without knowing the public keys used to form pkag PK . The group membership key query on PK is simulated only if pk i * ∈ PK by finding B ∈ Z n×n q satisfying A · M i,i * = A · B + pk i * · H 1 (pk i * , PK) · H 3 (i) and sets H 2 (pkag PK , i) = B. Here M i,i * ∈ Z m×n q is randomly chosen such that ||M i,i * || ≤ σ √ m. Let bad 2 be the event that a query to random oracle H 0 is made involving pkag PK before making group membership key query on PK. The simulator S aborts when the event bad 2 occurs as it cannot simulate the H 0 query without knowing mk i * ,PK . Also, H 0 -query on x = (pkag PK , M) is simulated by finding B ∈ Z n×n q satisfying A · M i,i * = A · B + Y i * · H 1 (pk i * , PK) · H 3 (i) and sets H 2 (pkag PK , i) = B where T i * ,M ∈ Z m×n q is randomly chosen such that ||T i * ,M || ≤ σ √ m. 3. With the view of all the allowed queries, F outputs a valid forgery. 4. The simulator S applies the generalized forking lemma (on H 1 query) and solves the SIS instance as we have done in the Theorem 4 in Sect. 3.1.

The complete proof will be provided in the full version of the paper.

Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma

Multi-signatures in the plain public-key model and a general forking lemma

Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme

Compact multi-signatures for smaller blockchains

On the security of two-round multi-signatures

Pixel: multi-signatures for consensus

An efficient lattice-based multisignature scheme with applications to bitcoins

Practical lattice-based cryptography: a signature scheme for embedded systems

Software speed records for lattice-based signatures

Group-oriented (t, n) threshold digital signature scheme and digital multisignature

Meta-multisignature schemes based on the discrete logarithm problem. Information Security -The Next Decade. IAICT

A public-key cryptosystem suitable for digital multisignatures

Weaknesses in some threshold cryptosystems

Threshold-multisignature schemes where suspected forgery implies traceability of adversarial shareholders

Sequential aggregate signatures, multisignatures, and verifiably encrypted signatures without random oracles

Simple Schnorr multi-signatures with applications to bitcoin

Accountable-subgroup multisignatures

On the risk of disruption in several multiparty signature schemes

A digital multisignature scheme based on the Fiat-Shamir scheme

Multi-signature schemes secure against active insider attacks

The power of proofs-of-possession: securing multiparty signatures against rogue-key attacks