Abstract
Message authentication codes (MACs) using polynomial evaluation have the advantage of requiring a very short key even for very large messages. We describe a low complexity software polynomial evaluation procedure, that for large message sizes gives a MAC that has about the same low software complexity as for bucket hashing but requires only small keys and has better security characteristics.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
G.J. Simmons, “A survey of information authentication≓, in Contemporary Cryptology, The Science of Information Integrity, ed. G.J. Simmons, IEEE Press, New York, 1992.
P. Rogaway, ≓Bucket hashing and its application to fast message authentication≓, Proceedings of CRYPTO ’95, Springer Verlag, pp. 29–42, August, 1995.
M. Bellare, J. Kilian, and P. Rogaway, “The security of cipher block chaining≓, Proceedings of CRYPTO’ 94, Springer Verlag, pp. 341–358, August, 1994.
M. Wegman and L. Carter, ≓New hash functions and their use in authentication and set equality≓, J. of Computer and System Sciences 22, pp. 265–279, 1981.
D. Stinson, ≓Universal hashing and authentication codes≓, Designs, Codes and Cryptography, Vol. 4, pp. 369–380, 1994.
J. Bierbrauer, T. Johansson, G. Kabatanskii and B. Smeets, ≓On families of hash functions via geometric codes and concatenation≓, Proceedings of CRYPTO ’93, Springer Verlag, pp. 331–342, 1994.
P. Gemmell and M. Naor, ≓Codes for interactive authentication≓, Proceedings of CRYPTO ’93, Springer Verlag, pp. 355–367, 1994.
C. Gehrmann, ≓Cryptanalysis of the Gemmell and Naor multiround authentication protocol≓, Proceedings of CRYPTO ’94, Springer Verlag, pp. 121–128, 1994.
C. Gehrmann, ≓Secure multiround authentication protocols≓, Proceedings of Eurocrypt ’95, Springer Verlag, pp. 158–167, 1995.
T. Johansson, Contribution to Unconditionally Secure Authentication, Ph. D. thesis, Lund 1994.
M. Atici and D. R. Stinson, ≓Universal hashing and multiple authentication≓, Proceedings of CRYPTO ’96, Springer Verlag, pp. 16–30, 1996.
J.E. Savage, ≓The complexity of decoders. Computational work and decoding time≓, IEEE. Trans. Inform. Theory, Vol. 17, pp. 77–85, January, 1971.
E.R. Berlekamp, ≓Bit-serial Reed-Solomon encoder≓, IEEE. Trans. Inform, Theory, Vol. 28, pp. 869–874, November, 1982.
M.A. Hasan and V.K. Bhargava, ≓Division and bit-serial multiplication over GF(qm)≓, IEE Proceedings-E, Vol.139, No. 3, May, 1992.
D. Jungnickel, Finite fields: structure and arithmetics, Wissenschaftsverlag, Mannheim-Leipzig-Wien-Zurich, 1993.
V.B. Afanassiev, ≓On the complexity of finite field arithmetic≓, Fifth Soviet-Swedish Int. Workshop on Inform. Theory, Moscow, January, 1991.
E.D. Mastrovito, VLSI Designs for Computations over Finite Fields GF(2m), Internal Report LiTH-ISY-I, Linköping Univ., Sweden, 1988.
T. Kasami, ≓An upper bound on k/n for affine-invariant codes with fixed d/n≓, IEEE Trans. Inform. Theory, Vol. 15, pp. 174–176, January, 1969.
Ph. Piret, ≓On the number of divisors of a polynomial over GF(2)≓, Springer Verlag, Lecture Notes in Comp. Sci. 228, pp. 161–168, 1985.
I. E. Shparlinski, Computational and algorithmic problems in finite fields, Kluwer, Dordtrecht-Boston-London, 1992.
H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhuser, Boston-Basel-Stuttgart, 1985.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Afanassiev, V., Gehrmann, C., Smeets, B. (1997). Fast message authentication using efficient polynomial evaluation. In: Biham, E. (eds) Fast Software Encryption. FSE 1997. Lecture Notes in Computer Science, vol 1267. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052346
Download citation
DOI: https://doi.org/10.1007/BFb0052346
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63247-4
Online ISBN: 978-3-540-69243-0
eBook Packages: Springer Book Archive