On Arithmetic Subtraction Linear Approximation
Krzysztof Chmiel · Kluwer Academic Publishers eBooks · 2006
In the paper two methods of linear approximation of n-bit arithmetic subtraction function are considered. In the first method, called the model of approximation of a single S-box, approximations are calculated for arbitrary m consecutive bits, where m ≤ n is limited by the size of so-called table of pairs TP, used during calculation. In the second method, called the model of exact composition of approximations, the subtraction approximations are calculated as a composition of k approximations of m-bit subtraction cells, where m ≤ n is limited by the size of the same table of pairs TP. In the first method, the set of nonzero approximations is limited to approximations in the range of m consecutive bits while in the second method is not limited. For n-bit arithmetic subtraction function however, the approximation probability can be calculated with use of the methods in time O(l) and O(k), respectively.