**Narrow T-functions**

*Magnus Daum*

**Abstract: **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.

**Category / Keywords: **cryptanalysis, hash functions, solution graph, T-functions, $w$-narrow

**Publication Info: **An extended abstract of this full version paper will appear at FSE 2005.

**Date: **received 22 Jan 2005, last revised 27 Jan 2005

**Contact author: **daum at cits rub de

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20050127:190938 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]