{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:40:21Z","timestamp":1764981621921,"version":"3.46.0"},"reference-count":34,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T00:00:00Z","timestamp":1606953600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,12,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    At ProvSec 2013, Minematsu presented the circulant hash, an almost-xor universal hash using only the xor and rotation operations. The circulant hash is a variant of Carter and Wegman\u2019s\n                    <jats:italic>H<\/jats:italic>\n                    <jats:sub>3<\/jats:sub>\n                    hash as well as Krawczyk\u2019s Toeplitz hash, both of which are hashes based on matrix-vector multiplication over \ud835\udd3d\n                    <jats:sub>2<\/jats:sub>\n                    . In this paper we revisit the circulant hash and reinterpret it as a multiplication in the polynomial ring \ud835\udd3d\n                    <jats:sub>2<\/jats:sub>\n                    [\n                    <jats:italic>x<\/jats:italic>\n                    ]\/(\n                    <jats:italic>\n                      x\n                      <jats:sup>n<\/jats:sup>\n                    <\/jats:italic>\n                    + 1). This leads to simpler proofs, faster implementations in modern computer chips, and newer variants with practical implementation advantages.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2018-0054","type":"journal-article","created":{"date-parts":[[2020,12,5]],"date-time":"2020-12-05T03:47:20Z","timestamp":1607140040000},"page":"250-257","source":"Crossref","is-referenced-by-count":0,"title":["The circulant hash revisited"],"prefix":"10.1515","volume":"15","author":[{"given":"Filipe","family":"Araujo","sequence":"first","affiliation":[{"name":"CISUC, Dept. of Informatics Engineering, University of Coimbra , Coimbra Portugal"}]},{"given":"Samuel","family":"Neves","sequence":"additional","affiliation":[{"name":"CISUC, Dept. of Informatics Engineering, University of Coimbra , Coimbra Portugal"}]}],"member":"374","published-online":{"date-parts":[[2020,12,3]]},"reference":[{"key":"2025120600333864830_j_jmc-2018-0054_ref_001","doi-asserted-by":"crossref","unstructured":"Mark N.Wegman and Larry Carter,New Classes and Applications of Hash Functions, in: 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979 pp. 175\u2013182, IEEE Computer Society, 1979.","DOI":"10.1109\/SFCS.1979.26"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_002","doi-asserted-by":"crossref","unstructured":"Larry Carter and Mark N. Wegman, Universal Classes of Hash Functions, J. Comput. Syst. Sci. 18 (1979), 143\u2013154.","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_003","doi-asserted-by":"crossref","unstructured":"Mark N. Wegman and Larry Carter, New Hash Functions and Their Use in Authentication and Set Equality, J. Comput. Syst. Sci. 22 (1981), 265\u2013279.","DOI":"10.1016\/0022-0000(81)90033-7"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_004","doi-asserted-by":"crossref","unstructured":"Victor Shoup, On Fast and Provably Secure Message Authentication Based on Universal Hashing, in: Advances in Cryptology - CRYPTO\u201996, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 1996, Proceedings (Neal Koblitz, ed.), Lecture Notes in Computer Science 1109, pp. 313\u2013328, Springer, 1996.","DOI":"10.1007\/3-540-68697-5_24"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_005","doi-asserted-by":"crossref","unstructured":"Stefan Lucks, Faster Luby-Rackoff Ciphers, in: Fast Software Encryption, Third International Workshop, Cambridge, UK, February 21-23, 1996, Proceedings (Dieter Gollmann, ed.), Lecture Notes in Computer Science 1039, pp. 189\u2013203, Springer, 1996.","DOI":"10.1007\/3-540-60865-6_53"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_006","doi-asserted-by":"crossref","unstructured":"Moni Naor and Omer Reingold, On the Construction of Pseudorandom Permutations: Luby-Rackoff Revisited, J. Cryptology 12 (1999), 29\u201366.","DOI":"10.1007\/PL00003817"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_007","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Leonid A. Levin and Michael Luby, Pseudo-random Generation from one-way functions (Extended Abstracts), in: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA (David S. Johnson, ed.), pp. 12\u201324, ACM, 1989.","DOI":"10.1145\/73007.73009"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_008","doi-asserted-by":"crossref","unstructured":"Edgar N. Gilbert, F. Jessie MacWilliams and Neil J. A. Sloane, Codes Which Detect Deception, Bell System Technical Journal 53 (1974), 405\u2013424.","DOI":"10.1002\/j.1538-7305.1974.tb02751.x"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_009","unstructured":"Albert L. Zobrist, A New Hashing Method With Application for Game Playing University of Wisconsin\u2014Madison Department of Computer Sciences, Report no. #88, April 1970."},{"key":"2025120600333864830_j_jmc-2018-0054_ref_010","doi-asserted-by":"crossref","unstructured":"Martin Dietzfelbinger, Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes, in: STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings (Claude Puech and R\u00fcdiger Reischuk, eds.), Lecture Notes in Computer Science 1046, pp. 569\u2013580, Springer, 1996.","DOI":"10.1007\/3-540-60922-9_46"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_011","unstructured":"Bert den Boer, A Simple and Key-Economical Unconditional Authentication Scheme, Journal of Computer Security 2 (1993), 65\u201372."},{"key":"2025120600333864830_j_jmc-2018-0054_ref_012","doi-asserted-by":"crossref","unstructured":"J\u00fcrgen Bierbrauer, Thomas Johansson, Gregory Kabatianskii and Ben J. M. Smeets, On Families of Hash Functions via Geometric Codes and Concatenation, in: Advances in Cryptology - CRYPTO \u201993, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings (Douglas R. Stinson, ed.), Lecture Notes in Computer Science 773, pp. 331\u2013342, Springer, 1993.","DOI":"10.1007\/3-540-48329-2_28"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_013","unstructured":"Richard Taylor, Near Optimal Unconditionally Secure Authentication, in: Advances in Cryptology - EUROCRYPT \u201994, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9-12, 1994, Proceedings (Alfredo De Santis, ed.), Lecture Notes in Computer Science 950, pp. 244\u2013253, Springer, 1994."},{"key":"2025120600333864830_j_jmc-2018-0054_ref_014","unstructured":"Michael O. Rabin, Fingerprinting by Random Polynomials Center for Research in Computing Technology, Harvard University, Report no. TR-CSE-03-01, 1981."},{"key":"2025120600333864830_j_jmc-2018-0054_ref_015","doi-asserted-by":"crossref","unstructured":"Richard M. Karp and Michael O. Rabin, Efficient Randomized Pattern-Matching Algorithms, IBM Journal of Research and Development 31 (1987), 249\u2013260.","DOI":"10.1147\/rd.312.0249"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_016","doi-asserted-by":"crossref","unstructured":"Hugo Krawczyk, LFSR-based Hashing and Authentication, in: Advances in Cryptology - CRYPTO \u201994, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings (Yvo Desmedt, ed.), Lecture Notes in Computer Science 839, pp. 129\u2013139, Springer, 1994.","DOI":"10.1007\/3-540-48658-5_15"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_017","doi-asserted-by":"crossref","unstructured":"Kazuhiko Minematsu, A Short Universal Hash Function from Bit Rotation, and Applications to Blockcipher Modes, in: Provable Security - 7th International Conference, ProvSec 2013, Melaka, Malaysia, October 23-25, 2013. Proceedings (Willy Susilo and Reza Reyhanitabar, eds.), Lecture Notes in Computer Science 8209, pp. 221\u2013238, Springer, 2013.","DOI":"10.1007\/978-3-642-41227-1_13"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_018","doi-asserted-by":"crossref","unstructured":"D. E. Daykin, On the Rank of the Matrix f A and the Enumeration of Certain Matrices over a Finite Field, Journal of the London Mathematical Society s1-35 (1960), 36\u201342.","DOI":"10.1112\/jlms\/s1-35.1.36"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_019","doi-asserted-by":"crossref","unstructured":"Umesh V. Vazirani, Efficiency Considerations in Using Semi-random Sources (Extended Abstract), in: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA (Alfred V. Aho, ed.), pp. 160\u2013168, ACM, 1987.","DOI":"10.1145\/28395.28413"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_020","doi-asserted-by":"crossref","unstructured":"Phillip Rogaway, Bucket Hashing and Its Application to Fast Message Authentication, J. Cryptology 12 (1999), 91\u2013115.","DOI":"10.1007\/PL00003822"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_021","unstructured":"Douglas R. Stinson, On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes, in: Congressus Numerantium 114 pp. 7\u201327, 1996."},{"key":"2025120600333864830_j_jmc-2018-0054_ref_022","doi-asserted-by":"crossref","unstructured":"Ronald L. Rivest, The invertibility of the XOR of rotations of a binary word, Int. J. Comput. Math. 88 (2011), 281\u2013284.","DOI":"10.1080\/00207161003596708"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_023","doi-asserted-by":"crossref","unstructured":"Cunsheng Ding and Zhengchun Zhou, Binary cyclic codes from explicit polynomials over GF(2m), Discrete Mathematics 321 (2014), 76\u201389.","DOI":"10.1016\/j.disc.2013.12.020"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_024","doi-asserted-by":"crossref","unstructured":"Olivier Martin, Andrew M. Odlyzko and Stephen Wolfram, Algebraic properties of cellular automata, Comm. Math. Phys. 93 (1984), 219\u2013258.","DOI":"10.1007\/BF01223745"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_025","doi-asserted-by":"crossref","unstructured":"Dario Bini, Gianna M. Del Corso, Giovanni Manzini and Luciano Margara, Inversion of circulant matrices over Zm Math. Comput. 70 (2001), 1169\u20131182.","DOI":"10.1090\/S0025-5718-00-01235-7"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_026","unstructured":"Joan Daemen, Cipher and hash function design, strategies based on linear and differential cryptanalysis, PhD Thesis K.U.Leuven, 1995."},{"key":"2025120600333864830_j_jmc-2018-0054_ref_027","unstructured":"Ian F. Blake and Ronald C. Mullin, The Mathematical Theory of Coding Academic Press, April 1975."},{"key":"2025120600333864830_j_jmc-2018-0054_ref_028","doi-asserted-by":"crossref","unstructured":"Christophe Doche, Finite Field Arithmetic Handbook of Elliptic and Hyperelliptic Curve Cryptography. (Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen and Frederik Vercauteren, eds.), Chapman and Hall\/CRC,2005, pp. 201\u2013237.","DOI":"10.1201\/9781420034981.ch11"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_029","doi-asserted-by":"crossref","unstructured":"Toshiya Itoh and Shigeo Tsujii, Structure of Parallel Multipliers for a Class of Fields GF(2m Inf. Comput. 83 (1989), 21\u201340.","DOI":"10.1016\/0890-5401(89)90045-X"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_030","doi-asserted-by":"crossref","unstructured":"Joseph H. Silverman, Fast Multiplication in Finite Fields GF(2N in: Cryptographic Hardware and Embedded Systems, First International Workshop, CHES\u201999, Worcester, MA, USA, August 12-13, 1999, Proceedings (\u00c7etin Kaya Ko\u00e7 and Christof Paar, eds.), Lecture Notes in Computer Science 1717, pp. 122\u2013134, Springer, 1999.","DOI":"10.1007\/3-540-48059-5_12"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_031","doi-asserted-by":"crossref","unstructured":"Ted Krovetz and Phillip Rogaway, Fast Universal Hashing with Small Keys and No Preprocessing: The PolyR Construction, in: Information Security and Cryptology - ICISC 2000, Third International Conference, Seoul, Korea, December 8-9, 2000, Proceedings (Dongho Won, ed.), Lecture Notes in Computer Science 2015, pp. 73\u201389, Springer, 2000.","DOI":"10.1007\/3-540-45247-8_7"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_032","doi-asserted-by":"crossref","unstructured":"Daniel J. Bernstein, The Poly1305-AES Message-Authentication Code, in: Fast Software Encryption: 12th International Workshop, FSE 2005, Paris, France, February 21-23, 2005, Revised Selected Papers (Henri Gilbert and Helena Handschuh, eds.), Lecture Notes in Computer Science 3557, pp. 32\u201349, Springer, 2005.","DOI":"10.1007\/11502760_3"},{"key":"2025120600333864830_j_jmc-2018-0054_ref_033","unstructured":"Scott Contini and Yiqun Lisa Yin, On differential properties of data-dependent rotations and their use in MARS and RC6, in: The 2nd Conference on Advanced Encryption Standard (AES), Rome, Italy, March 22-23, 1999 February 1999."},{"key":"2025120600333864830_j_jmc-2018-0054_ref_034","doi-asserted-by":"crossref","unstructured":"Ted Krovetz and Phillip Rogaway, The Software Performance of Authenticated-Encryption Modes, in: Fast Software Encryption - 18th International Workshop, FSE 2011, Lyngby, Denmark, February 13-16, 2011, Revised Selected Papers (Antoine Joux, ed.), Lecture Notes in Computer Science 6733, pp. 306\u2013327, Springer, 2011.","DOI":"10.1007\/978-3-642-21702-9_18"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/15\/1\/article-p250.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2018-0054\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2018-0054\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:35:33Z","timestamp":1764981333000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2018-0054\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,3]]},"references-count":34,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,4,20]]},"published-print":{"date-parts":[[2021,4,20]]}},"alternative-id":["10.1515\/jmc-2018-0054"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2018-0054","relation":{},"ISSN":["1862-2984"],"issn-type":[{"type":"electronic","value":"1862-2984"}],"subject":[],"published":{"date-parts":[[2020,12,3]]}}}