Abstract: The COVID19 pandemic had enormous economic and societal consequences. Contact tracing is an effective way to reduce infection rates by detecting potential virus carriers early.However, this was not generally adopted in the recent pandemic, and privacy concerns are cited as the most important reason.We substantially improve the privacy guarantees of the current state of the art in decentralized contact tracing. Whereas previous work was based on statistical inference only, we augment the inference with a learned neural network and ensure that this neural augmentation satisfies differential privacy. In a simulator for COVID19, even at $\varepsilon=1$ per message, this can significantly improve the detection of potentially infected individuals and, as a result of targeted testing, reduce infection rates.This work marks an important first step in integrating deep learning into contact tracing while maintaining essential privacy guarantees.