Dominating Polynomial of Graphs in Asymmetric Key Cryptosystem Construction: An Algorithm and Illustrative Example

In this paper, we have introduced a novel asymmetric key cryptosystem grounded in the dominating polynomial of graphs. The construction leverages the algebraic richness of D(G, x), its coefficient vector, and evaluation-based masking to encrypt and decrypt messages securely. The security relies on the hardness of the Domination Polynomial Root Problem and the Graph Recovery Problem, providing a multi-layered security foundation with partial post-quantum resilience. A detailed algorithm was presented and illustrated through a complete worked example encrypting and successfully decrypting the plaintext KRISHNA using C6 as the underlying graph. The scheme is correct by construction, and security analysis demonstrates IND-CPA security with straightforward extensions to IND-CCA2. Future directions include: (i) formal provable security reduction under DPRP, (ii) extending to elliptic curve variants of the polynomial construction, (iii) designing efficient algorithms for large-scale graph families, (iv) hybrid schemes combining dominating polynomial masks with lattice-based primitives for full post-quantum security, and (v) hardware implementation benchmarking.

[1] W. Diffie and M. E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644-654, 1976. [2] R. L. 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, 1978. [3] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [4] R. C. Merkle, "Secrecy, Authentication, and Public Key Systems," Ph.D. dissertation, Stanford University, 1979. [5] R. McEliece, "A Public-Key Cryptosystem Based on Algebraic Coding Theory," JPL DSN Progress Report, vol. 42-44, pp. 114-116, 1978. [6] O. Goldreich, S. Micali, and A. Wigderson, "Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems," Journal of the ACM, vol. 38, no. 3, pp. 691-729, 1991. [7] A. Kojevnikov and S. I. Nikolenko, "New Combinatorial Complete One-Way Functions," in Proc. STACS, 2009, pp. 457-466. [8] N. Alon, O. Goldreich, J. Hastad, and R. Peralta, "Simple Constructions of Almost k-wise Independent Random Variables," Random Structures & Algorithms, vol. 3, no. 3, pp. 289-304, 1992. [9] R. A. Hearn and E. D. Demaine, Games, Puzzles, and Computation. AK Peters, 2009. [10] S. Alikhani and Y.-H. Peng, "Dominating Sets and Domination Polynomials of Paths," International Journal of Mathematics and Mathematical Sciences, vol. 2009, Article ID 542040, 10 pages.