Analysis of public-key cryptography using a 3-regular graph with a perfect dominating set

Research on post-quantum cryptography (PQC) to improve the security against quantum computers has been actively conducted. In 2020, NIST announced the final PQC candidates whose design rationales rely on NP-hard or NP-complete problems. It is believed that cryptography based on NP-hard problem might be secure against attacks using quantum computers. N. Koblitz introduced the concept of public-key cryptography using a 3-regular graph with a perfect dominating set in the 1990s. The proposed cryptosystem is based on NP-complete problem to find a perfect dominating set in the given graph. Later, S. Yoon proposed a variant scheme using a perfect minus dominating function. However, their works have not received much attention since these schemes produce huge ciphertexts and are hard to implement efficiently. Also, the security parameters such as key size and plaintext-ciphertext size have not been proposed yet. We conduct security and performance analysis of their schemes and discuss the practical range of security parameters. As an application, the scheme with one-wayness property can be used as an encoding method in the white-box cryptography (WBC).