One example way you can do this goes like this:
* Token has a Secret Key S baked inside it
* During enrollment the token makes a random private key P1 and a corresponding public key K1
* It makes a Cookie C1 by encrypting P1 using S
* It signs a message Ma with P1 to produce Za
* It sends C1, K1 and Za
The relying party gets to influence Ma but they do NOT get to pick any of these other values like P1, C1, K1.
The relying party verifies that Za is indeed a signature of Ma with K1 and if so enrollment worked, store C1 and K1
Now, after enrollment the relying party can produce new challenge messages Mb Mc Md and so on for ever, and each time it supplies the token with C1.
Given C1 and Mb, the token can decrypt C1 with S to get back P1, and then it can sign Mb with P1 to produce Zb. It sends that back.
The relying party can confirm that Zb is a signature of Mb with K1 and so this must be the genuine token that was enrolled previously.
AFAIK It does not.
And if it does not, your explanation contains bigger errors about enrollment/process.
@akrel described it much better.
You've become fixated on the part akerl_ (not @akrel) got right, that tokens don't store the private key but missed the _essential_ element they got wrong which is how this key is generated.
One really obvious consequence of things working as I explained rather than as akerl_ (presumably mistakenly not maliciously) explained is what happens if we do enrollment again with the same token for the same Relying Party, for example maybe Alice and Bob are a couple sharing a token.
In reality, as in my explanation, these enrollments produce completely different results, the token will pick a random P1 (thus K1, C1, etc.) when Alice enrolls and a different random P2 (thus K2, C2, etc.) when Bob enrolls, and for the Relying Party everything is different between these two enrollments, just as if the token was different.
In akerl_'s description Alice and Bob would get the same application ID, same results, and now a Relying Party can tell that Alice and Bob are using the same token.
Nothing in my comment implied that if google betrayed you, it would leak your facebook token.