Use of Signed Permutations in Cryptography

Main Article Content

Iharantsoa Vero Raharinirina

Abstract

In this paper we consider cryptographic applications of the arithmetic on the hyperoctahedral group. On an appropriate subgroup of the latter, we particularly propose to construct public key cryptosystems based on the discrete logarithm. The fact that the group of signed permutations has rich properties provides fast and easy implementation and makes these systems resistant to attacks like the Pohlig-Hellman algorithm. The only negative point is that storing and transmitting permutations need large memory. Using together the hyperoctahedral enumeration system and what is called subexceedant functions, we define a one-to-one correspondence between natural numbers and signed permutations with which we label the message units.

Keywords:
Signed permutation, public key system, discrete logarithm problem, hyperoctahedral enumeration system, subexceedant function

Article Details

How to Cite
Raharinirina, I. V. (2020). Use of Signed Permutations in Cryptography. Journal of Advances in Mathematics and Computer Science, 35(1), 23-38. https://doi.org/10.9734/jamcs/2020/v35i130237
Section
Original Research Article

References

Diffie W, Hellman ME. New directions in cryptography. IEEE Transactions on Information Theory. 1976;IT-22:644-654.

Bernhard Esslinger. Learning and Experiencing Cryptography with CrypTool and SageMath. 12th Ed., CrypTool Project; 2018.

Rivest RL, Shamir A, Adleman LM. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978;21(2):120-126.

Galbraith SD, Gaudry P. Recent progress on the elliptic curve discrete logarithm problem. Designs, Codes and Cryptography. 2016;78.1:51-72.

Christophe Petit, Michiel Kosters, Ange Messeng. Algebraic approaches for the elliptic curve discrete logarithm problem over prime elds. IACR International Workshop on Public Key Cryptography. Springer Berlin Heidelberg. 2016;3-18.

ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory. 1985;IT-31:469-472.

Reiner V. Signed permutation statistics and cycle type. European Journal of Combinatorics. 1993;14:569-579.

Rotman JJ. Advanced Modern Algebra. 1st Edition, Prentice Hall, New Jersey; 2002.

Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithms. MIT Press, Second Edition; 2001.

Shanks D. Class number, a theory of factorization, and genera. In Proceedings of Symposia in Pure Mathematics. 1969;20:415-440.

Pollard JM. Monte Carlo methods for index computation ( mod p). Mathematics of Computation. 1978;32:918-924.

Pohlig SC, Hellman ME. An improved algorithm for computing logarithms over GF(p) and its cryptographic signicance. IEEE Transactions on Information Theory. 1978;24:106-110.

Adleman LM. A sub-exponential algorithm for the discrete logarithm problem with applications to cryptography. IEEE Annual Symposium on Foundations of Computer Science. 1979;20:49-74.

Gopalakrishna Hejmadi Gadiyar, Ramanathan Padma and Vellore. The discrete logarithm problem over prime elds: the safe prime case. the smart attack, non-canonical lifts and logarithmic derivatives. Czechoslovak Mathematical Journal. 2018;68(143):1115-1124.

Jung Hee Cheon, Taechan Kim. A new approach to the discrete logarithm problem with auxiliary inputs. LMS J. Comput. Math. 2016;19(1):1-15.