XMLSecurity exception while decrypting: Errors occurred during de-serialisation

[Peter Schober]

I've been reported a very weird issue: Using the same IDP (running
the Shibboleth software), person A runs into the following error on 2
out of 4 SPs (all running the Shibboleth SP software), while accessing
the other 2 SPs is working fine for them:

ERROR Shibboleth.SSO.SAML2 [17] [default]: failed to decrypt assertion: XMLSecurity exception while decrypting: Errors occurred during de-serialisation of decrypted element content
WARN Shibboleth.SSO.SAML2 [17] [default]: error processing incoming assertion: A valid authentication statement was not found in the incoming message.

To make things even weirder, another person B, using the same IDP, can
log in to all 4 SPs successfully, at the same time (shortly
before/after person A).

All entities (the 4 SPs and the IDP) are using the same metadata
aggregate from our little federation. No metadata changes concerning
these entities in a while.

None of this makes any sense to me, of course.
(I can already hear Scott saying that's all "physically impossible".)

* It can't be the metadata (e.g. EncryptionMethod), as that wouldn't
explain different results for the 2 subjects using the same IDP.
(Also the same metadata seemingly works for all other IDPs, including
my own.)

* It can't be the SP, because other person B from the same IDP can log
in there just fine, as can other people from all other IDPs, AFAIK.

* I fail to imagine what an IDP could to that would cause this issue
for one person but not for another, and then not for all SPs but only
for some.
According to the IDP operators the logs look the same for person A and
person B. (I'm assuming they only have looked at process/audit logs
with "normal" production logging. not debug logging.)

* Software versions don't help (and couldn't expain this anyway), as
both one of the working and one of the not-working-for-person-A SPs
are running SP v3.5.0 from current Debian 13 packages.

Any ideas? At least what to focus on, debug logging on the SPs or on
the IDP or both?

-peter