Service replication-based fault tolerant strategies use several web services as replicas to perform the same task and, therefore, become an effective approach to improve the reliability of service-oriented applications. A basic assumption of these strategies is that replicas are independent. However, it does not always hold in the web services environment since replicas could be composite services which may share some common component services. How to judge independence of replicas is therefore a critical issue for replication-based strategies. What makes the problem more complicated is that replicas may not be willing to disclose their inner implementation details. To address the above problem, we first analyse the relation between the performance of replication-based strategies and the independence of replicas. Based on the analysis, we propose an approach to determining the independence of replicas. We model the problem as a special Set-Intersection problem and devise a component, TTP (Trusted Third Party), which adopts homomorphism cryptosystem to solve it. Through the proposed approach, we can build reliable web services by using independent replicas without violating their autonomy and privacy.