A classical notion is preimage resistance of hash functions. Given an image, find a preimage. But what about finding multiple preimages? In other words, given a hash function digest $h$, find $x\geq1$ preimages. Can we derive a lower bound on the complexity? This is related to the oft-used property of multi-collision resistance.
If you are interested in this topic, please send an email to Bart Mennink via bart.mennink@ru.nl .