The recently introduced legislation on data retention to aid prosecuting cyber-related crime in Europe also affects the achievable security of systems for anonymous communication on the Internet. We have analysed the newly arising risks associated with the process of accessing and storage of the retained data and propose a secure logging system, which utilizes cryptographic smart cards, trusted timestamping servers and distributed storage. A practical implementation of the proposed scheme was performed for the AN.ON anonymity service, but the scheme can be used for other services affected by data retention legislation. We also discuss the practical experience from process of response to legal authorities’ requests both before and after the data retention directive was implemented. Moreover we give a general description of the legal obligations and the information about usefulness of the retained data is also provided. Derived from these obligations we give arguments reflecting challenges and obstacles for a secure and privacy respecting implementation of data retention.