×

On degree-\(d\) zero-sum sets of full rank. (English) Zbl 1443.94118

Summary: A set \(S \subseteq{{\mathbb{F}}_2^n}\) is called degree-\(d\) zero-sum if the sum \({\sum }_{s \in S} f(s)\) vanishes for all \(n\)-bit Boolean functions of algebraic degree at most \(d\). Those sets correspond to the supports of the \(n\)-bit Boolean functions of degree at most \(n - d - 1\). We prove some results on the existence of degree-\(d\) zero-sum sets of full rank, i.e., those that contain \(n\) linearly independent elements, and show relations to degree-1 annihilator spaces of Boolean functions and semi-orthogonal matrices. We are particularly interested in the smallest of such sets and prove bounds on the minimum number of elements in a degree-\(d\) zero-sum set of rank \(n\). The motivation for studying those objects comes from the fact that degree-\(d\) zero-sum sets of full rank can be used to build linear mappings that preserve special kinds of nonlinear invariants, similar to those obtained from orthogonal matrices and exploited by Y. Todo et al. [Lect. Notes Comput. Sci. 10032, 3–33 (2016; Zbl 1380.94126)] for breaking the block ciphers Midori, Scream and iScream.

MSC:

94D10 Boolean functions
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
94A60 Cryptography

Citations:

Zbl 1380.94126

Software:

