This article addresses the security of Semantic Web Services that are declaratively described in OWL-S. The authors propose ontologies to annotate OWL-S input and output parameters with respect to their security characteristics, including encryption and digital signatures. They incorporate privacy and authentication policies into OWL-S descriptions and requester profiles. The authors have designed and implemented algorithms to check policy compliance and integrated them in the OWL-S Matchmaker?s service selection process. They also discuss extending the OWL-S VM with features for encrypting and signing messages exchanged between a service requester and provider.