2
$\begingroup$

In a computational setting it is clear that we cannot do computation over the real numbers, as we couldn't generate, much less store them, so we have to instead deal with numbers that approximate them. If a cryptosystem has some component defined over the real numbers, or uses "real valued" functions such as $\sin$, then does using such systems over the discretized space compromise the theoretical security of the system?

I am particularly thinking of chaos based cryptosystems for example, where encryption consists of iterating a map over an interval of the real line. Are such systems inherently less secure because they cannot be actually implemented over the reals, and instead are approximations? Can such approximations be used to cryptanalyze the systems?

$\endgroup$
2
0
$\begingroup$

The complex roots of unity form a finite group under multiplication

$$z^k = \exp\bigg(\frac{2k{\pi}i}{n}\bigg) = \cos\frac{2k{\pi}}{n} + i\sin\frac{2k{\pi}}{n},$$

where $z$ is a complex generator of the order-$n$ multiplicative group. This is a cyclic group and is isomorphic to any other cyclic group of the same order, for example the integers modulo 2 under addition, which is equivalent to Boolean XOR

$$a \oplus b \iff z^a z^b = z^{a+b}$$

This equivalence gives rise to the group Fourier transform, in which vector convolution in the complex domain correspond to point-wise multiplication in the additive group. This fact is used by Joan Daemen in his thesis to derive the DC/LC properties for the AES S-BOX.

The obvious practical problem with computing in this group is the error associated with floating-point arithmetic. As the number of arithmetic operations increases, so does the error. This kind of round-off error may be more appropriately called quantization noise in the signal processing context.

$\endgroup$
2
  • 1
    $\begingroup$ I stand corrected: that does prove continuous systems can be useful building blocks for cryptography, at least when we restrict to theory. $\endgroup$ – fgrieu Jun 4 '20 at 4:47
  • 1
    $\begingroup$ I'd say that this is still finite though, the cos and sine are not needed and one can work purely in terms of roots of unity, say $w$ of order $n.$ So one works a finite structure of discrete (i.e., integer or rational) polynomials, say $\mathbb{Z}[w]$ with coefficients in integers or modulo some finite characteristic. In fact it is this kind of argument that leads to some fast number theoretic fourier transforms which are exact, i.e., no roundoff. $\endgroup$ – kodlu Jun 5 '20 at 11:23

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.