Due to the numerous advantages in terms of cost reduction, usability, and flexibility, today we are witnessing the adoption of solutions where individuals and enterprises prefer to outsource (part of) their private information or assets for processing to third parties. Yet, such adoption will not become a complete success unless outsourced data storages reliably guarantee the privacy of sensitive information. With this aim in mind, some data storage providers offer the possibility of encrypting assets, achieving a remarkable degree of privacy, but at the expense of usability. At best, advanced cryptographic primitives can be directly implemented over the encrypted data to allow its owners to perform certain operations, such as keyword-based searches, on the side of the data storages. The paper at hand proposes a novel approach based on fully homomorphic encryption to correlate encrypted pieces of data in outsourced data storages. The goal was to enrich searchable encryption solutions by transparently adding related keywords to a given query, yet preventing the data storages to know the outsourced information, the received query, the resulting response, or the relationship between queries and responses. The conducted experiments show that nowadays, the main bottleneck resides in the inefficiency of the existing fully homomorphic encryption algorithms. Nevertheless, our proposal is not tied to any particular algorithm, thereby allowing users to select the most efficient in terms of computing time.