Welcome to the resource topic for 2004/061
Title:
TTS: Rank Attacks in Tame-Like Multivariate PKCs
Authors: Bo-Yin Yang, Jiun-Ming Chen
Abstract:We herein discuss two modes of attack on multivariate public-key
cryptosystems. A 2000 Goubin-Courtois article applied these
techniques against a special class of multivariate PKC’s called
Triangular-Plus-Minus'' (TPM), and may explain in part the present dearth of research on true’’ multivariates – multivariate PKC’s
in which the middle map is not really taken in a much larger field.
These attacks operate by finding linear combinations of matrices
with a given rank. Indeed, we can describe the two attacks very
aptly as high-rank'' and low-rank’'.
However, TPM was not general enough to cover all pertinent true
multivariate PKC’s. \emph{Tame-like} PKC’s, multivariates with
relatively few terms per equation in the central map and an easy
inverse, is a superset of TPM that can enjoy both fast private maps
and short set-up times.
However, inattention can still let rank attacks succeed in tame-like
PKCs. The TTS (Tame Transformation Signatures) family of digital
signature schemes lies at this cusp of contention. Previous TTS
instances (proposed at ICISC '03) claim good resistance to other
known attacks. But we show how careless construction in current TTS
instances (TTS/4 and TTS/2') exacerbates the security concern of
rank, and show two different cryptanalysis in under 2^{57} AES
units.
TTS is not the only tame-like PKC with these liabilities – they are
shared by a few other misconstructed schemes. A suitable
equilibrium between speed and security must be struck. We suggest a
generic way to craft tame-like PKC’s more resistant to rank attacks.
A demonstrative TTS variant with similar dimensions is built for
which rank attack takes >2^{80} AES units, while remaining very
fast and as resistant to other attacks. The proposed TTS variants
can scale up.
In short: We show that rank attacks apply to the wider class of
tame-like PKC’s, sometimes even better than previously described.
However, this is relativized by the realization that we can build
adequately resistant tame-like multivariate PKC’s, so the general
theme still seem viable compared to more traditional or large-field
multivariate alternatives.
ePrint: https://eprint.iacr.org/2004/061
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .