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.