Conceptually, tuple spaces are shared memory objects that provide operations to store and retrieve ordered sets of data, called tuples. Tuples stored in a tuple space are accessed by the contents of their fields, working as an associative memory. Although there are some proposals for secure tuple spaces, accessing tuples through field contents makes these systems susceptible to attacks that could impair user and data privacy, since servers must access tuple data. In order to deal with these limitations and provide privacy in the tuple space model, this paper proposes some extensions to DEPSPACE, a tuple space system that implements dependability and security properties through a set of mechanisms that are not enough to ensure privacy. The resulting system provides privacy and, at the same time, allows tuple selection/matches similar to the traditional insecure model, i.e., it does not constraint the matching possibilities. The main problem to be addressed is that servers must select tuples based on their contents without knowing them. The proposed solution uses robust cryptographic schemes, as order-preserving encryption and homomorphic encryption, to provide this functionality without revealing the tuple contents. An analysis concerning security aspects of DEPSPACE is presented, as well as the benefits of the proposed solutions. A set of experiments, executed with an implementation of the proposed protocols, shows the feasibility of the proposed solutions and shed some light on both the behavior of the system and the costs to provide privacy in the tuple spaces model.