The Internet of Things, by digitizing the physical world, is envisioned to enable novel interaction paradigms with our surroundings. This creates new threats and leads to unprecedented security and privacy concerns. To tackle these concerns, we introduce Talos, a system that stores IoT data securely in a Cloud database while still allowing query processing over the encrypted data. We enable this by encrypting IoT data with a set of cryptographic schemes such as order-preserving and partially homomorphic encryption. In order to achieve this in constrained IoT devices, Talos relies on optimized algorithms that accelerate order-preserving and partially homomorphic encryption by 1 to 2 orders of magnitude. We assess the feasibility of Talos on low-power devices with and without cryptographic accelerators and quantify its overhead in terms of energy, computation, and latency. With a thorough evaluation of our prototype implementation, we show that Talos is a practical system that can provide a high level of security with a reasonable overhead. We envision Talos as an enabler of secure IoT applications.