On arithmetic subtraction linear approximation
January 2005
Pages 125 - 134
Abstract
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.
References
[1]
{1} Biham E., Shamir A. 1993. 'Differential Cryptanalysis of the Data Encryption Standard'. Springer-Verlag, New York.
[2]
{2} Chmiel K. 1998. 'Principles of Differential Cryptanalysis through the Example of the DES Algorithm'. (In Polish). Technical Report No. 461. Poznan University of Technology, Chair of Control, Robotics and Computer Science, Poznan (Oct.).
[3]
{3} Chmiel K. 1999. 'Principles of Linear Cryptanalysis through the Example of the DES Algorithm'. (In Polish). Technical Report No. 471. Poznan University of Technology, Chair of Control, Robotics and Computer Science, Poznan (Oct.).
[4]
{4} Chmiel K. 2000. 'Linear Cryptanalysis of the Reduced DES Algorithms'. Proceedings of the Regional Conference on Military Communication and Information Systems '2000 (Zegrze, Oct. 4-6) WIŁ, Zegrze, vol. 1, pp. 111-118.
[5]
{5} Chmiel K. 2000. 'Differential Cryptanalysis of the Reduced DES Algorithms'. (In Polish). Studia z Automatyki i Informatyki, vol. 25, pp. 127-146.
[6]
{6} Chmiel K. 2000. 'Linear Approximation of S-box Functions'. (In Polish). Technical Report No. 471. Poznan University of Technology, Chair of Control, Robotics and Computer Science, Poznan (Oct.).
[7]
{7} Chmiel K. 2001. 'Linear Approximation of some S-box Functions'. Proceedings of the Regional Conference on Military Communication and Information Systems 2001 (Zegrze, Oct. 10-12) WIŁ, Zegrze, vol. 1, pp. 211-218.
[8]
{8} Chmiel K. 2001. 'Linear Approximation of Arithmetic Sum'. (In Polish). Technical Report No. 481. Poznan University of Technology, Chair of Control, Robotics and Computer Science, Poznan (Oct.).
[9]
{9} Chmiel K. 2002. 'On Some Models of Arithmetic Sum Function Linear Approximation'. Proceedings of NATO Regional Conference on Military Communications and Information Systems 2002 (Zegrze, Oct. 9-11) WIŁ, Zegrze, vol. 2, pp. 199-204.
[10]
{10} Chmiel K. 2002. 'Linear Approximation of Arithmetic Sum Function'. Proceedings of the 9-th International Conference on Advanced Computer Systems ACS'2002 (Miedzyzdroje, Oct. 23-25), Szczecin, vol. 2, pp. 19-28.
[11]
{11} Górska A., Górski K., Kotulski Z., Paszkiewicz A., Szczepanski J. 2001. 'New Experimental Results in Differential - Linear Cryptanalysis of Reduced Variants of DES'. Proceedings of the 8-th International Conference on Advanced Computer Systems ACS'2001, Mielno, vol. 1, pp. 333-346.
[12]
{12} Matsui M. 1993. 'Linear Cryptanalysis Method for DES Cipher'. Advances in Cryptology Eurocrypt'93.
[13]
{13} Matsui M. 1998. 'Linear Cryptanalysis Method for DES Cipher'. Springer-Verlag, New York.
[14]
{14} Zugaj A., Górski K., Kotulski Z., Szczepanski J., Paszkiewicz A. 1999. 'Extending Linear Cryptanalysis - Theory and Experiments'. Proceedings of the Regional Conference on Military Communication and Information Systems '99 (Zegrze, Oct. 6-8) WIŁ, Zegrze, vol. 2, pp. 77-84.
Index Terms
- On arithmetic subtraction linear approximation
Recommendations
Linear approximation of arithmetic sum function
Artificial intelligence and security in computing systemsIn the paper the results concerning the linear approximation of n-bit arithmetic sum function are presented. In particular, the computationally effective algorithms are formulated, to compute values of the approximation tables and the distribution of ...
On the best linear approximation of addition modulo 2n
In this paper, the best linear approximations of addition modulo 2n are studied. Let x = (xnź1, xnź2,ź,x0) and y = (ynź1, ynź2,ź,y0) be any two n-bit integers, and let z = x + y (mod 2n). Firstly, all the correlations of a single bit zi approximated by ...
Multiple Discrete Logarithm Problems with Auxiliary Inputs
Proceedings, Part I, of the 21st International Conference on Advances in Cryptology -- ASIACRYPT 2015 - Volume 9452Let g be an element of prime order p in an abelian group and let $$\alpha _1, \dots , \alpha _L \in {\mathbb Z}_p$$ for a positive integer L. First, we show that, if $$g, g^{\alpha _i}$$, and $$g^{\alpha _i^d}$$$$i=1, \dots , L$$ are given for $$d \mid ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 January 2005
Author Tags
Qualifiers
- Chapter
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 29 Jan 2025