Many popular web sites use folksonomies to let people label objects like images (Flickr), music (Last.fm), or URLs (Delicous) with schema-free tags. Folksonomies may reveal personal information. For example, tags can contain sensitive information, the set of tagged objects might disclose interests, etc. While many users call for sophisticated privacy mechanisms, current folksonomy systems provide coarse mechanisms at most, and the system provider has access to all information. This paper proposes a privacy-aware folksonomy system. Our approach consists of a partitioning scheme that distributes the folksonomy data among four providers and makes use of encryption. A key sharing mechanism allows a user to control which party is able to access which data item she has generated. We prove that our approach generates folksonomy databases that are indistinguishable from databases consisting of random tuples.