3. Groups, Rings and Ideals

Common key lengths for block ciphers are 128, 192 and 256 bits, this means that in an exhaustive search one would have to sift through 2¹²⁸, 2¹⁹² or 2²⁵⁶ possible keys. This is not only exhausting, it’s downright impossible, no matter how fast your computer is running.

The reason, very roughly, is that if the set \(\{\psi _{k}\vert k \in \mathcal{K}\}\) is a group, then applying two of the (secret) permutations, one after the other, would not make breaking the cipher any more difficult than breaking just a single application, because there would be a single permutation in the set having the same effect anyway.

We need to warn here that the word lattice has two entirely different meanings in Mathematics. The type of lattice that we have defined here is related to the concept of (partial) order. Another unrelated definition of a lattice is as a discrete subgroup of the vector space \(\mathbb{R}^{n}\), which spans \(\mathbb{R}^{n}\). This second concept is the more important one in Number Theory, and therefore in Cryptology; in fact an important technique in this kind of Lattice Theory, the so-called L ³ algorithm, named after Lenstra, Lenstra and Lovász, was fundamental in breaking an early public key system which was based on the so-called knapsack problem. More recently, hard problems in lattice theory (of this second kind) have also been used in order to construct new public key schemes. See, e.g., the paper The two faces of lattices in cryptology by Nguyen and Stern in the Proceedings of the Cryptography and Lattices Conference 2001, edited by J.H. Silverman, LNCS 2146, Springer Verlag. Since the publication of that paper some major developments have taken place in lattice based cryptology, such as Craig Gentry’s discovery of a fully homomorphic encryption scheme, 2009. See Sect. 11.​2

This terminology is typical of the usage among mathematicians. If some property is convenient, or allows one to do things one would like to do, it is given some pleasant sounding name like “normal” or “regular”. In actual fact, in non-abelian groups, “normal” subgroups are in the minority among subgroups, and should therefore be considered somewhat abnormal.

It is unfortunate that the word “order” is used in what are really two different senses. On the one hand the order of a group is the number of elements in the group. On the other, the order of an element is as we have just defined it. The two are related: the order of an element a is equal to the order of the subgroup generated by a.

Here the symbol “⊕” does not stand for the exclusive or (XOR) operation, but for the operation which we first came across in Example 11 of Sect. 3.1: We recall that if {G, ∗} and {H, ⋅ } are groups, then the set G × H can be turned into a group, called the direct product, which is denoted by G ⊗ H. In the Abelian case this is called the direct sum of G and H and denoted by G ⊕ H. In both cases the group operation on the set G × H is defined component-wise.

It is called his “little” theorem, to distinguish it from his famous (or infamous) “Last Theorem”.

If you had done or had remembered Exercise 8 of Sect. 2.​6, you would have spotted immediately that 11 | 561. But then you would have missed the point for which we chose this example, which comes next.

Or even for all values of a! See our definition of Carmichael numbers in the next subsection.

We have already referred to ring-theoretic properties when dealing with the integers in the previous chapter.

The reader must try not to be offended by what is virtually universal practice among algebraists: We denote the operation by ‘⋅ ’, and then immediately proceed by writing ‘ab’ instead of ‘a ⋅ b’.