Miyaji Laboratory

abstract

Giophantus [AGO 17], one of the candidates for quantum-resistant cryptography, is based on the computational difficulty of finding the minimum solution of an indefinite equation. Giophantus is IND-CPA safe given the computational difficulties of the new distribution identification problem. In this study, we propose a new t = 1 substitution identification attack on the IE-LWE problem. In the proposed attack, the IE-LWE problem Identifies the distribution by reducing to a recent vector problem over integers. Computer experiments showed that existing substitution attacks can be attacked in a realistic time against powerful parameters.