5
$\begingroup$

Added Wed 13 Apr 2022

I have written a short note with experimental data, which shows not all pseudo keys are good keys.

Public key cryptography based on non-invertible matrices

We got public key cryptography scheme based on non-invertible matrices and would like to know how easy it is to break.

Working over $\mathbb{F}_p$ with $p$ large. All matrices are square $n \times n$.

Alice chooses matrices $M_A,X_A$ and makes $P_A=M_A X_A$ public.

Bob chooses matrices $M_B,X_B$ and makes $P_B=M_B X_B$ public.

Assume $M_A,M_B$ are not invertible and satisfy $M_A M_B=M_B M_A$.

To ensure this, take the field to be finite and Alice and Bob agree on a singular matrix $M_0$ and Alice chooses large integer $N_A$ and set $M_A=M_0^{N_A}$ and Bob chooses large integer $N_B$ and set $M_B=M_0^{N_B}$. Since powers of matrices commute, $M_A,M_B$ commute. Observe that this is different from the discrete logarithm since $M_A,M_B$ are unknown.

Assume that $X_A,X_B$ are invertible.

To exchange shared secret, Bob makes public $S_B=M_B P_A=M_B M_A X_A$ and Alice computes $S_B X_A^{-1}=M_B M_A$

Likewise, Alice makes public $S_A=M_A P_B=M_A M_B X_B$ and Bob computes $S_A X_B^{-1}=M_A M_B$.

At this point, Alice and Bob have the shared secret $M_A M_B=M_B M_A$, which is expected to be hard to find by adversary.

Also, everyone, including an adversary know

$P_A=M_A X_A,P_B=M_B X_B,S_A=M_A P_B,S_B=M_B P_A$.

If $P_B$ were invertible, adversary could break the scheme by computing $S_A P_B^{-1}=M_A$.

Q1 What is complexity of breaking this crypto scheme, i.e. given $P_A,P_B,S_A,S_B$, find $M_A M_B$?

Q2 Can we replace matrices by some object and make a crypto scheme based on non-invertibility?

We are interested in choices of the matrices and the field for which breaking the scheme is hard.

Treating the matrices as variables, we get $4n^2$ equations with $4n^2$ variables and $2n^2$ of the equations are linear and the other equations are quadratic.

We got partial results about hardness.

The problem is given $P_A,P_B,S_A,S_B$, find $M_A M_B$.

Experimentally with a toy implementations, we found many solutions which satisfy the construction, but don't give the shared secret. If the number of potential solutions is large, the scheme will be hard to break. For $p=3,n=3$, we got $27$ total solutions and for $p=2,n=4$ we got $256$ total solutions.

In addition, there is algebraic attack. We have four unknown matrices, set all their entries to variables.

We have four equations over matrices, two of which linear. From the linear equation eliminate variables using gaussian elimination, which leaves $2n^2$ quadratic equations.

sagemath toy implementation with many solutions:

https://pastebin.com/raw/Mb8yp3Gt

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ Since $M_A$ and $M_B$ are square matrices what you gain from the additional size of $n$ contributed by their null-spaces? $\endgroup$
    – Kapil
    Mar 28, 2022 at 8:11
  • 4
    $\begingroup$ If Alice chooses $M_A$ and Bob chooses $M_B$, what insures that they commute? $\endgroup$
    – Steven Landsburg
    Mar 28, 2022 at 12:31
  • 1
    $\begingroup$ @StevenLandsburg I think I solved your commuting issue by editing with taking M_A,M_B to be powers of matrix M_0 and powers of matrices commute. $\endgroup$
    – joro
    Mar 28, 2022 at 16:28
  • 3
    $\begingroup$ Couldn't you also solve that by "picking sides", i.e. one key is $P_A = X_AM_A$ and the other $P_B = M_BX_B$, and then communicate $S_B = P_AM_B = X_AM_AM_B$ (invert on the left to find $M_AM_B$) and $S_A = M_AP_B = M_AM_BX_B$ (invert on the right to find $M_AM_B$)? It just requires one extra bit of public communication (who is left and who is right), and greatly increases the set of admissible matrices. $\endgroup$
    – R. van Dobben de Bruyn
    Mar 28, 2022 at 21:04
  • 1
    $\begingroup$ @JosephVanName thanks, you are right. i edited the note, writing "Experimental data suggests the algorithm is not ready for usage" $\endgroup$
    – joro
    Apr 13, 2022 at 5:32

1 Answer 1

Reset to default
1
$\begingroup$

This key exchange is broken.

For this problem, let $\langle M_{0}\rangle$ denote the algebra generated by $M_{0}$.

Set $Z_{A}=X_{A}^{-1},Z_{B}=X_{B}^{-1}$. Then $M_{A}=P_{A}Z_{A},M_{B}=P_{B}Z_{B}$. In particular, $S_{B}=P_{B}Z_{B}P_{A}$.

A pseudo key is a matrix $Z_{B}^{p}$ such that $P_{B}Z_{B}^{p}\in\langle M_{0}\rangle$ and where $S_{B}=P_{B}Z_{B}^{p}P_{A}$. The affine space of all pseudo keys can be computed simply by solving a system of linear equations.

If $Z_{B}^{p}$ is a pseudo key, then $$M_{B}M_{A}=P_{B}Z_{B}P_{A}Z_{A}=S_{B}Z_{A}=P_{B}Z_{B}^{p}P_{A}Z_{A}=P_{B}Z_{B}^{p}S_{A},$$ so the secret key $M_{B}M_{A}$ is recoverable from a pseudo key $Z_{B}^{p}$ and the public information $S_{A}$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. How do you explain the experimental observation that there are many solutions to the construction, but only few give the shared secret? $\endgroup$
    – joro
    Mar 31, 2022 at 3:54
  • $\begingroup$ What do you mean by " An adversary will be able to recover MAMBy if the adversary has access to a pair like (MB,z)"? The public information is only 5 matrices (M0,P_A,P_B,S_A,S_B)? $\endgroup$
    – joro
    Mar 31, 2022 at 4:52
  • $\begingroup$ Also, do you break the discrete logarithm for singular matrices? Can you find X such that M_0^X=A with M_0 singular? In the exchange you can fix one of the keys to be of your choice. $\endgroup$
    – joro
    Mar 31, 2022 at 7:20
  • 3
    $\begingroup$ The discrete logarithm for singular matrices is not harder than the discrete logarithm for invertible matrices. If $M_{0}$ is a singular $n\times n$-matrix, then to solve $M_{0}^{X}=A$, one first puts $M_{0}$ into Jordan normal form. One can then test the cases when $X\leq n$ one by one, but if $X\geq n$, then all the Jordan blocks in $M_{0}^{X}$ with eigenvalue $0$ will become zero, so the problem for $X\geq n$ then reduces to the problem about solving the discrete logarithm for invertible matrices. $\endgroup$
    – Joseph Van Name
    Mar 31, 2022 at 11:40
  • 3
    $\begingroup$ An addition to what Joseph Van Name wrote, no reason to go all the way to Jordan form. Just use find bases for $\text{Ker}(M^n)$ and $\text{Im}(M^n)$. These will be complementary, so we can use them to block diagonalize $M$ as $\left[ \begin{smallmatrix} U&0 \\ 0&N \end{smallmatrix} \right]$ with $U$ invertible and $N$ nilpotent. $\endgroup$
    – David E Speyer
    Mar 31, 2022 at 12:10

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.