Construction of highly nonlinear Boolean functions with four-valued and five-valued spectra

Boolean functions with four-valued and five-valued spectra are of special interest for cryptography applications. By modifying bent functions in the Maiorana-McFarland class, a construction of Boolean functions on even numbers of variables with four-valued and five-valued spectra was presented, and their spectral distributions were determined. The nonlinearity of these functions was proved to be as good as that of semi-bent functions, i.e., <inline-formula><alternatives><math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M5"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msup><mo>-</mo><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mfrac><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></mrow></msup></math><graphic specific-use="big" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/8105B18F-4BC1-4b6f-9E5C-B315287E8921-M005.jpg"><?fx-imagestate width="13.12333298" height="5.16466665"?></graphic><graphic specific-use="small" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/8105B18F-4BC1-4b6f-9E5C-B315287E8921-M005c.jpg"><?fx-imagestate width="13.12333298" height="5.16466665"?></graphic></alternatives></inline-formula> (<inline-formula><alternatives><math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M6"><mi>n</mi></math><graphic specific-use="big" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/8105B18F-4BC1-4b6f-9E5C-B315287E8921-M006.jpg"><?fx-imagestate width="1.60866666" height="2.28600001"?></graphic><graphic specific-use="small" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/8105B18F-4BC1-4b6f-9E5C-B315287E8921-M006c.jpg"><?fx-imagestate width="1.60866666" height="2.28600001"?></graphic></alternatives></inline-formula> was the number of variables), and the algebraic degree could reach any value ranging from 3 to the theoretical upper bound <inline-formula><alternatives><math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M7"><mfrac><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><mo>+</mo><mn mathvariant="normal">1</mn></math><graphic specific-use="big" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/8105B18F-4BC1-4b6f-9E5C-B315287E8921-M007.jpg"><?fx-imagestate width="7.78933382" height="6.18066692"?></graphic><graphic specific-use="small" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/8105B18F-4BC1-4b6f-9E5C-B315287E8921-M007c.jpg"><?fx-imagestate width="7.78933382" height="6.18066692"?></graphic></alternatives></inline-formula>. Furthermore, a subclass of the construction was studied, which consisted of Boolean functions with five-valued spectra, the highest algebraic degree <inline-formula><alternatives><math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M8"><mfrac><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><mo>+</mo><mn mathvariant="normal">1</mn></math><graphic specific-use="big" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/8105B18F-4BC1-4b6f-9E5C-B315287E8921-M008.jpg"><?fx-imagestate width="7.78933382" height="6.18066692"?></graphic><graphic specific-use="small" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/8105B18F-4BC1-4b6f-9E5C-B315287E8921-M008c.jpg"><?fx-imagestate width="7.78933382" height="6.18066692"?></graphic></alternatives></inline-formula>, and without non-zero linear structures.