0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

... instead of addition of random errors I'm proposing deterministic erasure of the lower part of the data.

Truncation instead of addition of noise is an optimization that some LWE schemes use already.

... 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 more pertinent difference in your proposal is that it uses a one dimensional vector. There does exist a dimension/modulus size tradeoff for the LWE problem. But the problem is very sensitive to the concrete parameters that you instantiate it with.

An obvious algebraic attack might not be able to solve the problem, but you might be surprised at what the LLL algorithm can do. Understanding how to use LLL to actually do so is challenging. There are lots of papers about it.

$\endgroup$
  • 1
    $\begingroup$ This is very helpful. I was overlooking how direct the relationship is to LWE. I'm thinking now that this can probably be broken using LLL, like you suggest. Namely, we can define a two-dimensional lattice, generated by $(M, 0)$ and $(g, 1)$, and ask for the closest lattice point to $(-\tilde x, 0)$. In two dimensions this CVP can efficiently be solved exactly, and I believe it can be expected to result in the point $(-x, s)$, revealing $s$. $\endgroup$ – Brent Kerby Jul 2 '18 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.