A Graph-Based Public-Key Cryptosystem Using the NP-Complete Problem of Partitioning Into Perfect Matchings

Cryptography serves as the backbone of modern digital security, protecting sensitive information across electronic communication and transactions. The rapid advancement of quantum computing poses a threat to classical cryptographic systems, necessitating the development of post-quantum alternatives. We propose a novel graph-based public key encryption scheme that leverages the hardness of partitioning a 4-regular graph into four disjoint subsets, such that each induced subgraph is a perfect matching. The scheme encodes plaintexts as multivariate polynomials over edge variables using a recursive encoding structure. We provide a comprehensive security analysis demonstrating that the scheme achieves one-way security under chosen-plaintext attacks (OW-CPA) and is resilient against key recovery, ciphertext search, and plaintext search attacks. We analyze the theoretical time and space complexities of the core algorithms and validate our results through experimental implementation. The results demonstrate the practical feasibility of NIST (National Institute of Standards and Technology) Level I security parameters, highlighting the potential of graph-theoretic problems as a foundation for secure and efficient cryptographic primitives.