Abstract
In the late 1970s Magliveras invented a private-key cryptographic system calledPermutation Group Mappings (PGM). PGM is based on the prolific existence of certain kinds of factorization sets, calledlogarithmic signatures, for finite permutation groups. PGM is an endomorphic system with message space ℤ|G| for a given finite permutation groupG. In this paper we prove several algebraic properties of PGM. We show that the set of PGM transformations ℐ G is not closed under functional composition and hence not a group. This set is 2-transitive on ℤ|G| if the underlying groupG is not hamiltonian and not abelian. Moreover, if the order ofG is not a power of 2, then the set of transformations contains an odd permutation. An important consequence of these results is that the group generated by the set of transformations is nearly always the symmetric group ℒ|G|. Thus, allowing multiple encryption, any permutation of the message space is attainable. This property is one of the strongest security conditions that can be offered by a private-key encryption system.
Article PDF
Similar content being viewed by others
References
P. Cameron, Finite permutation groups and finite simple groups,Bulletin of the London Mathematical Society,13 (1981), 1–22.
I. D. de Caen, D. A. Gregory, and D. L. Kreher, Near-factors of finite groups, Preprint (1989).
M. Furst, J. E. Hopcroft, and E. Luks, Polynomial-time algorithms for permutation groups, inProceedings of the 21st IEEE Symposium on Foundations of Computation of Computer Science (1980), pp. 36–41.
P. Godlewski and C. Mitchell, Key-minimal cryptosystems for unconditional secrecy,Journal of Cryptology,3 (1991), 1–25.
M. Hall Jr.,The Theory of Groups, 2nd edn., Chelsea, New York (1976).
T. B. D. Jungnickel and H. Lenz,Design Theory, Cambridge University Press, Cambridge (1986), pp. 255–256.
B. S. Kaliski Jr., R. L. Rivest, and A. T. Sherman, Is the data encryption standard a group? (Results of cycling experiments on DES),Journal of Cryptology,1 (1988), 3–36.
D. E. Knuth, Notes on efficient representation of permutation groups, Correspondence with M. Furst (1981).
S. S. Magliveras, A cryptosystem from logarithmic signatures of finite groups, inProceedings of the 29th Midwest Symposium on Circuits and Systems (1986), pp. 972–975.
S. S. Magliveras and N. D. Memon, Properties of cryptosystem PGM, inAdvances in Cryptology —Crypto '89, Lecture Notes in Computer Science, Vol. 435, Springer-Verlag, Berlin (1989), pp. 447–460.
S. S. Magliveras and N. D. Memon, Linear complexity profile analysis of the PGM cryptosystem,Congressus Numerantium,72 (1989), 51–60.
S. S. Magliveras and N. D. Memon, Complexity tests for cryptosystem PGM,Congressus Numerantium,79 (1990), 61–68.
S. S. Magliveras, B. A. Oberg, and A. J. Surkan, A new random number generator from permutation groups,Rendiconti del Seminario Matematico di Milano,54 (1985), 203–223.
S. S. Magliveras and P. Petersen, Software implementation of the PGM encryption system, CCIS Report, Center for Communication and Information Science, University of Nebraska-Lincoln, (1991).
C. E. Shannon, The mathematical theory of communication,Bell Systems Technical Journal,28 (1949), 379–423.
E. Shult, Permutation groups with few fixed points: in P. Plaumann and K. Strambach, editors,Geometry-Von Staudt's Point of View, Reidel, Dordrecht (1981), pp. 275–311.
C. C. Sims, Some group-theoretic algorithms: in M. F. Newman, editor,Topics in Algebra, Lecture Notes in Mathematics, Vol. 697, Springer-Verlag, Berlin (1978), pp. 108–124.
H. Wielandt,Finite Permutation Groups, Academic Press, New York (1964).
Author information
Authors and Affiliations
Additional information
Communicated by Ernest F. Brickell
S. S. Magliveras was supported in part by NSF/NSA Grant Number MDA904-82-H0001, by U.S. West Communications, and by the Center for Communication and Information Science of the University of Nebraska.
Rights and permissions
About this article
Cite this article
Magliveras, S.S., Memon, N.D. Algebraic properties of cryptosystem PGM. J. Cryptology 5, 167–183 (1992). https://doi.org/10.1007/BF02451113
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/BF02451113
