Factorizations in the elementary abelian \(p\)-group and their cryptographic significance
type: Item
instance of: scholarly article
title: Factorizations in the elementary abelian \(p\)-group and their cryptographic significance
zbMATH Open document ID: 0827.20061
DOI: 10.1007/BF00203963
author: Minghua Qu
author: Scott A. Vanstone
published in: Journal of Cryptology
publication date: 1995-12-03T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 20K01
Mathematics Subject Classification ID: 20D60
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68P25
zbMATH DE Number: 701028
zbMATH Keywords: elementary Abelian \(p\)-groups
zbMATH Keywords: group factorizations
zbMATH Keywords: finite Abelian groups
zbMATH Keywords: translations of transversal factorizations
zbMATH Keywords: public-key cryptosystems
Wikidata QID: Q114234147
reviewed by: Dieter Jungnickel
MaRDI profile type: Publication
cites work: Q5818512
cites work: Q5820591
cites work: Q5798059
cites work: Sur le problème de factorisation des groupes cycliques
cites work: Algebraic properties of cryptosystem PGM
cites work: Zwei Lückensätze über Polynome in endlichen Primkörpern mit Anwendung auf die Abelschen Gruppen und die Gaus'schen Summen
cites work: Die neue Theorie der endlichen abelschen Gruppen und Verallgemeinerung des Hauptsatzes von Hajós
cites work: On the factorisation of finite abelian groups
cites work: THE FACTORIZATION OF ABELIAN GROUPS
Recommended article: On the security of a public-key cryptosystem
Recommended article: Q4934728
Recommended article: On Minimal Factorisations of Sporadic Groups
Recommended article: Towards a uniform description of several group based cryptographic primitives
Recommended article: Q3363232
Recommended article: A public key cryptosystem based on a subgroup membership problem
Recommended article: Groups, Factoring, and Cryptography
Recommended article: Q4314376
Recommended article: Q4783741
Recommended article: On the security of two public key cryptosystems using non-abelian groups
description: scientific article; zbMATH DE number 701028