Is this variant of Diffie-Hellman viable and quantum resilient?

Question

In this paper the author suggests using a variant of Diffie-Hellman which involves floating-point numbers of arbitrary size in the generation of a shared secret. There are no primes, calculations are performed$\bmod{1}$

In simple terms:

1. Alice picks $x$ (a decimal number) and $a$ (a random integer). She generates $a'=ax\bmod{1}$ and sends to Bob along with x.
2. Bob generates $b'=bx\mod{1}$ and sends to Alice.
3. $a'b \mod{1} \equiv b'a\bmod{1}$, accurate to a certain number of digits depending on the size of $a$ and $b$.

I've checked and remarkably (to me at least) the symmetry works.

In the concluding paragraph, the author suggests that this method is resilient to quantum computers:

Apart from being resilient to quantum computers, the great achievement of the suggested protocol as opposed to the Diffie–Hellman finite fields methodology is the use of the decimal part of a transcendental number rather than large finite integers. The use of transcendental numbers does not, by nature, restrict the number of digits in the calculation as do integers. In the case with finite fields, the secret numbers are limited by the order of the finite field q. For brute force guessing, one only has to systematically try all numbers less than q. With the proposed method, there is another bound indicated by the number of digits in the transmitted numbers $a_ 0$ and $b_0$ . However, the cryptanalysis made possible by Shor’s and Grover’s algorithm does not seem to be a threat to this procedure.

Questions

1. Is this actually a viable method of key exchange?
2. Is it really resilient to quantum computers?
3. Is the $\bmod{1}$ calculation as described a known one-way/symmetrical function, and is it used elsewhere?

Answer 1

1. Is this actually a viable method of key exchange?

