Problem: Are the upper bounds for loss in security established in [7,10] optimal?
Result: We show that for certain cryptographic primitives whose security model involves the adversary constructing a dynamic graph -- like, e.g., constrained PRF and group key agreement -- this is indeed the case when restricted to 'oblivious' reductions. In particular, we use
pebbling lower bounds and oracle separations to show fine-grained lower bounds on loss in security for these primitives.