imported>Elleh3113: Added short description

2024-08-21T16:53:14Z

Added short description

New page

{{Short description|Mathematical function used in cryptography}}
[[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, [[Pseudorandom number generator|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 (stream cipher)|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 book
| last1=Klimov | first1=Alexander
| last2=Shamir | first2=Adi
| year = 2002
| chapter=A New Class of Invertible Mappings
| chapter-url = https://link.springer.com/content/pdf/10.1007/3-540-36400-5_34.pdf
| title=Cryptographic Hardware and Embedded Systems - CHES 2002
| series=Lecture Notes in Computer Science
| volume=2523
| pages = 470–483
| publisher = [[Springer-Verlag]]
| doi=10.1007/3-540-36400-5_34
| isbn=978-3-540-00409-7
| s2cid=29129205
}}
* {{cite book
| last1=Klimov | first1=Alexander
| last2=Shamir | first2=Adi
| date = 2003
| chapter=Cryptographic Applications of T-Functions
| title=Selected Areas in Cryptography
| series=Lecture Notes in Computer Science
| volume=3006
| pages = 248–261
| publisher = Springer-Verlag
| doi=10.1007/978-3-540-24654-1_18
| isbn=978-3-540-21370-3
| s2cid=30281166
}}
* {{cite book
| last1=Klimov | first1=Alexander
| last2=Shamir | first2=Adi
| date = 2004
| chapter=New Cryptographic Primitives Based on Multiword T-Functions
| title=Fast Software Encryption
| series=Lecture Notes in Computer Science
| volume=3017
| pages = 1–15
| publisher = Springer-Verlag
| doi=10.1007/978-3-540-25937-4_1
| isbn=978-3-540-22171-5
}}
* {{cite book
| last1 = Daum | first1 = Magnus
| year = 2005
| chapter = Narrow T-Functions
| title = Fast Software Encryption
| series = Lecture Notes in Computer Science
| volume = 3557
| pages = 50–67
| publisher = Springer-Verlag
| doi = 10.1007/11502760_4
| isbn = 978-3-540-26541-2
}}
* {{cite book
| last1 = Hong | first1 = Jin
| last2 = Lee | first2 = Dong Hoon
| last3 = Yeom | first3 = Yongjin
| last4 = Han | first4 = Daewan
| date = 2005
| chapter = A New Class of Single Cycle T-Functions
| title = Fast Software Encryption
| series = Lecture Notes in Computer Science
| volume = 3557
| pages = 68–82
| publisher = Springer-Verlag
| doi=10.1007/11502760_5
| isbn = 978-3-540-26541-2
}}
* {{cite book
| last1 = Klimov | first1 = Alexander
| last2 = Shamir | first2 = Adi
| date = 2005
| chapter = New Applications of T-Functions in Block Ciphers and Hash Functions
| title = Fast Software Encryption
| series = Lecture Notes in Computer Science
| volume = 3557
| pages = 18–31
| publisher = Springer-Verlag
| doi=10.1007/11502760_2
| isbn = 978-3-540-26541-2
}}

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

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

T-function - Revision history

imported>Elleh3113: Added short description