For implementation of McEliece cryptosystem, I'm trying to generate a random binary invertible matrix and its inverse. Because this is usually the most time-consuming part of generating a McEliece keypair (matrix size is usually around $2^{13}\times2^{13}$), I'm searching for ways to do it faster.

So far, I've tried to use following approaches:

  • Generate an upper triangular matrix $U$ with random ones and zeroes in the upper triangle, and ones on diagonal (such $U$ is invertible), symmetrically generate $L$ lower triangular matrix, compute $M = UL$ and invert M by standard inversion. This is slow.
  • Compute $M = UL$ and $M^{-1} = L^{-1}U^{-1}$. In this case, the inversion is a lot faster (there's no need to compute full row operations, as the inverse remains lower/upper triangular shape), but still slow.
  • Have two identity matrices $I_1,I_2$, perform a number of random row operations on $I_1$, and symetrically perform those inverse row operations on $I_2$, so that equation $I_1^{-1} = I_2$ holds. I'm not sure what number of row operations should be done on the matrices so that the result would be completely random -- my best guess is that $n^2$ operations should be sufficient, giving algorithm complexity $O(n^3)$. If there was some lower limit so that the matrix would be random-enough, this approach could be the fastest.

Questions are:

  • Is there some better algorithm, or is the $O(n^3)$ bound impossible to break?
  • What is the lowest possible count of operations in the third algorithm so that the matrix gets undistinguishable from a random matrix from the first algorithm?




Your Answer

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

Browse other questions tagged or ask your own question.