14
$\begingroup$

Most of the cryptographic schemes I know are all based on group theory, e.g. they use finite groups. Can someone explain why is that the case? And why not base the schemes on elements and operations say from natural numbers or some other infinite sets? E.g. $\mathbb{Q, Z, R}$?

$\endgroup$
21
$\begingroup$

Can someone explain why is that the case?

Cryptosystems based on finite sets have two very nice properties:

  • There is an upper bound to the size of all involved mathematical objects. This also allows one to predict things like memory usage rather well. This also means that the precision / memory you need can't grow arbitrarily / infinitely.
  • You can actually draw numbers at random according to some distribution. You can't draw a number uniformly at random from the natural numbers because you'd have probability $0$ of drawing any single specific one. Also in theory if you wanted to sample a normal distribution, you could get $10^{10^{100}}$ drawn (even though that's unlikely) which also brings back the first point.
$\endgroup$
  • 2
    $\begingroup$ You can draw a number at random between 0 and 1 even though they all have probability 0. That isn't the reason, really. $\endgroup$ – Anonymous Pi Jan 7 '18 at 4:23
  • $\begingroup$ (+1) To echo @AnonymousPi, the problem with a uniform distribution on $\mathbb N$ is that there's no way to keep both $\sigma$-additivity and normalization, since if $P(\{n\}) = \varepsilon$ for each $n \in \mathbb N$, then we need $P(\mathbb N)=1$ by normalization but also $P(\mathbb N) = \sum_n P(\{n\}) = \varepsilon \sum_{n} 1$ by $\sigma$-additivity, and if $\varepsilon \in [0,1]$ this can only $0$ or $\infty$, never $1$. The only way to get a uniform distribution on $\mathbb N$ is to use probability measures taking values in a non-Archimedean field, e.g. the hyperreals. $\endgroup$ – jld Jan 7 '18 at 6:30
  • 4
    $\begingroup$ @AnonymousPi would you enlighten me how to draw a number uniformly at random from $[0,1]$ and not just from the finite subset thereof which is representable by <floating / fixed point standard>? $\endgroup$ – SEJPM Jan 7 '18 at 15:51
  • $\begingroup$ @SEJPM class RandomUniform < InfiniteNumber; def initialize; @bits = []; end; def [](ix); bits > 0 ? 0 : (@bits[~ix] ||= rand(2)); end; end. Have fun implementing addition and multiplication of infinite numbers, though, and don't even think about printing them exactly. Making infinitely big things is easy if you have infinitely much time to do so. $\endgroup$ – John Dvorak Jan 7 '18 at 17:06
  • $\begingroup$ More complex representations of infinite precision floats (you probably want a redundant representation) will call for slightly different deferred randomization schemes depending on the representation, but should be equally easy to make. $\endgroup$ – John Dvorak Jan 7 '18 at 17:11
16
$\begingroup$

Mostly, I would say that finite groups get used in crypto because they're a good way to describe things that naturally appear in many crypto schemes.

For example, going way back to the early days of cryptography, consider the simple Caesar cipher, where you replace every letter with the one $n$ positions after it in the alphabet, wrapping around from Z back to A. I'm sure that Julius Caesar (or whoever actually came up with this encryption scheme in the first place) had no idea what a "finite group" was, or that their cipher was equivalent to addition in such a group. But it is, anyway.

More generally, many of the things one works with in cryptography — letters of the alphabet, decimal digits, bits, bytes, $n$-bit strings, etc. — come in finite sets. And it's pretty easy to define a group operation on such sets; so easy that you can do it without even realizing it. Also, any invertible function from a finite set to itself, even if not a group operation on the original set itself, is automatically a permutation and thus an element of the permutation group over that set, so groups will inevitably sneak in that way, too.

As for why not work with infinite sets (or groups) like the integers, one major reason is that often in cryptography you'll want to pick a random element (e.g. a key) from the set you're working with, with each element being equally likely (i.e. with a uniform distribution). That's (relatively) easy if the set is finite, but impossible for most infinite sets.

And, of course, one cannot really represent most elements of an infinite set on a finite computer (or on paper, etc.), either. So it makes practical sense to work with sets of things that are representable, and those are always finite.

$\endgroup$
  • $\begingroup$ More specifically... Cryptographic primitives typically require trapdoor functions. F needs to be "fast", while Finverse needs to be "slow" (infeasibly so). We know a small number of usable trapdoors, and they happen to involve finite groups (large prime factorization, discrete log, elliptic curve). However, I don't believe that there are any trapdoors that are proven to be not-reversible. $\endgroup$ – Rob Jan 7 '18 at 2:57
  • $\begingroup$ @Rob For some definition of a non-reversible trapdoor you would actually have the existence of a non-reversible trapdoor imply P != NP. $\endgroup$ – kasperd Jan 7 '18 at 11:30

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.