Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 7 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.