Is it correct to say that AssociatedPublicHandler and AssociatedPrivateHandler are identical, except that the private and public ids are swapped? 

If so, I think it would be cleaner to put all get/put/delete handling into your AssociatedURIsHandler superclass, with the public and private ids abstracted out, to say self.primary_id and self.secondary_id. Then the subclasses would override these to provide the actual key names where needed. I think the only place where you actually need the key names is when returning:

    self.finish({self.primary_id: private_id, self.secondary_id: public_ids})