After the competition ended, I found out through the Discord channel that the code was an implementation of Eaglesign(not exactly same), and that there is a paper on attacks related to it.

Most of the solvers, aside from myself, seem to have either referenced the paper or figured out a similar method on their own to solve it.

Even though I only added a very short explanation along with my solver code on Discord channel, I sincerely thank @vishiswoz and @Neobeo for sharing their interpretations of my solution.

[@vishiswoz's interpretation](https://hackmd.io/@vishiswoz/BkgeMCH3A)<br>
[@Neobeo's interpretation](https://gist.github.com/AdibSurani/4e5596991a316ef6319ddb2c8a764e9e)

# Challenge

- N = 1024, q = 12289
- Key generation
- Private keys ($G, D$) are randomly generated polynomial on Quotient Ring $Z_q[x]/x^N + 1$
- coefficients must be {-1, 0, 1}.
- $G$ must be invertible.
- Public key $A$ is randomly generated polynomial on same Quotient Ring
- Public key $E = (A + D)G^{-1}$
- Sign
- Generate $Y1, Y2$ randomly
- $Y1$ has 140 nonzero coefficients, which are -1 or 1
- $Y2$ has bounded coefficients which absolute max are 64
- $P = AY1 + Y2$, $r = H(P)$
- Generate $C$ with given message and $r$
- $C$ has 38 nonzero coefficients, which are -1 or 1
- $U = Y1 + C$
- $V = GU$, $W = Y2 - DU$
- Signature is $(r, V, W)$
- Verify
- Generate $C$ with given message and $r$ (same as Sign)
- $Z = EV - AC + W$
- $EV - AC + W = EGU - AC + W = (A + D)U - AC + Y2 - DU = A(U - C) + Y2 = P$
- Check $r$ equals $H(Z)$
- Keys are generated and public Keys are given when code starts.
- We can sign for any message with no limit, and we need $D$ for get the flag.

# My approach

- $G^{-1} = (Y1 + C)V^{-1}$ ($\because V = GU = G(Y1 + C)$)
- So, $(Y1_i + C_i)V_i^{-1} = (Y1_0 + C_0)V_0^{-1}$ for every signature.
- We can express every $Y1_i$ as form $A_i(Y1_0) + B_i$
- $A_i = V_iV_0^{-1}$
- $B_i = A_iC_0 - C_i$

## Building equation
- Let $A_i = \sum\limits_{k=0}^{N - 1}a_{i, k}x^k$, $B_i = \sum\limits_{k=0}^{N - 1}b_{i, k}x^k$, $Y1_i = \sum\limits_{k=0}^{N - 1}c_{i, k}x^k$
- $x^jA_i = \sum\limits_{k=0}^{j - 1}-a_{i, N - j + k}x^{k} + \sum\limits_{k=j}^{N - 1}a_{i, k - j}x^{k}$
- $Y1_i = A_iY1_0 + B_i = \sum\limits_{j=0}^{N - 1}c_{0, j}(x^jA_i) + B_i$
- Therefore, we can express it as Matrix equation below:
$$ \begin{pmatrix}
a_{i,0} & -a_{i, N - 1} & -a_{i, N - 2} & \cdots & -a_{i,1} \\
a_{i,1} & a_{i,0} & -a_{i, N - 1} & \cdots & -a_{i,2} \\
a_{i,2} & a_{i,1} & a_{i,0} & \cdots & -a_{i,3} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{i,N - 1} & a_{i,N - 2} & a_{i, N - 3} & \cdots & a_{i,0} \\
\end{pmatrix}\begin{pmatrix}
c_{0, 0} \\
c_{0, 1} \\
c_{0, 2} \\
\vdots \\
c_{0, N - 1} \end{pmatrix} + \begin{pmatrix}
b_{0, 0} \\
b_{0, 1} \\
b_{0, 2} \\
\vdots \\
b_{0, N - 1} \end{pmatrix} = \begin{pmatrix}
c_{i, 0} \\
c_{i, 1} \\
c_{i, 2} \\
\vdots \\
c_{i, N - 1} \end{pmatrix}$$

- Let matrix $M_i = \begin{pmatrix}
a_{i,0} & -a_{i, N - 1} & -a_{i, N - 2} & \cdots & -a_{i,1} \\
a_{i,1} & a_{i,0} & -a_{i, N - 1} & \cdots & -a_{i,2} \\
a_{i,2} & a_{i,1} & a_{i,0} & \cdots & -a_{i,3} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{i,N - 1} & a_{i,N - 2} & a_{i, N - 3} & \cdots & a_{i,0} \\
\end{pmatrix} = \begin{pmatrix}
\vert & \vert & \vert & & \vert \\
\vec{v_{i, 0}} & \vec{v_{i, 1}} & \vec{v_{i, 2}} & \cdots & \vec{v_{i, N - 1}} \\
\vert & \vert & \vert & & \vert \\
\end{pmatrix}$
- Let vectors $\vec{y_i} = \begin{pmatrix}
c_{i, 0} \\
c_{i, 1} \\
c_{i, 2} \\
\vdots \\
c_{i, N - 1} \end{pmatrix}$, $\vec{b_i} = \begin{pmatrix}
b_{0, 0} \\
b_{0, 1} \\
b_{0, 2} \\
\vdots \\
b_{0, N - 1} \end{pmatrix}$
- So we can express equation above as below:
$$ \sum\limits_{j=0}^{N - 1}c_{0, j} \vec{v_{i, j}} + \vec{b_i} = \vec{y_i}$$

- Since Y1 has 140 nonzero coefficients which are -1 or 1, sum of square of coefficients equals 140, so $\vec{y_i} \cdot \vec{y_i} = 140$. It leads to equation below:
$$ \vec{y_i} \cdot \vec{y_i} = (\sum\limits_{j=0}^{N - 1}c_{0, j} \vec{v_{i, j}} + \vec{b_i})(\sum\limits_{j=0}^{N - 1}c_{0, j} \vec{v_{i, j}} + \vec{b_i}) $$
$$= \sum\limits_{0 \le j, k < N }(\vec{v_{i,j}} \cdot \vec{v_{i,k}})c_{0,j}c_{0,k} + 2\sum\limits_{j=0}^{N - 1}(\vec{v_{i,j}} \cdot \vec{b_i})c_{0,j} + (\vec{b_i} \cdot \vec{b_i}) = 140 $$
## Linearization & reduce unknown variables
- By linearization, we can treat equation above as linear equation of $(\binom{N}{2} + N) + N = N(N + 3) / 2$ unknown variables.
- But we can reduce $\binom{N}{2} + N$ unknown variables into $N$, because they shares same coefficients!
- $\vec{v_{i,k}}$ expresses coefficients of $x^jA_i$ as we announced ealier.
- Let $R = \begin{pmatrix}
0 & 0 & \cdots & 0& -1 \\
1 & 0 & \cdots & 0& 0 \\
0 & 1 & \cdots & 0& 0 \\
\vdots & \vdots & \ddots & \vdots& \vdots \\
0 & 0 & \cdots & 1& 0 \\
\end{pmatrix}$ then $R^TR = I$, $\vec{v_{i,j}} = R^j\vec{v_{i,0}}$
- be used to express the multiplication of $x$.
- $\vec{v_{i,j}} \cdot \vec{v_{i,k}} = (R^j\vec{v_{i,0}})^T(R^j\vec{v_{i,k - j}}) = \vec{v_{i,0}}^T (R^j)^T(R^j)\vec{v_{i,k - j}} = \vec{v_{i,0}} \cdot \vec{v_{i,k - j}}$
- So, a lot of terms sharing same coefficients $(\vec{v_{i,0}}\cdot \vec{v_{i,j}})$.
- Therefore, we can express equation above as below:
$$ \vec{y_i} \cdot \vec{y_i} = \sum\limits_{j=0}^{N - 1}(\vec{v_{i,0}} \cdot \vec{v_{i,j}})c_{0,j}' + 2\sum\limits_{j=0}^{N - 1}(\vec{v_{i,j}} \cdot \vec{b_i})c_{0,j} + (\vec{b_i} \cdot \vec{b_i}) = 140 $$
- We can treat equation above as linear equation of $N + N = 2N$ unknown variables

## Efficient calculation

- If $f = \sum\limits_{i=0}^{N - 1}a_ix^i$, let $f^* = \sum\limits_{i=0}^{N - 1}a_{N - 1- i}x^i$
- Let $f = \sum\limits_{i=0}^{N - 1}a_ix^i$, $g = \sum\limits_{i=0}^{N - 1}b_ix^i$. Then $\sum\limits_{i=0}^{N - 1}a_ib_i$ equals coefficient of term $x^{N-1}$ in $fg^*$
- $\vec{v_{i, j}} \cdot \vec{v_{i,0}}$ equals coefficient of term $x^{N -1}$ in $x^jA_iA_i^*$, which is also coefficient of term $x^{N - 1 - j}$ in $A_iA_i^*$
- As same reason, $\vec{v_{i, j}} \cdot \vec{b_i}$ equals coefficient of term $x^{N - 1 - j}$ in $A_iB_i^*$
- Therefore, we can $2N$ coefficients for linear equation by calculating $A_iA_i^*$ and $A_iB_i^*$
- It reduces time for running solution $O(N^3)$ to $O(N^2\log N)$

## Implementation

import os;os.environ["TERM"] = 'linux'
from pwn import *
from ntt import NTTDomain, NTTPoints
import hashlib
from tqdm import trange

#r = process(["python", "challenge.py"])
r = remote("54.78.163.105", "30859")

N, Q, W, P = 1024, 12289, 4324, 9389
PR.<x_> = PolynomialRing(GF(Q))
QR.<x> = PR.quotient(x_^N + 1)

def l2p(A):
    t = []
    while A:
        t.append(A % Q)
        A //= Q
    return QR(t)

def HashBall(m: bytes, tau: int) -> list:
    """ Deterministically generates sparse polynomials with weight tau. """
    if isinstance(m, str):
        m = m.encode()
    h = hashlib.sha256(m).digest()
    c = N * [0]
    for i in range(N - tau, N):
        hi = int(hashlib.sha256(h + i.to_bytes(2, 'big')).hexdigest(), 16)
        hi //= i; j = hi % i; hi //= i
        hi //= 2; k = hi % 2; hi //= 2
        c[i] = c[j]
        c[j] = (1 - 2 * k) % Q
    return c

def ntt(c):
    c = QR(c).lift()
    return QR([c(P * pow(W, i, Q)) for i in range(N)])

def intt(c):
    c = QR(c).lift()
    c = [c(pow(W, -i, Q)) * pow(N, -1, Q) for i in range(N)]
    c = [c[i] * pow(P, -i, Q) for i in range(N)]
    return QR(c)



r.recvuntil(b'= ')
data = eval(r.recvline().decode())
A = intt(l2p(int(data["A"], 16)))
E = intt(l2p(int(data["E"], 16)))


def get_sig(msg):
    r.recvuntil(b'|  Sig = ')
    sig = eval(r.recvline()[:-1].decode())
    sig_r = bytes.fromhex(sig["r"])
    sig_V = intt(l2p(int(sig["V"], 16)))
    sig_W = intt(l2p(int(sig["W"], 16)))
    sig_C = QR(HashBall(msg + sig_r, 38))
    sig_P = E * sig_V - A * sig_C + sig_W
    sig_Pint = sum([ZZ(j) * Q ** i for i,j in enumerate(ntt(sig_P).list())])
    sig_Pbyt = sig_Pint.to_bytes(-(-len(bin(sig_Pint)[2:]) // 8), 'big')
    assert sig_r == hashlib.sha256(sig_Pbyt.hex().encode()).digest()
    return sig_r, sig_V, sig_W, sig_C, sig_P

def send_n(msg, n):
    payload = b'S\n' + msg + b'\n'
    r.send(payload * n)

    

rs, Vs, Ws, Cs, Ps = [], [], [], [], []
m = 2 * N + 100
send_n(b'asdf', m)
for i in trange(m):
    r0, V0, W0, C0, P0 = get_sig(b'asdf')
    rs.append(r0)
    Vs.append(V0)
    Ws.append(W0)
    Cs.append(C0)
    Ps.append(P0)
As, Bs = [QR(1)], [QR(0)]
for i in trange(1, m):
    As.append(Vs[i] / Vs[0])
    Bs.append(Vs[i] / Vs[0] * Cs[0] - Cs[i])

M = []
for i in trange(m):
    Av = list(As[i]) + list(-As[i])
    Bv = list(Bs[i])
    coeff = list(As[i] * QR(list(As[i])[::-1]))[::-1]
    coeff += list(As[i] * QR(list(Bs[i])[::-1]))[::-1]
    #coeff.append(vector(Bs[i]) * vector(Bs[i]))
    M.append(coeff)

M = Matrix(GF(Q), M)
target_v = vector(GF(Q), [140 - vector(Bs[i]) * vector(Bs[i]) for i in trange(m)])
x = M.solve_right(target_v)
Y1_0 = QR(list(x[N:])) / 2
U_0 = Y1_0 + Cs[0]
G = Vs[0] / U_0
D = E * G - A

sig_Dint = sum([ZZ(j) * Q ** i for i,j in enumerate(ntt(D).list())])
sig_Dbyt = sig_Dint.to_bytes(-(-len(bin(sig_Dint)[2:]) // 8), 'big')
r.sendlineafter(b'> ', b'c')
r.sendlineafter(b') ', sig_Dbyt.hex().encode())
r.interactive()