Privacy on the Internet is becoming more and more important, as an increasing part of everyday life takes place over the Internet. Internet users lose the ability to control which information they give away about themselves or are even not aware that they do so. Privacy-enhancing technologies help control private information on the Internet, for example, by anonymizing Internet communication. Up to now, work on privacy-enhancing technologies has mainly focused on privacy of users requesting public services. This thesis introduces a new privacy risk that occurs when private persons run their own services. One example are instant messaging systems which allow users to exchange presence information and text messages in real time. These systems usually do not provide protection of presence information which is stored on central servers. As an alternative, decentralized instant messaging system designs mitigate this problem by having private persons provide instant messaging services to each other. However, providing a service as a private person causes new security problems as compared to providing a service as an organization or enterprise: First, the presence of such a service reveals information about the availability of the service provider. Second, the server location needs to be concealed in order to hide the whereabouts of a person. Third, the server needs to be specifically protected from unauthorized access attempts. This thesis proposes to use pseudonymous services as a building block for private services. Pseudonymous services conceal the location of a server that provides a specific service. The contribution made here is to analyze what parts of pseudonymous services, in particular Tor hidden services, are missing in order to apply them for private services. This analysis leads to three main problems for which solutions are proposed: First, known pseudonymous service designs do not scale to the expected number of private services which might be provided in the future. This thesis proposes a new approach to store hidden service descriptors in a distributed data structure rather than on central servers. A particular focus lies on the support of private entries which are required for private services. Second, pseudonymous services leak too much information about service identity during advertisement in the network and connection establishment by clients. The approach taken in this thesis is to reduce the information that a service publishes in the network to a minimum and prevent unauthorized clients from accessing a service already during connection establishment. These changes protect service activity and usage patterns from non-authorized entities. Third, pseudonymous services exhibit worse performance than direct service access. The contribution of this thesis is to measure performance, identify possible problems, and propose improvements.