Existing network service provisioning and lifecycle management (LCM) workflows rely on heterogeneous devices from multiple vendors and collaboration between multiple network actors, which can lead to numerous trust management and interoperability issues. Blockchain networks (BCNs) are a revolutionary way to establish trust in untrusted environments. In this complex environment, BCNs can help ensure transparency and security for network service LCM. However, BCNs are also vulnerable to quantum attacks. Advances in quantum computing will challenge the security of existing blockchain technology based on Public Key Infrastructure (PKI) technologies. In this paper, we explore how network services can be managed in a multiple administrative scenario. Our approach uses BCNs to track the operational steps of network service instantiation metrics while benefiting from the security features of post-quantum cryptography (PQC). Together with the use of N-th degree Truncated polynomial Ring Units (NTRU) as an example of a PQC algorithm that relies on the parallelization power of the Toom-Cook computation method with different security levels, we have shown that Quorum can provide a lower average time-to-write value compared to other BCNs considered (Ethereum and Hyperledger). At the end of the paper, we discuss the evaluation results and future directions regarding the coexistence of PQC algorithms and BCNs for network service orchestration and service federation between multiple administrative domains. © 2013 IEEE.