Aggregation Of Gamma-Signatures and Applications to Bitcoin

[xingchang]

We are the cryptographic research team at  Fudan University, Shanghai, China.  Here, we would like to briefly report our resent results on aggregate signature and applications to Bitcoin.

As you know, aggregate signature allows non-interactively condensing multiple individual signatures into a compact one. Besides the faster verification, it is useful to reduce storage and bandwidth, and is especially attractive for blockchain and cryptocurrency.

However, achieving aggregate signature from general elliptic curve group (without bilinear maps) is a long-standing open question and no convincing conclusion emerged.

We first observe the incapability of Schnorr’s for aggregating signatures in the Bitcoin system, which is demonstrated by concrete attacks. Then investigate the applicability of the Gamma-signature scheme (Paper: Online/Offline Signatures for Low-Power Devices, https://ieeexplore.ieee.org/document/6376177/ ) proposed by Yao and Zhao, and we show that aggregate signature can be derived from the Gamma-signature scheme. To the best of our knowledge, this is the first aggregate signature scheme from general groups without bilinear maps.

Akin to Schnorr’s, Gamma-signature is generated with linear combination of ephemeral secret-key and static secret-key, and enjoys almost all the advantages of Schnorr’s signature. Besides, Gamma-signature has salient features in online/offline performance, stronger provable security, and deployment flexibility with interactive protocols like IKE. Our this work demonstrate one more key advantage of Gamma-signature in signature aggregation.

When applying the resultant aggregate Gamma-signature to Bitcoin, the storage volume of signatures reduces about 50%, and the signature verification time can even reduce about 80%. And, we specify in detail the implementation of aggregate Gamma-signature in Bitcoin, with minimal modifications that are in turn more friendly to segregated witness (SegWit).

The security of aggregate Gamma-signature is proved based on a new assumption proposed and justified in this work, referred to as non-malleable discrete-logarithm (NMDL), which might be of independent interest and could find more cryptographic applications in the future.

This work is recently posted at ePrint, which is available from  https://eprint.iacr.org/2018/414

[xingchang]

We look forward to your insights.

[RGBKey]

I'm pretty interested by this. Are you claiming Schnorr signatures cannot be used by Bitcoin? As far as I know, that's what is being planned for Bitcoin's future. If not, are you claiming that gamma-signatures are preferable to schnorr signatures? I'll have to save this paper to read later. Very interesting to see academic papers here.

[xingchang]

I'm pretty interested by this. Are you claiming Schnorr signatures cannot be used by Bitcoin? As far as I know, that's what is being planned for Bitcoin's future. If not, are you claiming that gamma-signatures are preferable to schnorr signatures? I'll have to save this paper to read later. Very interesting to see academic papers here.

Thanks for the comments!  In general, Schnorr’s signature can be used with Bitcoin in place of EC-DSA. But our results show that Schnorr’s should NEVER be used for signature aggregation (please notice the differences between aggregate-signature and multi-signature). As signature aggregation is crucial for cryptocurrency and for blockchain-based applications in general, Gamma-siganture can be more preferable as it is currently the only scheme that supports signature aggregation on general ECC groups without bilinear pairings. Moreover, Gamma enjoys almost all the advantages of Schnorr, and additionally has the following advantages (besides signature aggregation): better online efficiency, stronger provable security (w.r.t. a stronger security model), being more flexible, easy deployment, etc. From our point of view, Gamma  might arguably be the best ECC-based  signature scheme for cryptocurrency and blockchain. Detailed specifications on implementing Gamma in Bitcoin are presented, with very minor modifications that are, in turn, useful to be against malleability attacks. A prototype is under construction, and skilled programmers are welcome  to join us. Thanks!

[RGBKey]

So you believe that we should not proceed with using Schnotr signatures completely, or do you just prefer gamma signatures?

[xingchang]

So you believe that we should not proceed with using Schnotr signatures completely, or do you just prefer gamma signatures?

We may prefer to use Gamma  in place of EC-DSA, if we believe that signature aggregation is important to Bitcoin.

[ncklr]

I have only skimmed the paper but the scheme doesn't seem to aggregate the public nonces (see table 4) and is therefore less space efficient than interactive Bellare-Neven signatures. Gamma signatures are similar to what was introduced on the bitcoin-dev mailing list as "non-interactive half aggregation", but gamma signatures appear to be broken by Wagner's algorithm because not all attacker given data (like messages and public nonces) is hashed into all the challenges ei. This problem was also mentioned on the mailing list https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014308.html.

In Gamma signatures the challenges are just ei = H(Pi, mi). Since the pubkeys Pi are just multiplied by ei and then summed in the verification equation an attacker can try to choose its pubkeys and challenges to cancel out the victim's.
The victim's pubkey is P1, the corresponding challenge e1. The attacker wants to cancel P1, so needs to find (ei, Pi) for i >= 2, s.t. -e1*P1 = e2*P2 + ... + en*Pn.
If the attacker for example chooses pubkeys Pi = i*P1 then solution -e1 = e2*2 + ... + en*n can be found with Wagner's algorithm in O(2^33) (for 256 bit groups).

[xingchang]

I have only skimmed the paper but the scheme doesn't seem to aggregate the public nonces (see table 4) and is therefore less space efficient than interactive Bellare-Neven signatures. Gamma signatures are similar to what was introduced on the bitcoin-dev mailing list as "non-interactive half aggregation", but gamma signatures appear to be broken by Wagner's algorithm because not all attacker given data (like messages and public nonces) is hashed into all the challenges ei. This problem was also mentioned on the mailing list https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014308.html.

In Gamma signatures the challenges are just ei = H(Pi, mi). Since the pubkeys Pi are just multiplied by ei and then summed in the verification equation an attacker can try to choose its pubkeys and challenges to cancel out the victim's.
The victim's pubkey is P1, the corresponding challenge e1. The attacker wants to cancel P1, so needs to find (ei, Pi) for i >= 2, s.t. -e1*P1 = e2*P2 + ... + en*Pn.
If the attacker for example chooses pubkeys Pi = i*P1 then solution -e1 = e2*2 + ... + en*n can be found with Wagner's algorithm in O(2^33) (for 256 bit groups).

Hi, Ncklr:
Sorry that we just noticed your comment. Thanks for referring us to the previous discussions. The proposal of aggregate Schnorr by  Tadge is the same as proposed in our work. But our attack against aggregate Schnorr, presented in our work, is more powerful/effective and fatal than the attack proposed by Russell based on Wagner’s generalized birthday attack.  Note that our attack is direct and constant time: one rogue-key to attack many honest victims; In comparison, the attack by Russel is to attack a single victim by many rogue-keys and also need Wagner’s algorithm. Nevertheless, all these attacks against aggregate Schnorr are variants of rogue-key attack, and the design of aggregate Gamma was well motivated to avoid such rogue-key attack.
 
With respect to your attack, we suggest it is not effective actually. Note also that, unlike Schnorr signature, both $e$ and $d$ control the security of aggregation of Gamma signatures. Moreover, e_i=h(m_i,P_i) is determined by (m_i,P_i), and R_i plays no role in generating e_i; Furthermore, for applications with Bitcoin, m_i actually commits to  the sender’s public key P_i （and other formatted data like time-stampt, etc). It is incorrect to conclude: solution -e1 = e2*2 + ... + en*n can be found with Wagner's algorithm in O(2^33)”. Here, 2 determines the input to e_2 that must be $P_2=2P_1$ and $m_2$ also commits to P_2; 3 determines the input to e_3 that must be $P_3=3P_1$ and $m_3$ also commits to P_3; and so on. Clearly, Wagner’s algorithm does not work hear. If no restrictions on the formats of inputs to $e_i$, we can use Wagner’s algorithm. But we are forced in coming up with strictly formatted input here. This is the design philosophy of Gamma-signature.
 
