A family of skew Hadamard difference sets. (English) Zbl 1106.05016

Summary: In 1933 a family of skew Hadamard difference sets was described by Paley using matrix language and was called the Paley-Hadamard difference sets in the literature. During the last 70 years, no new skew Hadamard difference sets were found. It was conjectured that there are no further examples of skew Hadamard difference sets. This conjecture was proved to be true for the cyclic case in 1954, and further progress in favor of this conjecture was made in the past 50 years. However, the conjecture remains open until today. In this paper, we present a family of new perfect nonlinear (also called planar) functions, and construct a family of skew Hadamard difference sets using these perfect nonlinear functions. We show that some of the skew Hadamard difference sets presented in this paper are inequivalent to the Paley-Hadamard difference sets. These new examples of skew Hadamard difference sets discovered 70 years after the Paley construction disprove the longstanding conjecture on skew Hadamard difference sets. The class of new perfect nonlinear functions has applications in cryptography, coding theory, and combinatorics.


05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)
Full Text: DOI


[1] Beth, T.; Jungnickel, D.; Lenz, H., Design Theory (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0945.05004
[2] Camion, P.; Mann, H. B., Antisymmetric difference sets, J. Number Theory, 4, 266-268 (1972) · Zbl 0275.05010
[3] Carlet, C.; Ding, C., Highly nonlinear mappings, J. Complexity, 20, 2, 205-244 (2004) · Zbl 1053.94011
[4] Chen, Y. Q.; Xiang, Q.; Sehgal, S. K., An exponent bound on skew Hadamard abelian difference sets, Des. Codes Cryptogr., 4, 313-317 (1994) · Zbl 0807.05012
[5] Coulter, R. S.; Matthews, R. W., Planar functions and planes of Lenz-Barlotti class II, Des. Codes Cryptogr., 10, 167-184 (1997) · Zbl 0872.51007
[6] Dembowski, P.; Ostrom, T. G., Planes of order \(n\) with collineation groups of order \(n^2\), Math. Z., 193, 239-258 (1968) · Zbl 0163.42402
[7] Johnson, E. C., Skew-Hadamard abelian group difference sets, J. Algebra, 4, 388-402 (1966) · Zbl 0178.33502
[8] Jungnickel, D., On \(λ\)-ovals and difference sets, (Bodendieck, R., Contemporary Methods in Graph Theory (1990), Bibliographisches Institut: Bibliographisches Institut Mannheim), 429-448 · Zbl 0746.51016
[9] Jungnickel, D., Difference sets, (Dinitz, J.; Stinson, D. R., Contemporary Design Theory, A Collection of Surveys. Contemporary Design Theory, A Collection of Surveys, Wiley-Intersci. Ser. Discrete Math. Optim. (1992), Wiley: Wiley New York), 241-324 · Zbl 0768.05013
[10] Jungnickel, D.; Schmidt, B., Difference sets: An update, (Hirschfeld, J. W.P.; Magliveras, S. S.; Resmini, M. J. de, Geometry, Combinatorial Designs and Related Structures (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 89-112 · Zbl 0883.05023
[11] Kelly, J. B., A characteristic property of quadratic residues, Proc. Amer. Math. Soc., 5, 38-46 (1954) · Zbl 0055.03702
[12] Lidl, R.; Mullen, G. L.; Turnwald, G., Dickson Polynomials (1993), Longman: Longman Essex · Zbl 0823.11070
[13] Lidl, R.; Niederreiter, H., Finite Fields (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge
[14] Ma, S. L., Planar functions, relative difference sets, and character theory, J. Algebra, 185, 2, 342-356 (1996) · Zbl 0865.05020
[15] Ma, S. L.; Pott, A., Relative difference sets, planar functions, and generalized Hadamard matrices, J. Algebra, 175, 2, 505-525 (1995) · Zbl 0830.05012
[16] Michael, T. S.; Wallis, W. D., Skew-Hadamard matrices and the Smith normal form, Des. Codes Cryptogr., 13, 173-176 (1998) · Zbl 0891.15006
[17] Nyberg, K., Perfect nonlinear \(S\)-boxes, (Advances in Cryptology, Proc. of Eurocrypt ’91. Advances in Cryptology, Proc. of Eurocrypt ’91, Lecture Notes in Comput. Sci., vol. 547 (1992), Springer-Verlag: Springer-Verlag Berlin), 378-386 · Zbl 0766.94012
[18] Rothaus, O. S., On bent functions, J. Combin. Theory Ser. A, 20, 300-305 (1976) · Zbl 0336.12012
[19] Paley, R. E.A. C., On orthogonal matrices, J. Math. Phys. MIT, 12, 311-320 (1933) · Zbl 0007.10004
[20] Pott, A., Nonlinear functions in abelian groups and relative difference sets, Discrete Appl. Math., 138, 177-193 (2004) · Zbl 1035.05023
[21] Roman, S., Field Theory (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0816.12001
[22] Store, T., Cyclotomy and Difference Sets (1967), Markham: Markham Chicago · Zbl 0157.03301
[23] Xiang, Q., Recent results on \(p\)-ranks and Smith normal forms of some \(2-(v, k, \lambda)\) designs, (Evans, D.; etal., Coding Theory and Quantum Computing. Coding Theory and Quantum Computing, Contemp. Math., vol. 381 (2005), Amer. Math. Soc.: Amer. Math. Soc. Providense, RI), 53-67 · Zbl 1087.05013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.