Bitcoin Forum
May 01, 2024, 07:50:03 PM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
  Home Help Search Login Register More  
  Show Posts
Pages: [1]
1  Bitcoin / Development & Technical Discussion / Re: Aggregation Of Gamma-Signatures and Applications to Bitcoin on: December 14, 2018, 10:05:57 AM
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).
Pages: [1]
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!