What kind of cryptography should i use?
Your requirements include the following:


S can decrypt the token.
C cannot decrypt the token.


Since S must be able to do something that C cannot, it needs to know something that C does not.

Your approach of signing the token with A's signature is fine for ensuring its integrity (C won't be able to modify it) as long as S knows A's public key through a trusted method (e.g. provisioning when you install your application). To encrypt the token, you will need something else.

The most obvious solution is that S generates a key pair and submits the public key to A (in a way that other parties cannot tamper with — TLS would be fine, as S already has A's public key).

A does not need to trust S in any way (unless there is some authorization mechanism and not just anyone can obtain a token, but that would be a different problem which you don't mention in your question). If S submits a self-signed certificate, just accept it, and identify S by its public key. If that certificate is invalid (i.e. S does not know the associated private key after all), then S will not be able to decrypt the token. S already has the power to refuse to decrypt the token, so this attack vector does not have any security impact.

Be careful in your protocol about replay attacks. Depending on what goes into the token, it may be reusable for other purposes, so make sure that all relevant information (identity of S, identity of C, purpose of the token, …) goes into the signature.