We welcome a more detailed discussion after your read our paper.
 
BTW, Gamma-signature appeared at ePrint since 2010, and was published at IEEE-TIFS 2013, which should be much earlier than the mailing discussions you mention.
 
Thanks!

[xingchang]

I have only skimmed the paper but the scheme doesn't seem to aggregate the public nonces (see table 4) and is therefore less space efficient than interactive Bellare-Neven signatures. Gamma signatures are similar to what was introduced on the bitcoin-dev mailing list as "non-interactive half aggregation", but gamma signatures appear to be broken by Wagner's algorithm because not all attacker given data (like messages and public nonces) is hashed into all the challenges ei. This problem was also mentioned on the mailing list https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014308.html.

In Gamma signatures the challenges are just ei = H(Pi, mi). Since the pubkeys Pi are just multiplied by ei and then summed in the verification equation an attacker can try to choose its pubkeys and challenges to cancel out the victim's.
The victim's pubkey is P1, the corresponding challenge e1. The attacker wants to cancel P1, so needs to find (ei, Pi) for i >= 2, s.t. -e1*P1 = e2*P2 + ... + en*Pn.
If the attacker for example chooses pubkeys Pi = i*P1 then solution -e1 = e2*2 + ... + en*n can be found with Wagner's algorithm in O(2^33) (for 256 bit groups).

In addition, your rogue-key attack can be easily defeated in practice (particularly for Bitcoin). Specifically, we require that the first use of each public key (i.e., signing for its first transaction) should not be aggregated. In other words, the first signing of each public key can be viewed as a proof of knowledge of the possession of the corresponding secret key. Note that our attack against aggregate Schnorr cannot be preventd with such a restriction that is practical for blockchain.

[xingchang]

I have only skimmed the paper but the scheme doesn't seem to aggregate the public nonces (see table 4) and is therefore less space efficient than interactive Bellare-Neven signatures. Gamma signatures are similar to what was introduced on the bitcoin-dev mailing list as "non-interactive half aggregation", but gamma signatures appear to be broken by Wagner's algorithm because not all attacker given data (like messages and public nonces) is hashed into all the challenges ei. This problem was also mentioned on the mailing list https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014308.html.

In Gamma signatures the challenges are just ei = H(Pi, mi). Since the pubkeys Pi are just multiplied by ei and then summed in the verification equation an attacker can try to choose its pubkeys and challenges to cancel out the victim's.
The victim's pubkey is P1, the corresponding challenge e1. The attacker wants to cancel P1, so needs to find (ei, Pi) for i >= 2, s.t. -e1*P1 = e2*P2 + ... + en*Pn.
If the attacker for example chooses pubkeys Pi = i*P1 then solution -e1 = e2*2 + ... + en*n can be found with Wagner's algorithm in O(2^33) (for 256 bit groups).

Another note: There is also another approach to defeating the rogue-key attack (besides non-aggregation of first use of each public key): including some unpredictable value into the input of $e_i$. For example, the random nonce appeared in the last confirmed block is also input to $e_i$. This way, the attacker cannot predict and know $e_1$ in your attack (except for a very short timing window, e.g., one hour). Note that, when applying  Wagner's algorithm, each operation corresponds to one exponentiation plus one hashing.  Also notice that the rogue-key attack can only be performed by a malicious miner who needs to successfully make such an attack along with hard POW competition. Actually, the fact that only a malicious miner can perform such an attack may already be a much  serious concern for the attacker :-)