Gee Law’s Blog
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.
Kowalczyk 和 Wee 在 EUROCRYPT 2019（欧密会）上发表的文章 Compact Adaptively Secure ABE for NC¹ from 𝑘-Lin 可以说是彻底解决了 NC¹ 访问策略的属性加密问题。我在最近的密码学读书会上将讲述该文，这篇博文算是我用母语对该文章的总结（感觉我脑内思考语言仍然是汉语），也算是在中文密码学社区里传播知识。
It is not the cmdlet that truncated the string. It’s the formatting. By the way, you can change the default if you want, and it’s all documented.