{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:59:27Z","timestamp":1740142767571,"version":"3.37.3"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62172075"],"award-info":[{"award-number":["62172075"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004607","name":"Natural Science Foundation of Guangxi Province","doi-asserted-by":"publisher","award":["2019GXNSFAA185033"],"award-info":[{"award-number":["2019GXNSFAA185033"]}],"id":[{"id":"10.13039\/501100004607","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,18]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Affine equivalence of Boolean functions has various applications in computer science and modern cryptography, such as circuit design and S-boxes. Existing methods for detecting affine equivalence of Boolean functions work in some cases but not when the truth table of a Boolean function is sparse. To improve previous methods and overcome this limitation, we propose a method by transforming the Boolean function to a function with the property that its function values at the orthonormal basis are all equal to 1 or 0, which narrows down the search space of affine transformations. Our first algorithm has the advantage of getting a smaller search space than previous methods and is especially useful for sparse functions. Specifically, when the Boolean functions are sparse, the search space can be reduced exponentially in average and experiments show the efficiency of our first algorithm. We then present another algorithm to transform one circuit into its equivalent affine circuit by synthesizing a reversible circuit and inserting it in front of the original circuit. To our knowledge, this is the first work to automatically synthesize an affine equivalent circuit for any given circuit and the first to do this by combining reversible circuit and non-reversible circuit.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac072","type":"journal-article","created":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T06:36:21Z","timestamp":1656743781000},"page":"2220-2229","source":"Crossref","is-referenced-by-count":2,"title":["Detecting Affine Equivalence Of Boolean Functions And Circuit Transformation"],"prefix":"10.1093","volume":"66","author":[{"given":"Xiao","family":"Zeng","sequence":"first","affiliation":[{"name":"University of Electronic Science and Technology of China , Chengdu 611731 , China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guowu","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering , Portland State University, Portland, OR 97201 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoyu","family":"Song","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering , Portland State University, Portland, OR 97201 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek A","family":"Perkowski","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering , Portland State University, Portland, OR 97201 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gang","family":"Chen","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics , Jiangjun Rd. Campus: 29 Jiangjun Ave., Nanjing 211100, Nanjing , China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,7,1]]},"reference":[{"key":"2023091720460170700_ref1","doi-asserted-by":"crossref","first-page":"1342","DOI":"10.1109\/31.99163","article-title":"A canonical representation for piecewise-affine maps and its applications to circuit analysis","volume":"38","author":"Guzelis","year":"1991","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"2023091720460170700_ref2","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/ECCTD.2009.5274957","volume-title":"2009 European Conference on Circuit Theory and Design, Antalya, Turkey, 23\u201327 August","author":"Oliveri","year":"2009"},{"key":"2023091720460170700_ref3","article-title":"Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis","volume":"475","author":"Courtois","year":"2011","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"2023091720460170700_ref4","first-page":"403","volume":"57","author":"Maiorana","year":"1991","journal-title":"Mathematics of Computation"},{"key":"2023091720460170700_ref5","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0012-365X(94)90113-9","volume":"128","author":"Hou","year":"1994","journal-title":"Discrete Mathematics"},{"key":"2023091720460170700_ref6","first-page":"324","volume-title":"32nd International Colloquium on Automata, Languages, and Programming, Lisbon, Portugal, 11\u201315 July","author":"Braeken","year":"2005"},{"key":"2023091720460170700_ref7","first-page":"751","article-title":"A new S-box structure named affine-power-affine","volume":"3","author":"Cui","year":"2007","journal-title":"International Journal of Innovative Computing, Information and Control"},{"key":"2023091720460170700_ref8","doi-asserted-by":"crossref","first-page":"3606","DOI":"10.1109\/TC.2016.2557329","article-title":"Computing affine equivalence classes of Boolean functions by group isomorphism","volume":"65","author":"Zhang","year":"2016","journal-title":"IEEE Trans. Comput."},{"volume-title":"Analysis and design of cryptographic hash functions Doctoral dissertation","year":"1993","author":"Preneel","key":"2023091720460170700_ref9"},{"key":"2023091720460170700_ref10","doi-asserted-by":"crossref","first-page":"2178","DOI":"10.1109\/TIT.2004.833361","article-title":"On the degree, nonlinearity, algebraic thickness, and nonnormality of Boolean functions, with developments on symmetric functions","volume":"50","author":"Carlet","year":"2004","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023091720460170700_ref11","doi-asserted-by":"crossref","first-page":"5865","DOI":"10.1109\/TIT.2019.2909910","article-title":"Designing plateaued Boolean functions in spectral domain and their classification","volume":"65","author":"Hod\u017ei\u0107","year":"2019","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023091720460170700_ref12","doi-asserted-by":"crossref","first-page":"2987","DOI":"10.1109\/TIT.2018.2795608","article-title":"Large sets of disjoint spectra plateaued functions inequivalent to partially linear functions","volume":"64","author":"Zhang","year":"2018","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023091720460170700_ref13","doi-asserted-by":"crossref","first-page":"6681","DOI":"10.1109\/TIT.2014.2345772","article-title":"Generalized Maiorana-McFarland construction of resilient Boolean functions with high nonlinearity and good algebraic properties","volume":"60","author":"Zhang","year":"2014","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023091720460170700_ref14","doi-asserted-by":"crossref","first-page":"7970","DOI":"10.1109\/TIT.2014.2360880","article-title":"Highly nonlinear balanced S-boxes with good differential properties","volume":"60","author":"Zhang","year":"2014","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023091720460170700_ref15","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1109\/TIT.1972.1054732","article-title":"Weight distributions of the cosets of the (32,6) Reed-Muller code","volume":"18","author":"Berlekamp","year":"1972","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023091720460170700_ref16","first-page":"74","volume-title":"10th International Workshop on Fast Software Encryption, Lund, Sweden, 24\u201326 February","author":"Fuller","year":"2003"},{"volume-title":"On linear Redundancy in the AES S-Box","year":"2002","author":"Fuller","key":"2023091720460170700_ref17"},{"key":"2023091720460170700_ref18","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1109\/TCAD.2003.811448","article-title":"Synthesis of reversible logic circuits","volume":"22","author":"Shende","year":"2003","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"2023091720460170700_ref19","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1093\/comjnl\/bxm042","article-title":"Bi-directional synthesis of 4-bit reversible circuits","volume":"51","author":"Yang","year":"2008","journal-title":"The Computer Journal"},{"key":"2023091720460170700_ref20","first-page":"282","article-title":"Optimal synthesis of linear reversible circuits","volume":"8","author":"Patel","year":"2008","journal-title":"Quantum Inf. Comput."},{"key":"2023091720460170700_ref21","doi-asserted-by":"crossref","DOI":"10.1016\/B978-0-12-802929-9.00001-7","volume-title":"Programmable logic controllers","author":"Bolton","year":"2015"},{"key":"2023091720460170700_ref22","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/s00145-012-9124-7","article-title":"Logic minimization techniques with applications to cryptology","volume":"26","author":"Boyar","year":"2013","journal-title":"Journal of Cryptology"},{"key":"2023091720460170700_ref23","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1109\/5.231340","article-title":"Architecture of field-programmable gate arrays","volume":"81","author":"Rose","year":"1993","journal-title":"Proc. IEEE"},{"volume-title":"Field-programmable gate array technology","year":"2012","author":"Trimberger","key":"2023091720460170700_ref24"},{"key":"2023091720460170700_ref25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2431211.2431220","article-title":"Synthesis and optimization of reversible circuits-a survey","volume":"45","author":"Saeedi","year":"2013","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"2023091720460170700_ref26","first-page":"85","volume-title":"17th Asia and South Pacific Design Automation Conference, Sydney, Australia, 30 January-02 February","author":"Soeken","year":"2012"},{"year":"2019","author":"Kissinger","article-title":"CNOT circuit extraction for topologically-constrained quantum memories","key":"2023091720460170700_ref27"},{"key":"2023091720460170700_ref28","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-030-52482-1_11","volume-title":"International Conference on Reversible Computation, 09 July","author":"Brugi\u00e9re","year":"2020"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/9\/2220\/51643461\/bxac072.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/9\/2220\/51643461\/bxac072.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T21:08:29Z","timestamp":1694984909000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/9\/2220\/6618067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,1]]},"references-count":28,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2022,7,1]]},"published-print":{"date-parts":[[2023,9,18]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac072","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2023,9]]},"published":{"date-parts":[[2022,7,1]]}}}