Service function chaining of network-functions across multiple domains enables next-generation services to be offered efficiently. Multi-domain orchestrator decouples the complexities of setting up such chains across domains on behalf of the users of the service. Privacy preservation is essential in this scenario since domains do not want to expose their topology, available resources, cost, and other operational aspects. Similarly, users try to minimize the exposure of their requirements to the domains and the orchestrator. Prior work relied on abstraction and/or aggregation of information in advertisements to preserve privacy. This paper presents a novel cryptographic mechanism based on bilinear mapping that allows the domains and users to privately advertise their information without revealing anything to the orchestrator and other domains. A private set intersection is used to compute the common elements between domains and users. Security proof for the proposed flows is provided using the universally composable framework. Usage of cryptographic techniques reduces the need for abstraction and provides strong privacy guarantees quantified in the privacy metrics of the paper. The simulation results demonstrate that the performance of the proposed system is at par with other existing work while providing strong cryptographic privacy, which none of the other systems provide. © 2022 IEEE.