Gee Law’s Blog
WeChat has this function to distribute red envelopes of random amount of money. The natural question to ask is how to sample the amount of money each person who opens the envelope should receive.
Two (equivalent) definitions of computational indistinguishability, two (isomorphic) ways of doing hybrids
It wasn’t until recently did I realise there are two isomorphic ways (different styles) of writing hybrid proofs. They actually correspond to the two equivalent definitions of computational indistinguishability — one based on guessing and the other based on distinguishing. Actually, I’ve been writing both kinds of proofs subconciously.
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…
There are two asymptotically equivalent definitions of IND-CPA for secret-key encryption schemes. I think the one-challenge one makes the proof neater.