Health data that appears anonymous, such as DNA records, can be re-identified to named patients via location visit patterns, or trails. This is a realistic privacy concern which continues to exist because data holders do not collaborate prior to making disclosures. In this paper, we present STRANON, a novel computational protocol that enables data holders to work together to determine records that can be disclosed and satisfy a formal privacy protection model. STRANON incorporates a secure encrypted environment, so no data holder reveals information until the trails of disclosed records are provably unlinkable. We evaluate STRANON on real-world datasets with known susceptibilities and demonstrate data holders can release significant quantities of data with zero trail re-identifiability.