Loughborough University
Browse

Counting Boolean functions with faster points

Download (335.94 kB)
journal contribution
posted on 2020-03-23, 09:47 authored by Ana SalageanAna Salagean, Ferruh Özbudak
Duan and Lai introduced the notion of “fast point” for a Boolean function f as being a direction a so that the algebraic degree of the derivative of f in direction a is strictly lower than the expected deg( f ) − 1. Their study was motivated by the fact that the existence of fast points makes many cryptographic differential attacks (such as the cube and AIDA attack) more efficient. The number of functions with fast points was determined by Duan et al. in some special cases and by Salagean and Mandache-Salagean in the general case. We generalise the notion of fast point, defining a fast point of order ? as being a fast point a so that the degree of the derivative of f in direction a is lower by at least ? than the expected degree.
We determine an explicit formula for the number of functions of degree d in n variables which have fast points of order ?. Furthermore, we determine the number of functions of degree d in n variables which have a given number of fast points of order ?, and also the number of functions which have a given profile in terms of the number of fast points of each order. We apply our results to compute the probability of a function to have fast points of order ?. We also compute the number of functions which admit linear structures (i.e. their derivative in a certain direction is constant); such functions have a long history of being used in the analysis of symmetric ciphers.

Funding

Newton Mobility Grant NI170158

History

School

  • Science

Department

  • Computer Science

Published in

Designs, Codes and Cryptography

Volume

88

Issue

9

Pages

1867 - 1883

Publisher

Springer Science and Business Media LLC

Version

  • VoR (Version of Record)

Rights holder

© the Authors

Publisher statement

This is an Open Access Article. It is published by Springer under the Creative Commons Attribution 4.0 Unported Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/4.0/

Acceptance date

2020-02-05

Publication date

2020-03-11

Copyright date

2020

ISSN

0925-1022

eISSN

1573-7586

Language

  • en

Depositor

Dr Ana Salagean . Deposit date: 20 March 2020