-1
$\begingroup$

Closely related to this question and extending comment of R. van Dobben de Bruyn.

Working over $\mathbb{F}_p$ and all matrices of square $n \times n$.

Alice chooses invertible $X_A$ and non-invertible $M_A$ and makes public $P_A = X_A M_A$.

Bob chooses invertible $X_B$ and non-invertible $M_B$ and makes public $P_B = M_B X_B$.

Alice makes public $S_A=M_A P_B=M_A M_B X_B$.

Bob makes public $S_B= P_A M_B=X_A M_A M_B$.

To compute the shared secret $S = M_A M_B$, Allice compute $S=X_A^{-1} S_B$ and Bob computes $S=S_A X_B^{-1}$

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$?

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

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.

We believe the set of solutions to be more than one and not all solutions lead to the shared secret.

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
2
$\begingroup$

This key exchange algorithm is broken for matrices using the same technique as I described in the answer to your previous question.

As before, let $Z_{A}=X_{A}^{-1},Z_{B}=X_{B}^{-1}$.

Observe that $S_{A}=M_{A}P_{B}=Z_{A}P_{A}P_{B}$. Observe that $S_{B}=P_{A}M_{B}=P_{A}P_{B}Z_{B}$ as well.

A pseudo private key for Alice is a matrix $Z_{A}^{p}$ such that $S_{A}=Z_{A}^{p}P_{A}P_{B}$.

A pseudo private key for Bob is a matrix $Z_{B}^{p}$ such that $S_{B}=P_{A}P_{B}Z_{B}^{p}$.

An adversary can easily compute the affine space of all pseudo private keys for Alice and the affine space of all pseudo private keys for Bob just by solving a collection of linear equations.

If $Z_{A}^{p}$ is a pseudo private key for Alice, then

$$M_{A}M_{B}=M_{A}P_{B}Z_{B}=S_{A}Z_{B}=Z_{A}^{p}P_{A}P_{B}Z_{B}=Z_{A}^{p}S_{B}.$$

If $Z_{B}^{p}$ is a pseudo private key for Bob, then $$M_{A}M_{B}=Z_{A}P_{A}M_{B}=Z_{A}S_{B}=Z_{A}P_{A}P_{B}Z_{B}^{p}=S_{A}Z_{B}^{p}.$$

Therefore, an adversary who knows a little bit of linear algebra can recover the shared key $M_{A}M_{B}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Define the pseudo keys as the quadruples of matrices which satisfy the construction. Do you agree there are pseudo keys, which are not real keys and don't give the shared secret M_A M_B? $\endgroup$
    – joro
    Commented Apr 4, 2022 at 17:50
  • $\begingroup$ I agree that there are probably pseudo private keys that are not real keys. But pseudo private keys still break this key exchange by recovering $M_AM_B$ since $M_AM_B=Z_A^pS_B=S_AZ_B^p$. $\endgroup$
    – Joseph Van Name
    Commented Apr 4, 2022 at 18:33
  • $\begingroup$ It is easy to make a key exchange algorithm where it is not feasible for an attacker to recover Alice and Bob's private keys. Alice's private key can simply be a 256 bit string $\mathbf{s}_{A}$, and then Alice can set $X_{A}=H_{0}(\mathbf{s}_{A}),M_{A}=H_{1}(\mathbf{s}_{A})$ where $H_{0},H_{1}$ are cryptographic hash functions. In this case, even if an adversary can obtain $X_{A},M_{A}$, such an adversary will not be able to recover the private key $\mathbf{s}_{A}$, but recovering $\mathbf{s}_{A}$ is not relevant recovering $M_{A}M_{B}$. $\endgroup$
    – Joseph Van Name
    Commented Apr 4, 2022 at 18:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .