IACR paper details
Title  A defect of the implementation schemes of the TTM cryptosystem 

Booktitle  IACR Eprint archive 

Pages  

Year  2003 

URL  http://eprint.iacr.org/2003/085 

Author  Jintai Ding 

Author  Dieter Schmidt 

Abstract 
We show all the existing TTM implementation schemes have a defect that there exist linearization equations
$$
\sum_{i=1,j=1}^{n,m} a_{ij}x_iy_j(x_1,\dots,x_{n})+ \sum_{i=1}^{n} b_ix_i+\sum_{j=1}^{m} c_jy_j(x_1,\dots,x_{n}) + d= 0,
$$
which are satisfied by the components $y_i(x_1,\dots,x_n)$ of the ciphers of the TTM schemes. We further demonstrate that, for the case of the most recent two implementation schemes in two versions of the paper \cite{CM}, where the inventor of TTM used them to refute a claim in \cite{CG}, if we do a linear substitution with the linear equations derived from the linearization equations for a given ciphertext, we can find the plaintext easily by an iteration of the procedure of first search for linear equations by linear combinations and then linear substitution. The computation complexity of the attack on these two schemes is less than $2^{35}$ over a finite field of size $2^8$.


Search for the paper
@misc{eprint200311801,
title={A defect of the implementation schemes of the TTM cryptosystem},
booktitle={IACR Eprint archive},
keywords={publickey cryptography / cryptanalysis, linerization, TTM},
url={http://eprint.iacr.org/2003/085},
note={ ding@math.uc.edu 12172 received 30 Apr 2003},
author={Jintai Ding and Dieter Schmidt},
year=2003
}
Download a complete BibTeX file.