{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T05:17:56Z","timestamp":1741324676117,"version":"3.38.0"},"reference-count":33,"publisher":"Walter de Gruyter GmbH","issue":"4-5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,8,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p xml:lang=\"en\">In the classical CMOS technology, EXOR gates are considered expensive and impractical. Recently, the growing relevance of cryptography-related applications and emerging technologies has revived the interest in EXOR gates. In this contexts, it is therefore important to consider network representations that assume EXOR gates explicitly, since the non-EXOR gates have, in general, a higher cost than EXOR ones. As a result, the widely adopted And-Inverter Graph (AIG) logic networks, have recently evolved into the new XOR-AND Graph (XAG) multi-level logic representation, and the logic synthesis on XAGs mainly aims at reducing the number of AND nodes. In general, we call EXOR-based synthesis the synthesis methods that minimize the non-EXOR gates in a Boolean circuit. Projected Sum Of Product, PSOP, decomposition is an EXOR based technique that can be applied to any Boolean function as a very fast pre-processing step for further minimizing the circuit area in standard logic synthesis. In this paper, we exploit PSOP decomposition in EXOR-based synthesis. The experimental results validate the proposed pre-processing method in EXOR-based synthesis, showing an interesting gain in area, within the same time limit.<\/jats:p>","DOI":"10.1515\/itit-2024-0073","type":"journal-article","created":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T12:34:46Z","timestamp":1737635686000},"page":"92-102","source":"Crossref","is-referenced-by-count":0,"title":["PSOP decomposition for EXOR-based synthesis"],"prefix":"10.1515","volume":"66","author":[{"given":"Anna","family":"Bernasconi","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica , Universit\u00e0 di Pisa , Pisa , Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentina","family":"Ciriani","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica , Universit\u00e0 degli Studi di Milano , Milan , Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianmarco","family":"Cuciniello","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica , Universit\u00e0 degli Studi di Milano , Milan , Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Asma","family":"Taheri Monfared","sequence":"additional","affiliation":[{"name":"University of Bergamo , Bergamo , Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2025,1,24]]},"reference":[{"key":"2025030616183067803_j_itit-2024-0073_ref_001","unstructured":"N. Weste and K. Eshraghian, Principles of CMOS VLSI Design, New York, NY, USA, IEEE, 1993."},{"key":"2025030616183067803_j_itit-2024-0073_ref_002","doi-asserted-by":"crossref","unstructured":"A. Bernasconi, V. Ciriani, R. Drechsler, and T. Villa, \u201cLogic minimization and testability of 2-SPP networks,\u201d IEEE Trans. Comput. Aided Des. Integrated Circ. Syst., vol.\u00a027, no.\u00a07, pp.\u00a01190\u20131202, 2008. https:\/\/doi.org\/10.1109\/tcad.2008.923072.","DOI":"10.1109\/TCAD.2008.923072"},{"key":"2025030616183067803_j_itit-2024-0073_ref_003","doi-asserted-by":"crossref","unstructured":"V. Ciriani, \u201cSynthesis of SPP three-level logic networks using affine spaces,\u201d IEEE Trans. Comput. Aided Des. Integrated Circ. Syst., vol.\u00a022, no.\u00a010, pp.\u00a01310\u20131323, 2003. https:\/\/doi.org\/10.1109\/tcad.2003.818121.","DOI":"10.1109\/TCAD.2003.818121"},{"key":"2025030616183067803_j_itit-2024-0073_ref_004","doi-asserted-by":"crossref","unstructured":"D. Debnath and T. Sasao, \u201cA heuristic algorithm to design AND-OR-EXOR three-level networks,\u201d in Asia and South Pacific Design Automation Conference, 1998, pp.\u00a069\u201374.","DOI":"10.1109\/ASPDAC.1998.669404"},{"key":"2025030616183067803_j_itit-2024-0073_ref_005","unstructured":"E. Dubrova, D. Miller, and J. Muzio, \u201cAOXMIN-MV: a heuristic algorithm for AND-OR-XOR minimization,\u201d in Int. Workshop on the Applications of the Reed Muller Expansion in circuit Design, 1999, pp.\u00a037\u201354."},{"key":"2025030616183067803_j_itit-2024-0073_ref_006","doi-asserted-by":"crossref","unstructured":"F. Luccio and L. Pagli, \u201cOn a new boolean function with applications,\u201d IEEE Trans. Comput., vol.\u00a048, no.\u00a03, pp.\u00a0296\u2013310, 1999. https:\/\/doi.org\/10.1109\/12.754996.","DOI":"10.1109\/12.754996"},{"key":"2025030616183067803_j_itit-2024-0073_ref_007","doi-asserted-by":"crossref","unstructured":"S. Cimato, V. Ciriani, E. Damiani, and M. Ehsanpour, \u201cAn obdd-based technique for the efficient synthesis of garbled circuits,\u201d in Security and Trust Management \u2013 STM, New York, NY, USA, Association for Computing Machinery (ACM), 2019, pp. 158\u2013167.","DOI":"10.1007\/978-3-030-31511-5_10"},{"key":"2025030616183067803_j_itit-2024-0073_ref_008","doi-asserted-by":"crossref","unstructured":"I. Halecek, P. Fiser, and J. Schmidt, \u201cAre xors in logic synthesis really necessary?\u201d in 20th IEEE International Symposium on Design and Diagnostics of Electronic Circuits & Systems, DDECS 2017, Dresden, Germany, April 19\u201321, 2017, 2017, pp.\u00a0134\u2013139.","DOI":"10.1109\/DDECS.2017.7934583"},{"key":"2025030616183067803_j_itit-2024-0073_ref_009","doi-asserted-by":"crossref","unstructured":"I. H\u00e1lecek, P. Fiser, and J. Schmidt, \u201cTowards AND\/XOR balanced synthesis: logic circuits rewriting with XOR,\u201d Microelectron. Reliab., vol. 81, nos. 1\u20133, pp. 274\u2013286, 2018. https:\/\/doi.org\/10.1016\/j.microrel.2017.12.031.","DOI":"10.1016\/j.microrel.2017.12.031"},{"key":"2025030616183067803_j_itit-2024-0073_ref_010","doi-asserted-by":"crossref","unstructured":"E. Testa, M. Soeken, L. G. Amar\u00f9, and G. D. Micheli, \u201cReducing the multiplicative complexity in logic networks for cryptography and security applications,\u201d in Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019, Las Vegas, NV, USA, 2019, p.\u00a074.","DOI":"10.1145\/3316781.3317893"},{"key":"2025030616183067803_j_itit-2024-0073_ref_011","doi-asserted-by":"crossref","unstructured":"E. Testa, M. Soeken, L. G. Amar\u00f9, and G. D. Micheli, \u201cLogic synthesis for established and emerging computing,\u201d Proc. IEEE, vol.\u00a0107, no.\u00a01, pp.\u00a0165\u2013184, 2019. https:\/\/doi.org\/10.1109\/jproc.2018.2869760.","DOI":"10.1109\/JPROC.2018.2869760"},{"key":"2025030616183067803_j_itit-2024-0073_ref_012","doi-asserted-by":"crossref","unstructured":"V. Kolesnikov and T. Schneider, \u201cImproved garbled circuit: free xor gates and applications,\u201d in International Colloquium on Automata, Languages, and Programming, Springer, 2008, pp.\u00a0486\u2013498.","DOI":"10.1007\/978-3-540-70583-3_40"},{"key":"2025030616183067803_j_itit-2024-0073_ref_013","doi-asserted-by":"crossref","unstructured":"R. K. Brayton and A. Mishchenko, \u201cABC: an academic industrial-strength verification tool,\u201d in Computer Aided Verification, 22nd International Conference, CAV 2010, Edinburgh, UK, July 15\u201319, 2010. Proceedings, 2010, pp.\u00a024\u201340.","DOI":"10.1007\/978-3-642-14295-6_5"},{"key":"2025030616183067803_j_itit-2024-0073_ref_014","doi-asserted-by":"crossref","unstructured":"A. Bernasconi, S. Cimato, V. Ciriani, and M. C. Molteni, \u201cMultiplicative complexity of autosymmetric functions: theory and applications to security,\u201d in 57th ACM\/IEEE Design Automation Conference, DAC 2020, San Francisco, CA, USA, July 20\u201324, 2020, IEEE, 2020, pp.\u00a01\u20136.","DOI":"10.1109\/DAC18072.2020.9218492"},{"key":"2025030616183067803_j_itit-2024-0073_ref_015","doi-asserted-by":"crossref","unstructured":"A. Bernasconi, S. Cimato, V. Ciriani, and M. C. Molteni, \u201cMultiplicative complexity of XOR based regular functions,\u201d IEEE Trans. Comput., vol.\u00a071, no.\u00a011, pp.\u00a02927\u20132939, 2022. https:\/\/doi.org\/10.1109\/tc.2022.3141249.","DOI":"10.1109\/TC.2022.3141249"},{"key":"2025030616183067803_j_itit-2024-0073_ref_016","doi-asserted-by":"crossref","unstructured":"A. Bernasconi, V. Ciriani, and R. Cordone, \u201cThe optimization of kEP-SOPs: computational complexity, approximability and experiments,\u201d ACM Trans. Des. Autom. Electron. Syst., vol.\u00a013, no.\u00a02, pp.\u00a01\u201331, 2008. https:\/\/doi.org\/10.1145\/1344418.1344431.","DOI":"10.1145\/1344418.1344431"},{"key":"2025030616183067803_j_itit-2024-0073_ref_017","doi-asserted-by":"crossref","unstructured":"J. C. Bioch, \u201cThe complexity of modular decomposition of boolean functions,\u201d Discret. Appl. Math., vol.\u00a0149, nos. 1\u20133, pp.\u00a01\u201313, 2005. https:\/\/doi.org\/10.1016\/j.dam.2003.12.010.","DOI":"10.1016\/j.dam.2003.12.010"},{"key":"2025030616183067803_j_itit-2024-0073_ref_018","unstructured":"P. Kerntopf, \u201cNew generalizations of shannon decomposition,\u201d in Int. Workshop on Applications of Reed-Muller Expansion in Circuit Design, 2001, pp.\u00a0109\u2013118."},{"key":"2025030616183067803_j_itit-2024-0073_ref_019","doi-asserted-by":"crossref","unstructured":"A. Bernasconi, V. Ciriani, G. Trucco, and T. Villa, \u201cOn decomposing boolean functions via extended cofactoring,\u201d in 2009 Design, Automation & Test in Europe Conference & Exhibition, IEEE, 2009, pp.\u00a01464\u20131469.","DOI":"10.1109\/DATE.2009.5090894"},{"key":"2025030616183067803_j_itit-2024-0073_ref_020","doi-asserted-by":"crossref","unstructured":"G. Meuli, M. Soeken, E. Campbell, M. Roetteler, and G. De Micheli, \u201cThe role of multiplicative complexity in compiling low t-count oracle circuits,\u201d in 2019 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD), IEEE, 2019, pp.\u00a01\u20138.","DOI":"10.1109\/ICCAD45719.2019.8942093"},{"key":"2025030616183067803_j_itit-2024-0073_ref_021","unstructured":"M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Berlin, Germany, Springer, 2010."},{"key":"2025030616183067803_j_itit-2024-0073_ref_022","doi-asserted-by":"crossref","unstructured":"Y. Lindell and B. Pinkas, \u201cSecure multiparty computation for privacy-preserving data mining,\u201d J. Priv. Confid., vol.\u00a01, no.\u00a01, p.\u00a05, 2009. https:\/\/doi.org\/10.29012\/jpc.v1i1.566.","DOI":"10.29012\/jpc.v1i1.566"},{"key":"2025030616183067803_j_itit-2024-0073_ref_023","doi-asserted-by":"crossref","unstructured":"M. Barni, P. Failla, V. Kolesnikov, R. Lazzeretti, A.-R. Sadeghi, and T. Schneider, \u201cSecure evaluation of private linear branching programs with medical applications,\u201d in ESORICS, vol.\u00a05789, Springer, 2009, pp.\u00a0424\u2013439.","DOI":"10.1007\/978-3-642-04444-1_26"},{"key":"2025030616183067803_j_itit-2024-0073_ref_024","doi-asserted-by":"crossref","unstructured":"J. Brickell, D. E. Porter, V. Shmatikov, and E. Witchel, \u201cPrivacy-preserving remote diagnostics,\u201d in Proceedings of the 14th ACM Conference on Computer and Communications Security, ACM, 2007, pp.\u00a0498\u2013507.","DOI":"10.1145\/1315245.1315307"},{"key":"2025030616183067803_j_itit-2024-0073_ref_025","doi-asserted-by":"crossref","unstructured":"M. Barni, G. Droandi, and R. Lazzeretti, \u201cPrivacy protection in biometric-based recognition systems: a marriage between cryptography and signal processing,\u201d IEEE Signal Process. Mag., vol.\u00a032, no.\u00a05, pp.\u00a066\u201376, 2015. https:\/\/doi.org\/10.1109\/MSP.2015.2438131.","DOI":"10.1109\/MSP.2015.2438131"},{"key":"2025030616183067803_j_itit-2024-0073_ref_026","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao, \u201cHow to generate and exchange secrets,\u201d in Foundations of Computer Science, 1986, 27th Annual Symposium on, IEEE, 1986, pp.\u00a0162\u2013167.","DOI":"10.1109\/SFCS.1986.25"},{"key":"2025030616183067803_j_itit-2024-0073_ref_027","doi-asserted-by":"crossref","unstructured":"V. Kolesnikov and T. Schneider, \u201cImproved garbled circuit: free xor gates and applications,\u201d Automata, Lang. Program., pp.\u00a0486\u2013498, 2008, https:\/\/doi.org\/10.1007\/978-3-540-70583-3_40.","DOI":"10.1007\/978-3-540-70583-3_40"},{"key":"2025030616183067803_j_itit-2024-0073_ref_028","doi-asserted-by":"crossref","unstructured":"E. Testa, M. Soeken, H. Riener, L. Amaru, and G. D. Micheli, \u201cA logic synthesis toolbox for reducing the multiplicative complexity in logic networks,\u201d in 2020 Design, Automation Test in Europe Conference Exhibition (DATE), 2020, pp.\u00a0568\u2013573.","DOI":"10.23919\/DATE48585.2020.9116467"},{"key":"2025030616183067803_j_itit-2024-0073_ref_029","unstructured":"S. Yang, \u201cLogic synthesis and optimization benchmarks user guide version 3.0,\u201d Microelectronic Center, User Guide, 1991."},{"key":"2025030616183067803_j_itit-2024-0073_ref_030","doi-asserted-by":"crossref","unstructured":"A. Bernasconi, V. Ciriani, and R. Cordone, \u201cOn projecting sums of products,\u201d in 11th Euromicro Conference on Digital Systems Design: Architectures, Methods and Tools, 2008.","DOI":"10.1109\/DSD.2008.105"},{"key":"2025030616183067803_j_itit-2024-0073_ref_031","doi-asserted-by":"crossref","unstructured":"A. Mishchenko, S. Chatterjee, and R. K. Brayton, \u201cDag-aware AIG rewriting a fresh look at combinational logic synthesis,\u201d in Proceedings of the 43rd Design Automation Conference, DAC 2006, San Francisco, CA, USA, July 24\u201328, 2006, E. Sentovich, Ed., ACM, 2006, pp.\u00a0532\u2013535.","DOI":"10.1109\/DAC.2006.229287"},{"key":"2025030616183067803_j_itit-2024-0073_ref_032","doi-asserted-by":"crossref","unstructured":"R. Bryant, \u201cSymbolic boolean manipulation with ordered binary-decision diagrams,\u201d ACM Comput. Surv., vol.\u00a024, no.\u00a03, pp.\u00a0293\u2013318, 1992. https:\/\/doi.org\/10.1145\/136035.136043.","DOI":"10.1145\/136035.136043"},{"key":"2025030616183067803_j_itit-2024-0073_ref_033","doi-asserted-by":"crossref","unstructured":"B. Schmitt, M. Soeken, G. D. Micheli, and A. Mishchenko, \u201cScaling-up ESOP synthesis for quantum compilation,\u201d in 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL), Fredericton, NB, Canada, May 21\u201323, 2019, IEEE, 2019, pp.\u00a013\u201318.","DOI":"10.1109\/ISMVL.2019.00011"}],"container-title":["it - Information Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2024-0073\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2024-0073\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T16:19:14Z","timestamp":1741277954000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2024-0073\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,1]]},"references-count":33,"journal-issue":{"issue":"4-5","published-online":{"date-parts":[[2025,3,3]]},"published-print":{"date-parts":[[2024,8,26]]}},"alternative-id":["10.1515\/itit-2024-0073"],"URL":"https:\/\/doi.org\/10.1515\/itit-2024-0073","relation":{},"ISSN":["1611-2776","2196-7032"],"issn-type":[{"type":"print","value":"1611-2776"},{"type":"electronic","value":"2196-7032"}],"subject":[],"published":{"date-parts":[[2024,8,1]]}}}