I understand that a MAC algorithm takes a message and a private key as input and hashes them to a value. I understand that senders and receivers often use MACs to authenticate a message and check the integrity of a message. If a sender/receiver successfully computes the same mac, then (1) the receiver has assurance that the sender has the secret key (2) the receiver has assurance that the message was not tampered with in sending (because otherwise it would generate a new mac value). I also understand that digital signatures are somehow different from MACs. But it seems like both verify the sender and authenticity of the message. If you have a successful MAC scheme set up you know that the message (1) is coming from a person with the key (handling authentication) and (2) has not been tampered with (handling tampering). So what do digital signatures do that MACs don't? What's the difference?
- Generation: given the message m and a key K1, compute the MAC value or signature s.
- Verification: given the message m, a key K2 and the MAC value or signature s, verify that they correspond to each other (the MAC value or signature is valid for the message m, using verification key K2)
With a MAC, keys K1 and K2 are identical (or can be trivially recomputed from each other). With a signature, the verification key K2 is mathematically linked with K1 but not identical, and it is unfeasible to recompute K1 from K2 or to generate valid signatures when you only know K2.
Thus, signatures dissociate the generation and verification powers. With a MAC, any entity who can verify a MAC value necessarily has the power to generate MAC values of its own. With signatures, you can make the verification key public, while keeping the generation key private. Signatures are when you want to produce a proof verifiable by third party without having to entrust these third parties with anything.
Application: a CA (like Verisign or Thawte or whatever) issues a certificate to a SSL server. Everybody, and in particular your Web browser, can verify that the certificate issued to the SSL server has indeed been signed by Verisign/Thawte/whatever. But this does not give you the power to issue (sign) certificates yourself, which would appear as if they were issued by Verisign/Thawte/whatever.
Thomas Pornin's answer, as always, is excellent, but I wanted to add a point, and that was the difference in what verification of each of these represents. The short of it is that a MAC can be used only to verify the integrity of the message. A signature verifies not only the message integrity, but the sender's identity.
The difference is inherent in the symmetric vs asymmetric structure of the algorithms. Back to Thomas's post, MACs are symmetric; they use the same key K both to generate the MAC and to verify it. As such, they verify that the message containing the MAC is the message originally sent by the other party to this conversation, because being able to tamper with the message in a way that the MAC would still match is believed to be difficult (and "difficult" in cryptography has the colloquial definition of "practically impossible").
However, because the key to a symmetric algorithm is a "shared secret", it has to be shared, and that means it isn't really a secret. There are known ways to share this key with one and only one other specific person, but it's this sharing process that allows you to positively identify the other person using the key; the algorithm itself has no way to demonstrate to either party that the other person is the one who is supposed to have it.
Digital signatures, OTOH, are asymmetric; two different keys are used, one to generate and the other to verify. The verification key is "public"; you can spray-paint it on your car and drive it into the middle of DEF CON (hacker convention) and it would not make the scheme any weaker. Again, it's believed to be difficult to generate or tamper with a message and/or its signature and still make one match the other, without knowing the generation key.
This generation key is "private"; it's a true secret, known only to one party, who can implement all sorts of additional layers of physical and electronic security to protect this data even from themselves (many PKIs are set up using a Hardware Security Module to actually generate the private key and perform encryption using it; the key never leaves that HSM). Therefore, it's theoretically possible to positively identify the other party to the conversation, based on their ability to properly sign messages that can be verified with their public key, because there is one and only one entity on the planet that has a prayer of doing so.