NP 验证式的答题风格
神来之笔一般的答案背后是草稿纸上的一通狂算，考试要看的是神来之笔，但其实一通狂算里的思路更有价值。关键词：十一学校、抄答案、“注意到”、“草稿”。
Blog entries with tag ‘Computer Science’
- 计算机科学
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.
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…
The two asymptotically equivalent definitions of IND-CPA
There are two asymptotically equivalent definitions of IND-CPA for secret-key encryption schemes. I think the one-challenge one makes the proof neater.
[KW19] 标准假设下适用于 NC¹ 策略的紧凑、适应性安全的属性加密
Kowalczyk 和 Wee 在 EUROCRYPT 2019（欧密会）上发表的文章 Compact Adaptively Secure ABE for NC¹ from 𝑘-Lin 可以说是彻底解决了 NC¹ 访问策略的属性加密问题。我在最近的密码学读书会上将讲述该文，这篇博文算是我用母语对该文章的总结（感觉我脑内思考语言仍然是汉语），也算是在中文密码学社区里传播知识。
![[KW19] 标准假设下适用于 NC¹ 策略的紧凑、适应性安全的属性加密](/entries/kw19-abe-nc1/assets/hero.png)
Universal circuit for aNC¹ in aNC¹
This just struck me. Of course, it has been carefully studied by computer scientists.
Brain teaser: locks, keys and gifts
A brain teaser that remains open in Yao class WeChat group, up to the time of writing of this entry. See if it interests you and if you can solve it.
微博校园发的一个阴（博）谋（弈）论题目
微博校园发了一个转得都“变质”的考试附加题照片——还有可能是 PS 的！那些字真的跟纹身刚刚纹上去的时候一样，底下还泛红。我把这个题做了一做，又苦于最近没什么新的博文主题，就暂且写一篇这个罢了。
The Code Book (Simon Singh) 读书笔记
操作系统课中讲安全的一节是代课老师上的，期间他推荐了 The Code Book (Simon Singh) 这本书，说是讲密码学历史的。我对密码学感兴趣，就读了一读，并照“不动笔墨不读书”的原则，记了读书笔记，发表出来以飨观众。
如何在操统课 Bitcoin 大作业组间比赛歇菜
交叉信息研究院的本科生操作系统课程的大作业很奇特，并不是 4 个 NachOS 作业，而是两次 NachOS、两次分布式数据库。最后一次大作业是要写一个 Bitcoin 挖矿程序，而且还有组间比赛，各个小组的矿机和客户端会一起运行一段时间，最终获得最高手续费的矿机会获胜。
A toy interpreter for recreational λ-calculus
Continuing the last entry. I wrote a reducer of lambda terms (normal order, call-by-need).
A toy parser for recreational λ-calculus
I have heard about λ-calculus as a computational model for long, but never got a chance to have an even recreational look at it. Today’s entry simply records the creating of the parser.
Chit-chat on Lagrange’s four-square theorem
Lagrange’s four-square theorem is a beautiful result in number theory. However, to the best of my knowledge, I haven’t encountered it often in theoretical computer science. Today’s entry discusses two interesting stories related to this theorem.
Is the pattern you found persuasive?
Starting from the classic puzzles of finding patterns in a sequence, this entry explores the framework to define persuasive patterns. The framework is found to be quite self-contained in the sense that it is ‘asymptotically invariant’ to the choice of ‘language of expression’. The only short-coming of this framework is that it works only for computable sequences, yet the process of pattern discovery is uncomputable.
Discount aux Galeries Lafayette and NP-completeness
I allowed myself some CHANEL products to ‘reward’ myself for the acceptance of my first cryptography paper. I also consider spending money at its best value an interesting game. A commonly-seen discount aux Galeries Lafayette Xidan (Beijing) leads to an obviously NP-complete problem. Haha!
How to implement Frequented Visitees of Sina Weibo
An algorithmic imagination of how Sina Weibo could implement Frequented Visitees, a feature that gives users the serveral accounts which they visit the most often.
我的第一篇（密码学）学术论文
在 Aarhus 的密码学研究从春天到秋天一直断断续续在进行。今日传来喜讯：我们的文章已被 PKC 2018 接收。
浴中奇思：计算熵
其实也不是洗澡的时候想的，是睡不着的时候想的。想完了，查一查文献，姚先生已经做了。
Of Kerckhoffs’ principle
Let me explain the classic idea that ‘the algorithm of a crypto system should be considered and made public’ to you. Particularly, I will discuss what it means by ‘crypto system’, which tells us what information should be no secret at all.
Using a ‘regular’ expression to test primality is a bad idea
A classic trick of backward references but painfully slow. And some comments on benchmarking JavaScript code.
Interviewed by THU IIIS
I was participating Advanced Assessment for Admission (AAA) of Tsinghua Union, passed the first phase and was interviewed by Insititute for Interdisciplinary Information Sciences of Tsinghua University. Here is a transcript of the interview.
去 THU IIIS 面试
我参加了“华约”（清华大学联盟）的自主招生（AAA，或“高水平大学自主选拔学业能力测试”）。我通过了初试并被清华大学交叉信息研究院面试。这是一份面试的转录。