ZKHack Puzzles #1 Let's Hash it Out

https://zkhack.dev/events/puzzle1.html

• private key
  $sk$
• public key
  $P=sk\cdot G_2$
• message
  $m$
• message's blake2s hash
  $h_m=\text{blake2s}(m)$,
  $h_m$ is a scalar field element with
  $256$ bits size.
• according to WINDOW_SIZE = 1;NUM_WINDOWS = 256, CRH will generate
  $256$ Points according to the rng. Let's use
  $Q_0,Q_1,\dots ,Q_{255}$ present them.
• hash to curve
  $H(h_m)=h_m[0]\cdot Q_0+h_m[1]\cdot Q_1+\cdots +h_m[255]\cdot Q_{255}$
• signature
  $S=sk\cdot H(h_m)$
• $e(S,G_2)=e(H(h_m),P)$

There are

$256$ messages:

$$\begin{array}{rl}{S}_0& =h_{m0}[0]\cdot sk\cdot Q_0+h_{m0}[1]\cdot sk\cdot Q_1+h_{m0}[2]\cdot sk\cdot Q_2+\cdots +h_{m0}[255]\cdot sk\cdot Q_{255}\\ S_1& =h_{m1}[0]\cdot sk\cdot Q_0+h_{m1}[1]\cdot sk\cdot Q_1+h_{m1}[2]\cdot sk\cdot Q_2+\cdots +h_{m1}[255]\cdot sk\cdot Q_{255}\\ S_2& =h_{m2}[0]\cdot sk\cdot Q_0+h_{m2}[1]\cdot sk\cdot Q_1+h_{m2}[2]\cdot sk\cdot Q_2+\cdots +h_{m2}[255]\cdot sk\cdot Q_{255}\\ \cdots \\ S_{255}& =h_{m255}[0]\cdot sk\cdot Q_0+h_{m255}[1]\cdot sk\cdot Q_1+h_{m255}[2]\cdot sk\cdot Q_2+\cdots +h_{m255}[255]\cdot sk\cdot Q_{255}\end{array}$$

$$\left[\begin{array}{ccccc}{h}_m[0][0]& h_m[0][1]& h_m[0][2]& \cdots & h_m[0][255]\\ h_m[1][0]& h_m[1][1]& h_m[1][2]& \cdots & h_m[1][255]\\ h_m[2][0]& h_m[2][1]& h_m[2][2]& \cdots & h_m[2][255]\\ \cdots \\ h_m[255][0]& h_m[255][1]& h_m[255][2]& \cdots & h_m[255][255]\end{array}\right]\left[\begin{array}{c}sk\cdot Q_0\\ sk\cdot Q_1\\ sk\cdot Q_2\\ \cdots \\ sk\cdot Q_{255}\end{array}\right]=\left[\begin{array}{c}{S}_0\\ S_1\\ S_2\\ \cdots \\ S_{255}\end{array}\right]$$

Let use

$A$ represent the

$h_m$ Matrix, use

$Q$ represent

$sk\cdot Q_i$ Vectors:

$$A\cdot Q=S⟹Q=A^{-1}\cdot S$$

and if we have a new message

$m^{\prime }$, we can get it's signature by

$S^{\prime }=h_m^{\prime }\cdot Q$

I think it would be dangerous to

The problem is that when hash to curve, first hash to field then

$\text{field}\ast Q$, will be dangerous.

Even though we know how to do it, there are still difficulties. In Rust, there are almost no libraries that can find the inverse of a matrix whose elements are in a finite field. I tried two linear algebra libraries, but they directly returned f32. In Sage, when multiplying a matrix by a vector, the data types of the matrix and vector are not allowed to be inconsistent:

sage solution.sage
Traceback (most recent call last):
  File "/Users/flyq/workspace/github/flyq/zkhack-bls-pedersen/solution.sage.py", line 798, in <module>
    Q = m1.inverse() * S
        ~~~~~~~~~~~~~^~~
TypeError: can't multiply sequence by non-int of type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'

So, we need use sage to find out the

$A^{-1}$, then use Rust to get the

$Q$ vector and calculate the signature by

$S^{\prime }=h_m^{\prime }\cdot Q$

we first used the sage code here to print the

$A$ matrix's inverse(a_inv), then we need copy the a_inv's values to rust code and finish the solution.

Whole code: https://github.com/flyq/zkhack-bls-pedersen