A unified analysis for the fast correlation attack

Abstract

In this paper, a general framework which enables to compare previously proposed approaches for the fast correlation attacks is developed. All attacks are based on decoding using a set of parity check sums of an underlying linear code. The purpose of this paper is two-fold: To provide a simple close form estimate about the number of check sums of a particular structure necessary for the corresponding attack to succeed. To illustrate how such estimates are useful in minimizing the computational complexity of each attack considered, and consequently, in establishing a unified framework for comparison.