- T-function
In
cryptography , a T-function is a bijective mapping that updates every bit of the state in a way that can be described as x_i' = x_i + f(x_0, cdots, x_{i-1}), or in simple words an update function in which each bit of the state is updated by a linear combination of the same bit and a function of a subset of its less significant bits. If every single less significant bit is included in the update of every bit in the state, such a T-function is called triangular. Thanks to their bijectivity (no collisions, therefore no entropy loss) regardless of the usedBoolean function s and regardless of the selection of inputs (as long as they all come from one side of the output bit), T-functions are now widely used in cryptography to constructblock cipher s,stream cipher s,PRNG s and hash functions. T-functions were first proposed in 2002 by A. Klimov and A. Shamir in their paper "A New Class of Invertible Mappings". Ciphers such asTSC-1 ,TSC-3 ,TSC-4 , ABC,Mir-1 andVEST are built with different types of T-functions.Because
arithmetic operation s such asaddition ,subtraction andmultiplication are also T-functions (triangular T-functions), software-efficient word-based T-functions can be constructed by combiningbitwise logic with arithmetic operations. Another important property of T-functions based on arithmetic operations is predictability of their period, which is highly attractive to cryptographers. Although triangular T-functions are naturally vulnerable to guess-and-determine attacks, well chosen bitwise transpositions between rounds can neutralize that imbalance. In software-efficientcipher s, it can be done byinterleaving arithmetic operations with byte-swapping operations and to a small degree withbitwise rotation operations. However, triangular T-functions remain highly inefficient in hardware.T-functions do not have any restrictions on the types and the widths of the update functions used for each bit. Subsequent transposition of the output bits and
iteration of the T-function also do not affect bijectivity. This freedom allows the designer to choose the update functions orS-box es that satisfy all other cryptographic criteria and even choose arbitrary or key-dependent update functions (seefamily keying ).Hardware-efficient lightweight T-functions with identical widths of all the update functions for each bit of the state can thus be easily constructed. The core accumulators of VEST ciphers are a good example of such reasonably light-weight T-functions that are balanced out after 2 rounds by the transposition layer making all the 2-round feedback functions of roughly the same width and losing the "T-function" bias of depending only on the less significant bits of the state.
References
* cite paper
author = A. Klimov, A. Shamir
title = A New Class of Invertible Mappings
date = 2002
url = http://citeseer.ist.psu.edu/klimov02new.html
format =PDF /PostScript
* cite conference
author = A. Klimov, A. Shamir
title = Cryptographic Applications of T-functions
booktitle =Selected Areas in Cryptography , SAC 2003, LNCS 3006
pages = 248-261
publisher =Springer-Verlag
date = 2003
url = http://citeseer.ist.psu.edu/klimov03cryptographic.html
format = PDF/PostScript
* cite conference
author = A. Klimov, A. Shamir
title = New Cryptographic Primitives Based on Multiword T-functions
booktitle =Fast Software Encryption , FSE 2004, LNCS 3017
pages = 1-15
publisher = Springer-Verlag
date = 2004
url = http://citeseer.ist.psu.edu/klimov04new.html
format = PDF/PostScript
* cite paper
author = Magnus Daum
title = Narrow T-functions
date = 2005
url = http://citeseer.ist.psu.edu/daum05narrow.html
format = PDF/PostScript
* cite conference
author = J. Hong, D. Lee, Y. Yeom, and D. Han
title = A New Class of Single Cycle T-functions
booktitle = Fast Software Encryption, FSE 2005, LNCS 3557
pages = 68-82
publisher = Springer-Verlag
date = 2005
* cite conference
author = A. Klimov and A. Shamir
title = New Applications of T-functions in Block Ciphers and Hash Functions
booktitle = Fast Software Encryption, FSE 2005, LNCS 3557
pages = pp.18-31
publisher = Springer-Verlag
date = 2005
url = http://www.wisdom.weizmann.ac.il/~ask/t3.ps.gz
format =gzip ped PostScript
Wikimedia Foundation. 2010.