Midori
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Banik, S., Bogdanov, A., Isobe, T., Shibutani, K., Hiwatari, H., Akishita, T., Regazzoni, F.: Midori: a block cipher for low energy. In: Iwata, T., Cheon, J.H. (eds.) Advances in Cryptology - ASIACRYPT 2015, volume 9453 of Lecture Notes in Computer Science, pp 411-436. Springer, Berlin (2015) · Zbl 1382.94057
[2] Bannier, A., Filiol, E.: Partition-based trapdoor ciphers. In: Partition-Based Trapdoor Ciphers. InTech (2017)
[3] Boura, C., Canteaut, A.: Another view of the division property. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology - CRYPTO 2016, volume 9814 of Lecture Notes in Computer Science, pp 654-682. Springer, Berlin (2016) · Zbl 1378.94026
[4] Camion, P., Carlet, C., Charpin, P., Sendrier. N.: On correlation-immune functions. In: Feigenbaum, J. (ed.) Advances in Cryptology - CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pp 86-100. Springer, Berlin (1991) · Zbl 0763.94006
[5] Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P. (eds.) Boolean Methods and Models. Cambridge University Press, Cambridge (2007) · Zbl 1209.94035
[6] Courtois, N.: Feistel schemes and bi-linear cryptanalysis. In: Franklin, M. (ed.) Advances in Cryptology - CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pp 23-40. Springer, Berlin (2004) · Zbl 1104.94308
[7] Grosso, V., Leurent, G., Standaert, F.-X., Varici, K.: LS-designs: bitslice encryption for efficient masked software implementations. In: Cid, C., Rechberger, C. (eds.) Fast Software Encryption, volume 8540 of Lecture Notes in Computer Science, pp 18-37. Springer, Berlin (2015) · Zbl 1382.94111
[8] Harpes, C., Kramer, G.G., Massey, J.L.: A generalization of linear cryptanalysis and the applicability of Matsui’s piling-up lemma. In: Guillou, L.C., Quisquater, J.-J. (eds.) Advances in Cryptology - EUROCRYPT’95, volume 921 of Lecture Notes in Computer Science, pp 24-38. Springer, Berlin (1995) · Zbl 0973.94522
[9] Hedayat, A.; Sloane, N.; Stufken, J., Orthogonal Arrays. Springer Series in Statistics (1999), New York: Springer, New York · Zbl 0935.05001
[10] Hedayat, A.; Wallis, W., Hadamard matrices and their applications, Ann. Stat., 6, 6, 1184-1238 (1978) · Zbl 0401.62061 · doi:10.1214/aos/1176344370
[11] Kasami, T.; Tokura, N., On the weight structure of Reed-Muller codes, IEEE Trans. Inf. Theory, 16, 6, 752-759 (1970) · Zbl 0205.20604 · doi:10.1109/TIT.1970.1054545
[12] Kasami, T.; Tokura, N.; Azumi, S., On the weight enumeration of weights less than 2.5d of Reed-Muller codes, Inf. Control., 30, 4, 380-395 (1976) · Zbl 0324.94003 · doi:10.1016/S0019-9958(76)90355-7
[13] Knudsen, L.R., Robshaw, M.J.B.: Non-linear approximations in linear cryptanalysis. In: Maurer, U. (ed.) Advances in Cryptology - EUROCRYPT’96, volume 1070 of Lecture Notes in Computer Science, pp 224-236. Springer, Berlin (1996) · Zbl 1304.94069
[14] Lai, X.: Higher order derivatives and differential cryptanalysis. In: Blahut, R.E., Costello, D.J., Maurer, U., Mittelholzer, T. (eds.) Communications and Cryptography. The Springer International Series in Engineering and Computer Science (Communications and Information Theory), volume 276, pp 227-233. Springer, Boston (1994)
[15] MacWilliams, FJ; Sloane, NJA, The Theory of Error-Correcting Codes, vol. 16 (1977), North-Holland: Elsevier, North-Holland · Zbl 0369.94008
[16] Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) Advances in Cryptology - EUROCRYPT’93, volume 765 of Lecture Notes in Computer Science, pp 386-397. Springer, Berlin (1994) · Zbl 0951.94519
[17] Meier, W., Pasalic, E., Carlet, C.: Algebraic attacks and decomposition of boolean functions. In: Cachin, C., Camenisch, J. (eds.) Advances in Cryptology - EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pp 474-491. Springer, Berlin (2004) · Zbl 1122.94041
[18] Patarin, J., Goubin, L.: Asymmetric cryptography with s-boxes. In: Han, Y., Okamoto, T., Qing, S. (eds.) Information and Communication Security, volume 1334 of Lecture Notes in Computer Science, pp 369-380. Springer, Berlin (1997) · Zbl 0893.94045
[19] Phelps, K.T., Rifà, J., Villanueva, M.: Hadamard codes of length 2^ts (s odd). Rank and kernel. In: Fossorier, M.P.C., Imai, H., Lin, S., Poli, A. (eds.) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 3857 of Lecture Notes in Computer Science, pp 328-337. Springer, Berlin (2006) · Zbl 1125.94045
[20] Rijmen, V., Preneel, B.: A family of trapdoor ciphers. In: Biham, E. (ed.) Fast Software Encryption, volume 1267 of Lecture Notes in Computer Science, pp 139-148. Springer, Berlin (1997) · Zbl 1385.94066
[21] Siegenthaler, T., Correlation-immunity of nonlinear combining functions for cryptographic applications, IEEE Trans. Inf. Theory, 30, 5, 776-780 (1984) · Zbl 0554.94010 · doi:10.1109/TIT.1984.1056949
[22] Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology - EUROCRYPT 2015, volume 9056 of Lecture Notes in Computer Science, pp 287-314. Springer, Berlin (2015) · Zbl 1370.94545
[23] Todo, Y., Leander, G., Sasaki, Y.: Nonlinear invariant attack. In: Cheon, J., Takagi, T. (eds.) Advances in Cryptology - ASIACRYPT 2016, volume 10032 of Lecture Notes in Computer Science, pp 3-33. Springer, Berlin (2016) · Zbl 1380.94126
[24] Todo, Y.; Leander, G.; Sasaki, Y., Nonlinear invariant attack: practical attack on full SCREAM, iSCREAM, and Midori64, J. Cryptol., 32, 4, 1383-1422 (2019) · Zbl 1435.94141 · doi:10.1007/s00145-018-9285-0
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.