How can $S=\{g_1^{e_1}\cdots g_t^{e_t}\}$ induce an hypercube?

Question

According to https://eprint.iacr.org/2022/1363.pdf at section 2.4, an hypercube can be induced by the equation 6:

Can someone explain to me how an hypercube can be induced? What are $g_1,\cdots, g_t$?

Answer 1

A hypercube structure seems fancy but it's just the cartesian product of the naturals that's bounded in each coordinate. We then place a convenient group structure on it to shunt symbols around. Lets look at a simple example.

Start with the set $S = \{(x,y) \in \mathbb{N}^2 \vert 0 \leq x < 3$, $0 \leq y < 7\}$ an it's not hard to see that this set has $3 \times 7 = 21$ elements. This is refered to as the "number of plaintext slots".

Now we're going to add a group structure to the $x$ coordinate by consider it as the integers modulo $3$. We pick some generator of that group, say $g_1: (x,y) \rightarrow (x+1,y)$ so that we can write each element of it in the form $g_1^{e_1}$ with $0 \leq e_1 < 3$. We do the same thing with the $y$ coordinate but this time we reduce modulo $7$ and consider the generator of that group, say $g_2:(x,y) \rightarrow (x,y+1)$ so that we can write each element of that group in the form $g_2^{e_2}$.

Now that we have those two substructures we can consider the group generated by both of them. Elements of this group will have the form $g_1^{e_1}g_2^{e_2}$ and this is because $g_1g_2=g_2g_1$ (check this!). This group is important enough to have enough so we're going to call it $h$, the hypercube group.

Now we don't have to stop here. We can generalize by adding a $z$ coordinate and bound it by $32$ so that we have a $3 \times 7 \times 32$ hypercube and we can define a group on the $z$ coordinate by considering the integers modulo $32$ which is generate by $g_3$ so that all elements will be of the form $g_3^{e_3}$ for $0 \leq e_3 < 32$ and doing the same thing as before we can generate a group from the elements $g_1^{e_1}g_2^{e_2}g_3^{e_3}$ which is an even fancier hypercube $h$.

And that's the whole thing. You just keep going by adding more coordinates that are bounded by $b$ and consider the integers modulo $b$ to generate a group, then add it into the mix to get a full group of transformations on the cube.