Target collision resistance.

A function family $\{f$_k}k∈ (where $$ is the key length, taken to be the security parameter) is Target Collision Resistant if any adversary $A$ (whose resources are bounded by a polynomial in $$) can win in the following game only with negligible probability. First $A$ generates a value $v$₁ in the common domain of $\{f$_k}. Next an $$-bit key $k$ is randomly chosen and given to $A$. Next $A$ wins if it generates $v$₂ such that $f$_k(v₁)=f_k(v₂). Note that target collision resistance implies 2nd pre-image collision resistance. See more details in [3, 23].

In our scheme we use a PRF family $\{f$_k} that also has the following flavor of target collision resistance. First a key $k$ is chosen at random, and the adversary is given $f$_k(0). Next the adversary is assumed to be unable (except with negligible probability) to find $k\text{'}\ne k$ such that $f$_k'(0)=f_k(0).

Since any PRF family is also a secure MAC family, in our schemes we use the same function family for both purposes. Still, for clarity, in the sequel we differentiate between the cryptographic functionality of a PRF and a MAC.

In addition, we use digital signatures (secure against chosen message attacks, see [15]), where the sender holds the signing key and all receivers hold the corresponding public verification key. The way in which the receivers obtain the verification key is left out of scope.