This document describes P2PNS, a secure distributed name service for P2PSIP. P2PNS can be used to resolve SIP AoRs to Contact URIs without using DNS or central SIP servers. P2PNS provides several security mechanisms to efficiently prevent identity theft and to ensure the uniqueness of SIP AoRs in a completely decentralized and untrusted network without login servers. The proposed proxy architecture allows a seamless integration of legacy SIP UAs, avoids modifications to the complex SIP protocol stack and facilitates the deployment of P2PSIP networks. Because P2PNS provides a generic name service it is not limited to P2PSIP but can also be used e.g. to build a distributed DNS system.