Paper 2004/061

TTS: Rank Attacks in Tame-Like Multivariate PKCs

Bo-Yin Yang and 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.

Note: taking care of a vulnerability