next up previous
Next: Security Analysis of Scheme Up: Proof of Security Previous: Pseudorandom functions (PRFs).

Target collision resistance.

A function family {fk}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 v1 in the common domain of {fk}. Next an -bit key k is randomly chosen and given to A. Next A wins if it generates v2 such that fk(v1)=fk(v2). 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 {fk} that also has the following flavor of target collision resistance. First a key k is chosen at random, and the adversary is given fk(0). Next the adversary is assumed to be unable (except with negligible probability) to find k'≠k such that fk'(0)=fk(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.gif

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.


next up previous
Next: Security Analysis of Scheme Up: Proof of Security Previous: Pseudorandom functions (PRFs).

Adrian Perrig
Sat Sep 2 17:01:14 PDT 2000