A tamper seal for a message that can't be forged however powerful the attacker, as long as each key seals just one message.
The idea: Think of the key as picking one hash function at random from a huge, carefully designed family. The tag is that function applied to the message. A forger who has seen one message and its tag still doesn't know which function was picked, and the family is built so that the right tag for any other message is still a blind guess. With a fresh key for every message there's nothing to learn, so even unlimited computing power doesn't help. In practice the fresh keys come from a cipher, which is where a hardness assumption sneaks back in.
Why it matters: It's the quick "did anyone change this?" check inside the encryption that protects most web traffic.
On the map: Poly1305, GHASH
A MAC (message authentication code) lets a receiver check that a message wasn't altered. One-time MACs built from universal hashing (Wegman-Carter)[1] are unconditionally secure: if each key authenticates a single message, a forger succeeds only with negligible probability, whatever their computing power.
Poly1305 and GHASH are of this kind[2, 3]. In ChaCha20-Poly1305 a fresh Poly1305 key is derived from the cipher for every message[4]. AES-GCM keeps one GHASH key but masks each tag with a fresh block from the cipher, the classic Wegman-Carter construction[5]. Either way the combination relies on the cipher being a good pseudorandom function. One-time MACs also authenticate the classical channel that QKD needs.
If any of these breaks, this breaks too.
If this breaks, these break with it.