A Like ELGAMAL Cryptosystem But Resistant To Post-Quantum Attacks

Main Article Content

Fouzia OMARY


The Modulo 1 Factoring Problem (M1FP) is an elegant mathematical problem which could be exploited to design safe cryptographic protocols and encryption schemes that resist to post quantum attacks. The ELGAMAL encryption scheme is a well-known and efficient public key algorithm designed by Taher ELGAMAL from discrete logarithm problem. It is always highly used in Internet security and many other applications after a large number of years. However, the imminent arrival of quantum computing threatens the security of ELGAMAL cryptosystem and impose to cryptologists to prepare a resilient algorithm to quantum computer-based attacks. In this paper we will present a like-ELGAMAL cryptosystem based on the M1FP NP-hard problem. This encryption scheme is very simple but efficient and supposed to be resistant to post quantum attacks.

Article Details

How to Cite
EL-YAHYAOUI, A., & OMARY, F. (2022). A Like ELGAMAL Cryptosystem But Resistant To Post-Quantum Attacks. International Journal of Communication Networks and Information Security (IJCNIS), 14(1). https://doi.org/10.17762/ijcnis.v14i1.5180 (Original work published April 12, 2022)
Research Articles


W. Diffie and M. Hellman, "New directions in cryptography," IEEE Transactions on Information Theory, vol. 22, no. 6, p. 644–654, 1976.

R. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, vol. 21, no. 2, pp. 120-126, 1976.

T. ELGAMAL, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms," IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 31, no. 04, pp. 469-472, 1985.

N. Koblitz, "Elliptic Curve Cryptosystems," MATHEMATICS OF COMPUTATION, vol. 24, no. 177, pp. 20.1-209, 1987.

D. Pointcheval and J. Stern, "Security Arguments for Digital Signatures and Blind Signatures," J. of Cryptology, vol. 13, p. 361–396, 2000.

J. Callas, L. Donnerhacke, H. Finney and R. Thayer, "OpenPGPmessage Format," 11 1998. [Online]. Available: https://datatracker.ietf.org/doc/html/rfc2440. [Accessed 16 09 2021].

J. Callas, L. Donnerhacke, H. Finney, D. Shaw and R. Thayer, "OpenPGP Message Format," 11 2007. [Online]. Available: https://datatracker.ietf.org/doc/html/rfc4880. [Accessed 16 09 2021].

J. Jonathan Katz and Y. Lindell, Introduction to Modern Cryptography, 2nd Edition, Boca Raton, 2014.

P. Shor, "Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM J. Comput, vol. 25, p. 1484–1509, 1997.

W. Beullens, J. D’Anvers, A. Hülsing, T. Lange, L. Panny, C. de Saint Guilhem and N. Smart, "POST-QUANTUM CRYPTOGRAPHY Current state and quantum mitigation," European Union Agency for Cybersecurity, 2021.

R. McEliece, "public-key cryptosystem based on algebraic coding theory," Technical report, NASA, 1978. https://tmo.jpl.nasa.gov/progress_report2/42-44/44N.PDF, 1978.

H. Niederreiter, "Knapsack-type cryptosystems and algebraic coding theory," Problems of Control and Information Theory, vol. 15, no. 2, p. :159–166, 1986.

D. Bernstein, T. Chou and P. Schwabe, "McBits: Fast constant-time codebased cryptography," in 15th International Workshop, Santa Barbara, CA, USA, August 20-23, 2013.

M. Albrecht, D. Bernstein, T. Chou, C. Cid, J. Gilcher, T. Lange, V. Maram, I. Maurich, R. Misoczki, R. Niederhagen, K. Paterson, E. Persichetti, C. Peters, P. Schwabe, N. Sendrier, J. Szefer, C. Tjhai, M. Tomlinson and W. Wang, "Classic McEliece," 30 10 2020. [Online]. Available: https://classic.mceliece.org/index.html. [Accessed 16 09 2021].

J. Couveignes, "Hard Homogeneous Spaces," IACR Cryptology ePrint Archive 2006/291., 2006.

A. Rostovtsev and A. Stolbunov, "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES," IACR Cryptology ePrint Archive 2006/145., 2006.

D. Jao, R. Azarderakhsh, M. Campagna, C. Costello, L. Feo, B. Hess, A. Hutchinson, A. Jalali, K. Karabina, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, G. Pereira, J. Renes, V. Soukharev and D. Urbanik, "SIKE – Supersingular Isogeny Key Encapsulation," SIKE.ORG, 09 06 2021. [Online]. Available: https://sike.org/. [Accessed 16 09 2021].

J. Buchmann, E. Dahmen and A. Hulsing, "Xmss-a practical forward secure signature scheme based on minimal security assumptions," in In International Workshop on Post-Quantum Cryptography, Taipei, Taiwan, 2011.

F. Leighton and S. Micali, "Large provably fast and secure digital signature schemes based on secure hash functions". USA Patent 5,432,852, 07 1995.

D. Cooper, D. Apon, Q. Dang, M. Davidson, M. Dworkin and C. Miller, "NIST Special Publication 800-208: Recommendation for Stateful Hash-Based Signature Schemes," National Institute of Standards and Technology, 2020.

J. Hoffshtein, J. Pipher and J. Silverman, "NTRU: A ring-based public key cryptosystem," in Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, 1998.

E. Alkim, L. Ducas, T. Poppelmann and P. Schwabe, "Newhope without reconciliation," IACR Cryptology ePrint, 2016:1157, 2016.

J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. Schanck, P. Schwabe, G. Seiler and D. Stehlé, "Crystals-kyber: a cca-secure module-lattice-based kem," IACR Cryptology ePrint Archive, 2017:634, 2017.

C. Gentry, A. Sahai and B. Waters, "Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based," IACR Cryptology ePrint Archive, 2013:340, 2013.

J. Ding, M. Chen, A. Petzoldt, D. Schmidt, B. Yang, M. Kannwischer and J. Patarin, "Post-Quantum Cryptography PQC," Technical report, National Institute of Standards and Technology, 2019.

A. Casanova, G. Faugère, G. Macario-Rat, J. Patarin, L. Perret and J. Ryckeghem, "Post-Quantum Cryptography PQC," Technical report, National Institute of Standards and Technology, 2019.

E. Jarpe, "An Alternative Diffie-Hellman Protocol," Cryptology, vol. 4, no. 5, 2020.