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.


1 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.)

  • $\begingroup$ Maybe it is a silly question, but why finding the inverse of $A$ (or the pseudoinverse) doesn't work for solving that equation? $\endgroup$
    – cygnusv
    Oct 29, 2014 at 8:11
  • 3
    $\begingroup$ Using any purely linear-algebraic method will result in a large solution R, when a "short" one is required. $\endgroup$ Oct 29, 2014 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.