Trapdoors for lattices

Question

I refer to an article https://eprint.iacr.org/2011/501. I focus on (a bit modified) Algorithm 1 which runs as follows (in my understanding): For given $n, m\in \mathbb N$, $q=2^k$ and a distribution $\mathcal D$, algorithm chooses a uniformly random matrix $\overline {\mathbf A}\in \mathbb Z_q^{n\times m-nk}$ and a matrix $\mathbf R \in \mathbb Z_q^{m-nk \times nk }$ from the $\mathcal D$ and outputs a matrix $\mathbf A=[\overline {\mathbf A}\| \mathbf G - \overline {\mathbf A}\mathbf R] \in \mathbb Z_q^{n\times m}$ and a trapdoor $\mathbf R \in \mathbb Z^{m-nk\times nk}$.

If $\mathbf G$ is public and $\overline {\mathbf A}$ can be derived from $\mathbf A$ since $\mathbf A = [\overline {\mathbf A} \| \mathbf A_1]$, why one can not obtain $\mathbf R$? It is important due to $\mathbf R$ contains all information about short basis of $\mathbf A$, which usually treated as a private key, while $\mathbf A$ is a public key.

Answer 1

It is computationally infeasible to find $R$ (or any other short matrix that satisfies the relation) because solving $A R = V \pmod{q}$ for uniformly random $A, V$ is the SIS problem (in its inhomogeneous version). SIS is provably as hard as solving worst-case approximation problems on lattices.

(Also, for the parameters considered in the paper, $[\bar{A} \mid -\bar{A}R]$ is very close to uniform, so finding a valid trapdoor given $A$ really is equivalent to the SIS problem.)