International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Generalized Correlation and Higher Order Nonlinearity for Probabilistic Algebraic Attacks Description

Sergiy Pometun
Search ePrint
Search Google
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.
  title={Generalized Correlation and Higher Order Nonlinearity for Probabilistic Algebraic Attacks Description},
  booktitle={IACR Eprint archive},
  keywords={foundations / cipher, algebraic attack, Boolean function, algebraic immunity, conditional correlation, partial higher order nonlinearity.},
  note={Not published before 13848 received 30 Nov 2007, last revised 30 Nov 2007},
  author={Sergiy Pometun},