{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:31:26Z","timestamp":1764981086726,"version":"3.46.0"},"reference-count":25,"publisher":"Walter de Gruyter GmbH","issue":"4","license":[{"start":{"date-parts":[[2018,6,19]],"date-time":"2018-06-19T00:00:00Z","timestamp":1529366400000},"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":[[2018,12,1]]},"abstract":"Abstract<\/jats:title>\n \n A\n block<\/jats:italic>\n is an\n n<\/jats:italic>\n -bit string, and a (possibly keyed)\n block-function<\/jats:italic>\n is a non-linear mapping that maps one block to another, e.g., a block-cipher. In this paper, we consider various symmetric key primitives with\n \n \n \n \u2113<\/m:mi>\n <\/m:math>\n \n {\\ell}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n block inputs and raise the following question:\n what is the minimum number of block-function invocations required for a mode to be secure?<\/jats:italic>\n We begin with encryption modes that generate\n \n \n \n \n \u2113<\/m:mi>\n \u2032<\/m:mo>\n <\/m:msup>\n <\/m:math>\n \n {\\ell^{\\prime}}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n block outputs and show that at least\n \n \n \n \n (<\/m:mo>\n \n \n \u2113<\/m:mi>\n +<\/m:mo>\n \n \u2113<\/m:mi>\n \u2032<\/m:mo>\n <\/m:msup>\n <\/m:mrow>\n -<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:math>\n \n {(\\ell+\\ell^{\\prime}-1)}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n block-function invocations are necessary to achieve the PRF security. In presence of a nonce, the requirement of block-functions reduces to\n \n \n \n \n \u2113<\/m:mi>\n \u2032<\/m:mo>\n <\/m:msup>\n <\/m:math>\n \n {\\ell^{\\prime}}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n blocks only. If\n \n \n \n \n \u2113<\/m:mi>\n =<\/m:mo>\n \n \u2113<\/m:mi>\n \u2032<\/m:mo>\n <\/m:msup>\n <\/m:mrow>\n <\/m:math>\n \n {\\ell=\\ell^{\\prime}}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , in order to achieve SPRP security, the mode requires at least\n \n \n \n \n 2<\/m:mn>\n \u2062<\/m:mo>\n \u2113<\/m:mi>\n <\/m:mrow>\n <\/m:math>\n \n {2\\ell}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n many block-function invocations. We next consider length preserving\n r<\/jats:italic>\n -block (called\n chunk<\/jats:italic>\n ) online encryption modes and show that, to achieve online PRP security, each chunk should have at least\n \n \n \n \n \n 2<\/m:mn>\n \u2062<\/m:mo>\n r<\/m:mi>\n <\/m:mrow>\n -<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n <\/m:math>\n \n {2r-1}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n many and overall at least\n \n \n \n \n \n 2<\/m:mn>\n \u2062<\/m:mo>\n r<\/m:mi>\n \u2062<\/m:mo>\n \u2113<\/m:mi>\n <\/m:mrow>\n -<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n <\/m:math>\n \n {2r\\ell-1}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n many block-functions for\n \n \n \n \u2113<\/m:mi>\n <\/m:math>\n \n {\\ell}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n many chunks. Moreover, we show that it can achieve online SPRP security if each chunk contains at least\n \n \n \n \n 2<\/m:mn>\n \u2062<\/m:mo>\n r<\/m:mi>\n <\/m:mrow>\n <\/m:math>\n \n {2r}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n non-linear block-functions. We next analyze affine MAC modes and show that an integrity-secure affine MAC mode requires at least\n \n \n \n \u2113<\/m:mi>\n <\/m:math>\n \n {\\ell}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n many block-function invocations to process an\n \n \n \n \u2113<\/m:mi>\n <\/m:math>\n \n {\\ell}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n block message. Finally, we consider affine mode authenticated encryption and show that in order to achieve INT-RUP security or integrity security under a nonce-misuse scenario, either (i) the number of non-linear block-functions required to generate the ciphertext is more than\n \n \n \n \u2113<\/m:mi>\n <\/m:math>\n \n {\\ell}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n or (ii) the number of extra non-linear block-functions required to generate the tag depends on\n \n \n \n \u2113<\/m:mi>\n <\/m:math>\n \n {\\ell}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1515\/jmc-2017-0011","type":"journal-article","created":{"date-parts":[[2018,6,19]],"date-time":"2018-06-19T18:15:46Z","timestamp":1529432146000},"page":"241-259","source":"Crossref","is-referenced-by-count":3,"title":["On the optimality of non-linear computations for symmetric key primitives"],"prefix":"10.1515","volume":"12","author":[{"given":"Avik","family":"Chakraborti","sequence":"first","affiliation":[{"name":"NTT Secure Platform Laboratories , Tokyo , Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nilanjan","family":"Datta","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering , Indian Institute of Technology , Kharagpur , India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mridul","family":"Nandi","sequence":"additional","affiliation":[{"name":"Applied Statistics Unit , Indian Statistical Institute , Kolkata , India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2018,6,19]]},"reference":[{"key":"2025120600294183895_j_jmc-2017-0011_ref_001_w2aab3b7b1b1b6b1ab1b7b1Aa","doi-asserted-by":"crossref","unstructured":"M. Bellare, A. Boldyreva, L. Knudsen and C. Namprempre,\nOn-line ciphers and the hash-cbc constructions,\nAdvances in Cryptology\u2014CRYPTO 2001,\nLecture Notes in Comput. Sci. 2139,\nSpringer, Berlin (2001), 292\u2013309.","DOI":"10.1007\/3-540-44647-8_18"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_002_w2aab3b7b1b1b6b1ab1b7b2Aa","doi-asserted-by":"crossref","unstructured":"M. Bellare, J. Kilian and P. Rogaway,\nThe security of cipher block chaining,\nAdvances in Cryptology\u2014CRYPTO 1994,\nLecture Notes in Comput. Sci. 839,\nSpringer, Berlin (1994), 341\u2013358.","DOI":"10.1007\/3-540-48658-5_32"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_003_w2aab3b7b1b1b6b1ab1b7b3Aa","doi-asserted-by":"crossref","unstructured":"T. P. Berger, M. Minier and G. Thomas,\nExtended generalized feistel networks using matrix representation,\nSelected Areas in Cryptography\u2014SAC 2013,\nSpringer, Berlin (2014), 289\u2013305.","DOI":"10.1007\/978-3-662-43414-7_15"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_004_w2aab3b7b1b1b6b1ab1b7b4Aa","doi-asserted-by":"crossref","unstructured":"J. Black and P. Rogaway,\nA block-cipher mode of operations for parallelizable message authentication,\nAdvances in Cryptology\u2014Eurocrypt 2002,\nLecture Notes in Comput. Sci. 2332,\nSpringer, Berlin (2002), 384\u2013397.","DOI":"10.1007\/3-540-46035-7_25"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_005_w2aab3b7b1b1b6b1ab1b7b5Aa","doi-asserted-by":"crossref","unstructured":"A. Chakraborti, N. Datta and M. Nandi,\nINT-RUP analysis of block-cipher based authenticated encryption schemes,\nTopics in Cryptology\u2014CT-RSA 2016,\nLecture Notes in Comput. Sci. 9610,\nSpringer, Berlin (2016), 39\u201354.","DOI":"10.1007\/978-3-319-29485-8_3"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_006_w2aab3b7b1b1b6b1ab1b7b6Aa","doi-asserted-by":"crossref","unstructured":"D. Chakraborty and M. Nandi,\nAn improved security bound for HCTR,\nFast Software Encryption\u2014FSE 2008,\nLecture Notes in Comput. Sci. 5086,\nSpringer, Berlin (2008), 289\u2013302.","DOI":"10.1007\/978-3-540-71039-4_18"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_007_w2aab3b7b1b1b6b1ab1b7b7Aa","doi-asserted-by":"crossref","unstructured":"S. Halevi,\nEME*: Extending EME to handle arbitrary-length messages with associated data,\nProgress in Cryptology\u2014INDOCRYPT 2004,\nLecture Notes in Comput. Sci. 3348,\nSpringer, Berlin (2004), 315\u2013327.","DOI":"10.1007\/978-3-540-30556-9_25"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_008_w2aab3b7b1b1b6b1ab1b7b8Aa","doi-asserted-by":"crossref","unstructured":"S. Halevi,\nInvertible universal hashing and the TET encryption mode,\nAdvances in Cryptology\u2014CRYPTO 2007,\nLecture Notes in Comput. Sci. 4622,\nSpringer, Berlin (2007), 412\u2013429.","DOI":"10.1007\/978-3-540-74143-5_23"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_009_w2aab3b7b1b1b6b1ab1b7b9Aa","doi-asserted-by":"crossref","unstructured":"S. Halevi and P. Rogaway,\nA tweakable enciphering mode,\nAdvances in Cryptology\u2014CRYPTO 2003,\nLecture Notes in Comput. Sci. 2729,\nSpringer, Berlin (2003), 482\u2013499.","DOI":"10.1007\/978-3-540-45146-4_28"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_010_w2aab3b7b1b1b6b1ab1b7c10Aa","doi-asserted-by":"crossref","unstructured":"S. Halevi and P. Rogaway,\nA parallelizable enciphering mode,\nTopics in Cryptology\u2014CT-RSA 2004,\nLecture Notes in Comput. Sci. 2964,\nSpringer, Berlin (2004), 292\u2013304.","DOI":"10.1007\/978-3-540-24660-2_23"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_011_w2aab3b7b1b1b6b1ab1b7c11Aa","doi-asserted-by":"crossref","unstructured":"V. T. Hoang and P. Rogaway,\nOn generalized feistel networks,\nAdvances in Cryptology\u2014CRYPTO 2010,\nSpringer, Berlin (2010), 613\u2013630.","DOI":"10.1007\/978-3-642-14623-7_33"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_012_w2aab3b7b1b1b6b1ab1b7c12Aa","doi-asserted-by":"crossref","unstructured":"T. Iwata and K. Kurosawa,\nOmac: One-key cbc mac,\nFast Software Encryption\u2014FSE 2003,\nLecture Notes in Comput. Sci. 2887,\nSpringer, Berlin (2003), 129\u2013153.","DOI":"10.1007\/978-3-540-39887-5_11"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_013_w2aab3b7b1b1b6b1ab1b7c13Aa","doi-asserted-by":"crossref","unstructured":"C. S. Jutla,\nEncryption modes with almost free message integrity,\nAdvances in Cryptology\u2014EUROCRYPT 2001,\nLecture Notes in Comput. Sci. 2045,\nSpringer, Berlin (2003), 529\u2013544.","DOI":"10.1007\/3-540-44987-6_32"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_014_w2aab3b7b1b1b6b1ab1b7c14Aa","doi-asserted-by":"crossref","unstructured":"C. S. Jutla,\nPrf domain extension using dag,\nTheory of Cryptography\u2014TCC 2006,\nLecture Notes in Comput. Sci. 3876,\nSpringer, Berlin (2006), 561\u2013580.","DOI":"10.1007\/11681878_29"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_015_w2aab3b7b1b1b6b1ab1b7c15Aa","doi-asserted-by":"crossref","unstructured":"C. S. Jutla,\nEncryption modes with almost free message integrity,\nJ. Cryptology 21 (2008), no. 4, 547\u2013578.\n10.1007\/s00145-008-9024-z","DOI":"10.1007\/s00145-008-9024-z"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_016_w2aab3b7b1b1b6b1ab1b7c16Aa","doi-asserted-by":"crossref","unstructured":"K. Kurosawa and T. Iwata,\nTmac: Two-key cbc mac,\nTopics in Cryptology\u2014CT-RSA 2003,\nLecture Notes in Comput. Sci. 2612,\nSpringer, Berlin (2003), 33\u201349.","DOI":"10.1007\/3-540-36563-X_3"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_017_w2aab3b7b1b1b6b1ab1b7c17Aa","doi-asserted-by":"crossref","unstructured":"M. Luby and C. Rackoff,\nHow to construct pseudo-random permutations from pseudo-random functions,\nAdvances in Cryptology\u2014CRYPTO 1985,\nLecture Notes in Comput. Sci. 218,\nSpringer, New York (1984), 447\u2013447.","DOI":"10.1007\/3-540-39799-X_34"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_018_w2aab3b7b1b1b6b1ab1b7c18Aa","doi-asserted-by":"crossref","unstructured":"M. Nandi,\nTwo new efficient cca-secure online ciphers: Mhcbc and mcbc,\nProgress in Cryptology\u2014INDOCRYPT 2008,\nLecture Notes in Comput. Sci. 5365,\nSpringer, Berlin (2008), 350\u2013362.","DOI":"10.1007\/978-3-540-89754-5_27"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_019_w2aab3b7b1b1b6b1ab1b7c19Aa","doi-asserted-by":"crossref","unstructured":"M. Nandi,\nA unified method for improving PRF bounds for a class of blockcipher based macs,\nFast Software Encryption\u2014FSE 2010,\nLecture Notes in Comput. Sci. 6147,\nSpringer, Berlin (2010), 212\u2013229.","DOI":"10.1007\/978-3-642-13858-4_12"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_020_w2aab3b7b1b1b6b1ab1b7c20Aa","doi-asserted-by":"crossref","unstructured":"M. Nandi,\nOn the optimality of non-linear computations of length-preserving encryption schemes,\nAdvances in Cryptology\u2014ASIACRYPT 2015 Part II,\nSpringer, Berlin (2015), 113\u2013133.","DOI":"10.1007\/978-3-662-48800-3_5"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_021_w2aab3b7b1b1b6b1ab1b7c21Aa","doi-asserted-by":"crossref","unstructured":"P. Rogaway,\nEfficient instantiations of tweakable blockciphers and refinements to modes ocb and pmac,\nAdvances in Cryptology\u2014ASIACRYPT 2004,\nLecture Notes in Comput. Sci. 3329,\nSpringer, Berlin (2004), 16\u201331.","DOI":"10.1007\/978-3-540-30539-2_2"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_022_w2aab3b7b1b1b6b1ab1b7c22Aa","doi-asserted-by":"crossref","unstructured":"P. Rogaway and H. Zhang,\nOnline ciphers from tweakable blockciphers,\nTopics in Cryptology\u2014CT-RSA 2011,\nLecture Notes in Comput. Sci. 6558,\nSpringer, Berlin (2011), 237\u2013249.","DOI":"10.1007\/978-3-642-19074-2_16"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_023_w2aab3b7b1b1b6b1ab1b7c23Aa","doi-asserted-by":"crossref","unstructured":"P. Sarkar,\nImproving upon the tet mode of operation,\nInformation Security and Cryptology\u2014ICISC 2007,\nLecture Notes in Computer Science 4817,\nSpringer, Berlin (2007), 180\u2013192.","DOI":"10.1007\/978-3-540-76788-6_15"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_024_w2aab3b7b1b1b6b1ab1b7c24Aa","doi-asserted-by":"crossref","unstructured":"P. Wang, D. Feng and W. Wu,\nHCTR: A variable-input-length enciphering mode,\nInformation Security and Cryptology\u2014CISC 2005,\nLecture Notes in Comput. Sci. 3822,\nSpringer, Berlin (2005), 175\u2013188.","DOI":"10.1007\/11599548_15"},{"key":"2025120600294183895_j_jmc-2017-0011_ref_025_w2aab3b7b1b1b6b1ab1b7c25Aa","unstructured":"L. Zhang, W. Wu, H. Sui and P. Wang,\niFeed[AES] v1, 2014, https:\/\/competitions.cr.yp.to\/round1\/ifeedaesv1.pdf."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/jmc.2018.12.issue-4\/jmc-2017-0011\/jmc-2017-0011.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2017-0011\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2017-0011\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:29:51Z","timestamp":1764980991000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2017-0011\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,19]]},"references-count":25,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,6,19]]},"published-print":{"date-parts":[[2018,12,1]]}},"alternative-id":["10.1515\/jmc-2017-0011"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2017-0011","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2018,6,19]]}}}