International Association for Cryptologic Research

International Association
for Cryptologic Research


Jiun-Ming Chen


Note on Design Criteria for Rainbow-Type Multivariates
Jintai Ding Lei Hu Bo-Yin Yang Jiun-Ming Chen
This was a short note that deals with the design of Rainbow or ``stagewise unbalanced oil-and-vinegar'' multivariate signature schemes. We exhibit new cryptanalysis for current schemes that relates to flawed choices of system parameters in current schemes. These can be ameliorated according to an updated list of security design criteria.
TTS: Rank Attacks in Tame-Like Multivariate PKCs
Bo-Yin Yang Jiun-Ming Chen
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.
A More Secure and Efficacious TTS Signature Scheme
Jiun-Ming Chen Bo-Yin Yang
In 2002 the new genre of digital signature scheme TTS (Tame Transformation Signatures) is introduced along with a sample scheme TTS/2. TTS is from the family of multivariate cryptographic schemes to which the NESSIE primitive {SFLASH} also belongs. It is a realization of Moh's theory for digital signatures, based on Tame Transformations or Tame Maps. Properties of multivariate cryptosystems are determined mainly by their central maps. TTS uses Tame Maps as their central portion for even greater speed than $C^\ast$-related schemes (using monomials in a large field for the central portion), previously usually acknowledged as fastest. We show a small flaw in TTS/2 and present an improved TTS implementation which we call TTS/4. We will examine in some detail how well TTS/4 performs, how it stands up to previously known attacks, and why it represents an advance over TTS/2. Based on this topical assessment, we consider TTS in general and TTS/4 in particular to be competitive or superior in several aspects to other schemes, partly because the theoretical roots of TTS induce many good traits. One specific area in which TTS/4 should excel is in low-cost smartcards. It seems that the genre has great potential for practical deployment and deserves further attention by the cryptological community.
On the Goubin-Courtois Attack on TTM
T.Moh Jiun-Ming Chen
In the paper [1] published in ``Asiacrypt 2000", L. Goubin and N.T. Courtois propose an attack on the TTM cryptosystem. In paper [1], they mispresent TTM cryptosystem. Then they jump an attack from an example of TTM to the general TTM cryptosystem. Finally they conclude:"There is very little hope that a secure triangular system (Tame transformation system in our terminology) will ever be proposed". This is serious challenge to many people working in the field. In this paper, we will show that their attack is full of gaps in section 5. Even their attack on one implementation of TTM is questionable. We write a lengthy introduction to restate TTM cryptosystem and point out many possible implementations. It will be clear that their attack on one implementation can not be generalized to attacks on other implementations. As one usually said: "truth is in the fine details", we quote and analysis their TPM system at the end of the introduction and $\S$ 2. We further state one implementations of TTM cryptosystem in $\S$ 3. We analysis their MiniRank(r) attack in $\S$ 4 and show that is infeasible. We conclude that the attack of [1] on the TTM cryptosystem is infeasible and full of gaps. There is no known attacks which can crack the TTM cryptosystem.