Learn Spanish (Latin America): Dudo que ellos hayan descifrado el acertijo. - I doubt that they have deciphered the riddle.

The phrase Dudo que (I doubt that) expresses uncertainty, which forces the second part of the sentence into the subjunctive mood. Because the action of deciphering is something they supposedly already did, we use the present perfect subjunctive (hayan plus the past participle) to say that they have deciphered it.

If I changed the sentence to say I am sure that they have deciphered the riddle, would I still use hayan?

No, you would not. Phrases expressing certainty, like Estoy seguro de que (I am sure that) or No dudo que (I do not doubt that), trigger the normal indicative mood. You would instead use the regular present perfect: Estoy seguro de que ellos han descifrado el acertijo.

Is it strictly necessary to include the pronoun ellos in this sentence?

It is not strictly necessary, but it is very helpful here. The verb form hayan can mean they have (ellos or ellas) or you all have (ustedes). Including ellos removes any ambiguity about who exactly you are doubting.

I see that descifrado looks a lot like deciphered. Is it a regular verb?