Partially inspired by ring learning with errors (RLWE), I am trying to construct a cryptosystem that requires the use of a non-invertible matrix.

Of the methods I've thought of to generate a matrix of determinant $0$, erasing a row/column or two seems the easiest, but I have no idea on how non-invertible this is.

I would like to know about known methods of reconstructing an unknown square matrix with known structure from its product with a non-square matrix.

  • $\begingroup$ You have a matrix equation $\rm A X = B$ and want to solve for $\rm X$? $\endgroup$ Sep 15, 2017 at 9:54
  • $\begingroup$ @RodrigodeAzevedo I have a non-square A and B, and I want to make sure nobody can find any X. $\endgroup$
    – DannyNiu
    Sep 16, 2017 at 4:01
  • $\begingroup$ Over what field? $\endgroup$ Sep 16, 2017 at 8:40
  • 1
    $\begingroup$ Suppose $\rm X$ is $n \times n$. Then you have $n$ linear systems $\rm A x_k = b_k$. If $\rm A$ is fat, these linear systems are underdetermined. If the null space is sufficiently high-dimensional, searching over all possible solutions may be sufficiently expensive. $\endgroup$ Sep 16, 2017 at 11:04
  • 3
    $\begingroup$ Computing the "pseudoinverse" of non-square matrices is done all the time when fitting linear regression models: en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse EDIT: Point being, there is some existing work in linear algebra on computing "inverses" of non-square matrices. $\endgroup$
    – pg1989
    Sep 18, 2017 at 4:14

1 Answer 1


As far as I know, there is no well-behaved and canonical topology on finite fields that would enable a consistent and useful definition of pseudoinverse. The main point in computing pseudoinverses over the complex or real field is that they minimize some second moment error functional, since there is no unique inverse defined.

However, and I may regret this, but there is a recent 2015 conference paper from the Springer Lecture Notes in Electrical Engineering book series (LNEE, volume 339)[behind paywall] which claims to construct such a beast, subject to some strong conditions, but there is no proof of any error minimizing properties for such an inverse, and I'd be really surprised if it results in a meaningful definition of pseudoinverse for lattice based cryptosystems, though it might be worth looking into. A quick look at the paper titles show that this is a very generic and broad conference, not really focused on cryptography, but that may well not be important.

title of paper


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.