en>Look2See1: Category:Aquifers

2010-09-30T18:40:05Z

Category:Aquifers

New page

[[Image:VEST Core4 LowLevel.png|thumbnail|320px|right|VEST-4 T-function followed by a transposition layer]]

In [[cryptography]], a '''T-function''' is a [[bijection|bijective]] mapping that updates every bit of the [[state (computer science)|state]] in a way that can be described as <math>x_i' = x_i + f(x_0, \cdots, x_{i-1})</math>, 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 used [[Boolean 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 construct [[block cipher]]s, [[stream cipher]]s, [[PRNG]]s and [[cryptographic hash function|hash functions]]. T-functions were first proposed in 2002 by [[Alexander Klimov|A. Klimov]] and [[Adi Shamir|A. Shamir]] in their paper "A New Class of Invertible Mappings". Ciphers such as [[TSC-1]], [[TSC-3]], [[TSC-4]], [[ABC (stream cipher)|ABC]], [[Mir-1]] and [[VEST]] are built with different types of T-functions.

Because [[arithmetic operation]]s such as [[addition]], [[subtraction]] and [[multiplication]] are also T-functions (triangular T-functions), software-efficient word-based T-functions can be constructed by combining [[bitwise logic]] with arithmetic operations. Another important property of T-functions based on arithmetic operations is predictability of their [[period (mathematics)|period]], which is highly attractive to cryptographers. Although triangular T-functions are naturally vulnerable to guess-and-determine attacks, well chosen bitwise [[transposition (mathematics)|transposition]]s between rounds can neutralize that imbalance. In software-efficient [[cipher]]s, it can be done by interleaving arithmetic operations with byte-swapping operations and to a small degree with [[bitwise 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 or [[S-box]]es that satisfy all other cryptographic criteria and even choose arbitrary or key-dependent update functions (see [[family 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
| year = 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
| format = PDF/PostScript }}
* {{cite paper
| author = Magnus Daum
| title = Narrow T-functions
| year = 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 = 18–31
| publisher = Springer-Verlag
| date = 2005
| url = http://www.wisdom.weizmann.ac.il/~ask/t3.ps.gz
| format = [[gzip]]ped PostScript }}

{{Cryptography navbox | block | hash | stream}}

[[Category:Symmetric-key cryptography]]
[[Category:Cryptographic primitives]]

Dupuit assumption - Revision history

en>Look2See1: Category:Aquifers