{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T14:42:11Z","timestamp":1740148931994,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T00:00:00Z","timestamp":1637280000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T00:00:00Z","timestamp":1637280000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cryptogr. Commun."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we want to estimate the nonlinearity of Boolean functions, by probabilistic methods, when it is computationally very expensive, or perhaps not feasible to compute the full Walsh transform (which is the case for almost all functions in a larger number of variables, say more than 30). Firstly, we significantly improve upon the bounds of Zhang and Zheng (1999) on the probabilities of failure of affinity tests based on nonhomomorphicity, in particular, we prove a new lower bound that we have previously conjectured. This new lower bound generalizes the one of Bellare et al. (IEEE Trans. Inf. Theory <jats:bold>42<\/jats:bold>(6), 1781\u20131795 1996) to nonhomomorphicity tests of arbitrary order. Secondly, we prove bounds on the probability of failure of a proposed affinity test that uses the BLR linearity test. All these bounds are expressed in terms of the function\u2019s nonlinearity, and we exploit that to provide probabilistic methods for estimating the nonlinearity based upon these affinity tests. We analyze our estimates and conclude that they have reasonably good accuracy, particularly so when the nonlinearity is low.<\/jats:p>","DOI":"10.1007\/s12095-021-00529-4","type":"journal-article","created":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T13:02:41Z","timestamp":1637326961000},"page":"459-481","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improving bounds on probabilistic affine tests to estimate the nonlinearity of Boolean functions"],"prefix":"10.1007","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8942-375X","authenticated-orcid":false,"given":"Ana","family":"S\u0103l\u0103gean","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8622-7120","authenticated-orcid":false,"given":"Pantelimon","family":"St\u0103nic\u0103","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,19]]},"reference":[{"issue":"6","key":"529_CR1","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1109\/18.556674","volume":"42","author":"M Bellare","year":"1996","unstructured":"Bellare, M., Coppersmith, D., H\u00e5stad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. IEEE Trans. Inf. Theory 42(6), 1781\u20131795 (1996)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"529_CR2","unstructured":"Bera, D., Maitra, S., Roy, D., St\u0103nic\u0103, P.: Limitation of the BLR testing in estimating nonlinearity. In: Workshop on Coding and Cryptography, Rennes, France, Paper #50 (2019)"},{"issue":"3","key":"529_CR3","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. J. Comput. Syst Sci. 47(3), 549\u2013595 (1993)","journal-title":"J. Comput. Syst Sci."},{"key":"529_CR4","doi-asserted-by":"crossref","unstructured":"Bullen, P. S.: Handbook of means and their inequalities. Springer (2003)","DOI":"10.1007\/978-94-017-0399-4"},{"key":"529_CR5","volume-title":"Cryptographic Boolean Functions and Applications","author":"TW Cusick","year":"2017","unstructured":"Cusick, T. W., St\u0103nic\u0103, P.: Cryptographic Boolean Functions and Applications, 2nd edn. Academic Press, San Diego (2017)","edition":"2nd edn."},{"key":"529_CR6","volume-title":"Cube attacks on tweakable black box polynomials. Adv. in Crypt. \u2013 EUROCRYPT pp. 278\u2013299, LNCS 5479","author":"I Dinur","year":"2009","unstructured":"Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. Adv. in Crypt. \u2013 EUROCRYPT pp. 278\u2013299, LNCS 5479. Springer, Berlin (2009)"},{"issue":"3-4","key":"529_CR7","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s12095-012-0068-4","volume":"4","author":"I Dinur","year":"2012","unstructured":"Dinur, I., Shamir, A.: Applying cube attacks to stream ciphers in realistic scenarios. Cryptogr. Communic. 4(3-4), 217\u2013232 (2012)","journal-title":"Cryptogr. Communic."},{"key":"529_CR8","unstructured":"Do\u011fanaksoy, A., Sa\u011fdi\u00e7o\u011flu, S., Saygi, Z., U\u011fuz, M.: A note on linearity and homomorphicity. In: Michon, J.-F., Valarcher, P., Yun\u00e8s, J.-B. (eds.) Boolean Functions: Cryptography and Applications, pp 280\u2013295 (2006)"},{"issue":"5","key":"529_CR9","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1137\/080715548","volume":"39","author":"T Kaufman","year":"2010","unstructured":"Kaufman, T., Litsyn, S., Xie, N.: Breaking the \ud835\udf16-soundness bound of the linearity test over GF(2). SIAM J. Computing 39(5), 1988\u20132003 (2010)","journal-title":"SIAM J. Computing"},{"key":"529_CR10","first-page":"373","volume-title":"An Improved Correlation Attack Against Irregular Clocked and Filtered Keystream Generators. Adv. in Crypt. \u2013 CRYPTO 2004","author":"H Molland","year":"2004","unstructured":"Molland, H., Helleseth, T.: An Improved Correlation Attack Against Irregular Clocked and Filtered Keystream Generators. Adv. in Crypt. \u2013 CRYPTO 2004, pp 373\u2013389. Springer, Berlin (2004)"},{"key":"529_CR11","unstructured":"S\u0103l\u0103gean, A., St\u0103nic\u0103, P.: Estimating the nonlinearity of Boolean functions using probabilistic linearity tests. Proc. Sequences and Their Applications \u2013 SETA 2020, Paper #45 (2020)"},{"key":"529_CR12","unstructured":"Vielhaber, M., Breaking, O.N.E.: FIVIUM by AIDA an algebraic IV differential attack. Cryptology ePrint Archive Report 2007\/413. http:\/\/eprint.iacr.org\/ (2007)"},{"key":"529_CR13","doi-asserted-by":"crossref","unstructured":"Winter, R., S\u0103l\u0103gean, A., Phan, R.C.W.: Comparison of cube attacks over different vector spaces. In: Groth, J. (ed.) 15th IMA International Conference on Cryptography and Coding, IMACC, LNCS 9496, pp 225\u2013238. Springer (2015)","DOI":"10.1007\/978-3-319-27239-9_14"},{"key":"529_CR14","doi-asserted-by":"crossref","unstructured":"Zhang, X.-M., Zheng, Y.: The nonhomomorphicity of Boolean functions. In: Tavares, S., Meijer, H. (eds.) Selected Areas in Cryptography, SAC, pp 280\u2013295. Springer (1999)","DOI":"10.1007\/3-540-48892-8_22"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-021-00529-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12095-021-00529-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-021-00529-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T07:16:40Z","timestamp":1646291800000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12095-021-00529-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,19]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["529"],"URL":"https:\/\/doi.org\/10.1007\/s12095-021-00529-4","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"type":"print","value":"1936-2447"},{"type":"electronic","value":"1936-2455"}],"subject":[],"published":{"date-parts":[[2021,11,19]]},"assertion":[{"value":"16 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}