{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T20:52:09Z","timestamp":1772052729219,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T00:00:00Z","timestamp":1691798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T00:00:00Z","timestamp":1691798400000},"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":[[2023,11]]},"abstract":"Abstract<\/jats:title>The algebraic degree is an important parameter of Boolean functions used in cryptography. When a function in a large number of variables is not given explicitly in algebraic normal form, it is usually not feasible to compute its degree, so we need to estimate it. We propose a probabilistic test for deciding whether the algebraic degree of a Boolean function f<\/jats:italic> is below a certain value k<\/jats:italic>. If the degree is indeed below k<\/jats:italic>, then f<\/jats:italic> will always pass the test, otherwise f<\/jats:italic> will fail each instance of the test with a probability $$\\textrm{dt}_k(f)$$<\/jats:tex-math>\n \n \n dt<\/mml:mtext>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is closely related to the average number of monomials of degree k<\/jats:italic> of the polynomials which are affine equivalent to f<\/jats:italic>. The test has a good accuracy only if this probability $$\\textrm{dt}_k(f)$$<\/jats:tex-math>\n \n \n dt<\/mml:mtext>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of failing the test is not too small. We initiate the study of $$\\textrm{dt}_k(f)$$<\/jats:tex-math>\n \n \n dt<\/mml:mtext>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> by showing that in the particular case when the degree of f<\/jats:italic> is actually equal to k<\/jats:italic>, the probability will be in the interval (0.288788,\u00a00.5], and therefore a small number of runs of the test will be sufficient to give, with very high probability, the correct answer. Exact values of $$\\textrm{dt}_k(f)$$<\/jats:tex-math>\n \n \n dt<\/mml:mtext>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all the polynomials in 8 variables were computed using the representatives listed by Hou and by Langevin and Leander.<\/jats:p>","DOI":"10.1007\/s12095-023-00660-4","type":"journal-article","created":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T03:18:38Z","timestamp":1691810318000},"page":"1199-1215","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Probabilistic estimation of the algebraic degree of Boolean functions"],"prefix":"10.1007","volume":"15","author":[{"given":"Ana","family":"S\u0103l\u0103gean","sequence":"first","affiliation":[]},{"given":"Percy","family":"Reyes-Paredes","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,12]]},"reference":[{"issue":"6","key":"660_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":"660_CR2","volume-title":"Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, pp 53\u201369","author":"C Carlet","year":"2002","unstructured":"Carlet, C.: On cryptographic complexity of boolean functions. In: Mullen, G.L., Stichtenoth, H., Tapia-Recillas, H. (eds.) Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, pp 53\u201369. Springer, Berlin, Heidelberg (2002)"},{"key":"660_CR3","volume-title":"Advances in Cryptology, EUROCRYPT, vol 5479, pp 278\u2013299","author":"I Dinur","year":"2009","unstructured":"Dinur, I., Shamir, I.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) Advances in Cryptology, EUROCRYPT, vol 5479, pp 278\u2013299. Springer, Berlin, Heidelberg (2009)"},{"key":"660_CR4","doi-asserted-by":"crossref","unstructured":"Duan, M., Lai, X.: Higher order differential cryptanalysis framework and its applications. In International Conference on Information Science and Technology (ICIST), pp 291\u2013297 (2011)","DOI":"10.1109\/ICIST.2011.5765256"},{"key":"660_CR5","doi-asserted-by":"crossref","unstructured":"Filiol, E.: A new statistical testing for symmetric ciphers and hash functions. In Deng, R., Bao, F., Zhou, J., Qing, S. (eds), Information and Communications Security, vol 2513 of LNCS, pp 342\u2013353. Springer, (2002)","DOI":"10.1007\/3-540-36159-6_29"},{"issue":"1","key":"660_CR6","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0012-365X(94)00342-G","volume":"149","author":"X Hou","year":"1996","unstructured":"Hou, X.: $$GL(m, 2)$$ acting on $$R(r, m)\/R(r-1, m)$$. Discrete Mathematics 149(1), 99\u2013122 (1996)","journal-title":"Discrete Mathematics"},{"key":"660_CR7","doi-asserted-by":"crossref","unstructured":"Lai, X.: Higher order derivatives and differential cryptanalysis. In Blahut, R.E., Costello, D.J., Jr., Maurer, U., Mittelholzer, T. (eds), Communications and Cryptography, vol. 276 of The Springer International Series in Engineering and Computer Science, pp 227\u2013233. Springer (1994)","DOI":"10.1007\/978-1-4615-2694-0_23"},{"key":"660_CR8","unstructured":"Langevin, P., Leander, G.: Classification of the quartic forms of eight variables. In Boolean Functions in Cryptology and Information Security, Svenigorod, Russia (2007). https:\/\/langevin.univ-tln.fr\/project\/quartics\/quartics.html"},{"key":"660_CR9","volume-title":"The Theory of Error-correcting Codes","author":"FJ MacWilliams","year":"1977","unstructured":"MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-correcting Codes. North Holland, Amsterdam (1977)"},{"key":"660_CR10","unstructured":"O\u2019Neil, S.: Algebraic structure defectoscopy. Cryptology ePrint Archive, Report 2007\/378, (2007). http:\/\/eprint.iacr.org\/"},{"key":"660_CR11","doi-asserted-by":"crossref","unstructured":"S\u0103l\u0103gean, A., Mandache-S\u0103l\u0103gean, M.: Counting and characterising functions with \u201cfast points\u201d for differential attacks. Cryptography and Communications, pp 217\u2013239, (2017)","DOI":"10.1007\/s12095-015-0166-1"},{"key":"660_CR12","unstructured":"Vielhaber, M.: Breaking ONE.FIVIUM by AIDA an algebraic IV differential attack. Cryptology ePrint Archive, Report 2007\/413, (2007). http:\/\/eprint.iacr.org\/"},{"key":"660_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. (eds), 15th IMA International Conference on Cryptography and Coding, IMACC, vol. 9496 of Lecture Notes in Computer Science, pp 225\u2013238. Springer, (2015)","DOI":"10.1007\/978-3-319-27239-9_14"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-023-00660-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12095-023-00660-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-023-00660-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T16:24:03Z","timestamp":1717431843000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12095-023-00660-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,12]]},"references-count":13,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["660"],"URL":"https:\/\/doi.org\/10.1007\/s12095-023-00660-4","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"value":"1936-2447","type":"print"},{"value":"1936-2455","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,12]]},"assertion":[{"value":"20 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}