  Unstructured textual data is at the heart of healthcare systems. For obvious
privacy reasons, these documents are not accessible to researchers as long as
they contain personally identifiable information. One way to share this data
while respecting the legislative framework (notably GDPR or HIPAA) is, within
the medical structures, to de-identify it, i.e. to detect the personal
information of a person through a Named Entity Recognition (NER) system and
then replacing it to make it very difficult to associate the document with the
person. The challenge is having reliable NER and substitution tools without
compromising confidentiality and consistency in the document. Most of the
conducted research focuses on English medical documents with coarse
substitutions by not benefiting from advances in privacy. This paper shows how
an efficient and differentially private de-identification approach can be
achieved by strengthening the less robust de-identification method and by
adapting state-of-the-art differentially private mechanisms for substitution
purposes. The result is an approach for de-identifying clinical documents in
French language, but also generalizable to other languages and whose robustness
is mathematically proven.
