Paper 2005/016

Narrow T-functions

Magnus Daum


T-functions were introduced by Klimov and Shamir in a series of papers during the last few years. They are of great interest for cryptography as they may provide some new building blocks which can be used to construct efficient and secure schemes, for example block ciphers, stream ciphers or hash functions. In the present paper, we define the narrowness of a T-function and study how this property affects the strength of a T-function as a cryptographic primitive. We define a new data strucure, called a solution graph, that enables solving systems of equations given by T-functions. The efficiency of the algorithms which we propose for solution graphs depends significantly on the narrowness of the involved T-functions. Thus the subclass of T-functions with small narrowness appears to be weak and should be avoided in cryptographic schemes. Furthermore, we present some extensions to the methods of using solution graphs, which make it possible to apply these algorithms also to more general systems of equations, which may appear, for example, in the cryptanalysis of hash functions.

Available format(s)
Publication info
Published elsewhere. An extended abstract of this full version paper will appear at FSE 2005.
cryptanalysishash functionssolution graphT-functions$w$-narrow
Contact author(s)
daum @ cits rub de
2005-01-27: last of 2 revisions
2005-01-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Magnus Daum},
      title = {Narrow T-functions},
      howpublished = {Cryptology ePrint Archive, Paper 2005/016},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.