Trapdoors for lattices
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.)