Cryptology ePrint Archive: Report 2007/448

Generalized Correlation and Higher Order Nonlinearity for Probabilistic Algebraic Attacks Description

Sergiy Pometun

Abstract: Abstract. Algebraic attacks are relatively new and interesting subject in cryptanalysis. The algebraic attacks where introduced in [1], where several possible attack's scenarios where given. The big attention was paid to deterministic scenarios of those. In this paper, probabilistic scenarios are studied. Conception of conditional correlation and partial higher order nonlinearity of Boolean function where introduced (briefly definition of conditional correlation: $C(g,f|f = a): = \Pr (g = f|f = a) - \Pr (g \ne f|f = a)$ ) . It was shown, that the both types of scenarios can be seen as a one unified attack - higher order correlation attack, which uses conditional correlation. The clear criteria of vulnerability of Boolean function to both types of scenarios was given. Accordingly, the notion of the algebraic immunity was extended.

There are very vulnerable functions to probabilistic scenario. Calculations show that if a function with a very low partial higher order nonlinearity was used in the cipher like SFINKS [8], the simple attack would require only about $ 2^{42}$ operations and $32Kb$ of keystream. The question about relation between partial higher order nonlinearity and algebraic immunity remains open yet.

Category / Keywords: foundations / cipher, algebraic attack, Boolean function, algebraic immunity, conditional correlation, partial higher order nonlinearity.

Publication Info: Not published before

Date: received 30 Nov 2007, last revised 30 Nov 2007

Contact author: pomu at mail ru

Available format(s): PDF | BibTeX Citation

Version: 20071205:213416 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]