Network virtualization has become increasingly popular in recent years. It has the potential to allow timely handling of network infrastructure requests and, after instantiated, their lifecycle. In addition, it enables improved physical resource utilization. However, the use of network virtualization in large-scale, real environments depends on the ability to adequately map virtual routers and links to physical resources, as well as to protect virtual networks against security threats. With respect to security, mechanisms supporting confidentiality and privacy have become essential in light of recent discoveries related to pervasive electronic surveillance. In this paper we propose a set of tools to efficiently embed virtual networks with privacy support and to allow their real instantiation on top of SDN/OpenFlow-based substrates. This toolset unfolds into three main contributions: (a) an exact VNE model suitable for smaller networks, which also serves the purpose of determining an optimality baseline; (b) a heuristic VNE algorithm, which features precise modeling of overhead costs of security mechanisms and handles incoming requests in an online manner; and (c) a VNE to SDN/OpenFlow translation mechanism, which takes as input the outcome of the heuristic VNE algorithm and produces a set of coherent OpenFlow rules to guide the real instantiation of the mapped virtual networks. We present a detailed performance comparison between the proposed heuristic and the optimization model. The obtained results demonstrate that the heuristic algorithm is able to find feasible mappings in the order of seconds even when dealing with large network infrastructures. Finally, we demonstrate how mappings generated by our heuristic VNE