Miyaji Laboratory

Abstract

If large quantum computers are built, almost all public key cryptosystems, such as RSA Cryptosystem and Elliptic Curve Cryptography, will be broken. Therefore, the research of cryptosystem, that is too difficult to be broken by quantum computers, Post-Quantum Cryptosystem (PQC), has been developing.
In SAC2017, Akiyama et al. presented Giophantus, as a candidate of PQC. Its secure basis is in the problem finding the solution of an indefinite equation on the polynomial ring Fq[t]/(t^n − 1). It ensures IND-CPA safety if IE Ring-LWE problem, a kind of LWE problem, is too difficult to be solved.
In SAC2019, the team of Muroi, Okumura and Miyaji presented the method solving IE Ring-LWE problem easily with the combination of the substitution attack and the lattice attack. Then Akiyama et al. presented Giophantus+, its secure basis on the improved polynomial ring Fq[t]/(t^n + 1).
In this paper, ideal methods of attacks against Giophantus+ will be examined, with experiments changing parameters of member sets and degrees of the indefinite equation.