One embodiment of the present method and apparatus for re-establishing anonymous data transfers between a first endpoint and a second endpoint in a network includes receiving, from a first node, the identity of a second node connected to the first node, where at least the first node is a neighbor node. A third node (a neighbor node) is then selected, and instructed to connect to the second node in order to establish a link for the path. In this manner, the first endpoint and the second endpoint remain unknown at least to each other (e.g., where “unknown” means that neither endpoint knows any identifying information, such as network address, about the other endpoint), and likely to all other nodes in the path as well. In another embodiment, a failure is detected at a neighbor node, where the neighbor node is part of an original path between the first endpoint and the second endpoint. The neighbor node's repair server is contacted for a repair node associated with the neighbor node, and a connection to the repair node is made such that the path is established in a manner that maintains anonymity of the first endpoint and the second endpoint relative to each other.