Show/Hide Menu
Hide/Show Apps
anonymousUser
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Açık Bilim Politikası
Açık Bilim Politikası
Frequently Asked Questions
Frequently Asked Questions
Browse
Browse
By Issue Date
By Issue Date
Authors
Authors
Titles
Titles
Subjects
Subjects
Communities & Collections
Communities & Collections
Counting Boolean functions with faster points
Date
2020-09-01
Author
Salagean, Ana
Özbudak, Ferruh
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
6
views
0
downloads
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 l as being a fast point a so that the degree of the derivative of f in direction a is lower by at least l 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 l. Furthermore, we determine the number of functions of degree d in n variables which have a given number of fast points of order l, 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 l. 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.
Subject Keywords
Applied mathematics
,
Computer science applications
URI
https://hdl.handle.net/11511/36054
Journal
DESIGNS CODES AND CRYPTOGRAPHY
DOI
https://doi.org/10.1007/s10623-020-00738-7
Collections
Department of Mathematics, Article