*-LWE equivalent of Diffie-Hellman $g^{x^2}$ vulnerability

Question

In Is Diffie-Hellman less secure when A and B select the same random number? , the possibility of Diffie-Hellman key exchange producing identical peer keys and the vulnerability of it against passive attackes was brought up, again - as a duplicate.

But is there a equivalent in *-LWE family of lattice-based key exchanges? My question being, without considering CCA-hardening such as Fujisaki-Okamoto transformation and LPR-like encryption scheme, does a plain *-LWE key exchange:

• Q1: have equivalent vulnerability?

• Q2: what mathematical property of *-LWE key exchange made such vulnerability possible or impossible?

Answer 1

Given $(A, Ax + e)$ and $(A, x^tA+e')$, you can do (at least) one potentially interesting thing to solve LWE. Namely, compute the sample

$$(A+ A^t, Ax + e + (x^tA+e')^t) = (A+A^t, (A + A^t)x + e + {e'}^t)$$

so you can reduce LWE to a case of LWE where the random matrix $A + A^t$ is symmetric. It isn't really clear to me that this helps you cryptanalytically --- it introduces some structure into the problem, but

1. it seems like less structure than assumptions like RLWE/MLWE introduce (for example, an $n$ dimensional symmetric matrix is determined by $O(n^2)$ parameters, while if you view an RLWE sample as a "matrix" it has $O(n)$ parameters).
2. it is not clear how the structure would be useful.

By this last point, I mostly mean that I am unaware of symmetric random linear codes (or random lattices) being easier to solve CVP on. If this were true, it would immediately imply the vulnerability you are interested in.

Answer 2

First I would like to define more precisely the "same $x$" attack.

First interpretation

Alice and Bob know their $x$ are the same. It doesn't make sense, because in this scenario, they already share secret information (they can already compute common public key $g^x$ without any communication).

Second interpretation

Now, let suppose, the adversary can force (we do not know how) $x$ to be equal to $y$ (But Alice and Bob do not know that and then communicate $g^x$). Then the goal for the adversary is to compute $g^{x^2}$ by knowing $g^x$. This problem is known to be hard in the generic model (you can look for example this), and then is probably also hard for concrete well-chosen group.

Third interpretation

Alice and Bob respect the protocol, but they unlucky choose the same $x$, it's remarkable than the adversary can easily detect this case. But computing $g^{x^2}$ is hard as in the second case.

About LWE

I will consider this version of the DH-key exchange:

About the first interpretation, it doesn't make sense as for DH.

An important remark is the fact, that even Alice and Bob have the same $x$, the partial keys sent are not identical (contrarily to the ones in DH). First because they computes $x^\perp A$ and $Ax$, and also because there is no reason they have the same noise.

For this reason, the detection of the equality in the third case is not trivial, (at least not trivial as in the DH case).

About the fact to compute the secret $x$ in the second case. It seems hard, but as far as I know there is no result about the hardness of this specific problem.

We can reformulate both problems. Given a square matrix $A$, is it hard to distinguish $(Ax+ 2e, x^\perp A+ 2e')$ and $(Ax+ 2e, y^\perp A+ 2e')$? And given $(Ax+ 2e, x^\perp A+ 2e')$ is it hard to guess the least significant bit of $x^\perp Ax$.

I'm tempted to think both problems are hard. But as far as I know it can not be reduce to any known hard problem.