2
$\begingroup$

During one of the seminars at my university on Cryptography, the presenter said that while computing $x/y$ over Finite Rings $\mathbb Z_{2^\ell}$, there exist some problems such as:

  1. $y^{-1}$ may not exist as over the ring $\mathbb Z_{2^\ell}$, only odd numbers have inverses and even numbers don’t.

I understand this is required as for the inverse to exist this condition needs to be satisfied: $\gcd(y,2^\ell)=1$

  1. Another problem is regarding the information leakage. Here, the final output of $x/y$ being odd will say that both x and y are odd with very high probability.

I understand this observation comes from the first point only.

Now, I was thinking what if we use IEEE-754 floating point arithmetic on rings to obtain the value $x/y$. Here, instead of first computing $1/y$, we will directly obtain $x/y$ by using different ring sizes for the sign, exponent, and significand values. As far as I know, in IEEE-754 FP arithmetic, we can compute $x/y$ without using any division operation directly, but rather using only addition, multiplication, left & right shift, and XOR operations. We can perform all of these operations on rings. We also don't need any inverse operations here and we can actually perform $x/y$ directly here without the risk of the initial problems discussed in the first two points. In this case, we may lose some accuracy (maybe in the order of $10^{-10}\ldots10^{-15}$), but a close result can be obtained and subsequently, we can prevent such leakages. Am I missing something? I tried searching over the internet for this but it didn't help. Any input on this will be very helpful.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The question is about arithmetic (in particular division) in the ring of integers modulo $2^\ell$, that the question notes $\mathbb Z_{2^\ell}$, and is also known as $\mathbb Z/2^\ell\mathbb Z$. That has little to do with arithmetic in the ring $\mathbb R$, which IEEE-754 approximates. Among other differences there is no notion of sign: $-1$, $2^\ell-1$, $-2^\ell-1$ are assimilated in $\mathbb Z_{2^\ell}$. It's unclear which FP representation for that the question would take, and how it would convert back from FP to $\mathbb Z_{2^\ell}$. The result it would get depends on that. $\endgroup$
    – fgrieu ♦
    Commented Oct 25, 2023 at 15:47
  • $\begingroup$ Related: there is a fast and simple algorithm to compute the modular inverse modulo $2^\ell$. $\endgroup$
    – fgrieu ♦
    Commented Oct 26, 2023 at 6:57
  • $\begingroup$ Without knowing the context of the remark, it's hard to say too much. But the observation of the bias of division probably isn't best solved by doing something "like" division but that isn't division. If you need the mathematical structure then your replacement won't do. And if you just need a way to combine 2 values there are lots of ways to do that and no particular reason to choose one inspired by floating point arithmatic. $\endgroup$
    – bmm6o
    Commented Oct 28, 2023 at 0:54
  • $\begingroup$ Try some examples: modulo 32, the inverse of 5 is 13 and the inverse of 7 is 23. How do you propose that floating-point arithmetic helps? $\endgroup$
    – Sam Jaques
    Commented Nov 19 at 18:24

1 Answer 1

Reset to default
0
$\begingroup$

You have to be careful. Using floating point arithmetic automatically means that you are no longer in the ring and what happens in this arithmetic is completely independent on (say) whether $\gcd(y,2^\ell)=1,$ for example.

It doesn't matter what the floating point error is, if the operational properties you obtain are not the same in the ring $\mathbb{Z}_{2^\ell}$ and in the structure obtained via your floating point approximation, say in a new set $S$, which it won't be in general. The fact that there is a non-exact floating point approximation is enough to destroy the arithmetic properties of the original ring.

Just try representing $x_1 y_1^{-1} + x_2 y_2^{-1}$ and $x_1 y_1^{-1} \times x_2 y_2^{-1}$ directly and compare the representations obtained to that obtained by representing $x_1 y_1^{-1}$ and $x_2 y_2^{-1}$ individually and then computing the addition and multiplication. There will be a small error as you point out, but the error will manifest itself as the answer not being the same. In a finite ring, this is deadly.

To repair this problem maybe you'd need to brute force through all finite expressions within the approximation error from the incorrect one and check one by one if any of them gives the real answer. In general, you may not want to do this.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the clarification. Suppose instead of x and y over FR $2^l$, consider x, y like (32-bit FP): x.sign and y.sign over $Z_{2^1}$, x.exp and y.exp over $Z_{2^{16}}$, x.sig and y.sig over $Z_{2^{46}}$ and compute $z = \frac{x}{y}$, s.t. it obtain z.sign, z.exp, z.sig over the respective rings. I perform the subsequent operations using these three components on $z$ as we can't represent it as a ring element. When needed I will output the three components of $z$ in different rings. In this scenario, the problems of computing $\frac{x}{y}$ over FR don't exist. What is the problem here $\endgroup$
    – Sumana Bagchi
    Commented Oct 25, 2023 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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