We extend traditional Virtual Private Networks (VPNs) with fault-tolerance and dynamic membership properties, defining a Dynamic Virtual Private Network (DVPN). We require no new hardware and make no special assumptions about line security. An implementation exhibits low overheard, provides guarantees of authenticity and confidentiality to any IP application running over the virtual network. Our system is lightweight, allowing the use of multiple fine-grained VPNs. Instead of using many point-to-point secure connections to bridge insecure communication paths we share a single symmetric encryption key throughout the VPN. This permits tight control of the VPN membership and fast dynamic membership change. Since we lower the cost of a single DVPN, we propose using multiple DVPNs to implement fine grained security. By enforcing policies over communication between DVPNs, our scheme supports multilevel security.