Miyaji Laboratory

It is well known that widely used cryptosystems, such as RSA and elliptic curve cryptography, can be broken in polynomial time by Large-scale quantum computers. Therefore, lattice-based cryptography, which is based on lattice theory, has been actively researched as a promising candidate for post-quantum cryptography. One of the mathematically difficult problems ensuring the security of lattice-based cryptography is the Ring Learning with Errors (Ring-LWE) problem, which involves solving systems of linear equations with errors over the ring of integers of a number field. The Order Learning with Errors (Order-LWE) problem is a generalization of the Ring-LWE problem to general orders. Although cyclotomic fields are commonly utilized in Ring-LWE, the discovery of new cryptanalytic techniques may render current cyclotomic-based schemes vulnerable. Thus, analyzing the security of Ring-LWE over non-cyclotomic fields is of paramount importance. From an implementation perspective, identifying an integral basis of the ring is essential for representing elements as vectors. However, computing the integral basis for the ring of integers in high-degree number fields is often computationally prohibitive, whereas bases for general orders can be constructed relatively easily. This highlights the significance of analyzing Order-LWE for practical cryptographic applications. In practical implementations, for the sake of computational efficiency, errors and secrets are often defined within the same ring as the public keys―a configuration referred to as the "non-dual" form. Despite its utility, the security of the non-dual form of Order-LWE has not been extensively analyzed. In this research, we evaluate the hardness of the non-dual Order-LWE problem across various orders. Our analysis utilizes representative lattice-based attacks, specifically Kannan's embedding method and the dual attack, to provide a comprehensive security assessment.