Existing multi-tenant network virtualization platforms have so far focused on the offer of conventional networking services by a single cloud provider. As such, they face limitations in terms of security and dependability, both in terms of the infrastructure itself and of the services offered to its customers. To address these challenges we present the design and implementation of Sirius, a network virtualization platform for multi-cloud environments. Contrary to existing solutions, Sirius considers not only connectivity and performance, but also security and dependability as first class citizens, leveraging from a substrate infrastructure composed of both public clouds and private data centers.