TY - GEN

T1 - Properties of cryptosystem PGM

AU - Magliveras, Spyros S.

AU - Memon, Nasir D.

N1 - Funding Information:
Supported by a

PY - 1990

Y1 - 1990

N2 - A cryptographic system, called PGM, was invented in the late 1970’s by S. Magliveras. PGM is based on the prolific existence of certain kinds of factorization sets, called logarithmic signatures, for finite permutation groups. Logarithmic signatures were initially motivated by C. Sims’ bases and strong generators. Statistical properties of random number generators based on PGM have been investigated in [7], [8] and show PGM to be statistically robust. In this paper we present recent results on the algebraic properties of PGM. PGM is an endomorphic cryptosystem in which the message space is Z|G|, for a given finite permutation group G. We show that the set of PGM transformations TG is not closed under functional composition and hence not a group. This set is 2-transitive on Z|G| if the underlying group G is not hamiltonian. Moreover, if |G| ≠ 2a, then the set of transformations contains an odd permutation. An important consequence of the above results is that the group generated by the set of transformations is nearly always the full symmetric group.

AB - A cryptographic system, called PGM, was invented in the late 1970’s by S. Magliveras. PGM is based on the prolific existence of certain kinds of factorization sets, called logarithmic signatures, for finite permutation groups. Logarithmic signatures were initially motivated by C. Sims’ bases and strong generators. Statistical properties of random number generators based on PGM have been investigated in [7], [8] and show PGM to be statistically robust. In this paper we present recent results on the algebraic properties of PGM. PGM is an endomorphic cryptosystem in which the message space is Z|G|, for a given finite permutation group G. We show that the set of PGM transformations TG is not closed under functional composition and hence not a group. This set is 2-transitive on Z|G| if the underlying group G is not hamiltonian. Moreover, if |G| ≠ 2a, then the set of transformations contains an odd permutation. An important consequence of the above results is that the group generated by the set of transformations is nearly always the full symmetric group.

UR - http://www.scopus.com/inward/record.url?scp=85031617132&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031617132&partnerID=8YFLogxK

U2 - 10.1007/0-387-34805-0_41

DO - 10.1007/0-387-34805-0_41

M3 - Conference contribution

AN - SCOPUS:85031617132

SN - 9780387973173

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 447

EP - 460

BT - Advances in Cryptology — CRYPTO 1989, Proceedings

A2 - Brassard, Gilles

PB - Springer Verlag

T2 - Conference on the Theory and Applications of Cryptology, CRYPTO 1989

Y2 - 20 August 1989 through 24 August 1989

ER -