I'm currently looking at different ways to break Dilithium and found this post: What is the effect of solving short integer solution problem in Dilithium or any other post quantum signature scheme?
However I can't seem to wrap my head around the answer given by Daniel S., he states that:
If one can solve MSIS, powerful attacks are possible: consider the key generation algorithm on page 4 of the specification:
Gen01 $A←R^{k×l}_q$
02 $(\mathbf s_1,\mathbf s_2)\leftarrow S_\eta^l \times S_\eta^k$
03 $\mathbf t := A\mathbf s_1 +\mathbf s_2$
04 return(pk=($A,\mathbf t$),sk=($A,\mathbf t,\mathbf s_1,\mathbf s_2$))
We are given the values $A$ and $\mathbf t$ and wish to recover $\mathbf s_1$ and $\mathbf s_2$ for a key recovery attack (top of the attack outcome hierarchy).
Note that the matrix $$\begin{matrix}(A|I|-T)\end{matrix}$$ where $I$ is the $k\times k$ identity matrix and $T$ is the $k\times k$ diagonal matrix with entries taken from $\mathbf t$ has the short solution $(\mathbf s_1^T,\mathbf s_2^T,1,\cdots 1)^T$.
Since $A|I|$ and $T$ are of different dimensions, how can we subtract the two?
Furthermore, can anyone explain why $(\mathbf s_1^T,\mathbf s_2^T,1,\cdots 1)^T$ would be a small solution or give a simple example of how recovering dilithium secret keys implies solving MSIS?
