At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham's algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham's problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham's algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.

The multivariate public key cryptosystem (MPKC), which is based on the problem of solving a set of multivariate systems of quadratic equations over a finite field, is expected to be secure against quantum attacks. Although there are several existing schemes in MPKC that survived known attacks and are much faster than RSA and ECC, there have been few discussions on security against physical attacks, aside from the work of Okeya et al. (2005) on side-channel attacks against Sflash. In this study, we describe general fault attacks on MPKCs including Big Field type (e.g. Matsumoto-Imai, HFE and Sflash) and Stepwise Triangular System (STS) type (e.g. UOV, Rainbow and TTM/TTS). For both types, recovering (parts of) the secret keys S,T with our fault attacks becomes more efficient than doing without them. Especially, on the Big Field type, only single fault is sufficient to recover the secret keys.