Breaking a new instance of TTM cryptosystems

Xuyun Nie*, Lei Hu, Jianyu Li, Crystal Updegrove, Jintai Ding

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review

14 Citations (Scopus)

Abstract

In 2004, the inventors of TTM cryptosystems proposed a new scheme that could resist the existing attacks, in particular, the Goubin-Courtois attack [GC00] and the Ding-Schmidt attack [DS03]. In this paper, we show the new version is still insecure, and we find that the polynomial components of the cipher (Fi) satisfy nontrivial equations of the special form ∑i=0n-1aixi + ∑ 0≤j≤k≤m-1 bjkFjFk+ ∑ j=0 m-1 cjFj + d = 0, which could be found with 238 computations. From these equations and consequently the linear equations we derive from these equations for any given ciphertext, we can eliminate some of the variables xi by restricting the functions to an affine subspace, such that, on this subspace, we can trivialize the "lock" polynomials, which are the key structure to ensure its security in this new instance of TTM. Then with method similar to Ding-Schmidt [DS03], we can find the corresponding plaintext for any given ciphertext. The total computational complexity of the attack is less than 2 39 operations over a finite field of size 28. Our results are further confirmed by computer experiments.

Original languageEnglish
Title of host publicationApplied Cryptography and Network Security - 4th International Conference, ACNS 2006, Proceedings
PublisherSpringer Verlag
Pages210-225
Number of pages16
ISBN (Print)3540347038, 9783540347033
DOIs
Publication statusPublished - 2006
Externally publishedYes
Event4th International Conference on Applied Cryptography and Network Security, ACNS 2006 - Singapore, Singapore
Duration: 6 Jun 20069 Jun 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3989 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Conference on Applied Cryptography and Network Security, ACNS 2006
Country/TerritorySingapore
CitySingapore
Period6/06/069/06/06

Keywords

  • Multivariate public key cryptography
  • Quadratic polynomial
  • TTM

Fingerprint

Dive into the research topics of 'Breaking a new instance of TTM cryptosystems'. Together they form a unique fingerprint.

Cite this