Virtual Private LAN Service (VPLS) is a VPN technology that connects remote client sites with provider networks in a transparent manner. Session key-based HIPLS (S-HIPLS) is a VPLS architecture based on the Host Identity Protocol (HIP) that provides a secure VPLS architecture using a Key Distribution Center (KDC) to implement security mechanisms such as authentication, encryption etc. It exhibits limited scalability though. Using multiple distributed KDCs would offer numerous advantages including reduced workload per KDC, distributed key storage, and improved scalability, while simultaneously eliminating the single point of failure of S-HIPLS. It would also come with the need for optimally placing KDCs in the provider network. In this work, we formulate the KDC placement (KDCP) problem for a secure VPLS network as an Integer Linear Programming (ILP) problem. The latter is NP-hard, thereby suggesting a high computational cost for obtaining exact solutions especially for large deployments. Therefore, we motivate the use of a primal-dual algorithm to efficiently produce near-optimal solutions. Extensive evaluations on large-scale network topologies, such as the random Internet graph, demonstrate our method’s time-efficiency as well as its improved scalability and usefulness compared to both HIPLS and S-HIPLS.