zk-Openings::Srdnlen CTF 2025

(Updated: )
,

Time: 2025.01.19-20 (online)

Interesting challenge, but I didn’t have enough time to solve it during the contest XDDD

zk-Openings (0 solve)

I actually learnt a lot from the implementation, thank you @lrnzsir.

KZG Commitment

KZG commitment is a polynomial commitment scheme proposed by Kate et al in 2010.

While the original paper used a symmertric type-1 pairing, we prefer to use type-3 pairing these days. Basically we have three groups $(G_1, G_2, G_T)$ , two generators $(g_1 \in G_1, g_2 \in G_2)$, and a bilinear pairing function $e: G_1 \times G_2 \rightarrow G_T$.

  1. $\mathcal{Setup}(d) \rightarrow srs$: randomly samples a secret value $x$, and computes $srs = (g_1^{x}, …, g_1^{x^d}, g_2^{x})$. While $x$ is considered to be “toxic waste”, it must be generated by trusted authority and deleted properly after use.
  2. $\mathcal{Commit}(srs, f) \rightarrow com$: computes the commitment $com = g_1^{\Sigma_{i=0}^d f_i \cdot x^i} = \Pi_{i=0}^{d} (g_1^{x^i})^{f_i}$ for the polynomial.
  3. $\mathcal{EvalProve}(srs, f, z) \rightarrow (\pi, f(z))$: computes a polynomial $q(x) = \frac{f(x) - f(z)}{x-z}$. Then it computes the proof $\pi = g_1^{\Sigma_{i=0}^d q_i \cdot x^i} = \Pi_{i=0}^{d} (g_1^{x^i})^{q_i}$, proving that one knows the evaluation of $f$ over $z$.
  4. $\mathcal{EvalVerify}(srs, com, \pi, z, f(z)) \rightarrow 0/1$: verifies the proof by checking $e(com \cdot g_1^{-f(z)}, g_2) \overset{?}{=} e(\pi, g_2^{s} \cdot g_2^{-z})$.

Note that KZG is a commitment (instead of ZKP) scheme.

The Challenge

For this challenge, we performs the KZG process on some secret polynomial $f$ and ended up with opening.json. Considering the difficulty of DLP under standard parameters, I actually just skip the content related to curve points. So basically we have $k=20$ pairs of $(x_i, y_i=f(x_i))$.

And here is how we get the secret polynomial. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
assert n in AES.key_size # 32
key = os.urandom(n)
evals = list(key)
poly = P(intt(evals))
assert all(poly(H[i]) == key[i] for i in range(n))


def lcg(m: int, a: int, c: int, x: int) -> "Generator[int, None, None]":
    """ Linear Congruential Generator """
    while True:
        x = (a * x + c) % m
        yield x


a, c, x = [secrets.randbelow(p) for _ in range(3)]
rng = lcg(p, a, c, x)

k = 20
hiding_poly = P([next(rng) for _ in range(k)])
hidden_poly = poly + hiding_poly * Z_H
assert all(hidden_poly(H[i]) == key[i] for i in range(n))

In short, we have a 32-degree polynomial $f(x)$ and a 20-degree polynomial $g(x)$, where $f(H_i) = key_i$ and $g_i$ is generated successively by a secret LCG. Then we have our secret polynomial $h(x) = f(x) + g(x) \cdot (x^n-1)$ satisfying $h(H_i) = f(H_i) = key_i$ since $H_i^n = 1$.

According to previous discussion, we have 20 pairs of random points $(x_i, h(x_i))$, which is apparently not enough to recover $h(x)$. Considering $key_i$ is very small compared to $p$, LLL is our option.

We can’t construct the Lattice directly, but we can resort to $g(x)$. The first step is to establish a linear representation between $g(x)$ and $key_i$, which is quite simple, since ntt, intt and polynomial_evaluation are all linear transformations.

  • $\vec{key} = NTT_{n \times n} \cdot \vec{f}$
  • $\vec{y} = X_{k \times (n+k)} \cdot \vec{h} = FX_{k \times n} \cdot \vec{f}+ GX_{k \times k} \cdot \vec{g}$

$\Rightarrow \vec{g} = GX^{-1} \cdot (\vec{y} - FX \cdot NTT^{-1} \cdot \vec{key})$

For $NTT^{-1}$, you can also compute $iNTT$.

Linearization for Unknown LCG

We know that $g_{i+1} = a \cdot g_i + b$, but $(a, b)$ are randomly chosen on $GF_p$. To get rid of them, we construct equations like $(g_{i+d_0} - g_{i}) \cdot (g_{j+d_1} - g_{j}) = (g_{i+d_1} - g_{i}) \cdot (g_{j+d_0} - g_{j})$.

Here comes an interesting (maybe) question: how many linearly independent equations can we get? Well this did appealled to me and @糖醋小鸡块. Since we can get $k-2$ equations like $y_{i+1} = a \cdot y_i$, we can choose any two of them to eliminate $a$, and thus we have $C(k-2, 2)$ equations.

For @lrnzsir’s strategy, he iterates $(g_{i+2}-g_{i+1}) \cdot (g_{j+1}-g_j) = (g_{i+1}-g_i) \cdot (g_{j+2}-g_{j+1})$ for all $i, j \in [k - 2]$ and $i < j$. We can get exactly $C(k-2, 2)$ equations and each equation contains a unique binomial (thus linear independent). So this is the best we can get.

We (@糖醋小鸡块) believe there exists a better way for theoratical analysis.

With linear transformation, we have $C(k-2, 2)$ quadratic equations about $key_i$ now, containing $n + C(n+1, 2)$ monomials. Then we can do LLL on the linearized system to recover the key. One can ignore some equations and utilize flatter for better efficiency.

exp.py

There maybe some difference in my code since it’s implemented months ago XD