我的第一篇（密码学）学术论文

本文是日记文体，内容按月按最近到最早排列，但索引按最早到最近排列。

12 月 14 日

忙申请（研究生项目）忙到昏天黑地，突然 Outlook 收到了推送，又是一封要被删除的邮件吗？瞥了一眼，标题是“Your submission was accepted to PKC 2018”。

哇！哇！哇哇哇！开心！

我赶紧打开了邮件，里面还有三个 reviewers 的评语。每个 reviewer 都先总结了一下 work 的内容，然后提出优点和不足，最后给出结论。他们分别给出了 accept、weak accept（书写方面需要改进）和 accept。有意思的是第三个 reviewer 认为我们的 protocol 里面有一个缺陷，但仍然给了 accept——不过，他的担心大概是因为读得比较仓促导致的，实际上他提出的问题并不存在。PKC 允许我们提供 feedback 给 reviewers，有一封邮件里说“在邮件的末尾有一个链接，可以用来提供反馈”，但是那个邮件末尾没有链接；从 刘天任 和我的一段对话来看，似乎这是 PKC 第一年允许给予反馈，估计是没搞好……

这段历程算是有了一个圆满的句号，很圆满。

9 月和 10 月

9 月 19 日，我和 Ivan 发邮件谈了一下正在进行的项目，并提醒他 PKC 2018 的截止日（10 月 7 日）快到了。Ivan 表示我们下周就 pick up 这个项目。彼时我已经加入 Microsoft Research Asia，所以放在这里的精力比较有限。

国庆假期期间，我迅速搞定了我要写的部分，国庆假期结束前我们投了出去。投了之后我看了一下 applications 的部分，发现 Peter Scholl 提出的 black-box construction of $k$-out-of-$n$ OT from 1-out-of-2 ones 居然用了这个 protocol 中我贡献的部分（Hamming weight bound $d>1$ 的情况），太开心了——我做出的理论贡献找到了应用价值。

10 月 22 日，文章放在了 Cryptology ePrint Archive 上，它是 Report 2017/1041。

8 月

3 日，Ivan 发邮件说 Peter Scholl 加入了这个项目，他想出了这个 protocol 的两个新的应用——一个是 OT，另一个是 TinyTable。

6 月

6 日，我们五月份课程就结束了，我的考试在六月底（除了串算法，在五月底），所以六月其实很颓。颓了很久的我决定发力一把，于是 made a commit，不过我在考虑的途中发现，之前的 protocol 我们都需要对数字（$f_j$ 和最初版本的 $j$）做范围的证明（比如在 $n$ 的某个多项式范围内），但是如果要求证明方先 commit to $f_j$，那似乎就不需要范围的证明了（算一下就知道，因为此时多项式已经固定了，如果不能“零化”所有 offending indices，只会导致最后验证的步骤更容易失败）。于是我停笔了，给 Ivan 和他的研究生发了邮件讨论。

7 日，我看了 Ivan 回的邮件，他也认同这样就不用证明范围了。这天我正好也开始整理这系列的日记，写到一半突然想到如果要求先放出 $f_j$ 的 commitments，那么一个不诚实的验证方可能会利用这个信息去生成随机化变量的随机数，这可能会对零知识的性质造成影响。总之这个问题还有待观察。

12 日，Ivan 发邮件给我解释了证明思路，把原来 protocol 的最后一步从“打开 $v$”改成“用一个常见的方式证明 $v=0$”就能完成了。

14 日，Ivan 发邮件提出了一个提高随机化效率的方法（不用 PRG）：随机选择一个 $\alpha$，然后 $x_i$ 乘 $\alpha^i$；这样整个式子就是 $\sum_{i=1}^{n}{f\left(i\right)\alpha^i x_i},$ 换一个观点看这个式子——它是对一个多项式^★求 $\alpha$ 处的值，如果有大于 $d$ 个元素非零，则这个多项式非零，且最多 $n$ 次，因此一个随机的 $\alpha$ 恰好是这个多项式的根的概率不超过 $n/{\left|\mathbb{F}\right|}$，只要域足够大即可。另外 Ivan 还提出了一个去掉对域的特征假设的方法——在之前的版本中，我们需要域特征大于^★★ $n$，要去掉这个限制，只要事先约定好一个 deterministic 互异域元素生成算法，然后把 $f\left(i\right)$ 替换为 $f\left(a_i\right)$ 即可（其中 $a_i$ 是生成的域元素），这个做法非常聪明，这利用到了我们最近发现的“先 commit to 多项式的系数就不需要范围证明了”。

