Two characterizations of crooked functions
Two characterizations of crooked functions
Chris Godsil∗ Aidan Roy†
October 26, 2018
Abstract
We give two characterizations of crooked functions: one based on the minimum
distance of a Preparata-like code, and the other based on the distance-regularity of a
crooked graph.
1 Introduction
Highly nonlinear functions over finite vector spaces have attracted much interest in the
last several years, for both their applications to cryptography (see [8] for example) and
their connections to a variety of different combinatorial structures. The functions that
are furthest from linear are called perfect nonlinear; unfortunately, none exist for binary
vector spaces, which are the most cryptographically useful. However functions do exist
in several lesser categories of nonlinearity, such as almost perfect nonlinear, almost bent,
and crooked. We focus on the latter, which is the most specialized of the three.
Crooked functions were introduced by Bending and Fon Der Flaass [2], who, build-
ing on the graphs of de Caen, Mathon and Moorhouse [9], showed that every crooked
function defines a distance-regular graph of diameter 3 with a particular intersection
array. Shortly thereafter, van Dam and Fon Der Flaass [14] observed that every crooked
function defines a binary code of minimum distance 5, similar to the classical Preparata
code. In this paper, we show that the converse of each of these results is also true:
crooked functions can be characterized using both Preparata-like codes (Theorem 3)
and distance-regular graphs (Theorem 5). Those codes and graphs offer a more combi-
natorial way of understanding the nature of nonlinear binary functions.
2 Almost Perfect Nonlinear Functions
Before considering crooked functions we need to characterize a more general class,
namely almost perfect nonlinear functions. Throughout this article, let V := V (m, 2),
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON N2L 3G1.
email: cgodsil@uwaterloo.ca. CG is supported by NSERC.
Institute for Quantum Information Science, University of Calgary, Calgary, AB, T2N 1N4.
email: aroy@qis.ucalgary.ca. AR is supported by NSERC and MITACS.
http://arxiv.org/abs/0704.1293v1
a vector space of dimension m over F2, with m odd. Given a function f : V → V ,
consider the following system of equations:
x+ y = a
f(x) + f(y) = b
. (1)
Note that solutions to (1) come in pairs: if (x, y) is a solution, then so is (y, x). If f is a
linear function, then equation (1) has 2m solutions when b = f(a). We say f is almost
perfect nonlinear if, for every (a, b) 6= (0, 0), the system has at most two solutions.
Equivalently, f is almost perfect nonlinear if and only if for all a 6= 0 in V , the set
Ha(f) := {f(x) + f(x+ a) | x ∈ V }
has cardinality 2m−1.
We may construct a binary code from a function on V in the following manner.
Identify V with the finite field F2m , and let α be a primitive element of F2m . Also let
n = 2m− 1, and assume f : V → V is a function such that f(0) = 0. We define a parity
check matrix Hf by
Hf :=
1 α α2 . . . αn−1
f(1) f(α) f(α2) . . . f(αn−1)
and define the code Cf to be the kernel of Hf over F2.
The code Cf can be thought of as a generalization of the double error-correcting
BCH code, which is the specific case of f(α) := α3. It is clear from the parity check
matrix that the minimum distance of Cf is at least 3, and it can be shown that the
minimum distance is at most 5. The following characterization is due to Carlet, Charpin,
and Zinoviev [7, Theorem 5].
Theorem 1. The minimum distance of Cf is 5 if and only if f is almost perfect
nonlinear. In this case, the dimension of Cf is
k = 2m − 2m− 1.
In the next section, we give a similar characterization of crooked functions, which
are a special class of almost perfect nonlinear functions.
3 Crooked Functions and Preparata-like Codes
A function f : V → V is crooked if the following three conditions hold:
1. f(0) = 0;
2. f(x) + f(y) + f(z) 6= f(x+ y + z) for distinct x, y, and z;
3. f(x) + f(y) + f(z) 6= f(x+ a) + f(y + a) + f(z + a) for all a 6= 0.
Condition 2 is equivalent to almost perfect nonlinearity; thus every crooked function
is almost perfect nonlinear. Condition 3 states that for every a 6= 0, no three points
in Ha(f) are collinear. It follows that f is crooked if and only if f(0) = 0 and Ha(f)
is the complement of a hyperplane for all a 6= 0. Note that we are using the original
definition of crooked functions given in [2], rather than the generalization appearing in
Byrne and McGuire [6] or Kyureghyan [12].
The canonical example of a crooked function is the Gold function. Identify V with
F2m for odd m; then f(x) := x
+1 is called a Gold function if gcd(k,m) = 1. More gen-
erally, f(x) := x2
is crooked provided that gcd(k − j,m) = 1, and Kyureghyan [12]
has shown that all crooked power functions have this form. For recent progress in con-
structing nonlinear functions which are not equivalent to the Gold functions, see [4, 5,
Just as almost perfect nonlinear functions give rise to BCH-like codes, crooked func-
tions give to Preparata-like codes. Given f : V → V such that f(0) = 0, let Pf be the
code whose codewords are the characteristic vectors of (S, T ), for S ⊂ V ∗ and T ⊂ V ,
such that the following three conditions hold:
• |T | is even,
r, and
f(r) +
f(r).
Identifying V with F2m , we get the actual Preparata code when f(x) := x
3 and the
generalized Preparata code when f(x) = x2
+1 (see [1]). In general Pf is not linear,
and it is easy to verify that Pf always has minimum distance at least 3. The following
result is due to Van Dam and Fon Der Flaass [14, Theorem 7].
Theorem 2. If f is crooked, then Pf has minimum distance 5 and size 2
−2m−2.
If Pf has minimum distance 5, then it is nearly perfect: it satisfies the Johnson
bound [13, Theorem 17.13] with equality. Hence Pf has minimum distance at most 5
for any f . We show the converse of Theorem 2.
Theorem 3. If Pf has minimum distance 5, then f is crooked.
Proof. We assumed in the definition of Pf that f(0) = 0, so condition 1 of crookedness
is satisfied. If Pf has minimum distance 5, then there is no pair (φ, T ) in Pf with
|T | = 4. That is, for any distinct w, x, y, z such that w + x+ y + z = 0,
f(w) + f(x) + f(y) + f(z) 6= 0. (2)
Thus condition 2 of crookedness is also satisfied, and it remains to show condition 3.
Since condition 2 is saitsfied, f is almost perfect nonlinear and Cf has dimension 2
2m− 1 by Theorem 1. But Cf is the kernel of Hf , so it follows that Hf has a column
space of dimension 2m, namely V × V . This implies that for any (a, b) in V × V , there
is a subset S of V ∗ such that
= (a, b). (3)
Given any x ∈ V , let T = {x, 0}, so that |T | is even and
r = x. Then from
equation (3), there exists some S ⊂ V ∗ such that
= (x, 0) .
Choosing S in this way, (S, T ) is in Pf . Now given any y, z and a 6= 0, consider
(S′, T ′) := (S ⊕ {y} ⊕ {y + a}, T ⊕ {z} ⊕ {z + a}).
This vector is at distance 4 from (S, T ). Since Pf has distance 5, (S
′, T ′) must not be
in Pf . But |T
′| is even, and
r∈T ′
hence for (S′, T ′) /∈ Pf it must be the case that
f(r) +
r∈T ′
f(r).
This implies
f(x+ a) 6=
f(r) + f(y) + f(y + a) +
f(r) + f(z) + f(z + a),
or in other words
f(x+ a) 6= f(y) + f(y + a) + f(x) + f(z) + f(z + a).
Thus condition 3 of crookedness is satisfied for f .
4 Crooked Graphs
As usual, assume f(0) = 0. Define the crooked graph of f , denoted Gf , to have vertex
set V ×F2×V with the following adjacency condition: distinct (a, i, α) and (b, j, β) are
adjacent if and only if
α+ β = f(a+ b) + (i+ j + 1)(f(a) + f(b)).
It is not difficult to show that any two vertices in the subset
Fai := {(a, i, α) | α ∈ V }
are at distance at least three, and that any two distinct subsets Fai and Fbj are joined
by a perfect matching. It follows that Gf is a 2
m-cover of the complete graph K2m+1 ,
and each Fai is a fibre (for background on covers of complete graphs, see [11]). The
following theorem is given by Bending and Fon-Der-Flaass [2, Proposition 13].
Theorem 4. If f is crooked, then Gf is an antipodal distance-regular graph with inter-
section array
{2m+1 − 1, 2m+1 − 2, 1; 1, 2, 2m+1 − 1}.
For background on distance-regular graphs, see [3]. Again, we show the converse.
Theorem 5. If Gf is distance-regular with intersection array
{2m+1 − 1, 2m+1 − 2, 1; 1, 2, 2m+1 − 1},
then f is crooked.
Proof. For convenience, consider the graph G′f which consists of Gf with a loop added
to every vertex. This can be done by removing the restriction (a, i, α) 6= (b, j, β) from
the adjacency condition of Gf . If Gf is distance-regular with a1 = 0 and c2 = 2,
then G′
is a graph with the property that any two vertices at distance 1 or 2 have
exactly two common neighbours. That is, for any two vertices (a, i, α), (b, j, β) such
that (a, i) 6= (b, j), there are exactly two vertices (c, k, γ) such that
α+ γ = f(a+ c) + (i+ k + 1)(f(a) + f(c)), (4)
β + γ = f(b+ c) + (j + k + 1)(f(b) + f(c)). (5)
We restrict our attention to the cases in which i = j, so that a 6= b. Adding (4) and (5)
together, there are exactly two pairs (c, k) such that
α+ β = f(a+ c) + f(b+ c) + (i+ k + 1)(f(a) + f(b)).
Running over all values of α+ β, we see that for fixed (a, b, i), the multiset
{f(a+ c) + f(b+ c) + (i + k + 1)(f(a) + f(b)) | c ∈ V, k ∈ F2}
= {f(a+ c) + f(b+ c) | c ∈ V } ∪ {f(a+ c) + f(b+ c) + f(a) + f(b) | c ∈ V } (6)
contains each element of V exactly twice.
Now for some fixed c, consider f(a+ c) + f(b+ c). Letting c′ := c+ a+ b, we have
f(a+ c) + f(b+ c) = f(a+ c′) + f(b+ c′).
However, the value f(a + c) + f(b + c) only occurs twice in (6), so there is no third
solution c′′ 6= c, c′ such that
f(a+ c) + f(b+ c) = f(a+ c′′) + f(b+ c′′).
In other words, letting x = a+ c, y = b+ c, and z = a+ c′′, we have
f(x) + f(y) 6= f(z) + f(x+ y + z)
for z 6= x, y. This is condition 2 of crookedness for f . Also because f(a+ c) + f(b+ c)
has already occured twice in (6), there is no c′′ such that
f(a+ c) + f(b+ c) = f(a+ c′′) + f(b+ c′′) + f(a) + f(b).
Setting x = a+ c, y = a+ c′′, z = a and w = a+ b, we have
f(x) + f(x+ w) 6= f(y) + f(y + w) + f(z) + f(z + w)
for any x, y, z and w, with w 6= 0. This is the condition 3 of crookedness, so f is
crooked.
References
[1] Ronald D. Baker, Jacobus H. van Lint, and Richard M. Wilson. On the Preparata
and Goethals codes. IEEE Trans. Inform. Theory, 29(3):342–345, 1983.
[2] T. D. Bending and D. Fon-Der-Flaass. Crooked functions, bent functions, and
distance regular graphs. Electron. J. Combin., 5(1):Research Paper 34, 14 pp.
(electronic), 1998.
[3] A. E. Brouwer, A. M. Cohen, and A. Neumaier. Distance-Regular Graphs. Springer-
Verlag, Berlin, 1989.
[4] Lilya Budaghyan, Claude Carlet, Patrick Felke, and Gregor Leander. An infinite
class of quadratic apn functions which are not equivalent to power mappings. In
Information Theory, 2006 IEEE International Symposium on, pages 2637–2641,
2006.
[5] Lilya Budaghyan, Claude Carlet, and Alexander Pott. New classes of almost
bent and almost perfect nonlinear polynomials. IEEE Trans. Inform. Theory,
52(3):1141–1152, 2006.
[6] Eimear Byrne and Gary McGuire. On the non-existence of
quadratic apn and crooked functions on finite fields. 2005.
http://www.maths.may.ie/staff/gmg/APNniceWeilEBGMG.pdf.
[7] Claude Carlet, Pascale Charpin, and Victor Zinoviev. Codes, bent functions
and permutations suitable for DES-like cryptosystems. Des. Codes Cryptogr.,
15(2):125–156, 1998.
[8] Florent Chabaud and Serge Vaudenay. Links between differential and linear crypt-
analysis. In Advances in cryptology—EUROCRYPT ’94 (Perugia), volume 950 of
Lecture Notes in Comput. Sci., pages 356–365. Springer, Berlin, 1995.
[9] D. de Caen, R. Mathon, and G. E. Moorhouse. A family of antipodal distance-
regular graphs related to the classical Preparata codes. J. Algebraic Combin.,
4(4):317–327, 1995.
[10] Yves Edel, Gohar Kyureghyan, and Alexander Pott. A new APN function which is
not equivalent to a power mapping. IEEE Trans. Inform. Theory, 52(2):744–747,
2006.
[11] C. D. Godsil and A. D. Hensel. Distance regular covers of the complete graph. J.
Combin. Theory Ser. B, 56(2):205–238, 1992.
[12] Gohar Kyureghyan. Crooked maps in finite fields. In 2005 European Conference on
Combinatorics, Graph Theory and Applications (EuroComb ’05), Discrete Mathe-
matics & Theoretical Computer Science Proceedings, AE, pages 167–170, 2005.
[13] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes.
North-Holland Publishing Co., Amsterdam, 1977.
[14] E. R. van Dam and D. Fon-Der-Flaass. Uniformly packed codes and more distance
regular graphs from crooked functions. J. Algebraic Combin., 12(2):115–121, 2000.
	Introduction
	Almost Perfect Nonlinear Functions
	Crooked Functions and Preparata-like Codes
	Crooked Graphs
