Properties of cryptosystem PGM

Spyros S. Magliveras, Nasir D. Memon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology — CRYPTO 1989, Proceedings
EditorsGilles Brassard
PublisherSpringer Verlag
Pages447-460
Number of pages14
ISBN (Print)9780387973173
DOIs
StatePublished - 1990
EventConference on the Theory and Applications of Cryptology, CRYPTO 1989 - Santa Barbara, United States
Duration: Aug 20 1989Aug 24 1989

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume435 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherConference on the Theory and Applications of Cryptology, CRYPTO 1989
CountryUnited States
CitySanta Barbara
Period8/20/898/24/89

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Properties of cryptosystem PGM'. Together they form a unique fingerprint.

Cite this