Compact formulas are derived to represent the Algebraic Normal Form (ANF) of f({\=x} + ā mod 2n) and f({\=x} × ā mod 2n) from the ANF of f, where f is a Boolean function on double struck F sign2n and ā is a constant of double struck F sign2n We compare the algebraic degree of the composed functions with the algebraic degree of the original function f. As an application, the formula for addition modulo 2n is applied in an algebraic attack on the summation generator and the E0 encryption scheme in the Bluetooth keystream generator.
Braeken, A & Semaev, I 2005, The ANF of the composition of addition and multiplication mod 2n with a boolean function. in International workshop on Fast Software Encryption. vol. 3557, Lecture notes in computer science, springer link, pp. 112-125, 12th International Workshop on Fast Software Encryption. FSE 2005, Paris, France, 21/02/05. https://doi.org/10.1007/11502760_8
Braeken, A., & Semaev, I. (2005). The ANF of the composition of addition and multiplication mod 2n with a boolean function. In International workshop on Fast Software Encryption (Vol. 3557, pp. 112-125). (Lecture notes in computer science). springer link. https://doi.org/10.1007/11502760_8
@inproceedings{e39ea0be6bab466a8919a3b73a226d36,
title = "The ANF of the composition of addition and multiplication mod 2n with a boolean function",
abstract = "Compact formulas are derived to represent the Algebraic Normal Form (ANF) of f({\=x} + ā mod 2n) and f({\=x} × ā mod 2n) from the ANF of f, where f is a Boolean function on double struck F sign2n and ā is a constant of double struck F sign2n We compare the algebraic degree of the composed functions with the algebraic degree of the original function f. As an application, the formula for addition modulo 2n is applied in an algebraic attack on the summation generator and the E0 encryption scheme in the Bluetooth keystream generator.",
author = "An Braeken and Igor Semaev",
year = "2005",
doi = "10.1007/11502760_8",
language = "English",
volume = "3557",
series = "Lecture notes in computer science",
publisher = "springer link",
pages = "112--125",
booktitle = "International workshop on Fast Software Encryption",
note = "12th International Workshop on Fast Software Encryption. FSE 2005 ; Conference date: 21-02-2005 Through 23-02-2005",
}