5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You have a matrix equation $\rm A X = B$ and want to solve for $\rm X$? $\endgroup$ – Rodrigo de Azevedo Sep 15 '17 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 '17 at 4:01
  • $\begingroup$ Over what field? $\endgroup$ – Rodrigo de Azevedo Sep 16 '17 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$ – Rodrigo de Azevedo Sep 16 '17 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 '17 at 4:14
2
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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