Cryptographic Primitives Based on Groups of Hidden Order

Spyros S. Magliveras

Department of Mathematical Sciences
Florida Atlantic University
Boca Raton, Florida, U.S.A.
(Joint work with Tran van Trung and Wandi Wei)


Many of the known attacks against several known cryptographic primitives are based on knowing the order of the underlying group. We propose a new idea of combining the intractability of the integer factorization problem and the discrete logarithm problem to construct signature schemes based on groups of hidden order. Using this notion we describe two signature schemes. The first scheme arises by applying the idea to the ElGamal signature scheme. We show that the new scheme withstands all known attacks to the ElGamal scheme. The second scheme, considered as an application of the idea to the Schnorr signature scheme, provides a much shorter signature, as does the Schnorr scheme, and enhanced security. Time permitting we will also describe the construction of a new public key system based on the idea of hiding the order of the underlying group.


Spyros Magliveras is "Henson Professor Emeritus" at the University of Nebraska - Lincoln, and Professor of Mathematical Sciences at Florida Atlantic University. He is Coordinator of the Applied Mathematics Program, and Director of the "Cryptology and Computer Security Initiative" at Florida Atlantic University.