Biblio

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).

Structural analysis is the study of finding component functions for a given function. In this paper, we proceed with structural analysis of structures consisting of the S (nonlinear Substitution) layer and the A (Affine or linear) layer. Our main interest is the S1AS2 structure with different substitution layers and large input/output sizes. The purpose of our structural analysis is to find the functionally equivalent oracle F* and its component functions for a given encryption oracle F(= S2 ∘ A ∘ S1). As a result, we can construct the decryption oracle F*−1 explicitly and break the one-wayness of the building blocks used in a White-box implementation. Our attack consists of two steps: S layer recovery using multiset properties and A layer recovery using differential properties. We present the attack algorithm for each step and estimate the time complexity. Finally, we discuss the applicability of S1AS2 structural analysis in a White-box Cryptography environment.