I'm considering a variation of the Diffie-Hellman key exchange protocol based on integer modular multiplication in place of exponentiation. If done naively, that would obviously be insecure, but I'm wondering if it is possible to recover security by erasing the least significant bits before transmitting a product. The idea is inspired by RLWE, where introducing random errors can transform a trivially insecure protocol into a possibly secure (maybe even quantum-proof) one; only here instead of addition of random errors I'm proposing deterministic erasure of the lower part of the data.
Here are the details: Let $n \in \mathbb N$ be fixed (say $n=1024$), and let $M=2^{3n} -1$. We will use the notation $x \bmod M$ to denote the unique integer $y$ in $0, 1, \dots, M-1$ with $x \equiv y \pmod M$.
- Alice and Bob begin with a shared public value $g \in \mathbb N$ with $0 \leq g < M$. (Whoever initiates the protocol should choose $g$ uniformly at random and send it to the other party.)
- Alice chooses a secret integer $0 \leq s_1 < 2^n$ uniformly at random, computes $x_1 = gs_1 \bmod M$, rounds $x_1$ to a nearest multiple of $2^n$, and sends the result $\tilde x_1$ to Bob.
- Bob chooses a secret integer $0 \leq s_2 < 2^n$ uniformly at random, computes $x_2 = gs_2 \bmod M$, rounds $x_2$ to a nearest multiple of $2^n$, and sends the result $\tilde x_2$ to Alice.
- Alice computes $y_1 = \tilde x_2 s_1 \bmod M$, rounds $y_1$ to a nearest multiple of $2^{2n}$, and stores the result $\tilde y_1$.
- Bob computes $y_2 = \tilde x_1 s_2 \bmod M$, rounds $y_2$ to a nearest multiple of $2^{2n}$, and stores the result $\tilde y_2$.
It can be shown that $\left\lfloor \frac{\tilde y_1}{2^{2n}}\right\rfloor$ and $\left\lfloor \frac{\tilde y_2}{2^{2n}}\right\rfloor$ differ by at most 1 (modulo $2^n$), and from this Alice and Bob can easily agree on a secret key of length $n-1$.
I'm wondering if anything is known about the security of this protocol? Has anything been published about this sort of technique, or is there some obvious attack that breaks it?
The most straightforward avenue for an adversary to break it would seem to be if they had some way where, given integers $g$ and $\tilde x$ in the interval $[0, M)$ they could find $s$ with $0 \leq s \leq 2^n$ such that the most significant $2n$ bits of $gs \bmod M$ agrees with $\tilde x$ (assuming that such $s$ exists, which it will if $\tilde x$ was produced as one of the $\tilde x_i$ in the protocol). Here the restriction $0 \leq s \leq 2^n$ is the part that is intended to make it hard; it would be easy for anyone to find an $s$ in $[0, M)$ such that $gs \equiv \tilde x \pmod M$, but that would not appear to be sufficient to succeed in an attack.
Edit: We run into trouble if $g$ or $s_i$ happen to share a large divisor with $M$. To fix this, we could replace $M$ with a prime number (say, the largest prime less than $2^{3n}$) or restrict $g$ and $s_i$ to be relatively prime to $M$.
