September 21st, 2025

Helpful topic to teach yourself lattice-based crypto: cosets

Before we even begin to talk about the fun stuff, it's time to talk about one more topic: cosets. What they are is what will be discussed further in this article.

I've talked about subgroups. The thing about studying subgroups, is that it may feel like we're dismissing all other subsets. The next logical question would be, why not study the rest of the sets?

And this is where cosets comes along. Although cosets don't cover every subsets of a group, but, nevertheless, it still broadens the scope further than what subgroups ever did, and they can be used to build powerful primitives. Primitives that are used in many cryptographic studies.

So what is a coset?

A coset is what you get when you take a subgroup HH of a group GG and "shift" it by some element of GG.

Formally, if GG is a group and H≤GH \leq G is a subgroup, as well as some operator ⋅\cdot, then cosets take on any of the following forms

  • left coset of HH by g∈Gg \in G: g⋅H={g⋅h∣h∈H}g\cdot H = \{g\cdot h | h \in H\}
  • right coset of HH by g∈Gg \in G: H⋅g={h⋅g∣h∈H}H \cdot g = \{h \cdot g | h \in H\}

The key properties of cosets are:

  • The set of all left cosets of H≤GH \leq G forms a partition of GG, and right cosets of H≤GH \leq G forms a partition of GG. Meaning that every element of GG belong to exactly one left coset and one right coset of HH
  • Every element of GG belongs to exactly one left coset and right coset of any subgroup HH.
  • All cosets of HH have the same number of elements as HH itself.
  • Cosets are either equal or disjoint

Example with Integers

Additions in integers Z\mathbb{Z} forms a group. We can define a subgroup of Z\mathbb{Z} as being nothing but multiples of a particular integer, using nZn\mathbb{Z} (where n∈Zn \in \mathbb{Z}), e.g. 5Z={…,−15,−10,−5,0,5,10,15,…}5\mathbb{Z} = \{\ldots, -15, -10, -5, 0, 5, 10, 15, \ldots\}.

Using additions as the "shift" operator, then the possible left cosets of H=5ZH = 5\mathbb{Z} gives:

  • 0+H={…,−15,−10,−5,0,5,10,15,…}0 + H = \{\ldots, -15, -10, -5, 0, 5, 10, 15, \ldots\}
  • 1+H={…,−14,−9,−4,1,6,11,16,…}1 + H = \{\ldots, -14, -9, -4, 1, 6, 11, 16, \ldots\}
  • 2+H={…,−13,−8,−3,2,7,12,17,…}2 + H = \{\ldots, -13, -8, -3, 2, 7, 12, 17, \ldots\}
  • 3+H={…,−12,−7,−2,3,8,13,18,…}3 + H = \{\ldots, -12, -7, -2, 3, 8, 13, 18, \ldots\}
  • 4+H={…,−11,−6,−1,4,9,14,19,…}4 + H = \{\ldots, -11, -6, -1, 4, 9, 14, 19, \ldots\}

These cosets partition Z\mathbb{Z} into 5 distinct sets, each containing all integers that give the same remainder when divided by 5. This is a fundamental concept that leads to modular arithmetic.

This is a powerful idea to be leveraged when discussing quotient groups.