Factorizations in the elementary abelian \(p\)-group and their cryptographic significance (Q1340194): Difference between revisions

Let \(G\) be a finite abelian group, and let \(A_i\) be a subset with at least two elements (for \(i=1,\dots,s\)). The ordered collection \({\mathbf A}=(A_1,\dots,A_s)\) is called a factorization of \(G\) if and only if each group element may be written uniquely as a product of the form \(a_1\dots a_s\) with \(a_i\in A_i\) for \(i=1,\dots,s\). Trivially, one obtains an example from each chain \(\{0\}=G_s<\dots<G_1<G_0=G\) of subgroups of \(G\) by taking \(A_i\) as a complete set of coset representatives of \(G_{i-1}\) in \(G_i\); such a factorization is called transversal. By adding an arbitrary element \(g_i\) to each element in \(A_i\) (for \(i=1,\dots,s\)), one obtains from any given factorization \(\mathbf A\) another factorization \(\mathbf B\) (called a translation of \(\mathbf A\)). The authors prove the following beautiful theorem: Let \(G\) be the elementary abelian group of order \(p^n\). Then the only factorizations of \(G\) involving \(n\) sets \(A_i\) are translations of transversal factorizations. This result is then applied to show that two public-key cryptosystems proposed (in different terminology) by \textit{W. Webb} [Lect. Notes Pure Appl. Math. 141, 411-415 (1993; Zbl 0792.11052)] are insecure.