We introduce a new type of cryptographic primitives which enforce high communication or storage complexity. Intuitively, to evaluate these primitives on a random input one has to engage in a protocol of high communication complexity, or one has to use a lot of storage. Therefore, the ability to compute these primitives constitutes certain “proof of work,” because the computing party is forced to contribute a lot of its communication or storage resources to this task. Such primitives can be used in applications which deal with non-malicious but selfishly resource-maximizing parties. For example, they can be useful in constructing peer-to-peer systems which are robust against so called “free riders.” In this paper we define two such primitives, a communication enforcing signature and a storage-enforcing commitment scheme, and we give constructions for both.