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 