Are poly1305 authenticators distinguishable from random data?

Assume Alice authenticates a message $M$ with nonce $N$ and secret key $K$, creating authenticator $A$. She then sends $A$ across the network.

The Poly1305 paper does not seem to specify whether it is possible for an adversary, whom has seen $A$, to determine whether $A$ is just random bytes or has characteristics of an output from poly1305.

For someone interested in deniability, this is an important distinction. Are poly1305 authenticators distinguishable from random data?

-

No, they are not distinguishable from random.

The Poly1305-AES authenticator is defined as:

$$(((c_1 r^q + c_2 r^{q−1} + ... + c_q r^1 ) \bmod {(2^{130} - 5)}) + \operatorname{AES}_k (N)) \bmod 2^{128}$$

Since it is the sum of an AES output and some other number modulo $2^{128}$, it is PRF if:

• the AES output is PRF and
• the two numbers are independent.

AES output looks like PRF as long as you see less than ~$2^{64}$ of them and $k$ and $r$ are required to be independent (since they are chosen from a uniform distribution), so the authenticators are indistinguishable from random at least as long as you see significantly fewer than $2^{64}$ of them.

-