{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:41:07Z","timestamp":1586335267293},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"URL":"http:\/\/www.springer.com\/tdm","start":{"date-parts":[[2012,5,3]],"date-time":"2012-05-03T00:00:00Z","timestamp":1336003200000},"delay-in-days":0,"content-version":"tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2013,4]]},"DOI":"10.1007\/s00145-012-9124-7","type":"journal-article","created":{"date-parts":[[2012,5,2]],"date-time":"2012-05-02T06:20:14Z","timestamp":1335939614000},"page":"280-312","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":44,"title":["Logic Minimization Techniques with Applications to Cryptology"],"prefix":"10.1007","volume":"26","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[]},{"given":"Philip","family":"Matthews","sequence":"additional","affiliation":[]},{"given":"Ren\u00e9","family":"Peralta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,5,3]]},"reference":[{"key":"9124_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and the hardness of approximation problems. J. Assoc. Comput. Mach.\n 45, 501\u2013555 (1998)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9124_CR2","author":"P. Austrin","first-page":"74","year":"2009","unstructured":"P. Austrin, S. Khot, M. Safra, Inapproximability of vertex cover and independent set in bounded degree graphs, in IEEE Conference on Computational Complexity (IEEE Computer Society, Los Alamitos, 2009), pp. 74\u201380","volume-title":"IEEE Conference on Computational Complexity"},{"key":"9124_CR3","unstructured":"D.J. Bernstein, Optimizing linear maps modulo\u00a02, in Workshop Record of SPEED-CC: Software Performance Enhancement for Encryption and Decryption and Cryptographic Compilers. \n http:\/\/cr.yp.to\/papers.html#linearmod2"},{"key":"9124_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Am. Math. Soc.\n 21, 1\u201346 (1989)","journal-title":"Bull. Am. Math. Soc."},{"issue":"1\u20133","key":"9124_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.tcs.2008.01.030","volume":"396","author":"J. Boyar","year":"2008","unstructured":"J. Boyar, R. Peralta, Tight bounds for the multiplicative complexity of symmetric functions. Theor. Comput. Sci.\n 396(1\u20133), 223\u2013246 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9124_CR6","unstructured":"J. Boyar, R. Peralta, Patent application number 61089998 filed with the U.S. Patent and Trademark Office. A new technique for combinational circuit optimization and a new circuit for the S-Box for AES, 2009"},{"key":"9124_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1007\/978-3-642-13193-6_16","volume-title":"9th International Symposium on Experimental Algorithms, SEA 2010","author":"J. Boyar","year":"2010","unstructured":"J. Boyar, R. Peralta, A new combinational logic minimization technique with applications to cryptology, in 9th International Symposium on Experimental Algorithms, SEA 2010. Lecture Notes in Computer Science, vol. 6049 (Springer, Berlin, 2010), pp. 178\u2013189"},{"key":"9124_CR8","unstructured":"J. Boyar, R. Peralta, A depth-16 circuit for the AES S-box. Cryptology ePrint archive, report 2011\/332, 2011. \n http:\/\/eprint.iacr.org\/","DOI":"10.1007\/978-3-642-30436-1_24","doi-asserted-by":"crossref"},{"key":"9124_CR9","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0304-3975(99)00182-6","volume":"235","author":"J. Boyar","year":"2000","unstructured":"J. Boyar, R. Peralta, D. Pochuev, On the multiplicative complexity of Boolean functions over the basis (\u2227,\u2295,1). Theor. Comput. Sci.\n 235, 43\u201357 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9124_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-540-85238-4_13","volume-title":"33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008","author":"J. Boyar","year":"2008","unstructured":"J. Boyar, P. Matthews, R. Peralta, On the shortest linear straight-line program for computing linear forms, in 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008. Lecture Notes in Computer Science, vol. 5162 (Springer, Berlin, 2008), pp. 168\u2013179"},{"key":"9124_CR11","author":"P. B\u00fcrgisser","year":"1997","unstructured":"P. B\u00fcrgisser, M. Clausen, M.A. Shokrollahi, Algebraic Complexity Theory (Springer, Berlin, 1997), Chap.\u00a013","volume-title":"Algebraic Complexity Theory","DOI":"10.1007\/978-3-662-03338-8","doi-asserted-by":"publisher"},{"key":"9124_CR12","unstructured":"D. Canright, A very compact Rijndael S-box. Technical report NPS-MA-05-001, Naval Postgraduate School, 2005","DOI":"10.21236\/ADA434781","doi-asserted-by":"crossref"},{"key":"9124_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/11545262_32","volume-title":"7th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2005","author":"D. Canright","year":"2005","unstructured":"D. Canright, A very compact Rijndael S-box, in 7th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2005. Lecture Notes in Computer Science, vol. 3659 (Springer, Berlin, 2005), pp. 441\u2013455"},{"key":"9124_CR14","author":"A.E.F. Clementi","first-page":"333","year":"1996","unstructured":"A.E.F. Clementi, L. Trevisan, Improved non-approximability results for vertex cover with density constraints, in Computing and Combinatorics (1996), pp. 333\u2013342","volume-title":"Computing and Combinatorics","DOI":"10.1007\/3-540-61332-3_167","doi-asserted-by":"publisher"},{"key":"9124_CR15","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"J.W. Cooley","year":"1965","unstructured":"J.W. Cooley, J.W. Tukey, An algorithm for the machine calculation of complex Fourier series. Math. Comput.\n 19, 297\u2013301 (1965)","journal-title":"Math. Comput."},{"key":"9124_CR16","unstructured":"N. Courtois, D. Hulme, T. Mourouzis, Solving circuit optimisation problems in cryptography and cryptanalysis. IACR Cryptology ePrint Archive, 2011:475, 2011"},{"key":"9124_CR17","author":"FIPS","year":"2001","unstructured":"FIPS, Advanced Encryption Standard (AES) (National Institute of Standards and Technology, Gaithersburg, 2001)","volume-title":"Advanced Encryption Standard (AES)"},{"key":"9124_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/978-3-642-14186-7_8","volume-title":"13th International Conference on Theory and Applications of Satisfiability Testing","author":"C. Fuhs","year":"2010","unstructured":"C. Fuhs, P. Schneider-Kamp, Synthesizing shortest linear straight-line programs over GF(2) using SAT, in 13th International Conference on Theory and Applications of Satisfiability Testing. Lecture Notes in Computer Science, vol. 6175 (Springer, Berlin, 2010), pp. 71\u201384"},{"key":"9124_CR19","author":"C. Fuhs","year":"2010","unstructured":"C. Fuhs, P. Schneider-Kamp, Optimizing the AES S-Box using SAT, in Proceedings of the 8th International Workshop on the Implementation of Logics (2010)","volume-title":"Proceedings of the 8th International Workshop on the Implementation of Logics"},{"issue":"4","key":"9124_CR20","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1016\/0196-6774(90)90014-6","volume":"11","author":"J. H\u00e5stad","year":"1990","unstructured":"J. H\u00e5stad, Tensor rank is NP-Complete. J. Algorithms\n 11(4), 644\u2013654 (1990)","journal-title":"J. Algorithms"},{"key":"9124_CR21","author":"Y. Huang","year":"2011","unstructured":"Y. Huang, D. Evans, J. Katz, L. Malka, Faster secure two-party computation using garbled circuits, in Proceedings of the 20th USENIX Security Symposium, San Francisco, CA, August 2011","volume-title":"Proceedings of the 20th USENIX Security Symposium"},{"issue":"3","key":"9124_CR22","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0890-5401(88)90024-7","volume":"78","author":"T. Itoh","year":"1988","unstructured":"T. Itoh, S. Tsujii, A fast algorithm for computing multiplicative inverses in GF(2\n m\n ) using normal bases. Inf. Comput.\n 78(3), 171\u2013177 (1988)","journal-title":"Inf. Comput."},{"key":"9124_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-04138-9_1","volume-title":"11th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2009","author":"E. K\u00e4sper","year":"2009","unstructured":"E. K\u00e4sper, P. Schwabe, Faster and timing-attack resistant AES-GCM, in 11th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2009. Lecture Notes in Computer Science, vol. 5747 (Springer, Berlin, 2009), pp. 1\u201317"},{"key":"9124_CR24","author":"S. Khot","first-page":"767","year":"2002","unstructured":"S. Khot, On the power of unique 2-prover 1-round games, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, STOC \u201902, New York, NY, USA (ACM, New York, 2002), pp.\u00a0767\u2013775","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing, STOC \u201902"},{"key":"9124_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1007\/978-3-540-70583-3_40","volume-title":"Proceedings of Automata, Languages and Programming, 35th International Colloquium, ICALP 2008","author":"V. Kolesnikov","year":"2008","unstructured":"V. Kolesnikov, T. Schneider, Improved garbled circuit: free XOR gates and applications, in Proceedings of Automata, Languages and Programming, 35th International Colloquium, ICALP 2008. Lecture Notes in Computer Science, vol. 5126 (Springer, Berlin, 2008), pp. 486\u2013498"},{"key":"9124_CR26","first-page":"120","volume":"1","author":"O.B. Lupanov","year":"1958","unstructured":"O.B. Lupanov, A method of circuit synthesis. Izv. Vys\u0161. U\u010debn. Zaved., Radiofiz.\n 1, 120\u2013140 (1958)","journal-title":"Izv. Vys\u0161. U\u010debn. Zaved., Radiofiz."},{"key":"9124_CR27","unstructured":"E. Mastrovito, VLSI architectures for computation in Galois fields. Ph.D. thesis, Link\u00f6ping University, Dept. Electr. Eng., Sweden, 1991"},{"key":"9124_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/3-540-36400-5_14","volume-title":"Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2002","author":"S. Morioka","year":"2003","unstructured":"S. Morioka, A. Satoh, An optimized S-Box circuit architecture for low power AES design, in Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2002. Lecture Notes in Computer Science, vol. 2523 (Springer, Berlin, 2003), pp. 172\u2013186"},{"key":"9124_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-642-15031-9_16","volume-title":"12th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2010","author":"Y. Nogami","year":"2010","unstructured":"Y. Nogami, K. Nekado, T. Toyota, N. Hongo, Y. Morikawa, Mixed bases for efficient inversion in f(((22)2)2) and conversion matrices of subbytes of AES, in 12th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2010. Lecture Notes in Computer Science, vol.\u00a06225 (Springer, Berlin, 2010), pp. 234\u2013247"},{"key":"9124_CR30","author":"C. Paar","first-page":"58","year":"1995","unstructured":"C. Paar, Some remarks on efficient inversion in finite fields, in 1995 IEEE International Symposium on Information Theory, Whistler, BC, Canada (1995), p.\u00a058","volume-title":"1995 IEEE International Symposium on Information Theory","DOI":"10.1109\/ISIT.1995.531160","doi-asserted-by":"publisher"},{"key":"9124_CR31","author":"C. Paar","first-page":"250","year":"1997","unstructured":"C. Paar, Optimized arithmetic for Reed-Solomon encoders, in IEEE International Symposium on Information Theory (1997), p. 250","volume-title":"IEEE International Symposium on Information Theory","DOI":"10.1109\/ISIT.1997.613165","doi-asserted-by":"publisher"},{"key":"9124_CR32","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou, M. Yannakakis, Optimization, approximation, and complexity classes. J. Comput. Syst. Sci.\n 43, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9124_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/3-540-45682-1_15","volume-title":"Advances in Cryptology\u2014Proceedings of ASIACRYPT 01","author":"A. Satoh","year":"2001","unstructured":"A. Satoh, S. Morioka, K. Takano, S. Munetoh, A compact Rijndael hardware architecture with S-Box optimization, in Advances in Cryptology\u2014Proceedings of ASIACRYPT 01. Lecture Notes in Computer Science, vol. 2248 (Springer, Berlin, 2001), pp. 239\u2013254"},{"issue":"2","key":"9124_CR34","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1137\/0203011","volume":"3","author":"J.E. Savage","year":"1974","unstructured":"J.E. Savage, An algorithm for the computation of linear forms. SICOMP\n 3(2), 150\u2013158 (1974)","journal-title":"SICOMP"},{"key":"9124_CR35","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"C. Shannon","year":"1949","unstructured":"C. Shannon, The synthesis of two-terminal switching circuits. Bell Syst. Tech. J.\n 28, 59\u201398 (1949)","journal-title":"Bell Syst. Tech. J."},{"key":"9124_CR36","author":"L.G. Valiant","first-page":"249","year":"1979","unstructured":"L.G. Valiant, Completeness classes in algebra, in Proceedings of the 11th Annual ACM Symposium on the Theory of Computing (1979), pp. 249\u2013261","volume-title":"Proceedings of the 11th Annual ACM Symposium on the Theory of Computing"},{"key":"9124_CR37","author":"R. Williams","first-page":"995","year":"2007","unstructured":"R. Williams, Matrix-vector multiplication in sub-quadratic time (some preprocessing required), in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007), pp. 995\u20131001","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"9124_CR38","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/cpa.3160230204","volume":"23","author":"S. Winograd","year":"1970","unstructured":"S. Winograd, On the number of multiplications necessary to compute certain functions. Commun. Pure Appl. Math.\n 23, 165\u2013179 (1970)","journal-title":"Commun. Pure Appl. Math."},{"key":"9124_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-45760-7_6","volume-title":"Topics in Cryptology\u2014CT-RSA 2002","author":"J. Wolkerstorfer","year":"2002","unstructured":"J. Wolkerstorfer, E. Oswald, M. Lamberger, An ASIC implementation of AES SBoxes, in Topics in Cryptology\u2014CT-RSA 2002. Lecture Notes in Computer Science, vol. 2271 (Springer, Berlin, 2002), pp.\u00a067\u201378"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-012-9124-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-012-9124-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-012-9124-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-012-9124-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:08:44Z","timestamp":1586333324000},"score":1.0,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,3]]},"references-count":39,"journal-issue":{"published-print":{"date-parts":[[2013,4]]},"issue":"2"},"alternative-id":["9124"],"URL":"http:\/\/dx.doi.org\/10.1007\/s00145-012-9124-7","relation":{"cites":[]},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":["Software","Applied Mathematics","Computer Science Applications"],"assertion":[{"value":"8 February 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2012","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}