Protection of digital property has become crucial in the widespread and rapidly growing use of digital media. Making the misuse of copyrighted works detectable, and thus deterring people from misuse, is the most promising measure currently known. To achieve this, most proposals apply watermarking techniques and focus on resolving the ownership in disputes which may arise after a misuse has been detected. Here a trusted third party (judge) compares the ownership claims of disputing parties. However, this does not necessarily imply determining the rightful owner, since she might not be participating in the dispute. Moreover, in contrast to disputes, one is in practice often confronted with only a single claim of ownership, e.g., in electronic market places where buyers intend to purchase digital items from someone claiming to be the rightful copyright holder. Proof of ownership is highly desirable in such situations because on the one hand, the buyers are ensured not to buy digital items from fake copyright holders and on the other hand, the copyright holders are protected against unauthorized reselling of their digital works.