Again, I do not know how to solve this problem. Leave it to the future me to digest how to solve lattice problems and understand a bit more about group theory. The original attack is from Shamir et al., but a low-density attack that leverages the LLL algorithm. A version is mentioned in this awesome paper. Sage Implementation: a = [ #public key ] s = #ciphertext n = len(a) N = ceil(sqrt(n) / 2) b = [] for i in range(n): vec = [0 for _ in range(n + 1)] vec[i] = 1 vec[-1] = N * a[i] b.

I did not manage to solve this challenge. The private key is composed by some $f, g$, both smaller than $\sqrt{\frac{q}{2}}$, with the relation that $fh - g = 0 \mod q$ This means that there exists a $k$ such that $fh = qk + g$, since $h$ is about the same size of $q$, we have that $k$ is the same size of $f$. We have the observation that $f \cdot (h, 1) + (-k) \cdot (q, 1) = (g, f - k)$, where both components of the result are small (g is around the square root of $\frac{q}{2}$, and $f$ is approximately $k$).