{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T23:19:26Z","timestamp":1773962366468,"version":"3.50.1"},"reference-count":36,"publisher":"Walter de Gruyter GmbH","issue":"3","license":[{"start":{"date-parts":[[2017,9,1]],"date-time":"2017-09-01T00:00:00Z","timestamp":1504224000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Statistical analysis of symmetric key attacks aims to obtain an expression for the data complexity which is the number of plaintext-ciphertext pairs needed to achieve the parameters of the attack.\nExisting statistical analyses invariably use some kind of approximation, the most common being the approximation of the distribution of a sum of random variables by a normal distribution.\nSuch an approach leads to expressions for data complexities which are\n                    <jats:italic>inherently approximate<\/jats:italic>\n                    .\nPrior works do not provide any analysis of the error involved in such approximations.\nIn contrast, this paper takes a rigorous approach to analyzing attacks on block ciphers.\nIn particular, no approximations are used. Expressions for upper bounds on the data complexities of several basic and advanced attacks are obtained.\nThe analysis is based on the hypothesis testing framework. Probabilities of type-I and type-II errors are upper bounded by using standard tail inequalities.\nIn the cases of single linear and differential cryptanalysis, we use the Chernoff bound.\nFor the cases of multiple linear and multiple differential cryptanalysis, Hoeffding bounds are used.\nThis allows bounding the error probabilities and obtaining expressions for data complexities.\nWe believe that our method provides important results for the attacks considered here and more generally, the techniques that we develop should have much wider applicability.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2016-0026","type":"journal-article","created":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T06:01:01Z","timestamp":1505973661000},"page":"147-175","source":"Crossref","is-referenced-by-count":5,"title":["Rigorous upper bounds on data complexities of block cipher cryptanalysis"],"prefix":"10.1515","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5737-2281","authenticated-orcid":false,"given":"Subhabrata","family":"Samajder","sequence":"first","affiliation":[{"name":"Applied Statistics Unit , Indian Statistical Institute , 203, B.T. Road, 700108 Kolkata , India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5346-2650","authenticated-orcid":false,"given":"Palash","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Applied Statistics Unit , Indian Statistical Institute , 203, B.T. Road, 700108 Kolkata , India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2017,9,21]]},"reference":[{"key":"2025120600191285177_j_jmc-2016-0026_ref_001_w2aab3b7b2b1b6b1ab1c13b1Aa","doi-asserted-by":"crossref","unstructured":"M. A.  Abdelraheem, M.  \u00c5 gren, P.  Beelen and G.  Leander,\nOn the distribution of linear biases: Three instructive examples,\nAdvances in Cryptology (Santa Barbara 2012),\nLecture Notes in Comput. Sci. 7417,\nSpringer, Heidelberg (2012), 50\u201367.","DOI":"10.1007\/978-3-642-32009-5_4"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_002_w2aab3b7b2b1b6b1ab1c13b2Aa","doi-asserted-by":"crossref","unstructured":"T.  Baign\u00e8res, P.  Junod and S.  Vaudenay,\nHow far can we go beyond linear cryptanalysis?,\nAdvances in Cryptology (Jeju Island 2004),\nLecture Notes in Comput. Sci. 3329,\nSpringer, Berlin (2004), 432\u2013450.","DOI":"10.1007\/978-3-540-30539-2_31"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_003_w2aab3b7b2b1b6b1ab1c13b3Aa","doi-asserted-by":"crossref","unstructured":"T.  Baign\u00e8res, P.  Sepehrdad and S.  Vaudenay,\nDistinguishing distributions using Chernoff information,\nProvable Security,\nLecture Notes in Comput. Sci. 6402,\nSpringer, Berlin (2010), 144\u2013165.","DOI":"10.1007\/978-3-642-16280-0_10"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_004_w2aab3b7b2b1b6b1ab1c13b4Aa","doi-asserted-by":"crossref","unstructured":"T.  Baign\u00e8res and S.  Vaudenay,\nThe complexity of distinguishing distributions (invited talk),\nInformation Theoretic Security (Calgary 2008),\nLecture Notes in Comput. Sci. 5155,\nSpringer, Berlin (2008), 210\u2013222.","DOI":"10.1007\/978-3-540-85093-9_20"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_005_w2aab3b7b2b1b6b1ab1c13b5Aa","doi-asserted-by":"crossref","unstructured":"E.  Biham, A.  Biryukov and A.  Shamir,\nCryptanalysis of Skipjack reduced to 31 rounds using impossible differentials,\nJ. Cryptology 18 (2005), no. 4, 291\u2013311.\n10.1007\/s00145-005-0129-3","DOI":"10.1007\/s00145-005-0129-3"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_006_w2aab3b7b2b1b6b1ab1c13b6Aa","doi-asserted-by":"crossref","unstructured":"E.  Biham and A.  Shamir,\nDifferential cryptanalysis of DES-like cryptosystems,\nJ. Cryptology 4 (1991), no. 1, 3\u201372.\n10.1007\/BF00630563","DOI":"10.1007\/BF00630563"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_007_w2aab3b7b2b1b6b1ab1c13b7Aa","doi-asserted-by":"crossref","unstructured":"E.  Biham and A.  Shamir,\nDifferential cryptanalysis of DES-like cryptosystems,\nAdvances in Cryptology (Santa Barbara 1990),\nLecture Notes in Comput. Sci. 537,\nSpringer, Berlin (2003), 2\u201321.","DOI":"10.1007\/3-540-38424-3_1"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_008_w2aab3b7b2b1b6b1ab1c13b8Aa","doi-asserted-by":"crossref","unstructured":"A.  Biryukov, C.  De Canni\u00e8re and M.  Quisquater,\nOn multiple linear approximations,\nAdvances in Cryptology (Santa Barbara 2004),\nLecture Notes in Comput. Sci. 3152,\nSpringer, Berlin (2004), 1\u201322.","DOI":"10.1007\/978-3-540-28628-8_1"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_009_w2aab3b7b2b1b6b1ab1c13b9Aa","doi-asserted-by":"crossref","unstructured":"C.  Blondeau, A.  Bogdanov and G.  Leander,\nBounds in shallows and in miseries,\nAdvances in Cryptology (Santa Barbara 2013),\nLecture Notes in Comput. Sci. 8042,\nSpringer, Berlin (2013), 204\u2013221.","DOI":"10.1007\/978-3-642-40041-4_12"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_010_w2aab3b7b2b1b6b1ab1c13c10Aa","doi-asserted-by":"crossref","unstructured":"C.  Blondeau and B.  G\u00e9rard,\nMultiple differential cryptanalysis: Theory and practice,\nFast Software Encryption (Lyngby 2011),\nLecture Notes in Comput. Sci. 6733,\nSpringer, Berlin (2011), 35\u201354.","DOI":"10.1007\/978-3-642-21702-9_3"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_011_w2aab3b7b2b1b6b1ab1c13c11Aa","doi-asserted-by":"crossref","unstructured":"C.  Blondeau, B.  G\u00e9rard and K.  Nyberg,\nMultiple differential cryptanalysis using LLR\\mathrm{LLR} and \u03c72\\chi^{2} statistics,\nSecurity and Cryptography for Networks,\nLecture Notes in Comput. Sci. 7485,\nSpringer, Heidelberg (2012), 343\u2013360.","DOI":"10.1007\/978-3-642-32928-9_19"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_012_w2aab3b7b2b1b6b1ab1c13c12Aa","doi-asserted-by":"crossref","unstructured":"C.  Blondeau, B.  G\u00e9rard and J.-P.  Tillich,\nAccurate estimates of the data complexity and success probability for various cryptanalyses,\nDes. Codes Cryptogr. 59 (2011), no. 1\u20133, 3\u201334.\n10.1007\/s10623-010-9452-2","DOI":"10.1007\/s10623-010-9452-2"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_013_w2aab3b7b2b1b6b1ab1c13c13Aa","doi-asserted-by":"crossref","unstructured":"A.  Bogdanov and E.  Tischhauser,\nOn the wrong key randomisation and key equivalence hypotheses in Matsui\u2019s algorithm 2,\nFast Software Encryption (Singapore 2013),\nLecture Notes in Comput. Sci. 8424,\nSpringer, Berlin (2014), 19\u201338.","DOI":"10.1007\/978-3-662-43933-3_2"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_014_w2aab3b7b2b1b6b1ab1c13c14Aa","doi-asserted-by":"crossref","unstructured":"B.  Collard, F.-X.  Standaert and J.-J.  Quisquater,\nExperiments on the multiple linear cryptanalysis of reduced round serpent,\nFast Software Encryption (Lausanne 2008),\nLecture Notes in Comput. Sci. 5086,\nSpringer, Berlin (2008), 382\u2013397.","DOI":"10.1007\/978-3-540-71039-4_24"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_015_w2aab3b7b2b1b6b1ab1c13c15Aa","unstructured":"B. Collard, F.-X. Standaert and J.-J. Quisquater, data file, 2008."},{"key":"2025120600191285177_j_jmc-2016-0026_ref_016_w2aab3b7b2b1b6b1ab1c13c16Aa","doi-asserted-by":"crossref","unstructured":"I.  Dinur and A.  Shamir,\nCube attacks on tweakable black box polynomials,\nAdvances in Cryptology (Cologne 2009),\nLecture Notes in Comput. Sci. 5479,\nSpringer, Berlin (2009), 278\u2013299.","DOI":"10.1007\/978-3-642-01001-9_16"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_017_w2aab3b7b2b1b6b1ab1c13c17Aa","doi-asserted-by":"crossref","unstructured":"C.  Harpes, G. G.  Kramer and J. L.  Massey,\nA generalization of linear cryptanalysis and the applicability of Matsui\u2019s piling-up lemma,\nAdvances in Cryptology (Saint-Malo 1995),\nLecture Notes in Comput. Sci. 921,\nSpringer, Berlin (1995), 24\u201338.","DOI":"10.1007\/3-540-49264-X_3"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_018_w2aab3b7b2b1b6b1ab1c13c18Aa","doi-asserted-by":"crossref","unstructured":"M.  Hermelin, J. Y.  Cho and K.  Nyberg,\nMultidimensional linear cryptanalysis of reduced round serpent,\nInformation Security and Privacy (Wollongong 2008),\nLecture Notes in Comput. Sci. 5107,\nSpringer, Berlin (2008), 203\u2013215.","DOI":"10.1007\/978-3-540-70500-0_15"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_019_w2aab3b7b2b1b6b1ab1c13c19Aa","doi-asserted-by":"crossref","unstructured":"M.  Hermelin, J. Y.  Cho and K.  Nyberg,\nMultidimensional extension of Matsui\u2019s algorithm 2,\nFast Software Encryption (Leuven 2009),\nLecture Notes in Comput. Sci. 5665,\nSpringer, Berlin (2009), 209\u2013227.","DOI":"10.1007\/978-3-642-03317-9_13"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_020_w2aab3b7b2b1b6b1ab1c13c20Aa","doi-asserted-by":"crossref","unstructured":"P.  Junod,\nOn the optimality of linear, differential, and sequential distinguishers,\nAdvances in Cryptology (Warsaw 2003),\nLecture Notes in Comput. Sci. 2656,\nSpringer, Berlin (2003), 17\u201332.","DOI":"10.1007\/3-540-39200-9_2"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_021_w2aab3b7b2b1b6b1ab1c13c21Aa","doi-asserted-by":"crossref","unstructured":"P.  Junod and S.  Vaudenay,\nOptimal key ranking procedures in a statistical cryptanalysis,\nFast Software Encryption (Lund 2003),\nLecture Notes in Comput. Sci. 2887,\nSpringer, Berlin (2003), 235\u2013246.","DOI":"10.1007\/978-3-540-39887-5_18"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_022_w2aab3b7b2b1b6b1ab1c13c22Aa","doi-asserted-by":"crossref","unstructured":"B. S.  Kaliski, Jr. and M. J. B.  Robshaw,\nLinear cryptanalysis using multiple approximations,\nAdvances in Cryptology (Santa Barbara 1994),\nLecture Notes in Comput. Sci. 839,\nSpringer, Berlin (1994), 26\u201339.","DOI":"10.1007\/3-540-48658-5_4"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_023_w2aab3b7b2b1b6b1ab1c13c23Aa","doi-asserted-by":"crossref","unstructured":"L. R.  Knudsen,\nTruncated and higher order differentials,\nFast Software Encryption (Leuven 1994),\nLecture Notes in Comput. Sci. 1008,\nSpringer, Berlin (1995), 196\u2013211.","DOI":"10.1007\/3-540-60590-8_16"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_024_w2aab3b7b2b1b6b1ab1c13c24Aa","doi-asserted-by":"crossref","unstructured":"X.  Lai,\nHigher order derivatives and differential cryptanalysis,\nCommunications and Cryptography (Ascona 1994),\nKluwer Int. Ser. Eng. Comput. Sci. 276,\nKluwer Academic Publishers, Boston (1994), 227\u2013233.","DOI":"10.1007\/978-1-4615-2694-0_23"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_025_w2aab3b7b2b1b6b1ab1c13c25Aa","doi-asserted-by":"crossref","unstructured":"G.  Leander,\nOn linear hulls, statistical saturation attacks, PRESENT and a cryptanalysis of PUFFIN,\nAdvances in Cryptology (Tallinn 2011),\nLecture Notes in Comput. Sci. 6632,\nSpringer, Heidelberg (2011), 303\u2013322.","DOI":"10.1007\/978-3-642-20465-4_18"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_026_w2aab3b7b2b1b6b1ab1c13c26Aa","doi-asserted-by":"crossref","unstructured":"M.  Matsui,\nLinear cryptanalysis method for DES cipher,\nAdvances in Cryptology (Lofthus 1993),\nLecture Notes in Comput. Sci. 765,\nSpringer, Berlin (1993), 386\u2013397.","DOI":"10.1007\/3-540-48285-7_33"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_027_w2aab3b7b2b1b6b1ab1c13c27Aa","doi-asserted-by":"crossref","unstructured":"M.  Matsui,\nThe first experimental cryptanalysis of the data encryption standard,\nAdvances in Cryptology (Santa Barbara 1994),\nLecture Notes in Comput. Sci. 839,\nSpringer, Berlin (1994), 1\u201311.","DOI":"10.1007\/3-540-48658-5_1"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_028_w2aab3b7b2b1b6b1ab1c13c28Aa","doi-asserted-by":"crossref","unstructured":"M.  Mitzenmacher and E.  Upfal,\nProbability and Computing: Randomized Algorithms and Probabilistic Analysis,\nCambridge University Press, Cambridge, 2005.","DOI":"10.1017\/CBO9780511813603"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_029_w2aab3b7b2b1b6b1ab1c13c29Aa","doi-asserted-by":"crossref","unstructured":"R.  Motwani and P.  Raghavan,\nRandomized Algorithms,\nCambridge University Press, Cambridge, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_030_w2aab3b7b2b1b6b1ab1c13c30Aa","doi-asserted-by":"crossref","unstructured":"S.  Murphy,\nThe independence of linear approximations in symmetric cryptanalysis,\nIEEE Trans. Inform. Theory 52 (2006), no. 12, 5510\u20135518.\n10.1109\/TIT.2006.885528","DOI":"10.1109\/TIT.2006.885528"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_031_w2aab3b7b2b1b6b1ab1c13c31Aa","doi-asserted-by":"crossref","unstructured":"K.  Nyberg and M.  Hermelin,\nMultidimensional walsh transform and a characterization of bent functions,\nProceedings of the 2007 IEEE Information Theory Workshop on Information Theory for Wireless Networks,\nIEEE Press, Solstrand (2007), 83\u201386.","DOI":"10.1109\/ITWITWN.2007.4318037"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_032_w2aab3b7b2b1b6b1ab1c13c32Aa","doi-asserted-by":"crossref","unstructured":"S.  Samajder and P.  Sarkar,\nAnother look at normal approximations in cryptanalysis,\nJ. Math. Cryptol. 10 (2016), no. 2, 69\u201399.","DOI":"10.1515\/jmc-2016-0006"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_033_w2aab3b7b2b1b6b1ab1c13c33Aa","unstructured":"S.  Samajder and P.  Sarkar,\nCan large deviation theory be used for estimating data complexity?,\nCryptology ePrint Archive (2016), https:\/\/eprint.iacr.org\/2016\/465.pdf."},{"key":"2025120600191285177_j_jmc-2016-0026_ref_034_w2aab3b7b2b1b6b1ab1c13c34Aa","doi-asserted-by":"crossref","unstructured":"A. A.  Sel\u00e7uk,\nOn probability of success in linear and differential cryptanalysis,\nJ. Cryptology 21 (2008), no. 1, 131\u2013147.\n10.1007\/s00145-007-9013-7","DOI":"10.1007\/s00145-007-9013-7"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_035_w2aab3b7b2b1b6b1ab1c13c35Aa","doi-asserted-by":"crossref","unstructured":"C.  Tezcan,\nThe improbable differential attack: Cryptanalysis of reduced round CLEFIA,\nProgress in Cryptology (Hyderabad 2010),\nLecture Notes in Comput. Sci. 6498,\nSpringer, Berlin (2010), 197\u2013209.","DOI":"10.1007\/978-3-642-17401-8_15"},{"key":"2025120600191285177_j_jmc-2016-0026_ref_036_w2aab3b7b2b1b6b1ab1c13c36Aa","doi-asserted-by":"crossref","unstructured":"D.  Wagner,\nThe boomerang attack,\nFast Software Encryption (Rome 1999),\nLecture Notes in Comput. Sci. 1636,\nSpringer, Berlin (1999), 156\u2013170.","DOI":"10.1007\/3-540-48519-8_12"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/jmc.2017.11.issue-3\/jmc-2016-0026\/jmc-2016-0026.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2016-0026\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2016-0026\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:19:19Z","timestamp":1764980359000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2016-0026\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,1]]},"references-count":36,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2017,9,21]]},"published-print":{"date-parts":[[2017,9,1]]}},"alternative-id":["10.1515\/jmc-2016-0026"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2016-0026","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"value":"1862-2984","type":"electronic"},{"value":"1862-2976","type":"print"}],"subject":[],"published":{"date-parts":[[2017,9,1]]}}}