Signature with HTTP Redirect Binding

The SAML binding documentation describe how to encode and sign a SAML message sent with HTTP Redirect Binding

My question is about signature :

I'm more familiar with XML Signature which usually includes the certificate (or public key) that can be used to verify the signature

But with HTTP-Redirect, I presume that certificate can't be send due to space concerns.

So how does the receiver knows the public key to be used to verifiy the signature ?

Does it have to maintain a list of all possible senders with their associated public key ?

Val廨ie