Or is authentication essentially incompatible with anonymity?
If we have the idea that authentication is proving that someone is who they say they are and anonymity is essentially having an unknown identity, could you have a system that could authenticate you but that you could still use anonymously?
Would adding a 3rd party service to the mix change the answer?
First, authentication is not really “proving that someone is who they say they are”, but linking an action, message or situation with an identity. If I show my passport to prove who I am, what I am really doing is linking my physical presence with the identity conferred to me by the state of which I am a national.
A person may well have multiple identities. For example, people with dual citizenship have two passports and what they do with one is somewhat decoupled with what they do with the other.
Multiple identities are the basis of anonymity. Indeed, as soon as you interact with anyone else in any way, this creates an identity: you're the person who did this thing at that time. Anonymity is not a lack of identity, but a lack of a link between a certain identity and any other identity that you may have.
Coming back to authentication, it is a link between two identities: the person who did that thing at this time is the same person who owns these credentials. Phrased this way, authentication is exactly contradictory with anonymity. However, there are many situations where it is useful to have partial authentication or partial anonymity.
An obvious solution to partial anonymity is to have a trusted third party as an intermediary. I'm using one right now: you know me by my Stack Exchange account, and you can use this identity to authenticate my Stack Exchange activity. Stack Exchange knows me by an identity with an OpenID provider, but isn't telling you. My OpenID provider in turn knows some things about me, but they only know the name on my passport if I've been telling them. There is a chain of links between identities (which could be traced all the way to, say, my home address via ISP logs), but you need the collaboration of multiple parties to resolve the chain.
How satisfactory such situations are depends on how the identification linkage chain is set up and what parties you're prepared to trust. Having identification linkage chains that are practically impossible to trace is the basis of anonymity systems such as TOR.
Going in another direction, authentication is very often used for authorization. I may use this account because I am the account owner. I may enter this building because I am an employee. An authorization system can be set up to decouple the action that is being authorized from the identity that led to the authorization. A well-known example is voting systems: they have both strong authorization requirements (only registered voters may vote, and only once per election) and strong anonymity requirements (even I cannot prove who I voted for, at least not if I want my vote to be counted). In traditional voting systems, anonymity is ensured by stepping into a booth to put a standardized piece of paper in an opaque envelope. Anonymity is ensured by observers who control that everyone steps into the booth and by rules that make non-anonymous ballots void.
There are several definitions of anonymous.
As per the free dictionary for example, "Having no distinctive character or recognition factor" is anonymous. Eg: Having an unknown or unacknowledged name: an anonymous author.
As per the wikipedia page on the anonymous group, "The name Anonymous itself is inspired by the perceived anonymity under which users post images and comments on the Internet. Usage of the term Anonymous in the sense of a shared identity began on imageboards, particularly the /b/ board of 4chan, dedicated to random content. A tag of Anonymous is assigned to visitors who leave comments without identifying the originator of the posted content. Users of imageboards sometimes jokingly acted as if Anonymous was a single individual. The concept of the Anonymous entity advanced in 2004 when an administrator on the 4chan image board activated a "Forced_Anon" protocol that signed all posts as Anonymous"
As per Google, (of a person) not identified by name; of unknown name.
tl;dr: Through all these definitions the one thing we can establish is the fact that behind every real or fake anonymous persona, there is inherently a very real person who made it. Anonymity therefore lies in the lack of information correlating the real identity and "anonymous identity" of the person. The more the correlation's tangibility, the lesser the obtained anonymity.
For example, voting in a democratic process, votes must be verifiable, but yet anonymous. It's a clear example of how it is possible to have a system where within the system you are anonymous. Votes are termed anonymous because you can not correlate a vote to a specific individual.
There are three limitations to this approach:
1) For anonymity, there can not be a distinguishing factor. For example, in an "anonymous publishing system" writing works would have distinctive characteristics that could be used for recognition. Or in a voting system, those close to the person voting would know his vote. Or you can interrogate a person until he gives up his anonymous vote (both of which can be flawed by disinformation).
2) Numerical Strength Numerical strength makes it harder to tie patterns to one individual.
3) Legal Standpoint Any system that goes "against the law" will have to prove accountability for the accused illegal actions. If it fails to do so, there will be attempts to shut/disrupt the system's functioning. Additionally as history shows, all its members will be treated equally liable as the anonymous identity that committed the accused crime.
In practice, if you had to authenticate someone, you would need a secret.
If this secret was shared amongst all trusted members based on an identity requirement (how voting is done), then when inside the system with static input their identity would be anonymous. In case of dynamic input systems, the person would have to reduce recognizable marks enough to blend into the system's population to stay anonymous. The problem in this system that gives you authentication and anonymity, is accountability if data leak prevention fails. That is, if the shared secret is leaked, there is no viable long term defense measure.
If the secret is not a shared secret, but rather unique to a each person, then the system must be designed such that it does not leak session data when making a post. Eg. All posts on /b/ appear as Anonymous. Obviously, the backed should not have logs for IP, etc as well. In this scenario, a leak is isolated to that person's online identity on that system only, thus preserving system security. Since in this implementation there is no correlation between the now selectively isolated user and his real life identity, he is still anonymous. Obviously, the limitation of this is a reset. In case of a forum, banning an anonymous member would mean that he can re-register. In case of a voting systems, banning a compromised account would mean that the user would have to wait until the entire systems' users reset. Eg: If the counter for voting for a candidate fails, then people can't really complain about it while being anonymous. They would have to wait for next year or complain about it after giving up anonymity. However, it would work when banning a member from a system that does not accept new members.
So in this case, you can build systems to have authentication and ensure anonymity of actions while within the system, however unless you fake legal documents, being truly anonymous in the system of life is not a possibility.
A 3rd party in this case would be to ensure the system itself is not compromised. But the system is inherently only as safe or as vulnerable as any other software built.
Lastly, BitCoins is another example of where it is possible to have a system with authentication, accountability and anonymity within the system. So yes, it is possible. What's not possible is to guarantee that all successful authentications by the original real identity that formed the online identity.
Batman was temporarily stunned. The goon crouched over him and tried to grasp his mask.
- What are you doing, you fool ? rasped the Joker.
- Hu, I wanna see his real face, guv'.
The Joker lashed his cane at the thug, sending him rolling to the floor.
- Idiot ! The mask is his real face !
Authentication is about making sure that some data (or action, as @Gilles says) really originates from somebody who matches a given notion of identity. However, any individual has a lot of identities. Consider, for instance, a Web forum (or a Q&A site as this one). And a user; let's call him Bruce. Bruce has created an account under the pseudonym of "racoonman". The account is linked to his email address, which is "racoonman@anonemail.com", obtained from a provider of "free mail accounts". Bruce connects to both the Web forum and the email provider only through Tor (for this question, we assume that Tor provides perfect "anonymity" in that connections cannot be traced back to Bruce's name or IP address).
In a sense, Bruce is completely anonymous: the messages he posts on the Web forum cannot be linked to his "true name", as defined by legal authorities. On the other hand, he is not anonymous at all. To illustrate this, let's assume that another individual tries to create his own account on the forum, with the same pseudonym of "racoonman", and then proceeds to posts messages under that name, with outrageous contents that Bruce finds demeaning. Bruce will be very irate; he will denounce the framing with the utmost vehemence; he will call upon the forum administrators to make the usurpation cease; at the very least, he will unleash all his rhetoric fury on the villain who dared steal the good name of Racoonman.
Therefore Bruce is "anonymous" on the forum because Bruce is not really using the forum; Racoonman is connecting. And Racoonman is certainly not anonymous; he will defend to the death his name and fame. Yet Racoonman's identity is limited in scope; it exists only on the Web forum, and, more importantly (for Bruce), it is not traceable to Bruce's legal identity. The anonymity that Bruce is looking for is really this absence of link between his two personae. Yet Racoonman is certainly well-authenticated from the point of view of the forum administrators: he uses his password and they are quite sure that it is the same Racoonman all along. That is the notion of identity which is at work on the Web forum: that several messages can be unambiguously linked together as being from the same author, whoever that guy may be.
The many facets of identity and anonymity are an attractive playground for cryptographers. For instance, there is the nice concept of ring signatures as described in 2001 by Rivest, Shamir and Tauman. In this algorithm, each user in a group has his public/private key pair, and the public keys are all known and unambiguously linked to the individual group members. Then one group member can take an arbitrary message and produce a signature on it, with the following properties:
Ring signatures thus realize an interesting mixture of authenticity and anonymity. A ring signature absolutely demonstrates involvement of "a group member" while absolutely protecting the member's identity within that group (even against the other group members) -- that is, everybody knows who is member of the group, but the signed message cannot be traced back to a specific member.
(On the surface, we could have the same kind of property by using a single signature private key that all group members know; but ring signatures allow for adding and removing members at will, and the signer can even "create" the group whenever he signs, since the other members are not actively involved.)
An important point to make is that this notion of anonymity is not the same as the one used above in the Web forum example. Depending on the context, someone who wants to be "anonymous" might want to refer to one notion of anonymity, or the other, or yet another of the myriads of possible definitions.
This all depends on the purpose of the authentication. Authentication has nothing directly to do with identification, rather authentication is a process by which one person or system determines that they are okay dealing with another person or system.
In most cases this means something like a user log in system, where each user has some identity, and something like a password is used to authenticate.
However that is not necessary, maybe I'm not trying to say only people the system knows are allowed, but rather, only people are permitted. That is what capchas are for, they authenticate the humanity of a user.
Another example is a great history of persecuted groups (often underground religions) that would use special signs/symbols/phrases to tell others that they were part of the group. In such cases anonymity was incredibly important, but authentication was still possible.
So the answer is that anonymous authentication is most certainly possible, but the applicability depends on the particular use case.
You could have authenticated communication over a system in which you do not use your real names, but you have set up together so that the two of you know who each-other is. In this way you would be anonymous to everyone else but be authenticated to each-other (Off-The-Record chat, or OTR, would be an example of this). A third party makes it easier, because it could authenticate both participants but they would not know who the other is. This idea is used in the "web of trust" concept that GPG and PGP users use to authenticate each-other, they use cryptographic signatures of people they trust to confirm the validity of encryption keys they do not know.
The SQRL project over at GRC offers a pretty simple but brilliant system for Authentication without identification. Granted, without the necessary precautions (using a VPN or such to anonymize your IP), you may still be able to be identified by certain means.
