{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T14:31:19Z","timestamp":1723473079058},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2012,2]]},"abstract":"Finite fields are widely used in constructing error-correcting codes and cryptographic algorithms. In practice, error-correcting codes use small finite fields to achieve high-throughput encoding and decoding. Conversely, cryptographic systems employ considerably larger finite fields to achieve high levels of security. We focus on developing efficient software implementations of arithmetic operations in reasonably large finite fields as needed by secure storage applications.<\/jats:p>\n \n In this article, we study several arithmetic operation implementations for finite fields ranging from\n GF<\/jats:italic>\n (2\n 32<\/jats:sup>\n ) to\n GF<\/jats:italic>\n (2\n 128<\/jats:sup>\n ). We implement multiplication and division in these finite fields by making use of precomputed tables in smaller fields, and several techniques of extending smaller field arithmetic into larger field operations. We show that by exploiting known techniques, as well as new optimizations, we are able to efficiently support operations over finite fields of interest. We perform a detailed evaluation of several techniques, and show that we achieve very practical performance for both multiplication and division.\n <\/jats:p>\n \n Finally, we show how these techniques find applications in the implementation of HAIL, a highly available distributed cloud storage layer. Using the newly implemented arithmetic operations in\n GF<\/jats:italic>\n (2\n 64<\/jats:sup>\n ), HAIL improves its performance by a factor of two, while simultaneously providing a higher level of security.\n <\/jats:p>","DOI":"10.1145\/2093139.2093141","type":"journal-article","created":{"date-parts":[[2012,2,22]],"date-time":"2012-02-22T18:42:36Z","timestamp":1329936156000},"page":"1-27","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Efficient software implementations of large finite fields\n *GF<\/i>\n (2\n *^{\n n<\/i>\n <\/sup>\n ) for secure storage applications"],"prefix":"10.1145","volume":"8","author":[{"given":"Jianqiang","family":"Luo","sequence":"first","affiliation":[{"name":"Wayne State University, Detroit, MI"}]},{"given":"Kevin D.","family":"Bowers","sequence":"additional","affiliation":[{"name":"RSA Laboratories, Cambridge, MA"}]},{"given":"Alina","family":"Oprea","sequence":"additional","affiliation":[{"name":"RSA Laboratories, Cambridge, MA"}]},{"given":"Lihao","family":"Xu","sequence":"additional","affiliation":[{"name":"Wayne State University, Detroit, MI"}]}],"member":"320","published-online":{"date-parts":[[2012,2,24]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aranha D. F. 2010. RELIC is an Efficient Library for Cryptography version 0.2.3. http:\/\/code.google.com\/p\/relic-toolkit\/. Aranha D. F. 2010. RELIC is an Efficient Library for Cryptography version 0.2.3. http:\/\/code.google.com\/p\/relic-toolkit\/."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 1st International Conference on Cryptology and Information Security in Latin America (LATINCRYPT'10)","author":"Aranha D. F.","unstructured":"Aranha , D. F. , L\u00f3pez , J. , and Hankerson , D . 2010. Efficient software implementation of binary field arithmetic using vector instruction sets . In Proceedings of the 1st International Conference on Cryptology and Information Security in Latin America (LATINCRYPT'10) . Aranha, D. F., L\u00f3pez, J., and Hankerson, D. 2010. Efficient software implementation of binary field arithmetic using vector instruction sets. In Proceedings of the 1st International Conference on Cryptology and Information Security in Latin America (LATINCRYPT'10)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73074-3_7"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Annual International Cryptology Conference (CRYPTO'98)","author":"Bailey D. V.","unstructured":"Bailey , D. V. and Paar , C . 1998. Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms . In Proceedings of the Annual International Cryptology Conference (CRYPTO'98) . Bailey, D. V. and Paar, C. 1998. Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms. In Proceedings of the Annual International Cryptology Conference (CRYPTO'98)."},{"key":"e_1_2_1_5_1","unstructured":"Beachy J. A. and Blair W. D. 2006. Abstract Algebra. Waveland Press Inc. Beachy J. A. and Blair W. D. 2006. Abstract Algebra. Waveland Press Inc."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1981.37"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653662.1653686"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Annual International Conference on the Theory and Application of Cryptology Information Security (ASIACRYPT'96)","author":"DeWin E.","unstructured":"DeWin , E. , Bosselaers , A. , Vanderberghe , S. , Gersem , P. D. , and Vandewalle , J . 1996. A fast software implementation for arthmetic operation in GF(2n) . In Proceedings of the Annual International Conference on the Theory and Application of Cryptology Information Security (ASIACRYPT'96) . DeWin, E., Bosselaers, A., Vanderberghe, S., Gersem, P. D., and Vandewalle, J. 1996. A fast software implementation for arthmetic operation in GF(2n). In Proceedings of the Annual International Conference on the Theory and Application of Cryptology Information Security (ASIACRYPT'96)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057074"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Symposium on Foundations of Computational Mathematics (FoCM'97)","author":"Gao S.","unstructured":"Gao , S. and Panario , D . 1997. Tests and constructions of irreducible polynomials over finite fields . In Proceedings of the Symposium on Foundations of Computational Mathematics (FoCM'97) . Gao, S. and Panario, D. 1997. Tests and constructions of irreducible polynomials over finite fields. In Proceedings of the Symposium on Foundations of Computational Mathematics (FoCM'97)."},{"key":"e_1_2_1_12_1","unstructured":"gentoo wiki. 2010. http:\/\/en.gentoo-wiki.com\/wiki\/CFLAGS. gentoo wiki. 2010. http:\/\/en.gentoo-wiki.com\/wiki\/CFLAGS."},{"key":"e_1_2_1_13_1","unstructured":"Greenan K. M. Miller E. L. and Schwarz T. J. E. 2007. Analysis and construction of galois fields for efficient storage reliability. Tech. rep. UCSC-SSRC-07-09. Greenan K. M. Miller E. L. and Schwarz T. J. E. 2007. Analysis and construction of galois fields for efficient storage reliability. Tech. rep. UCSC-SSRC-07-09."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS'08)","author":"Greenan K. M.","unstructured":"Greenan , K. M. , Miller , E. L. , and Schwarz , T. J. E. 2008. Optimizing galois field arithmetic for diverse processor architectures and applications . In Proceedings of the International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS'08) . Greenan, K. M., Miller, E. L., and Schwarz, T. J. E. 2008. Optimizing galois field arithmetic for diverse processor architectures and applications. In Proceedings of the International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS'08)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10440-006-9046-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/648253.752410"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt'92)","author":"Harper G.","unstructured":"Harper , G. , Menezes , A. , and Vanstone , S . 1992. Public-key cryptosystems with very small key lengths . In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt'92) . Harper, G., Menezes, A., and Vanstone, S. 1992. Public-key cryptosystems with very small key lengths. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt'92)."},{"key":"e_1_2_1_18_1","unstructured":"Huang C. and Xu L. 2003. Fast software implementation of finite field operations. Tech. rep. Washington University. Huang C. and Xu L. 2003. Fast software implementation of finite field operations. Tech. rep. Washington University."},{"key":"e_1_2_1_19_1","unstructured":"Intel. 2007. Intel SSE4 Programming Reference. http:\/\/software.intel.com\/file\/18187\/. Intel. 2007. Intel SSE4 Programming Reference. http:\/\/software.intel.com\/file\/18187\/."},{"key":"e_1_2_1_20_1","unstructured":"Intel. 2011. Intel advanced encryption standard (AES) instructions set. http:\/\/software.intel.com\/file\/24917. Intel. 2011. Intel advanced encryption standard (AES) instructions set. http:\/\/software.intel.com\/file\/24917."},{"key":"e_1_2_1_21_1","first-page":"231","article-title":"Digital signature algorithm","volume":"5","author":"Kravitz D. W.","year":"1993","unstructured":"Kravitz , D. W. 1993 . Digital signature algorithm . U.S. Patent 5 , 231 ,668. Kravitz, D. W. 1993. Digital signature algorithm. U.S. Patent 5,231,668.","journal-title":"U.S. Patent"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Lidl R. and Niederreiter H. 1997. Finite Fields. Cambridge University Press. Lidl R. and Niederreiter H. 1997. Finite Fields. Cambridge University Press.","DOI":"10.1017\/CBO9780511525926"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Annual International Conference on Cryptology in India (INDOCRYPT'00)","author":"L\u00f3pez J.","unstructured":"L\u00f3pez , J. and Dahab , R . 2000. High-speed software multiplication in 𝔽2m . In Proceedings of the Annual International Conference on Cryptology in India (INDOCRYPT'00) . L\u00f3pez, J. and Dahab, R. 2000. High-speed software multiplication in 𝔽2m. In Proceedings of the Annual International Conference on Cryptology in India (INDOCRYPT'00)."},{"key":"e_1_2_1_24_1","unstructured":"MacWilliams F. J. and Sloane N. J. A. 1977. The Theory of Error Correcting Codes. North-Holland Amsterdam. MacWilliams F. J. and Sloane N. J. A. 1977. The Theory of Error Correcting Codes. North-Holland Amsterdam."},{"key":"e_1_2_1_25_1","unstructured":"Menezes A. van Oorschot P. and Vanstone S. 1997. Handbook of Applied Cryptography. CRC Press. Menezes A. van Oorschot P. and Vanstone S. 1997. Handbook of Applied Cryptography. CRC Press."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/646751.704566"},{"key":"e_1_2_1_27_1","unstructured":"National Institute for Standards and Technology (NIST). 2009. FIPS 186-3: Digital Signature Standard (DSS). http:\/\/www.itl.nist.gov\/fipspubs\/by-num.htm. National Institute for Standards and Technology (NIST). 2009. FIPS 186-3: Digital Signature Standard (DSS). http:\/\/www.itl.nist.gov\/fipspubs\/by-num.htm."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50214"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199709)27:9%3C995::AID-SPE111%3E3.3.CO;2-Y"},{"key":"e_1_2_1_30_1","unstructured":"Plank J. S. 2007. Fast galois field arithmetic library in C\/C++. http:\/\/www.cs.utk.edu\/~plank\/plank\/papers\/CS-07-593\/. Plank J. S. 2007. Fast galois field arithmetic library in C\/C++. http:\/\/www.cs.utk.edu\/~plank\/plank\/papers\/CS-07-593\/."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 7th Usenix Conference on File and Storage Technologies (FAST'09)","author":"Plank J. S.","year":"2009","unstructured":"Plank , J. S. , Luo , J. , Schuman , C. D. , Xu , L. , and Wilcox-O'Hearn , Z. 2009 . A performance evaluation and examination of open-source erasure coding libraries for storage . In Proceedings of the 7th Usenix Conference on File and Storage Technologies (FAST'09) . Plank, J. S., Luo, J., Schuman, C. D., Xu, L., and Wilcox-O'Hearn, Z. 2009. A performance evaluation and examination of open-source erasure coding libraries for storage. In Proceedings of the 7th Usenix Conference on File and Storage Technologies (FAST'09)."},{"key":"e_1_2_1_32_1","volume-title":"Jerasure: A library in C\/C++ facilitating erasure coding for storage applications. Tech. rep. CS-08-627","author":"Plank J. S.","year":"2008","unstructured":"Plank , J. S. , Simmerman , S. , and Schuman , C. D . 2008 . Jerasure: A library in C\/C++ facilitating erasure coding for storage applications. Tech. rep. CS-08-627 , University of Tennessee . Plank, J. S., Simmerman, S., and Schuman, C. D. 2008. Jerasure: A library in C\/C++ facilitating erasure coding for storage applications. Tech. rep. CS-08-627, University of Tennessee."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0108018"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the Annual International Cryptology Conference (CRYPTO'95)","author":"Schroeppel R.","unstructured":"Schroeppel , R. , Orman , H. , Malley , S. O. , and Spatscheck , O . 1995. Fast key exchange with elliptic curve systems . In Proceedings of the Annual International Cryptology Conference (CRYPTO'95) . Schroeppel, R., Orman, H., Malley, S. O., and Spatscheck, O. 1995. Fast key exchange with elliptic curve systems. In Proceedings of the Annual International Cryptology Conference (CRYPTO'95)."},{"key":"e_1_2_1_35_1","unstructured":"Seroussi G. 1998. Table of low-weight binary irreducible polynomials. http:\/\/www.hpl.hp.com\/techreports\/98\/HPL-98-135.pdf. Seroussi G. 1998. Table of low-weight binary irreducible polynomials. http:\/\/www.hpl.hp.com\/techreports\/98\/HPL-98-135.pdf."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1995.1055"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/648184.749748"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2093139.2093141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T20:52:20Z","timestamp":1672347140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2093139.2093141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1145\/2093139.2093141"],"URL":"http:\/\/dx.doi.org\/10.1145\/2093139.2093141","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2]]},"assertion":[{"value":"2010-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}}