Score:2

Crypto

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

DannyNiu

3/18/23, 9:25 AM

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?

0 + 0

key-exchange

lwe

DannyNiu

3/18/23, 9:28 AM

I realize I've made some mistake about the feasibility of Squre-Diffie-Hellman attack. I plea to people familiar with the topic edit out the factually wrong parts in my question.

Score:4

Crypto

Mark

3/18/23, 7:51 PM

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

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).
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.

0 + 0

Score:3

Crypto

Ievgeni

3/18/23, 6:06 PM

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.

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: *-LWE เทียบเท่ากับ Diffie-Hellman $g^{x^2}$ ช่องโหว่

RO: *-LWE echivalent al vulnerabilității Diffie-Hellman $g^{x^2}$

RU: *-LWE эквивалент уязвимости Диффи-Хеллмана $g^{x^2}$

VI: *-LWE tương đương với lỗ hổng Diffie-Hellman $g^{x^2}$

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.