Paper 2003/085

A defect of the implementation schemes of the TTM cryptosystem

Jintai Ding and 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$.

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptanalysislinerizationTTM
Contact author(s)
ding @ math uc edu
History
2003-05-02: received
Short URL
https://ia.cr/2003/085
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/085,
      author = {Jintai Ding and Dieter Schmidt},
      title = {A  defect of the implementation schemes of the TTM cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2003/085},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/085}},
      url = {https://eprint.iacr.org/2003/085}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.