×

Walsh transforms and cryptographic applications in bias computing. (English) Zbl 1382.94136

Summary: Walsh transform is used in a wide variety of scientific and engineering applications, including bent functions and cryptanalytic optimization techniques in cryptography. In linear cryptanalysis, it is a key question to find a good linear approximation, which holds with probability \((1+d)/2\) and the bias \(d\) is large in absolute value. The authors [Lect. Notes Comput. Sci. 6829, 16–28 (2011; Zbl 1297.94089)] take a step toward answering this key question in a more generalized setting and initiate the work on the generalized bias problem with linearly-dependent inputs. In this paper, we give fully extended results. Deep insights on assumptions behind the problem are given. We take an information-theoretic approach to show that our bias problem assumes the setting of the maximum input entropy subject to the input constraint. By means of Walsh transform, the bias can be expressed in a simple form. It incorporates Piling-up lemma as a special case. Secondly, as application, we answer a long-standing open problem in correlation attacks on combiners with memory. We give a closed-form exact solution for the correlation involving the multiple polynomial of any weight for the first time. We also give Walsh analysis for numerical approximation. An interesting bias phenomenon is uncovered, i.e., for even and odd weight of the polynomial, the correlation behaves differently. Thirdly, we introduce the notion of weakly biased distribution, and study bias approximation for a more general case by Walsh analysis. We show that for weakly biased distribution, Piling-up lemma is still valid. Our work shows that Walsh analysis is useful and effective to a broad class of cryptanalysis problems.

MSC:

94A60 Cryptography
62E15 Exact distribution theory in statistics
68Q25 Analysis of algorithms and problem complexity
06E30 Boolean functions

Citations:

Zbl 1297.94089

Software:

