Abstract:
TTM is a type of Multivariate public key cryptosystem. By analyzing the instance of TTM proposed in 2004, it can be found that there are many first order linearization equations satisfied by the cipher in this scheme. For a given public key, all first order linearization equations can be found through precomputation. For any given ciphertext, the corresponding plaintext can be found in less than 219 operations over a finite field of size 28 by linearization equation attack. This attack reduced complexity of recovering plaintext from 231 to 219 compare to second order linearization equation attack. The results above are further confirmed by computer experiments.