Welcome to the resource topic for 2004/057
Title:
On Multiple Linear Approximations
Authors: Alex Biryukov, Christophe De Cannière, Michael Quisquater
Abstract:In this paper we study the long standing problem of information
extraction from multiple linear approximations. We develop a formal
statistical framework for block cipher attacks based on this technique
and derive explicit and compact gain formulas for generalized versions
of Matsui’s Algorithm 1 and Algorithm 2. The theoretical framework
allows both approaches to be treated in a unified way, and predicts
significantly improved attack complexities compared to current linear
attacks using a single approximation. In order to substantiate the
theoretical claims, we benchmarked the attacks against reduced-round
versions of DES and observed a clear reduction of the data and time
complexities, in almost perfect correspondence with the predictions.
The complexities are reduced by several orders of magnitude for
Algorithm 1, and the significant improvement in the case of
Algorithm 2 suggests that this approach may outperform the currently
best attacks on the full DES algorithm.
ePrint: https://eprint.iacr.org/2004/057
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .