Re: 'Nuff Said
Is that enough for you?
Let's not confuse anonymity with pseudonimity. The paper describes a method for building the latter upon a network that assume the former as a building block.
There are two routes to proving "identity" (ie, ownership of a particular pseudonym) as outlined/mentioned in the paper. The first is through ZK proofs. Using this, you come up with a secret and then convince some other party (the ZK proof part) that you know the secret or some property of it. When the paper talks about "identity", it's talking about a pseudonym, and when it talks about an "authority" it's talking about something that's acting as your delegate in proving that you own that nym (via a credential that you issue). ZK proofs mean that you can prove that you know the secret key, but never reveal any knowledge that could be used to reconstruct it.
The second kind of identity is group identity. You can prove that you're a member of a group by using one-way accumulators. A CA will generate an accumulator (like a hash table, but more compact and opaque) for each member of the group. Then each member can use that to identify themselves as being part of the group without revealing the other group members. This preserves the essential anonymity of the group (even to other members, though the CA knows the signing keys), while still allowing nym-to-nym self-recognition (and even proving membership to non-members).
It's pretty amazing the things that can be done these days with the crypto primitives we have. It's totally possible to set up an identity (read: pseudonym) system that is totally (well, computationally, to any degree you want) anonymous. That's why I called you out on your initial comment.