A note on (non-)uniform reductions
I learnt how to write uniform hybrid reductions in my rudimentary cryptography course, which are beasty beauties that wrap an adversary, trying break each of the many underlying cryptographic assumptions simultaneously. However, those constructions are less easy to write and read than using the transitivity of computational indistinguishability up to polynomially many times. The latter involves writing out the (perhaps polynomially many) hybrids and arguing that adjacent hybrids are indistinguishable. I also learnt non-uniform reductions, noticeably the technique to only work with deterministic adversaries. I’m writing a proof using hybrid argument lately, and I asked my advisor about whether I should write the beast or just the hybrids…
