Internet-like
I would think about names on Internet - You know, that I am Gilhad and my reputation is (just now, just here) 221, with 1 silver and 4 bronze badges. This is not much, so I am now really known here, but anyway it is that I am not total newbie here and maybe you will remember me so. Maybe a year later my reputation will be much higher and I will have more badges and you will say "I got this idea from Gilhad. You know him? Does not talk many times, but usually has something to say." and others would or would not agree and they would know about me, my ideas and such. You can google me and find out more about "gilhad" and it would probably be me. But if you meet me on the street, you would not recognize me, until I, or someone else, will give it away. And it would be hard to prove whether that dog with the black left leg is "gilhad" or not.
Anyway if I want to disappear, I can stop being "gilhad" any moment and create another nickname and go by it with new reputation, maybe even with a new approach to problems. (Actually I may do that already for years, who knows and who cares?)
My true name is something totally different and many people, who know me as "gilhad", have never heard it and would not recognize me by it. Still, they consider me a friend, some of them met me in person on more occasion and that is enough for them. "gilhad" means something for them for sure. But for the Caliphat it has no real value.
I play a lot of Role Playing Games and I change characters even in one game over time. Co-players usually refer to me by my character's name during the session and also in every day life at the era of that game campain, as some of those names are more catchy for them than plain old "gilhad", which they use to address me formally. So if there was some conspiracy against the Caliphat and some rebels were interrogated, they may (by their best knowledge) give me as "Monsieur Klobrc" as it is the only name they did hear in personal talking about me. And so the Caliphat would need to catch some members of my group to reveal, that "Monsieur Klobrc" is "gilhad". But even so, who is that "gilhad" anyway - there is more people who knows me as "gilhad" only, than who knows my official name (and of that a lot did not hear anything about "gilhad"). Still, nobody has a problem with it (except maybe the Caliphat).
So using nicknames can be the answer to your question - of those, who should know, the nickname is good enought to describe and target person. But out of that group the nickname means nothing and one person may go under more nicknames at the same time, without problems.
The only way the Caliphat can pin-point down is to force people to point fingers at those, who (they think) know me and are able to point their finger at me personally. But shouting loudly in the right places (or write on a wall or anything else) to tell "Monsieur Klobrc" that there is such and such problem would probably work in the way, that I would get aware about mentioned problem soon enough.
Also, see at this very question - I bet there is a way less real names than nicknames and it still looks natural for all of us to the way, that nobody mentioned it here before. (As answer from gilhad to Mickey - the Caliphat has good luck find who asked and who answered. The community knows well, but cannot say it to you, oh mighty Calif, no matter what.)