This paper focuses on the protection of the confidentiality of the data space content when Shared Data Spaces are deployed in open, possibly hostile, environments. In previous approaches, the data space content was protected against access from unauthorised application components by means of access control mechanisms. The basic assumption is that the hosts (and their administrators) where the data space is deployed have to be trusted. When such an assumption does not hold, then encryption schemes can be used to protect the data space content from malicious hosts. However, such schemes do not support searching on encrypted data. As a consequence, performing retrieval operations is very expensive in terms of resource consumption. Moreover, in these schemes applications have to share secret keys requiring a very complex key management. In this paper, we present a novel encryption scheme that allows tuple matching on completely encrypted tuples. Since the data space does not need to decrypt tuples to perform the search, tuple confidentiality can be guaranteed even when the data space is deployed on malicious hosts (or an adversary gains access to the host). Our scheme does not require authorised components to share keys for inserting and retrieving tuples. Each authorised component can encrypt, decrypt, and search encrypted tuples without knowing other components' keys. This is beneficial inasmuch as it simplifies the task of key management. An implementation of an encrypted data space based on this scheme is described and some preliminary performance results are given. © 2009 Elsevier B.V. All rights reserved.