ZKHack IV Puzzles #3 Chaos Theory

Puzzle: https://zkhack.dev/zkhackIV/puzzleF3.html
Solution: https://github.com/flyq/puzzle-chaos-theory

ElGamal encryption

Key generation

Alice:

• secret key:
  $x$
• public key:
  $H=x\cdot G$

Encryption

Bob:

• $M=F(m)$, the
  $m$ is the message, and the
  $M$ is the element in
  $G$.
• ephemeral key:
  $y$
• shared secret:
  $S=H\cdot y=x\cdot y\cdot G$
• $C_1=y\cdot G$
• $C_2=S+M$

if someone knows

$(C_1,C_2)$ and

$M$, the

$S=C_2-M$

Decryption

Alice:

• $S=C_1\cdot x=x\cdot y\cdot G$
• $M=C_2-S$
• $m=F^{-1}(M)$

Sender(Bob):

$y$ and

$C_1=y\cdot G_1$
Receiver(Alice):

$H$ in

$G_1$ group
Message:

$M$ in

$G_1$ group
ElGamal:

$(C_1,C_2)$ in

$G_1$ group,

$H((C_1,C_2))=\text{hash\_to\_curve}((C_1,C_2))\cdot Q$ in

$G_2$ group

s:

$T=y\cdot H((C_1,C_2))$

• send:
  $C_1$,
  $C_2=H\cdot y+M=S+M$
• authenticate:
  $H((C_1,C_2))\cdot y$
• check_auth:
  $e(G_1,T)=e(C_1,H((C_1,C_2)))$

blob:

$C_1,(C_1,C_2),T,H$