Cryptography Reference
In-Depth Information
General Fault Attacks on Multivariate Public
Key Cryptosystems
Yasufumi Hashimoto
1
, Tsuyoshi Takagi
2
, and Kouichi Sakurai
3
1
Department of Mathematical Sciences, University of the Ryukyus
2
Institute of Mathematics for Industry, Kyushu University
3
Department of Informatics, Kyushu University,
Institute of Systems, Information Technologies and Nanotechnologies
Abstract.
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 sur-
vived 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 Trian-
gular 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 ecient than doing without them. Especially, on the Big
Field type, only
single
fault is sucient to recover the secret keys.
Keywords:
post-quantum cryptography, multivariate public-key cryp-
tosystems, fault attacks.
1
Introduction
It is well known that, if a large scale quantum computer is realized, RSA and
elliptic curve cryptosystems (ECC) can be broken by Shor's algorithm [43], and
that post-quantum cryptography is now one of the most avidly studied areas
in cryptology. Lattice-based cryptosystems, code-based cryptosystems and the
multivariate public key cryptosystem (MPKC) are leading candidates for the
post quantum cryptosystems.
The cryptosystem studied in the present paper is MPKC, which is based on
the problem of solving a set of multivariate systems of quadratic equations over a
finite field. The MPKC schemes were first proposed by Matsumoto and Imai [34]
and Tsujii
et al.
[44] in the 1980's and have since been extensively developed.
Although some of these schemes have already been broken (
e.g.
Matsumoto-
Imai's and Tsujii's schemes were broken by Patarin [39], and Hasegawa and
Kaneko [28] respectively), others, such as (variants of) HFE and Rainbow, have
survived known attacks like the Grobner basis attacks [23,24], the rank attacks
[32,46] and the differential attacks [41,26,22]. Another attractive advantage of