^★ 注意不是 $f\left(x\right)$ 这个多项式，这个看法很漂亮，是协议中第二次利用“域上多项式的根的数目不超过其次数”。

^★★ 特征是 0 的域不是有限域，所以不在考察范围内。

这段 protocol 的发展太让我激动了！这生动地展现了一个实际的密码学协议是怎么一步步构建起来的——先有一个最特殊的情况，然后扩展到更一般的情况，在探索的过程中简化、改进，最终让这个 protocol 非常一般化。

20 日，我和 Ivan、Mark、Sabine 见面会议，Ivan 让我写 zero-knowledge 部分的证明。回家我重新阅读了一下现在的文章，以及 Ivan 邮件里面提到的方法，我仔细看才想起来这是上个学期我学过的 hybrid argument——密码学的基础技巧，不能忘。我在书写的时候完善了细节，比如 Ivan 邮件里面的思路是考虑三个分布（只有一个中间 hybrid），但是我发现实际操作起来用四个分布更方便（两个中间 hybrid）。

26 日，说些和论文本身关系不大的。今天进行了密码学课程的口头考试，我是在考试之前两天狂复习的（对身体不好啊，别学我！），可以说在考试的 36 小时之前有一半的考试可能内容（随机抽取一个主题进行口头考试）我是全然不知道的……到最后也没有特别准备好，抽到了一个我还很迷糊、没准备 notes 的话题，于是磕磕绊绊总之是过了（成绩是 10/12）。这里要提到我复习的时候发现的事情：之前我和 Ivan 说我们弄出来的 protocol 是 HVZK，Ivan 说没关系，虽然可能在实践使用中确实没关系，但是我总觉得理论上会欠缺一些完整性；结果我在复习 Σ-protocol 的时候看到讲义上有一个 explicit 通过 Σ-protocol 变出一个效率相当的 ZK protocol 的方法——看来是我上课没好好听也没认真读笔记，这个思路也很巧妙，任意的 Σ-protocol 都可以先通过和自己 OR construction 得到一个 witness hiding 的 Σ-protocol，然后配合身份识别协议的思路（设法让 P 证明自己知道 A 或 B，但是 A 是 P 不可能知道的，于是我们就得到了 P 知道 B 的结论），先交换 P、V 的位置，让 V 制造一个辅助知识证明，证明完成后让 P 做一个辅助知识和目标知识的 OR，即可完成整个协议，而 transcript simulator 可以通过 rewind V 的方法获取 V 的辅助知识，从而不用 P 的知识也可以模拟出一个证明。具体业务参考 Ivan Damgård 的 Σ-protocol 讲义。

5 月

4 日，Ivan 发邮件给我和他的研究生，准备完成论文啦！我们的论文是用 SVN 进行版本控制的。Ivan 表示他先把我们的 setting 搞定（我们的 assumption、用语体系啦），然后我们再把内容填进去。不过他太忙了，我中间还小催了一下😀。

31 日，Ivan 填好了论文框架。

4 月

21 日（周五），我颓了很久之后终于打算验证一下我一个月前的想法，写了一写之后发邮件给 Ivan，我们约定下一个周五面谈。

28 日，我和 Ivan 讲了我的 idea，但是感觉自己语言方面有些表达不太明确，以致于 Ivan 之后发邮件跟我说用 Vandermonde 矩阵（似乎“多项式”的想法没有成功地 convey 给他）算出来的数似乎不符合 protocol 中对于范围的要求云云。不过后来我比较详细地再讲了一次大家就明白了。这个 protocol 的思路是之前 $d=1$ 情况的自然扩展：

注意 用语有所变更，现在我们直接用 $g=0$ 表达之前 $g\in H$ 的含义，实际上真正的语言框架是建立在 homomorphic commitment 上的。

设已经随机化的待考察元素是 $y_1,...,y_n$，如果里面至多 $d$ 个不是 $0$，那么存在 $d$ 次首一多项式 $f\left(x\right)$ 使得 $\sum_{i=1}^{n}{f\left(i\right)y_i}=0,$ 且这和如何随机化无关——只要让 $f\left(x\right)$ 的零点是那些 offending indices 即可。

