meta.title

Splitting and Aggregating Signatures in Cryptocurrency Protocols S. Sharmila Deva Selvi1 , Arinjita Paul1 , C. Pandu Rangan1 , Siva Dirisala2 , and Saswata Basu2 1 Department of Computer Science and Engineering, IIT Madras, India Email: {sharmila,arinjita,prangan}@cse.iitm.ac.in 2 0chain LLC, San Jose, USA Email: {siva,saswata}@0chain.net A BSTRACT The blockchain technology and a vast amount of cryptocurrency related activities have generated an unprecedented level of interest among the public. However, even at the entry level, cryptocurrency users need to deal with the complex task of key management. In this paper, we propose a simple way to manage a user's private key, under a reasonable assumption that the user has two devices at his disposal (say a laptop and a mobile phone). We refer to our strategy as key splitting. Since these cryptographic keys are used for generating digital signatures, we should take a closer look at the signature schemes that would perform best under key splitting. At the operational level, scalability is one of the main challenges faced by the users and developers. While there are fundamental issues like consensus that challenge scalability, we focus on the computational efficiency in a block formation. Aggregation of signatures is one of the effective solutions to this problem. To this end, we observe that none of the existing signature schemes work well for BOTH key splitting and aggregation. The current popular schemes such as the ones used in Bitcoin or Schnorr's scheme implemented over Elliptic curves are neither suitable for aggregation nor can their keys be split in a convenient and meaningful way. A detailed theoretical and empirical analysis shows that the BLS short signature scheme is best suited for achieving both key splitting and aggregation. Index Terms—Blockchain, key management, wallet, signature, scalability. I. I NTRODUCTION The real-world as well as the academic studies on cryptocurrencies and the block chain technology are among the most significant and trendy developments of Information Technology. Block-chain technology is witnessing an exponential growth in interest and technical advancement at this point of time. While these areas are witnessing an unprecedented growth and attention, their deployments face major hurdles at several fronts. One of the major concerns related to this technology is scalability and in general efficiency/reliability of the whole operation. For instance, every user in this community, sooner or later, directly or indirectly, is forced to deal with challenges of maintaining and managing the cryptographic keys that are used. The subtleties and challenges involved in key generation, maintenance and management are well known in security industry and both cryptographic and policy based solutions have been devised in the past. However, in the context of cryptocurrencies, we still do not have satisfactory solutions that would help scalability or ease of use. The second major concern is related to computational efficiency of the tasks performed during the execution of the protocols. One of the most computationally intense and most frequently used cryptographic primitives in blockchain technology is digital signatures. The users need to generate every transaction with appropriate authentication done on the transaction and the minors or validators need to verify/validate the same multiple number of times. In this paper, we focus on the signing process at the users end and verification process at the block formation/validation end. In order to handle the challenges and complexities of key management, a number of techniques were proposed and deployed in different cryptocurrencies. In Bitcoin core, the keys are maintained in local storage. A typical user will have an access to a wallet software of his choice and use the same to authenticate transactions he is generating. As wallets generate the digital signature, it requires an access to the private key of the user. While this speeds up the wallet operations, the presence of a key for a long time in a system that is online increases its vulnerability. Off-line storage and air gapped storages are used by systems such as Armory [1]. Password protected wallets are deployed by certain systems but they do not provide any security against a malware that might read the key strokes etc. Third party hosted wallets are also suggested to remove the pains of key management to a novice user but then it requires enormous amount of trust in a third party. A detailed analysis on various techniques that are currently used in practice together with limitations in their usability is reported in [7]. In view of the shortcomings of the existing systems, we take a fresh look at key generation and management using two systems that may be available with a typical user. Our proposal is simple, easy to implement, secure and offers protections against theft/loss of the systems. Given that a typical user may have at his disposal several devices(atleast two, say a laptop "BLS Keys Private Key: x ∈ Z∗q Public key: X = xP σ = xH(m) and a mobile phone/notepad), is it possible to handle key management with relative ease? Specifically, we are interested in “splitting the private key” into several components and store each in a device so that: Device 1 Device 2 Accept mnemonic1 x1 = H1 (mnemonic1 ) x2 = x − x1 Store x1 and x2 P Send x2 to device 2 1) We have adequate protection even in the case of loss/corruption of a component of a key. 2) Even in the case of loss/theft of the device and subsequent abuse of the key component available in the device. 3) Signature generation must involve all the split components. 4) The individual components of the signatures generated in each device is secure on its own and does not lead to any attacks and key exposure. Accept P asscode s1 = x2 − H1 (P asscode) Store s1 TABLE I: Our Key-Split algorithm Device 2 Accept Passcode x2 = s1 + H1 (P asscode) σ2 = x2 H(m) Send σ2 to device 1 Device 1 ? Check if ê(σ2 , P ) = ê(H(m), x2 P ) σ = x1 H(m) + σ2 = x1 H(m) + x2 H(m) = xH(m) Output σ as the signature for m We note that the (BLS) short signature scheme of Boneh, Lynn and Shacham [6] is quite amenable for such split-ups and we describe a way in which an effective split-up be achieved. Also, such split-up is not possible in Schnorr signature [12] or Elliptic Curve Digital Signature Algorithm (ECDSA) [9] without sharing information between the two devices that generate the partial signatures. The transaction generation as well as the block formation/validation involve running computationally intense signing and verification algorithms. Typically, the block size is kept small by design in order to speed up the communication and in small blocks, it is observed that signatures occupy a significant amount of space. For example, it is estimated that nearly 40% of the transcript space is occupied by signatures in case of bitcoin [14]. The computations involved in some of the deployed signature schemes are found to be very complex. For instance, the most widely used ECDSA combines the long term and short term keys in a non linear fashion and that directly contributes to its inefficiency [14]. Moreover, each block formation calls for verification of a number of signatures (the signatures found in the transactions chosen for pooling) and when the block is broadcast, again the validation process calls for huge number of signature verifications at every node of the network. In this context, aggregate verification offers an efficient solution. In signature aggregation/verification, we combine several signatures into one “super” signature and carry out the verification only on the super signature rather than on the individual signature. Thus we see a dramatic drop in the verification cost of n signatures to the cost of verifying one signature. This clearly saves space and a significant amount of computing time. While the aggregation is a neat idea leading to efficiency, it is unfortunate that not all signature schemes are suitable for aggregation. For some schemes, aggregation may not reduce the cost at all and the verification cost may remain the same without any reductions. The Schnorr or the ECDSA signature does not offer any natural way to aggregate due to the independent randomness deployed in different signatures on different messages. In fact, it is shown that any attempt to aggregate may even lead to serious attack as shown in [14]. In view of this fact, fresh attempts are made to create aggregatable signatures and the TABLE II: Signing Workflow Gamma Γ- signature scheme in [14] is the most recent one. However, the keys of this scheme cannot be split in any convenient way. Moreover, empirical analysis shown in Table IV shows that BLS signature is far more efficient than the Γ-signature scheme. Thus we show that BLS scheme can be tinkered to accommodate key splitting at the users end and can be aggregated for verification at the block generation end. We have presented the details of signature scheme based on key splitting and aggregate verification. We have also carried out performance analysis and compared the running times of our approach with that of the Schnorr, ECDSA and Γ-signature schemes. II. D EFINITION In this section, we describe the syntactical definition of a signature scheme that provides key split-up and aggregation. A. Signature Scheme with Key Split-up A signature scheme with key split-up consists of the following algorithms: • Setup(λ): On input of a security parameter λ, this algorithm generates the public parameters P arams. • KeyGen(P arams): On input of the public parameters P arams, this algorithm generates a public-private key pair (P K, SK) for a user. • Key-split(SK, P arams): On input of a private key SK and public parameters P arams, this algorithm generates two partial private keys SK1 and SK2 for device 1 and device 2 respectively. This algorithm is run by the user. • Sign-1(m, SK1 , P arams): On input of a message m and the partial private key SK1 , this algorithm outputs the partial signature σ1 . This algorithm is run on device 1. • Sign-2(m, SK2 , P arams): On input of a message m and the partial private key SK2 , this algorithm outputs the partial signature σ2 . This algorithm is run on device 2. • Sign-Combine(σ1 , σ2 , P arams): On input of the partial signatures σ1 and σ2 and the public parameters P arams, 2 "• F with a single public key P KT and gives F the power to select all public keys except the challenger public key P KT . An aggregate signature scheme with key split-up is secure against existential forgery under the adaptive chosen message attack, if no probabilistic polynomial time algorithm F has a non-negligible advantage in the following game: • Setup Phase: The challenger C generates the public parameters and sends it to the aggregated forger F. The challenger C also provides the forger F with a public key P KT and access to one of the partial private key corresponding to SKT of F 0 s choice. • Training Phase: The forger F adaptively queries for signatures and partial signatures on public key P KT with various messages of his choice. • Forgery Phase: Finally, F outputs n = k + 1 additional public keys P K1 , P K2 , · · · , P Kn−1 , P KT , messages m1 , m2 , · · · mn−1 , mT and an aggregated signature δ signed under public keys P K1 , P K2 , · · · , P Kk , P KT on the messages m1 , m2 , · · · mk , mT respectively. Here it should be noted that F has generated all the public keys P K1 , P K2 , · · · , P Kk except P KT and the challenger C does not know the private key corresponding to P K1 , P K2 , · · · , P Kk . The forger F wins the game if the aggregate signature δ is a valid aggregate of the signatures on the messages m1 , m2 , · · · mk , mT signed under public keys P K1 , P K2 , · · · , P Kk , P KT respectively, such that the signature on message mT under P KT (i.e. both Sign-1(mT , P KT ) and Sign-2(mT , P KT )) has not been queried upon by F. this algorithm combines the signatures and outputs a compressed short signature σ. This algorithm is run on device 1. Verify(m, σ, P K, P arams): On input of an aggregated signature σ, a public key P K and the public parameters, the algorithm returns “VALID” if σ is a valid signature on message m and public key P K. Else, it will output “INVALID”. B. Aggregate Signature Scheme with Key Split-up An aggregate signature scheme with key split-up consists of the following algorithms along with the Setup(), KeyGen(), Key-Split(), Sign-1(), Sign-2(), Verify() algorithms shown in Section II-A to enable signature aggregation. • Aggregate-Sign(Σ={(mi , σi , P Ki )}i=1 to n , P arams): On input of message mi , public key P Ki and signature σi of n different users and the public parameters P arams, this algorithm generates and outputs the aggregate signature δ. This algorithm can be run by any user who possess Σ. • Aggregate-Verify(δ, {mi , P Ki }i=1 to n , P arams): On input of an aggregate signature δ, the message, public key pair (mi , P Ki ) of n different users and the public parameters P arams, the algorithm returns “VALID” if δ is a valid aggregate signature on message-key pairs {mi , P Ki }i=1 to n . Else, it will output “INVALID”. III. S ECURITY M ODEL A. Security Model for Signature with Key Split-up The security model for signature schemes with key splitup is same as that of the traditional signature schemes, by replacing the sign oracle modified into Sign-1 and Sign-2. The challenger C provides the forger F with a public key P KT . The forger F can ask one of the partial private keys corresponding to P KT of its choice. A signature scheme with key split-up is secure against existential forgery under the adaptive chosen message attack, if no probabilistic polynomial time algorithm F has a non-negligible advantage in the following game: • Setup Phase: The challenger C generates the public parameters and sends it to the forger F. The challenger C also provides the forger F with a public key P KT . F now decides to request one part of the private key of its choice. • Training Phase: The forger F adaptively queries partial signatures on public key P KT with various messages of his choice. • Forgery Phase: Finally, F produces a valid message, signature pair (mT , σT ) signed under public key P KT on a message mT . Definition 1. An aggregate forger F(t, qH , qs , ) breaks an aggregate signature scheme with key split-up if F runs in time atmost t, making qH hash queries, qS signing queries and his advantage AdvAggSigA is atleast . An aggregate signature scheme with key split-up is (t, qH , qs , )−secure against existential forgery in the aggregate chosen key model if no (t, qH , qs , ) forger breaks it. IV. S HORT S IGNATURE USING B ILINEAR PAIRING The Boneh-Lynn-Shacham(BLS) signature scheme [6] is a signature scheme based on bilinear pairing of an elliptic curve group. Signatures produced by the BLS signature scheme are short signatures. The signature scheme is provably secure (the scheme is existentially unforgeable under adaptive chosenmessage attacks) assuming both the existence of random oracles and the intractability of the computational DiffieHellman problem in a gap Diffie-Hellman group. The BLS signature scheme consists of the algorithms, Setup(), KeyGen(), Sign() and Verify(). BLS Scheme: • B. Security Model for Aggregate Signature with Key Split-up Our game based definition of the security of aggregate signature schemes with key split is an adaption of the aggregate chosen-key security model by Boneh et al. [5]. In this model, the challenger C provides the aggregated forger 3 Setup(κ) :On input of the security parameter κ this algorithm will perform the following, – Choose a large prime q. – Choose two cyclic groups G and GT of order q, where G is additive group and GT is a multiplicative group. "• • • – Choose the generator P ∈ G. – Define the bilinear pairing ê : G × G → GT . – Define cryptographic hash function H : {0, 1}lm → G, where lm is the size of the message. – Output the system parameters P arams = hq, P, H, êi. KeyGen(P arams)This protocol is run by the user. This will output the public and private key of the user. – Choose x ∈ Zq ∗ . – Set X = xP ∈ G. – Output public key P K = hXi and private key SK = hxi. Sign(m, SK, P arams): This protocol is run by user in the mobile. On input of message m and private key x, this will output the signature σ computed as shown below: – Compute σ= xH(m, P K) ∈ G. – Output σ. Verify(m, σ, P K, P arams): This protocol can be run by any user who possess the message m, signature σ on message m and public key P K, this algorithm will perform the following: – Compute H = H(m, P K) ∈ G. ? – If ê(H, X) = ê(σ, P ) then output VALID, else output INVALID. • • • • A. BLS Scheme with key split-up for secure wallet: • • • Setup(κ) :On input of the security parameter κ this algorithm will perform the following. – Choose a large prime q. – Choose two cyclic groups G and GT of order q, where G is additive group and GT is a multiplicative group. – Choose the generator P ∈ G. – Define the bilinear pairing ê : G × G → GT – Define cryptographic hash function H : {0, 1}lm × G → G, where lm is the size of the message. – Output the system parameters P arams = hq, P, H, êi. KeyGen(P arams)This protocol is run by the user. This will output the public and private key of the user. – Choose x ∈ Zq ∗ . – Set X = xP ∈ G. – Output public key P K = hXi and private key SK = hxi. Key-Split(SK, P arams): This protocol is run by the user. On input of private key x, this algorithm will output the two private keys SK1 and SK2 corresponding to private key SK. – Choose x1 ∈ Zq ∗ – Set x2 = (x − x1 ) ∈ Zq ∗ – Output private key pair SK2 = x2 and private key SK1 = x1 . Here SK1 is the private key corresponding to device 1 and SK2 is the private key for device 2. Sign-1(m, SK1 , P arams): This protocol is run by user in the device 1. On input of message m and private key x1 , this will output the signature σ1 computed as below: – Compute σ1 = x1 H(m, P K) ∈ G. – Output σ1 . Sign-2(m, SK2 , P arams): This protocol is run by user in the device 2. On input of message m and private key x2 , this algorithm will output the signature σ2 computed as below: – Compute σ2 = x2 H(m, P K) ∈ G. – Output σ2 . Sign-Combine(σ1 , σ2 , P arams): This protocol is run by user on device 1 with the partial signature σ1 of device 1, partial signature σ2 from device 2 and public parameters Params as inputs and outputs the signature σ on message m by the private key SK corresponding to the public key P K. – Output σ = σ1 + σ2 = x1 H(m, P K) + x2 H(m, P K) = xH(m, P K). Verify(m, σ, P K, P arams): This protocol can be run by any user who possess the message m, a signature σ of the message m and the public key P K. This algorithm will perform the verification as following: – Compute H = H(m, P K) ∈ G. ? – If ê(H, X) = ê(σ, P ) then output VALID, else output INVALID. B. BLS Scheme with key split-up and aggregation The aggregation mechanism is helpful during the verification of n signatures generated by n different users on n different messages m1 , m2 , · · · , mn . The algorithms Setup(), KeyGen(), Key-Split(), Sign-1(), Sign-2(), Verify() are same as that of the scheme given in Section IV-A. It has two more algorithms for generating aggregate signatures and verification of aggregate signatures, i.e., Aggregate-Sign() and Aggregate-Verify() respectively. The description of both the algorithms is given below: • Aggregate-Sign(Σ={(mi , σi , P Ki )}i=1 to n , P arams): This protocol is run by an user who has all the signatures in Σ as input and outputs the aggregate signature δ on message mi by the private key SKi corresponding to the public key P Ki , for i = 1 to n. – If Verify(mi , σi , P Ki , P arams) is VALID for all signatures σi in Σ then output: n P δ= σi . i=1 • 4 – Else, Output ⊥. Aggregate-Verify( δ, {mi , P Ki }i=1 to n , P arams): This protocol can be run by any user who possess the messages mi , public keys P Ki , and an aggregate signature δ. This algorithm will perform the signature verification as follows: – For (i = 1 to n), compute Hi = H(mi , P Ki ) ∈ G. "– If n Q ? ê(Hi , Xi ) = ê(δ, P ) then output VALID, else i=1 output INVALID. V. S ECURITY P ROOF A. Security Proof of our Signature Scheme with Key Split-up In this section we formally prove the security of the signature scheme with key split-up against existential forgery under adaptive chosen-message attack in the random oracle model. We formally show that our scheme is secure and its security follows from the Computational Diffie-Hellman (CDH) assumption in (G, GT ). Definition 2. Computational Diffie-Hellman (CDH) assumption: The Computational Diffie-Hellman (CDH) assumption in G is, given a tuple of elements (P, aP, bP ) ∈ G, where a,b ∈R Z∗q , there exists no polynomial time adversary which can compute abP in G, with a non-negligible advantage. Theorem 1. Let (G, GT ) be a (t0 , 0 )-CDH group of order p. Then our signature scheme is (t, qs1 , qs2 , qH1 , )-secure against existential forgery under the adaptive chosen-message attack in the random oracle model, for all t and that satisfies, , and 0 ≥ e(1 + qs2 ) t0 ≤ t + (qH1 + qs1 + qs2 + O(1)) Proof. Suppose F is a forger algorithm that (t, qs1 , qs2 , qH1 , )-breaks our signature scheme on (G, GT ) in time t. Then, we show how to construct a t0 -time algorithm C that solves the CDH problem on (G, GT ) with probability atleast 0 . The existence of such polynomial time solver for CDH problem is not possible, hence the existence of polynomial time attacker for the signature scheme is also not possible Let P be the generator of G. Algorithm C is provided with the challenge instance (P, aP, bP ) ∈ G whose goal is to generate abP ∈ G. Forger F interacts with the challenger C and the challenger will answer all the queries asked by the Forger in the following way : • Setup Phase : Challenger C starts by giving F the common reference string (P, G, GT ) and the public key P KT = hXT = (s1 + s2 a)P )i, where s1 , s2 is chosen at random from Z∗q . The corresponding private key xT = s1 + s2 a, which is not known to the challenger. Now, F will request C the partial key SK1 or SK2 which F wishes to compromise . If he decides to get access to partial private key SK1 then x1 = s1 and x2 = as2 . If F decides to get access to partial private key SK2 then x1 = as2 and x2 = s1 . Note that C does not know the value of either x1 or x2 . For simplicity we assume that F decides to compromise partial private key x1 . • Training Phase : During this phase, F is given access to the following oracles provided by the challenger C: – H query: C handles the hash queries of the forger F by maintaining a list LH consisting of tuples defined as hm, P K, c, h, Hm i. Initially the list is empty and • is updated as explained below. When F queries the oracle H with a message m ∈ {0, 1}lm and public key P K as input, C responds in the following way: ∗ If a tuple hm, P K, c, h, Hm i already exists in the LH list, then C responds with H(m, P K) = Hm ∈ G. ∗ Otherwise, C picks a random h ∈ Z∗q and flips a coin c ∈ {0, 1} such that P r[c = 0] = γ (defined later) and sets Hm = hbP if c = 1. Else, it sets Hm = hP . Also, C stores the tuple hm, P K, c, h, Hm i in LH list and output Hm . – Sign-1 query: When a signature query is generated for device 1, C does the following: 1) C queries H(m, P K) to obtain Hm . 2) C computes σ1 = x1 Hm . 3) C sends σ1 as the signature to A. – Sign-2 query: When a signature query is generated for device 2, C does the following: 1) C checks whether (m, P K) is already present LH list. If (m, P K) belongs to LH list, then: ∗ C retrieves the tuple hm, P K, c, h, Hm i from LH list. ∗ If c = 0, sets σ2 = s2 haP =as2 Hm =x2 Hm . ∗ Else, Aborts. 2) If (m, P K) does not belong to LH list, then: ∗ C picks a random h ∈ Zq ∗ ∗ C sets Hm = hP and c = 0. ∗ Also, C stores hm, P K, c, h, Hm i in LH list. ∗ C computes σ2 = s2 haP =(as2 )hP =as2 Hm =x2 Hm . 3) C sends σ2 as the signature to F. Forgery Phase : On getting sufficient training, algorithm F produces a message-signature pair (m∗ , σ ∗ ) such that σ ∗ is not obtained by querying the signing oracle for a message m∗ and σ ∗ is valid. Now, C computes the solution to the hard problem as shown below. – C checks LH for a tuple hm∗ , P K, c, h, Hm∗ i . – C computes T = (hs2 )−1 (σ ∗ − hs1 P ). This correctly generates the solution to the hard problem T = abP as below. T = (hs2 )−1 (σ ∗ − hs1 P ) = (hs2 )−1 (x(hP ) − hs1 P ) = (hs2 )−1 ((s1 + s2 a)hP − hs1 P ) = (hs2 )−1 (s1 hP + s2 abhP − hs1 P ) = (hs2 )−1 (s2 abhP ) = abP = LHS. • 5 Thus, no forgery is possible by F in polynomial time with a non-negligible advantage. Probability Analysis: We calculate the probability with which C aborts during the simulation. Let Abort denote "the event that C aborts during the game and qs2 denote the number of queries made to the Sign-2 oracle. We note that C does not abort in the following events: − E1 : c = 0 in a Sign-2 query of Training phase. − E1 : c∗ = 1 in the Forgery phase. We have P r[¬Abort] ≥ γ qs2 (1 − γ), which has a q s2 . Using γOP T , we maximum value at γOP T = 1+q s2 obtain: 1 P r[¬Abort] ≥ e(1+q , s2 ) where, e is the base of the natural logarithm. Note that the simulation of the random oracles is perfect. Therefore, C solves the CDH problem in (G, GT ) with probability: . 0 ≥ e(1 + qs2 ) to generate abP ∈ G. Forger F interacts with the challenger C and the challenger will answer all the queries asked by the Forger in the following way : • Setup Phase:This phase is similar to the Setup Phase in V-A. • Training Phase : During this phase, F is given access to the following oracles provided by the challenger C: – H query: C handles the hash queries of the forger F by maintaining a list LH consisting of tuples defined as hm, P K, c, h, Hm i. Initially the list is empty and is updated as explained below. When F queries the oracle H with a message m ∈ {0, 1}lm and public key P K as input, C responds in the following way: ∗ If (P K 6= P KT ): · If a tuple hm, P K, c, h, Hm i already exists in the LH list, then C responds with H(m, P K) = Hm ∈ G. · C picks a random h ∈ Z∗q sets Hm = hP , Also, C stores the tuple hm, P K, −, h, Hm i in LH list and output Hm . ∗ If (P K = P KT ): · If a tuple hm, P K, c, h, Hm i already exists in the LH list, then C responds with H(m, P K) = Hm ∈ G. · Otherwise, C picks a random h ∈ Z∗q and flips a coin c ∈ {0, 1} such that P r[c = 0] = γ (defined later) and sets Hm = hbP if c = 1, Else, it sets Hm = hP . Also, C stores the tuple hm, P K, c, h, Hm i in LH list and outputs Hm . – Sign-1 query: When a Sign-1 is requested by F, C does the following: 1) C queries H(m, P K) to obtain Hm . 2) C computes σ1 = x1 Hm . 3) C sends σ1 as the signature to A. – Sign-2 query: When a Sign-2 is requested by F, the challenger C does the following: 1) C checks whether (m, P K) is already present LH list. If (m, P K) belongs to LH list, then ∗ C retrieves the tuple hm, P K, c, h, Hm i from LH list. ∗ If c = 0, sets σ2 = s2 haP =as2 Hm =x2 Hm . ∗ Else aborts. 2) If (m, P K) does not belong to LH list, then ∗ C picks a random h ∈ Zq ∗ ∗ C sets Hm = hP and c = 0. ∗ Also, C stores hm, P K, c, h, Hm i in LH list. ∗ C computes σ2 = s2 haP =(as2 )hP =as2 Hm =x2 Hm . 3) C sends σ2 as the signature to F. • Forgery Phase: On getting sufficient training, algorithm F produces a n message-public pair {(mi , P Ki ), (mT , P KT )}i=1 to k , where (n=k+1) and a valid aggregate signature δ such that mT , P KT is not queried to Note that C solves the hard problem after the forger F makes qH queries to the H oracle, qs1 queries to the Sign-1 oracle, qs2 queries to the Sign-2 oracle and generates a forged signature. Also, given the forged signature, the challenger extracts the solution to the CDH problem with O(1) computation. Therefore the total time t0 taken by C in solving the hard problem is as below: t0 ≤ t + (qH + qs1 + qs2 + O(1)) If t is a polynomial, it would imply that t0 is also a polynomial which contradicts the assumption that (G, GT ) is a CDH group pair. This completes the proof of the theorem. B. Security Proof of our Aggregate Signature Scheme with Key Split-up In this section we formally prove the security of the signature scheme with key split-up against existential forgery under adaptive chosen-message attack in the random oracle model. We formally show that our scheme is secure and its security follows from the CDH assumption in (G, GT ). Theorem 2. Let (G, GT ) be a (t0 , 0 )-CDH group of order p. Then our signature scheme is (t, qs1 , qs2 , qH1 , )-secure against existential forgery under the adaptive chosen-message attack in the random oracle model, for all t and that satisfies, , and 0 ≥ e(1 + qs2 ) t0 ≤ t + (qH1 + qs1 + qs2 + O(1)) Proof. Suppose F is a forger algorithm that (t, qs1 , qs2 , qH1 , )-breaks our signature scheme on (G, GT ) in time t. Then, we show how to construct a t0 -time algorithm C that solves the CDH problem on (G, GT ) with probability atleast 0 . The existence of such polynomial time solver for CDH problem is not possible, hence the existence of polynomial time attacker for the signature scheme is also not possible Let P be the generator of G. Algorithm C is provided with the challenge instance (P, aP, bP ) ∈ G whose goal is 6 "problem with O(1) computation. Therefore the total time t taken by C in solving the hard problem is as below: both Sign-1 and Sign-2 oracle. Now, C computes the solution to the hard problem as shown below. – For all i=1 to k, C checks and retrieves hi from the entry hmi , P Ki , −, hi , Hmi i in LH list. – C retrieves h corresponding to hmT , P KT , c, h, HmT i in LH list. k P (hi P Ki ) − hs1 P ). – Computes T = (hs2 )−1 (δ − t0 ≤ t + (qH + qs1 + qs2 + O(1)) If t0 is a polynomial, it would imply that t is also a polynomial which contradicts the assumption that (G, GT ) is a CDH group pair. This completes the proof of the theorem. i=1 This correctly generates the solution to the hard problem T = abP as below. VI. R EMARK ON M ULTI - SIGNATURES k X T = (hs2 )−1 (δ − (hi P Ki ) − hs1 P ) Multi-signatures [4] is a special case of signature aggregation where the message to be signed is same for all the parties involved in the signature generation process. Typically this calls for a coordinated way of generating the multi-signature and this is in contrast to the signatures in the transactions which are independently generated. While the BLS scheme works well for general aggregation, it suffers from a subtle flaw when used for aggregation or multi-signature in blockchain as pointed out in [8]. However, there is an easy fix by including the public key of the signer along with the message to be signed. This fix is also suggested in [8]. i=1 n k X X = (hs2 )−1 ( (xj Hj ) − (hi Xi ) − hs1 P ) j=1 i=1 k X −1 = (hs2 ) ( (xj Hj ) + xT HT j=1 − k X (xi Hi ) − hs1 P ) i=1 = (hs2 )−1 (xT HT − hs1 P ) VII. C OMPARISON OF S CHNORR , ECDSA, Γ− S IGNATURES AND BLS BASED APPROACHES = (hs2 )−1 ((s1 + s2 ab)hP − hs1 P ) = (hs2 )−1 (s1 hP + s2 abhP − hs1 P ) = (hs2 ) −1 Based on the proposed protocol, we present the computational complexity and storage complexity for the generation and verification of a single signature and n signatures for Schnorr, ECDSA, Γ− signatures and our approach in Table III. Note that, both Schnorr and ECDSA signature schemes do not allow key-aggregation nor key-split. Our signature scheme requires only one pairing operation for verifying an aggregate signature, which is more efficient than the Schnorr, ECDSA and Γ− signatures, where the time taken increases with the number of signatures combined. In Table IV, we provide the time taken (in microseconds (µs), milliseconds (ms) and seconds (s)) for the aggregation, verification of n signatures and also the time for verification of an n-signatures aggregation for values n = 1, 100, 300, 400, 500 and 1000 signatures. The different implementations on performance are tested under 2.4 GHz Intel Core i7 quad-core processor. The programming language used is Go language [2], and the programming tool is Goland 2018.2. For symmetric bilinear pairing operation, we have used the MCL Library in the implementation of our signature protocol, which is a portable and fast pairingbased cryptography library that supports optimal Ate pairing over BN curves and BLS12-381 curves [13]. The Schnorr signature is implemented on the edwards25519-curve [3], which is the current standard deployed in cryptocurrencies [10] for fast performances. We have implemented the ECDSA signature scheme on the Koblitz curve secp256k1 [11] over Fq as defined in FIPS 186-3 [9]. The Γ− signature is also constructed on the secp256k1 curve as per the protocol [14]. Note that both the Schnorr and ECDSA scheme does not support aggregation. From the performance comparison, it is (s2 abhP ) = abP = LHS. • Thus, no forgery is possible by F in polynomial time with a non-negligible advantage. Probability Analysis: We calculate the probability with which C aborts during the simulation. Let Abort denote the event that C aborts during the game and qs2 denote the number of queries made to the Sign-2 oracle. We note that C does not abort in the following events: − E1 : c = 0 in a Sign-2 query of Training phase. − E1 : c∗ = 1 in the Forgery phase. We have P r[¬Abort] ≥ γ qs2 (1 − γ), which has a qs2 . Using γOP T , we maximum value at γOP T = 1+q s2 obtain: 1 P r[¬Abort] ≥ e(1+q , s ) 2 where e is the base of the natural logarithm. Note that the simulation of the random oracles is perfect. Therefore, C solves the CDH problem in (G, GT ) with probability: 0 ≥ . e(1 + qs2 ) Note that C solves the hard problem after the forger F makes qH queries to the H oracle, qs1 queries to the Sign-1 oracle, qs2 queries to the Sign-2 oracle and generates a forged signature. Also, given the forged signature, the challenger extracts the solution to the CDH 7 "evident that our scheme is more efficient than the existing aggregatable Γ− signature scheme, and also provides the added functionality of key split-up. VIII. C ONCLUSION In this paper, we propose a simple key management scheme, called key split-up and showed that it is easy to realize that in BLS signature scheme. We also noted that both Schnorr and ECDSA does not allow any natural way to split their keys. Since it is known that aggregation is not possible/desirable for Schnorr or ECDSA, we have chosen the aggregatable Γ− signature scheme that is the most recent. Even in this case, we note that BLS is more efficient than the Γ signature protocol. Acknowledgment.: The authors would like to thank Dr. Rupesh Nasre for providing access to multi-core processors to conduct experimental studies as a part of this work. R EFERENCES [1] Armory. Armory Secure Wallet. https://www.bitcoinarmory.com/, 2016. [2] Daniel J. Bernstein. The go programming language. https://golang.org/. [3] Daniel J. Bernstein. Curve25519: New diffie-hellman speed records. In Public Key Cryptography - PKC 2006, 9th International Conference on Theory and Practice of Public-Key Cryptography, New York, NY, USA, April 24-26, 2006, Proceedings, pages 207–228, 2006. [4] Dan Boneh, Manu Drijvers, and Gregory Neven. Compact multisignatures for smaller blockchains. In Advances in Cryptology ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part II, pages 435–464, 2018. [5] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings, pages 416–432, 2003. [6] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. In Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings, pages 514–532, 2001. [7] Shayan Eskandari, Jeremy Clark, David Barrera, and Elizabeth Stobert. A first look at the usability of bitcoin key management. CoRR, abs/1802.04351, 2015. [8] Sergey Gorbunov. How not to use aggregate signatures in your blockchain. https:medium.com/@sergey nog /how-not-to-use-aggregate-signatures -in-your-blockchain 63e05be2cbbe. [9] G Locke and P Gallagher. Fips pub 186-3: Digital signature standard (dss). Federal Information Processing Standards Publication, 3:186–3, 2009. [10] Hartwig Mayer. Ecdsa security in bitcoin and ethereum: a research survey. CoinFaabrik, June, 28, 2016. [11] C. Research. SEC 2: Recommended Elliptic Curve Domain Parameters 2010. http://www.secg.org/sec2-v2.pdf, 2010. [12] Claus-Peter Schnorr. Efficient signature generation by smart cards. J. Cryptology, 4(3):161–174, 1991. [13] Mitsunari Shigeo. Mcl-a portable and fast pairing-based cryptography library. https://github.com/herumi/mcl. [14] Yunlei Zhao. Aggregation of gamma-signatures and applications to bitcoin. Cryptology ePrint Archive, Report 2018/414, 2018. https://eprint.iacr.org/2018/414. 8 "Feature Size of 1 signature Size of n signatures(aggregated) Complexity of 1 signature Generation Complexity of n signature Generation Complexity of 1 verification Complexity of n verification Size of Public Key Schnorr [12] |Zq | + |G| |Zq | + n|G| RA (n)RA 2RA + P A (n + 1)RA + nP A |G| ECDSA 2|Zq | (2n)|Zq | RA (n)RA 2RA (2n) RA +PA |G| Γ−Signature [14] 2|Zq | (n + 1)|Zq | RA (n)RA 2RA + P A (2n+1) RA+(n+1)PA |G| Our Approach |G| |G| 2RA + P A (2n)RA + nP A 2 P airing (n + 1) P airing |G| TABLE III: The Efficiency comparisons of Schnorr,ECDSA, Γ− Signatures and our Signature scheme based on BLS. Abbreviations: RA- Repeated Point Addition, PA- Point Addition Schnorr Signature 1 Signature 100 Signatures 300 Signatures 400 Signatures 500 Signatures 1000 Signatures ECDSA Signature 1 Signature 100 Signatures 300 Signatures 400 Signatures 500 Signatures 1000 Signatures Γ− Signature 1 Signature 100 Signatures 300 Signatures 400 Signatures 500 Signatures 1000 Signatures Our Scheme 1 Signature 100 Signatures 300 Signatures 400 Signatures 500 Signatures 1000 Signatures Aggregation Cost Not Possible Not Possible Not Possible Not Possible Not Possible Not Possible Aggregation Cost Not Possible Not Possible Not Possible Not Possible Not Possible Not Possible Aggregation Cost 2.59 s 7.58 s 10.19 s 12.81 s 27.6 s Aggregation Cost 50.35 ms 153.91 ms 206.55 ms 256.52 ms 504.96 ms Verification Cost 418.9 µs 42.55 ms 125.3 ms 165.31 ms 204.83 ms 411.36 ms Verification Cost 280.1 µs 22.65 ms 60.3 ms 86.17 ms 104.32 ms 211.62 ms Verification Cost 25.57 ms 2.61 s 7.62 s 10.24 s 12.97 s 27.67 s Verification Cost 1.12 ms 1.10 ms 1.12 ms 1.17 ms 1.13 ms 1.88 ms Aggregation + Verification Aggregation + Verification Aggregation + Verification 25.57 ms 5.2 ms 15.2 s 20.43 s 25.78 s 55.3 s Aggregation + Verification 1.12 ms 51.45 ms 155.03 ms 207.72 ms 257.65 ms 506.84 ms Cost Cost Cost Cost TABLE IV: Performance Evaluation of our Signature scheme, Schnorr Signature scheme, ECDSA scheme and Γ-signature scheme for aggregation and verification cost. Note that Schnorr and ECDSA do not support aggregation. 9 "