Let's hash out

BLSPedersenHash.tex

Title : Let's hash out
Solved by Hyunok Oh (hyunokoh@gmail.com)

Problem : Alice designed an authentication system in which users gain access by presenting it a signature on a username, which Alice provided.
One day, Alice discovered 256 of these signatures were leaked publicly, but the secret key wasn't. Phew.
The next day, she found out someone accessed her system with a username she doesn't know! This shouldn't be possible due to existential unforgeability, as she never signed such a message.

Can you find out how it happend and produce a signature on your username?

Answer : BLS signature is H(m)^sk where m is a message and sk is a signing key.
If a pedersen hash H is used for 256 bit input then H(m) = \sum_{j=1}^{256} b_j G_j 
where m=b_1 || ... || b_256, and b_j are binary, and G_j are hash keys (group elements).

Since 256 signatures are given, let each signature be S_i (1<= i <=256).
Then S_i = \sum_{j=1}^{256} b_{i,j} sk G_j for 1<= i <=256.
To simply the equation, let S be a column vector of (S_1, ..., S_256), 
B be a matrix of [[b_{1,1} ... b_{1,256}] ... [b_{256,1} ... b_{256,256}]],
and A be a column vector of (sk G_1, ..., sk G_256).
Then the equations are becoming S = B A.
For a randomly generated binary matrix B, it is known that the probability that B is invertible is more than 0.288. 
Note  that  the  probability of a random l×l binary  matrix  to  be  invertible is
p(l)  =\prod_{k=1}^l(1−2^{−k}) and the limit is \lim_{l-->\inf}p(l) ≈ 0.288788.
Therefore with a non-negligible probability (exactly more than 28%), we can compute A ( = B^{-1} S).
After computing A, for a given message m' ( = b'_1 || ... || b'_256), 
we can compute the forged signature \sum_{j=1}^{256} b'_j sk G_j.