No. An eavesdropper can find the integer $b$ chosen by Bob from $x$ (as sent by Alice) and $b'$ (as sent by Bob), and the equation $b'\,=\,b\,x\bmod 1$ (meaning $\exists d\in\mathbb Z,\ b'+d=b\,x$). The shared $k$ can then be determined from the $a'$ sent by Alice, just as Bob does.

If we take the numbers in the paper's example (section 5), given the first 14 decimals $B$ of $b'$ (out of the 61 sent by Bob) and the 24 first decimals $X$ of $x$ (out of about 71 received by Bob and 30 shown), we get $b$ as follows:

• $B$ is the 14 first decimals of $b'$, thus $\big|B-10^{14}\,b'\big|<1$
• $X$ is the 24 first decimals of $x$, thus $\big|X-10^{24}\,x\big|<1$
• $b'+d=b\,x$ implies $10^{24}\,(b'+d)=10^{24}\,b\,x$
• thus $10^{10}\,(10^{14}\,b')+10^{24}\,d=(10^{24}\,x)\,b$
• thus $\big|10^{10}\,B+10^{24}\,d-X\,b\big|\le10^{10}$

One method to solve such Diophantine inequality for $b$ (we don't care for $d$) uses continued fractions¹. But we can be lazy and ask Wolfram in near-natural language
|10^10*62932060503117+10^24*d-693147180559945309417232*b|≤10^10 and b>0 Diophantine
and it gives us $b=6913952452$; or use Mathematica to the same effect, Try It Online!

B = 62932060503117;                 (* 14 first decimals of b' *)
X = 693147180559945309417232;       (* 24 first decimals of x  *)
Solve[Abs[10^10*B+10^24*d-X*b]≤10^10 && b>0 && b<10^11, {b,d}, Integers]
…
{{b -> 6913952452, d -> 4792386648}}

More generally, if $a$ and $b$ have $n$ digits, and we want the shared $k$ to agree over $m$ digits with residual odds of the contrary in the order of $10^{-j}/5$ (where that $/5$ assumes rounding to the nearest), then Alice and Bob should agree on $x$ over $2n+m+j$ digits, and send $a'$ and $b'$ over $n+m+j$ digits.

The paper's example targets $m=30$ shared digits in $k$, uses $j=21$ (thus almost always reaches its target), and $n=10$, which is small enough that brute force is usable to find $b$. But the attack above (or the explicit method¹) works in time only polynomial in the number of digits used. Try It Online! with $m=50$, $j=21$, $n=70$: it still takes under 1 second to recover $b$.

The paper should have been screened by the review process of a would-be scientific peer-reviewed journal on cryptography. I conclude Article Processing Charges do not ensure quality. I am not aware of similar mishaps in peer-reviewed publications of the IACR (thus excluding eprint), but that happens more than occasionally in many other publications. See Wikipedia's article on the publisher, and the publisher's response.

---

2. Is it really resilient to quantum computers?

In a sense yes for today's quantum computers, since they are unable to compute exact results on more than a few bits. In a distant future, perhaps no. That is: the scheme is not quantum-resilient. It's not even resistant to classical computer.

---

3. Is the $\bmod1$ calculation a known one-way/symmetrical function, and is it used elsewhere?

In cryptography, schemes that manipulate reals to a precision better than an FPU register are the exception rather than the norm, and always are internally implemented as integers divided by some integer scaling factor (often a power of a base). Therefore $\bmod1$ is implemented as modular reduction modulo the scaling factor.

Modular reduction modulo an integer is a common building block for one-way functions, such as (in Diffie-Hellman) $k\mapsto g^k\bmod p$ where $p$ is prime, $q=(p-1)/2$ is prime, and $g^q+1\bmod p=0$. But modular multiplication by a public constant (as used in the question's article) is not one-way.

---

Following the author's comment: the question, and this answer, assume $x$ is public. If $x$ is secret, the scheme is indeed less insecure, and even secure on first use of $x$ when the right parameterization is used. But with the parameterization in the example, we don't need $x$ to find the shared value². And even with good parameterization, if $x$ is reused, security quickly breaks down. The second part of the article's “The security benefits from distributing $x$ via a secure channel, but this is not necessary” is untenable.

---

¹ It took me more time than I had hoped to reconstruct an explicit method:

• Using continued fractions, write $\frac X{10^{24}}$ as the simplest fraction $\frac r s$ such that $\left\lfloor\frac{10^{24}\,r}s\right\rceil=X$. This is essentially the most compact representation of $x$ as an integer fraction giving it to 24 decimal places. Here $\frac r s=\frac{698526063389}{1007760087583}$
• Round $\frac{s\,B}{10^{14}}$ (here 634204188043.9984…) to the nearest integer $t=\left\lfloor\frac{s\,B}{10^{14}}\right\rceil$.
• Without proof: there remains to solve for $b$ the Diophantine equation $s\,d+t=r\,b$, here $1007760087583\,d+634204188044=698526063389\,b$
• Reducing modulo $s$, we get $t\equiv r\,b\bmod s$, with $r$ and $s$ coprime by construction of $\frac r s$, thus $r^{-1}\,t\bmod s=b$ when $b<s$ (without proof: which holds with high probability when enough digits of $x$ are known in order for the scheme to work reliably). Here $b=6913952452$.

---

² Assume we have $a'$ and $b'$ to 61 digits as in the example, but not $x$. :

• Using continued fraction, express what's known of $a'$ (61 digits each) as a reduced fraction $a'=\frac e f$ with $f^2<10^{61}$, same for $b'=\frac g h$.
• From $a'+c=a\,x$ and $b'+d=b\,x$ with $0<x<1$, for at-most-10-digit $a$ and $b$, it holds the Diophantine inequality $\big|b\,h\,(e+c\,f)-a\,f\,(g+d\,h)\big|<2\cdot10^{10}$ with $0\le c\le a<10^{10}$, $0\le d\le b<10^{10}$
• Reducing this $\bmod f$ and $\bmod h$, it comes that for some unknown integer $r$ with $\big|r\big|<2\cdot10^{10}$, it holds $a\,g\,f\equiv r\pmod h$ and $b\,e\,h\equiv-r\pmod f$.
• With $\ell\gets\gcd(f,h)$, $f'\gets f/\ell$, $h'\gets h/\ell$, and $s$ defined as $r/\ell$, it comes that for some integer $s$ with $\big|r'\big|<2\cdot10^{10}/\ell$, it holds $a=((g\,f')^{-1}\,r'\bmod h')$ and $b=((-e\,h')^{-1}\,r'\bmod f')$.
• With $g'\gets(g\,f')^{-1}\bmod h'$ and $e'\gets(-e\,h')^{-1}\bmod f'$, it comes $a=(g'\,r'\bmod h')$ and $b=(e'\,r'\bmod f')$.
• This now can be solved by Mathematica, Try It Online!. This gives 4 possible values for the shared $k$, and 10 for $x$.

Answer 2

Just a quick comment on:

3. Is the $\bmod 1$ calculation as described a known one-way/symmetrical function, and is it used elsewhere?

fgrieu mentions in his answer:

Modular reduction modulo an integer is a common building block for one-way functions, such as (in Diffie-Hellman) $k\to g^k\bmod p$ where $p$ is prime, $q=(p−1)/2$ is prime, and $g^q+1\bmod p=0$. But modular multiplication by a public constant (as used in the question's article) is not one-way.

What I am about to say does not contradict this, but instead shows that upon (slight variation) modular "multiplication" is thought to be one-way. As fgrieu mentions, $a\bmod 1\equiv b\iff pa\bmod p\equiv bp$ for $p\in\mathbb{N}$, so the difference between $\bmod 1$ and $\bmod p$ is one of scaling.

If we consider the scaled modular equation $ax\bmod p\equiv b$ and further restrict everything to be integers (so no arbitrary floats to start $\bmod 1$, unless the scaling factor is large), there are a few ways of modifying this slightly to achieve a function which is thought to be one-way.

1. LWE-based cryptosystems --- instead, use the function $\langle \vec{a}, \vec{b}\rangle + e\bmod p \equiv b$. Here, you're given a modular scalar product (not multiplication), which is additionally "noisy" ($e$ is drawn from some "concentrated" error distribution).

2. RLWE-based cryptosystems --- here, the function is of the form $a\cdot b + e\bmod I$, where $I$ is an "ideal in an algebraic number field", and $a, b, e$ are "integer" polynomials. Formalizing this more requires more work, but one can change the (integer) scalar product to an "actual multiplication" for things which are mathematically "generalized" forms of integers

3. RLWR-based cryptosystems --- here, the function is of the form $\lfloor a\cdot b\rceil \bmod I$, where $\lfloor\cdot \rceil$ "rounds" the product in a standard (publicly known) way (I believe it is just applying the function which rounds each coordinate to the closest integer).

To answer your particular question, it depends on the author. I have seen some that have described schemes of the above form in terms of $\bmod 1$ computations (for example the TFHE scheme if I recall correctly).

The above schemes end up having a lot of different possible variants - not all of them are thought to be secure!

A quick description of the various parameters you can choose (there can actually be more than this unfortunately, but these are somehow the "core" ones):

1. The size of the modulus $q$;
2. The "size" of the noise $\sigma$ (generally seen as a fraction of $q$ --- if you can take $\sigma$ arbitrarily large things get information-theoretically secure, but we no longer know how to build crypto from it);
3. The "dimension" of $a, b$ (either as vectors $\vec{a}, \vec{b}$, or as "generalized integers);
4. The particular choice of "generalized integer" to use (there is a community standard, but not 100% of the community backs this standard).

You cannot build "true" DH-type schemes which are post-quantum from this, but you can build "noisy"-DH type schemes. The big difference here is that the "noisy" schemes seem to require another half round trip of communication before data can be sent (I believe).

I think there are ways to get around this half round trip by having clients hold long-term public keys of servers, or by using a separate type of PQ cryptography known as "isogeny-based crypto" (the above is "lattice based"), but I am not familiar with isogenies.