eSTREAM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bluetooth TM, Bluetooth Specification (version 2.0 + EDR)., http://www.bluetooth.org
[2] Canteaut, A., Trabbia, M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5, EUROCRYPT 2000, LNCS, vol. 1807, pp 573-588. Springer (2000) · Zbl 1082.94509
[3] Chabaud, F., Vaudenay, S.: Links between differential and linear cryptanalysis, EUROCRYPT 1994, LNCS. vol. 950, pp. 356-365. Springer (1995) · Zbl 0879.94023
[4] Charpin, P., Pasalic, E., Tavernier, C.: On bent and semi-bent quadratic Boolean functions. IEEE Trans. Inf. Theory 51(12), 4286-4298 (2005) · Zbl 1184.94234 · doi:10.1109/TIT.2005.858929
[5] Collard, B., Standaert, F. -X., Quisquater, J.-J.: Improving the time complexity of Matsui’s linear cryptanalysis, ICISC 2007, LNCS, vol. 4817, pp 77-88. Springer (2007) · Zbl 1337.94027
[6] Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: an algorithmic point of view, EUROCRYPT 2002, LNCS, vol. 2332, pp 209-221. Springer (2002) · Zbl 1055.94010
[7] Cover, T.M., Thomas, J.A.: Elements of information theory, 2nd Edn. Wiley (2006) · Zbl 1140.94001
[8] eSTREAM: ECRYPT stream cipher project., http://www.ecrypt.eu.org/stream/ · Zbl 0492.94019
[9] Golomb, S. W., Gong, G.: Signal design with good correlation: for wireless communications, cryptography and radar applications. Cambridge University Press, Cambridge (2005) · Zbl 1097.94015 · doi:10.1017/CBO9780511546907
[10] Hakala, R. M., Nyberg, K.: Linear distinguishing attack on Shannon, ACISP 2008, LNCS, vol. 5107, pp 297-305. Springer (2008) · Zbl 1285.94066
[11] Harpes, C., Massey, J.L.: Partitioning cryptanalysis, FSE 1997, LNCS, vol. 1267, pp. 13-27. Springer (1997) · Zbl 1385.94042
[12] Helleseth, T., Kholosha, A.: On generalized bent functions, ITA 2010, pp 178-183. IEEE (2010) · Zbl 1257.11105
[13] Horadam, K.J.: Hadamard Matrices and Their Applications. Princeton University Press, Princeton (2007) · Zbl 1145.05014 · doi:10.1515/9781400842902
[14] Kukorelly, Z.: The Piling-up lemma and dependent random variables, IMA 1999, LNCS, vol. 1746, pp 186-190. Springer (1999) · Zbl 0981.94029
[15] Lidl, R., Niederreiter, H.: Introduction to finite fields and their applications. Cambridge University Press, Cambridge (1986) · Zbl 0629.12016
[16] Löndahl, C., Johansson, T.: Improved algorithms for finding low-weight polynomial multiples in F2[x] and some cryptographic applications, Designs, Codes and Cryptography, vol. 73, pp 625-640. Springer (2014) · Zbl 1335.11098
[17] Lu, Y.: Applied stream ciphers in mobile communications, Ph.D. Thesis, EPFL (2006). doi:10.5075/epfl-thesis-3491
[18] Lu, Y.: Sampling with Walsh transforms (2015). arXiv:1502.06221
[19] Lu, Y., Desmedt, Y.: Bias analysis of a certain problem with applications to E0 and Shannon cipher, ICISC 2010, LNCS, vol. 6829, pp. 16-28. Springer (2011) · Zbl 1297.94089
[20] Lu, Y., Desmedt, Y.: Improved Davies-Murphy’s attack on DES revisited, FPS 2013, LNCS, vol. 8352, pp 264-271. Springer (2014) · Zbl 1184.94234
[21] Lu, Y., Vaudenay, S.: Faster correlation attack on Bluetooth keystream generator E0, CRYPTO 2004, LNCS, vol. 3152, pp 407-425. Springer (2004) · Zbl 1104.94311
[22] Lu, Y., Vaudenay, S.: Cryptanalysis of an E0-like combiner with memory, Journal of Cryptology, vol. 21, pp. 430-457. Springer (2008) · Zbl 1161.94416
[23] Matsui, M.: Linear cryptanalysis method for DES cipher, EUROCRYPT 1993, LNCS, vol. 765, pp 386-397. Springer (1994) · Zbl 0951.94519
[24] Maximov, A., Johansson, T.: Fast computation of large distributions and its cryptographic applications, ASIACRYPT 2005, LNCS, vol. 3788, pp 313-332. Springer (2005) · Zbl 1154.94419
[25] Meier, W., Staffelbach, O.: Fast correlation attacks on certain stream ciphers. J. Cryptol. 1, 159-176 (1989). Springer · Zbl 0673.94010 · doi:10.1007/BF02252874
[26] Meier, W., Staffelbach, O.: Nonlinearity criteria for cryptographic functions, EUROCRYPT 1989, LNCS, vol. 434, pp 549-562. Springer (1990) · Zbl 0724.94009
[27] Meier, W., Staffelbach, O.: Correlation properties of combiners with memory in stream ciphers. J. Cryptol. 5, 67-86 (1992). Springer · Zbl 0743.94023 · doi:10.1007/BF00191322
[28] Meier, W.: Fast correlation attacks: methods and countermeasures, FSE 2011, LNCS, vol. 6733, pp 55-67. Springer (2011) · Zbl 1282.94056
[29] Menezes, A.J., van Oorschot, P.C., Vanstone, S. A.: Handbook of applied cryptography. CRC Press (1996) · Zbl 0868.94001
[30] Molland, H., Helleseth, T.: An improved correlation attack against irregular clocked and filtered keystream generators, CRYPTO 2004, LNCS, vol. 3152, pp 373-389. Springer (2004) · Zbl 1104.94031
[31] Nyberg, K.: Perfect nonlinear S-boxes, EUROCRYPT 1991, LNCS, vol. 547, pp 378-386. Springer (1991) · Zbl 0766.94012
[32] Nyberg, K.: Constructions of Bent functions and difference sets, EUROCRYPT 1990, LNCS, vol. 473, pp. 151-160. Springer (1991) · Zbl 0767.05031
[33] Olsen, J., Scholtz, R., Welch, L.: Bent-function sequences. IEEE Trans. Inf. Theory IT-28(6), 858-864 (1982) · Zbl 0492.94019 · doi:10.1109/TIT.1982.1056589
[34] Pearl, J.: Application of Walsh transform to statistical analysis. IEEE Trans. Syst. Man Cybern. SMC-1(2), 111-119 (1971) · Zbl 0226.62114 · doi:10.1109/TSMC.1971.4308267
[35] Rose, G., Hawkes, P., Paddon, M., McDonald, C., Vries, M.: Design and primitive specification for Shannon, Symmetric Cryptography (2007) · Zbl 0492.94019
[36] Rothaus, O. S.: On “Bent” functions. J. Comb. Theory Ser. A 20(3), 300-305 (1976) · Zbl 0336.12012 · doi:10.1016/0097-3165(76)90024-8
[37] Wagner, D.: A generalized birthday problem, CRYPTO 2002, LNCS, vol. 2442, pp. pp. 288-304. Springer (2002) · Zbl 1026.94541
[38] Yaroslavsky, L.P.: Digital picture processing - an introduction. Springer, Berlin (1985) · Zbl 0585.94001 · doi:10.1007/978-3-642-81929-2
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.