On The Impossibilty Of Tight Cryptographic Reductions

Sven Sch├Ąge

We describe a new and very general meta-reduction technique for proving impossibility of tight security reductions. Our results (published at Eurocrypt 2016) affect many cryptographic systems where the number of users/calls to the underlying primitives is still unknown at deployment time. Our results suggest that for a theoretically-sound deployment of these systems, their parameter sizes need to be increased considerably.