由 Viète 定理，$f\left(x\right)$ 的系数是这些下标的初等对称多项式，如果 $d$ 是常数，则它们都在 $n$ 的多项式范围内。设 $f\left(x\right)=x^d+\sum_{j=d-1}^{0}{f_j x^j},$ 利用恒等式 $\sum_{i=1}^{n}{f\left(i\right)y_i}=\sum_{i=1}^{n}{i^d y_i}+\sum_{j=d-1}^{0}{f_j\sum_{i=1}^{n}{i^j y_i}},$ 大多数计算都可以 locally 完成，只要让证明方“秘密地供出”$f_j$ 即可。

3 月

6 日，我和许悦从巴黎回奥胡斯的路上遇到了延误，我邮件告诉 Ivan 我们会缺席一次密码学的课程，Ivan 回复表示没问题，并提了一句之前他发给我们的论文的事情。

彼时，我和许悦都还没怎么看呢！（他倒是看了 Kasper 给的论文的一些，我是完全没看。）于是我赶紧停止摸鱼，读了读论文。

21 日，我和 Ivan 约时间面谈；24 日，在 Ivan 办公室，我和他说关于这个论文的事情。我提出他一开始给的那篇论文并没有留什么问题，似乎是已经完结的研究。他说这个论文还需要一些数据，现在能做的 project 有两个方向，一个是写代码（工程性的活儿），写程序来验证最开始那篇论文的一个部分，另一个选项是做理论方面的问题。根据之前学长学姐的反馈，之前他们会收到一个 open problem, which has been open for years。我内心还是觉得理论比实际写程序要高一些的，而且我也想在理论研究方面积累一些经验，所以我想打听这个理论方面的问题看看。Ivan 在白板上讲了一下目前的一个正在进行的课题，大概是：

考虑交换群 $G$（加法记号）和一个正规子群 $H$，又假设 $G/H$ 是循环群且给定 $x\in G$ 判断 $x\in H$ 是困难的。现在有一系列 $x_1,...,x_n\in G$，给定自然数 $d\leq n$，希望寻求一个零知识证明（a zero-knowledge proof protocol of）这些 $x_i$ 中至多只有 $d$ 个不属于 $H$。

显然这个问题有一个平凡的解法：用 Σ-protocol 的 OR-construction。但这个方法的效率很低：它要求证明方、验证方之间的通信内容很多，或者说 transcript（转录、笔录？）很长。目前 Ivan 和他的两个 D.Phil. 学生正在思考更高效的 protocol，目前对 $d=1$ 的特殊情况已经有了很好的解法：

1. 验证方生成并公布随机数 $y_1,...,y_n$，双方计算 $z_i=y_i x_i$ 以及 $\delta=\sum_{i=1}^{n}{z_i},\quad\gamma=\sum_{i=1}^{n}{iz_i};$
2. 设 $j$ 是惟一允许 $x_j\notin H$ 的下标，则有 $\gamma\equiv j\delta\ \left(\bmod\ H\right)$，于是只要让证明方证明存在小的 $j$ 使得前述等式成立。

相反，如果有至少两个 $x_i,x_j\notin H$，那么计算 $\gamma\delta^{-1}$ 可以发现它很小的概率是可忽略函数（当然，假设 $G/H$ 足够大）。至于后面这个命题的零知识证明法，总之是可做的。此外，第一步的随机数可以用一个 secure PRG 代替，这样就可以缩短证明长度。

Ivan 表示目前还不知道 $d=2$ 之类的是否可做，这便是这个问题了。我几乎是马上有了 idea：对 $d$，我们试试 $d$ 次多项式？Ivan 说这可能是一个思路，让我慢慢想想。此外，这还是我第一次见用 secure PRG 来缩短证明长度的，太巧妙了！

我最后问 Ivan 这是不是之前给学长学姐的那个 open problem，他表示并不是，这个是今年的新问题。我松了一口气——毕竟前面那个问题多年未解，这个问题看起来还是挺有戏的。

27 日，Ivan 把目前的 draft 发给了我。

2017 年 2 月

不晚于 2 月 9 日，我和许悦到办公室拜访了 Kasper Green Larsen 和 Ivan Bjerre Damgård，表达我们对参与研究的兴趣。数日之后我们也受到了来自两位教授的邮件，内容是着手这些领域的阅读材料。Kasper 的领域是 hardness in P（P 类问题复杂度归约），Ivan 的是密码学。我之后着重于密码学，所以就不多提及 hardness 那部分的内容了。

14 日，Ivan 邮件里面提到了 Secure Arithmetic Computation with Constant Computational Overhead。