{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:40:06Z","timestamp":1751924406496,"version":"3.41.2"},"reference-count":20,"publisher":"International Association for Cryptologic Research","issue":"2","license":[{"start":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T00:00:00Z","timestamp":1743897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,6,2]]},"abstract":"<jats:p>We present a new construction of cryptographically significant Boolean functions defined over a large number of variables, with an emphasis on efficient circuit realizability. Our method is based on a variant of the well-known Maiorana-McFarland (MM) construction, adapted to enable circuit structures with less than <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mn>6<\/mml:mn>\n                <mml:mi>n<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math> gates on the number of input bits <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>n<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math>. We evaluate the circuit efficiency in terms of the total number of logic gates (for example AND, OR, NOT, and XOR \u2013 each with a maximum fan-in of two) required to implement a given function. While prior studies have explored cryptographic parameters of such functions in theory, they often overlooked circuit-level efficiency, especially in high-dimensional settings. In this work, we construct a class of balanced functions with high nonlinearity, low absolute autocorrelation and high algebraic degree, yet realizable using a small number of logic gates. Towards application, this work provides additional design directions for cryptographic primitives in domains such as fault-resistant cryptography and homomorphic encryption, where both security and circuit efficiency at scale are critical. Further investigations are required towards actual hardware implementation of our proposed functions as well as to exploit them in concrete cipher designs. <\/jats:p>","DOI":"10.62056\/akmpgyl7s","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:09Z","timestamp":1751922549000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Construction of Maiorana-McFarland type cryptographically significant Boolean functions with good implementation properties"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8373-9200","authenticated-orcid":false,"given":"Deng","family":"Tang","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/0220qvk04","id-type":"ROR","asserted-by":"publisher"}],"name":"Shanghai Jiao Tong University, Shanghai 200240","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8818-6983","authenticated-orcid":false,"given":"Anupam","family":"Chattopadhyay","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02e7b5302","id-type":"ROR","asserted-by":"publisher"}],"name":"Nanyang Technological University, 50 Nanyang Avenue, 639798","place":["Singapore"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1364-2814","authenticated-orcid":false,"given":"Manmatha","family":"Roy","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00q2w1j53","id-type":"ROR","asserted-by":"publisher"}],"name":"Indian Statistical Institute, Kolkata 700108","place":["India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9874-0087","authenticated-orcid":false,"given":"Bimal","family":"Mandal","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03yacj906","id-type":"ROR","asserted-by":"publisher"}],"name":"Indian Institute of Technology, Jodhpur 342030","place":["India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8348-7971","authenticated-orcid":false,"given":"Subhamoy","family":"Maitra","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00q2w1j53","id-type":"ROR","asserted-by":"publisher"}],"name":"Indian Statistical Institute, Kolkata 700108","place":["India"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"ref1:CH10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1017\/9781108606806.006","article-title":"Boolean functions for cryptography and error correcting\n  codes","author":"C. Carlet","year":"2010"},{"key":"ref2:PS09","doi-asserted-by":"publisher","DOI":"10.1016\/C2016-0-00852-5","volume-title":"Cryptographic Boolean Functions and Applications","author":"T. W. Cusick","year":"2009"},{"key":"ref3:DL74","doi-asserted-by":"publisher","DOI":"10.13016\/M2MS3K194","volume-title":"Elementary Hadamard Difference Sets","author":"J. F. Dillon","year":"1974"},{"key":"ref4:SM16","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32595-8","volume-title":"Bent Functions \u2013 Fundamentals and Results","author":"S. Mesnager","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319325934"},{"key":"ref5:RO76","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0097-3165(76)90024-8","article-title":"On bent functions","volume":"20","author":"O. S. Rothaus","year":"1976","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"ref6:HD95","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/3-540-60590-8_5","article-title":"Construction of bent functions and balanced Boolean\n  functions with high nonlinearity","volume":"1008","author":"H. Dobbertin","year":"1994"},{"key":"ref7:SMD19","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10623-018-0522-1","article-title":"Construction and search of balanced Boolean functions on\n  even number of variables towards excellent autocorrelation profile","volume":"87","author":"S. Kavut","year":"2019","journal-title":"Designs, Codes and Cryptography"},{"key":"ref8:TM18","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1109\/tit.2017.2769092","article-title":"Constructions of $n$-variable ($n \\equiv 2 \\bmod 4$)\n  balanced Boolean functions with maximum absolute value in autocorrelation\n  spectra $< 2^{n\/2}$","volume":"64","author":"D. Tang","year":"2018","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref9:TMM19","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1137\/18m1202864","article-title":"Modifying Maiorana\u2013McFarland type bent functions for good\n  cryptographic properties and efficient implementation","volume":"33","author":"D. Tang","year":"2019","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"ref10:TMM21","doi-asserted-by":"publisher","first-page":"101903","DOI":"10.1016\/j.ffa.2021.101903","article-title":"Construction of balanced vectorial Boolean functions with\n  almost optimal nonlinearity and very low differential-linear uniformity","volume":"76","author":"D. Tang","year":"2021","journal-title":"Finite Fields and Their Applications"},{"key":"ref11:PS01","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/3-540-44709-1_27","article-title":"Efficient implementation of \"large\" stream cipher systems","volume":"2162","author":"P. Sarkar","year":"2001"},{"key":"ref12:PS03","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1109\/TC.2003.1190582","article-title":"Efficient implementation of cryptographically useful `large'\n  Boolean functions","volume":"52","author":"P. Sarkar","year":"2003","journal-title":"IEEE Transactions on Computers"},{"key":"ref13:KG04","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-540-31815-6_26","article-title":"Efficient representation and software implementation of\n  resilient Maiorana\u2013McFarland S-boxes","volume":"3325","author":"K. C. Gupta","year":"2004"},{"key":"ref14:EO23","doi-asserted-by":"publisher","first-page":"159","DOI":"10.3390\/computers12080159","article-title":"Genetic approach to improve cryptographic properties of\n  balanced Boolean functions using bent functions","volume":"12","author":"E. Ozcekic","year":"2023","journal-title":"Computers"},{"key":"ref15:ASK18","volume-title":"Design of filtering functions for lightweight stream\n  ciphers","author":"A. Canteaut","year":"2018"},{"key":"ref16:KH18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-030-05153-2_6","article-title":"On hardware implementation of Tang\u2013Maitra Boolean\n  functions","volume":"11321","author":"M. Khairallah","year":"2018"},{"key":"ref17:Gentry2009FHE","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1145\/1536414.1536440","article-title":"Fully Homomorphic Encryption Using Ideal Lattices","author":"Craig Gentry","year":"2009"},{"key":"ref18:Rivest1978HE","first-page":"169","article-title":"On data banks and privacy homomorphisms","volume":"4","author":"R. L. Rivest","year":"1978","journal-title":"Foundations of Secure Computation"},{"key":"ref19:DFA21","doi-asserted-by":"publisher","first-page":"2161","DOI":"10.1109\/tc.2020.3038236","article-title":"Differential fault attack on Kreyvium & FLIP","volume":"70","author":"D. Roy","year":"2021","journal-title":"IEEE Transactions on Computers"},{"key":"ref20:grfault","doi-asserted-by":"publisher","first-page":"1647","DOI":"10.1109\/tc.2014.2339854","article-title":"Differential fault attack against Grain family with very few\n  faults and minimal assumptions","volume":"64","author":"S. Sarkar","year":"2015","journal-title":"IEEE Transactions on Computers"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:44Z","timestamp":1751922584000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/2\/15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":20,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,7,7]]}},"URL":"https:\/\/doi.org\/10.62056\/akmpgyl7s","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,7]]},"assertion":[{"value":"2025-04-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-2-33"}}