The Domain Name System (DNS) is an essential component of the critical infrastructure of the Internet. The role of DNS is vital, as it is involved in virtually every Internet transaction. It is sometimes remarked that DNS works well as it is now and any changes to it may disrupt its functionality and add complexity. However, due to its importance, an insecure DNS is unacceptable for current and future networks. The astonishing simplicity of mounting an attack against the DNS and the damaging potential of such an attack should convince practitioners and system administrators to employ a secure version of DNS. However, security comes with a cost. In this paper, we examine the performance of two proposals for secure DNS and we discuss the advantages and disadvantages of both. In particular, we analyze the impact that security measures have on the performance of DNS. While it is clear that adding security will lower DNS performance, our results show that the impact of security can be mitigated by deploying different security extensions at different levels in the DNS tree. We also describe the first implementation of the SK-DNSSEC  protocol. The code is freely downloadable and released under an open-source license.