Homomorphic MAC

• Given a pseudo random generator and a pseudo random function. Let and are the keys used for the MAC construction.

Sign: Given basis vector and a key pair do:

1.

2.

3.

Here, is a MAC tag.

Combine: Given, , , compute,

Verify: Given a secret key and, verify a tag as follows.

• and

•

• If then output 1; otherwise output 0