[Resource Topic] 2003/085: A defect of the implementation schemes of the TTM cryptosystem

Resource Public-key cryptography
#1

Welcome to the resource topic for 2003/085

Title:
A defect of the implementation schemes of the TTM cryptosystem

Authors: Jintai Ding, 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.

ePrint: https://eprint.iacr.org/2003/085

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 .