• 引言
• 实名投票
• 非对称加密函数组
• FOO 方案
• 函数组的数学实现

引言

密码学（主要是非对称加密），利用一些数学问题正问题和反问题（主要是求离散对数）解决难度的不对称性，通过巧妙的构造实现了一些基础功能和函数组，比如加密文件，数字签名，提交机制，零知识证明等。而进一步的在这些基础功能上，结合一些博弈论和工程学的想法，可以实现一些看起来不太可能的系统，加密货币就是一个典型的例子。

本文想要讨论的是投票问题。考虑一个投票的过程，现在投票模式最大的问题是什么？从投票进箱子或者按下按钮到统计出最终票数结果，我们实际上无法确定和跟踪，我们的选票是否被篡改或者直接忽略了。这一中心化的投票方案高度依赖于组织投票者的自觉和诚实。密码学对社会的一大贡献就是，很多时候通过巧妙的设计，我们可以尽可能的避免掉系统中不诚实行为的发生和奏效，这远比自觉监督法律等社会学手段可靠健壮的多。因此本文尝试一下投票问题的密码学设计。这篇博客主要参考了Cryptographic Voting — A Gentle Introduction。本文要求读者具有基本的非对称加密常识，至少对公钥私钥，加密文件和数字签名都有基本的了解。

实名投票

如果不要求投票人匿名的话，这个系统非常容易设计。只需要根据每个人的声明，由验证机构维护一份所有投票人的公钥列表。之后每个人直接网络或者任何公开的地方，公布自己的选票（比如内容是T/F，再加上时间戳），同时附上自己用私钥对该选票的数字签名即可。之后任何一个人都可以公开的验证其他任何人选票的合法性和统计投票结果。由于数字签名的存在，每个投票人只能投一票，没有资格的人也无法投出合格的票。由于所有的票被集中公开并附有签名，所有人都可以持续跟踪自己的选票，保证选票内容无法被篡改和忽略。而整个过程里，不需要中心化的机构作出任何黑箱行为，其唯一的作用是维护一份可信的投票人公钥列表。一旦投票组织者在这份列表上做手脚，由于列表本身也是公开的，投票人可以直接公开指出列表的异常。

在以上整个模型里没有胁迫者出现。但实际投票中，总会或多或少明里暗里受到胁迫者的影响，他们或是威逼或是利诱，来影响投票人的选择。因此能够保证所有人做出自己选择的方式，只能是不记名投票。当需要匿名投票时，整个系统设计起来就变得微妙了。作为投票人，你又想追踪自己投票的结果被正确的录入，又不想让任何其他人包括投票组织者知道你的选择，两者存在着明显的矛盾。密码学的魅力就是总会从一些看起来不可调和的问题中间找到一条令人拍案的解决路径，我们首先来熟悉一下非对称加密的几个基本组件。

非对称加密函数组

利用非对称加密，我们可以实现一些基本的功能，每个功能都需要一组函数来实现，我们现在来定义本文需要的几个基本功能的函数组。这些函数的定义是从功能出发的，背后可能有多种数学可以实现对应的函数功能，其中一种实现，我们留到本文最后给仍有兴趣的人稍作讲解。

• 数字签名

  需要的函数组 $\Sigma$ = (KeyGen, Sign, Verify)。

  定义为 $KeyGen() \rightarrow (sk,vk)$; $Sign(sk,m)\rightarrow \sigma$; $Verify(vk,m,\sigma)\rightarrow b$.

  KeyGen 是公钥私钥对的生成函数，这也是一切非对称加密的起点。其输出是公钥 vk （verify key）和私钥 sk（secret key）。签名函数负责对想要公布的信息 m 进行签名，其输出是另一个文件 $\sigma$。对文件的数字签名，就是会附加一份签名文件。验证函数的输入是原文件 m，签名文件$\sigma$，和公钥 vk。由于公钥是完全公开的，所以任何人都可以自行验证文件m的签名是否合法。其输出b（boolen），取1时则为验证成功，取0时则为验证失败。签名的好处一方面可以使得别人知道对应的文件 m 确实是自己发布的，另一方面也保证了 m 的内容完整性及不会被篡改。任何一个字节的后续改动，都会使得签名验证失败。

  数字签名实现的安全性要求，作弊者无法根据已有的若干信息签名对，来伪造出可以通过验证函数的信息签名对。

• 盲签名

  上述签名机制基本上是一个人的事情，一个人用自己的章给自己的文件签名。设想现在 Alice 希望自己发布的一段话被 Bob 签名，如果 Alice 并不介意这段话被 Bob 看到的话，上述的数字签名机制依旧完全适用，只需 m 用 Alice 的，而 sk，vk 用 Bob 的即可。但如果 Alice 不希望被 Bob 看到自己的内容还希望得到其签名的话，就需要用到盲签名函数组。这有点像，自己把选票密封在信封里，验证通过后认证官员会在信封上签名，而不知道你的选票内容。

  函数组 BS = (KeyGen, Blind, Sign, Unblind, Verify)。

  其中密钥对生成和签名验证函数定义与数字签名部分完全相同（只需注意此时 m 和 vk，sk 往往来源于不同的人）。另外两个函数定义为 $Blind(vk,m)\rightarrow (b,u)$; $Unblind(vk,s,u)\rightarrow \sigma$. 其中混淆函数会生成一个带签名的混淆信息 b，和另一部分用来去混淆自己留存的因子 u。而去混淆函数输入 s 是签名函数的输出，结合上签名者的公钥和前边留存的因子，可以去混淆还原为签名 $\sigma$，该签名将恰好是未混淆文件 m 的数字签名。

  这一实现的安全性要求，除了无人可以伪造 Bob 的签名，Bob无法识别被混淆过的内容之外，还包括了 Bob 无法通过验证后来被公开的 m 和转化过的签名 $\sigma$ 来确定来源是自己的哪次签名 s。

• 提交机制

  提交机制用来确保某内容已提前确定，但他人无法查看。这就有点像你讲写好的信息放在信封里，再打开信封之前，别人无法获取其内容，你也无法在改变其内容。

  函数组 CS = (Setup, Commit, Open)

  函数定义 $Setup()\rightarrow p$; $Commit(p,m)\rightarrow c$; $Open (p,m,c)\rightarrow b$.

  这里我们对提交机制的函数做了一定的简化。基本思路是首先选取一个类似密钥或“盐”的东西叫做 p，之后将想要公布的信息 m 和盐 p 一起输出需要提交的内容 c。最后当需要验证究竟提交的是和内容时，同时输入密钥，信息和提交即可，若b为1则说明提交内容确实为信息 m。

  实现的安全性要求，自然就是目的所讲的两个方面，提交者不能用其他信息 $m'$ 来通过 Open 函数的检验，其他人不能通过提交 c 来猜测原始的内容 m。

有了以上三组函数，就足够我们搭建一个匿名可靠的投票系统了。

FOO 方案

通过以盲签名为核心的非对称加密技术，实现的不记名可追溯投票体系就是所谓的 FOO protocol，这一提议可追溯到1992年，名称来源于三位提出者 Fujioka，Okamoto，和 Ohta。

这一投票系统又组织者，计票人，投票人三部分组成。基本思路是投票人将选票找组织者盲签名，组织者验证投票人身份和进行签名，投票人根据去混淆函数将签名转化为对原始的投票内容的签名。之后的事情就和记名投票部分相同。只不过现在公布的每张选票都是组织者的签名，当然你自己还是可以根据选票公开时被分配的序号，默默地追踪选举的统计情况。

更具体地，在这一方案中我们有

• 投票人 (Voter)
  • 拥有自己的公钥私钥（$vk_V,sk_V$）对，并且公钥在组织者处有权威记录，同时已知组织者的公钥 $vk_A$。
  • 写下投票内容 v，生成一个提交 $CS.Commit(p,v)\rightarrow c$。并将提交进行混淆$BS.Blind(vk_A,c)\rightarrow (b,u)$, 对混淆后的信息 b 用自己的私钥签名 $\Sigma.Sign(sk_V,b)\rightarrow \sigma_V$。
  • 将个人身份信息及带签名的混淆提交以及改内容的自己的签名$(ID, b,\sigma_V)$ 提交给组织者，若验证通过，组织者将返回其使用私钥 $sk_A$ 对b的签名 s。
  • 将 s 还原成相对原始提交的签名 $\sigma_A$: $BS.Unblind(vk_A,s,u)\rightarrow \sigma_A$。并将自己的提交 c 和事实上组织者对 c 的签名 $\sigma_A$, 一起匿名发送给计票人。此时计票人会返回给投票人一个随机唯一的标记 i。
  • 投票全部结束时，投票人将标记，生成提交的盐 p，以及投票内容 v，$(i,p,v)$ 一起匿名发送给计票人。
• 组织者 (Authority)
  • 组织者负责验证投票人的身份信息，同时维护所有合格投票人的公钥 $vk_V$ 的列表。此外还需维护一个初始为空的公开列表 L，用于记录已签过名的投票人（包括其提供的混淆提交b和私钥签名$\sigma_V$），防止投票人投出多票。
  • 当收到投票人的数组 $(ID,b,\sigma_v)$时，验证个人信息ID符合投票人之一，同时验证 $\Sigma.Verify(vk_V,b,\sigma_V)\rightarrow 1$, 确保是本人的投票提交。再之后查询 L 中是否已有同一人的投票纪录，若没有，进行盲签名 $BS.Sign(sk_A,b)\rightarrow s$ 并更新 L 列表已投票名单。最后将对混淆提交的签名 s 返回给投票人。
• 计票人 (Counter)
  • 每个人都可以是计票人，只一过程即可理解为匿名给计票人的过程，也可理解为直接匿名公开的过程。计票人掌握和收到的信息都是公开的，所有人都可获得，也因此所有人都可进行最后计票。
  • 每次投票阶段计票人收到 $(c,\sigma_A)$ 数组时，进行验证 $\Sigma.Verify(vk_A,c,\sigma_A)\rightarrow 1$，也即验证了投票的合法性。从而将选票（只显示为提交，尚不知道具体内容）纳入合法票池（票池记录了一张关于 $(i,c,\sigma_A)$ 的表格），并对每张选票产生一个唯一标记 i，返回给投票人留存。这一过程事实上建立了 i 和投票人的一一对应，i 是公开的，因此投票人可以一直追踪自己选票的被记录情况。但每个投票人只知道自己的投票和自己手中 i 的联系，选票对其他人完全匿名。
  • 到了投票阶段结束，开票时，计票人匿名接收 $(i,p,v)$ 信息，通过逐一选票验证 $CS.Open(p,v,c)\rightarrow 1$, 将第 i 张选票公开为内容 v 并最终进行计票。

我们对以上方案进行一些简单的分析，看看有没有什么漏洞。匿名性得到了很好的保证。开票前选票池中处于提交状态，无法知道投票的具体内容。开票后虽然所有选票内容公开，但由于只有组织者的签名，无法溯源到投票人。盲签的安全性要求，也保证了即使组织者也无法通过被去混淆的自己的签名，来确认对应了哪张之前的选票。不过投票人知道自己的提交的详细内容，再加上附加的标记 i，可以一直默默追踪自己投票的完整性和被记录。选票的计票由于全部是公开的，所有人都可以检验，使得计票人无法欺骗。而选票的合法性，除去组织者的部分，可以通过选票的提交和组织者签名验证。而如果组织者本身不诚实，对非法的选票进行签名，其公开的列表L将会暴露这种行为。

不过由于列表 L 被公开这一特征，虽然没有暴露投票人的投票内容，却暴露了投票人是否参与了投票，这在威胁者具有相应策略的情况下，可能还是没有完全发挥出匿名性来。另一方面，这一方案里，作为投票者需要反复互动，无法痛快的一次完成投票，显得有些啰嗦。但至少这一方案已经从原则上基本解决了不记名投票的防作弊设计问题。我们将来会看到更先进的密码学设计，使得投票人工作更轻松些。这可能会在该系列的另文论述。

函数组的数学实现

最后我们稍微看一下，非对称加密基本功能的数学实现。

提交机制最简单，hash 函数就好了。p 就是hash的随机盐，比如 $Commit(m,p)\rightarrow H(H(m)H(p))$。其中 H 是某种摘要函数，不管是 md5 或是 sha256，虽然 hash 本就不可逆，但不同强度的 hash 对应的逆向难度不同，有些可能有一定的提交被破解出真实内容的风险。这方面就不在这具体讨论了。原则就是用个 hash 函数就好了，这种和随机盐在一起 hash 对信息加密，但给原始信息又可进行验证的行为，和网站加密保存用户密码是一种哲学。事实上，很多网站也就是这样保存密码的。其中对密码 m 的第一个 hash 可能发生在浏览器前端，防止网络传输时被窃听，加密密码传到后端服务器后，存入 sql 之前还要和盐一起在 hash 一次。这一过程和提交机制里最简单的 Commit 函数实现一模一样。安全要求的满足上，很明显其他人无法从 hash 后的提交容易的推测出原始内容，另一方面提交者自己也无法改变提交的内容，否则 hash 值就会改变，从而 $Open$ 验证会失败。

至于签名部分的实现，我们这里引入 RSA 来实现。考虑两个大质数的乘积 $N=pq$, 与 N 互质的比 N 小的数共有 $\phi(N)=(p-1)(q-1)$. 我们忽略细节，并且为了便于理解，下文的等式中均省略对N的模。我们指定一个与$\phi(N)$互质的数e，并且找到唯一对应d，使得$ed=1 \;mod\; \phi(N)$，利用欧拉定理，从而有$(x^e)^d=(x^d)^e=x$ 成立（x小于N）。那么e和d对称，可以随意让任何一个作为私钥，另一个作为公钥（当然我们忽略了$mod\; N$，N应在私钥公钥中都出现）。

此时简单的数字签名算法就是显然的，只需对待签名信息m做一个 hash，$Sign(sk,m)\rightarrow H(m)^{sk}$。对于验证签名来说，使用公钥即可，$Verify(vk,\sigma)\rightarrow \sigma^{vk}=H(m)^{sk*vk}=H(m)$。这里不直接对原内容m签名而是对m的某种 hash 摘要签名，有两个好处。第一是本来非对称加密的长度就有限制$(x<N)$，无法对长文进行完整签名（也没有意义），使用 hash 函数之后每次都是对定长信息签名，更实用；第二是，如果不用 hash，攻击者可以先编出个签名 $\sigma'$ 出来，并计算 $\sigma'^{vk}=m'$，一旦 $m'$ 被碰撞出意义，攻击者便可声称 $(m',\sigma')$ 是信息签名对，而且可以通过验证，安全隐患较大。安全要求的满足上，RSA 算法久经考验，除了暴力大数分解之外，没人明确提出有什么快速的破解方案。

最后看如何通过 RSA 实现盲签名。盲签名由五个函数构成，其中三个和普通数字签名相同，背后的数学操作也完全一样（唯一区别是签名时不再需要 hash，因为混淆时已hash过）。我们重点只需看混淆和反混淆函数的 RSA 实现。混淆函数 $Blind(vk,m)\rightarrow b=H(m)r^{vk};u=r$, 其中 r 是个随机挑选的与N互质的整数。去混淆函数实现 $Unblind(vk,s,u)\rightarrow \frac{s}{u}$。对应的验证函数的数学为

$$Verify(vk,\sigma)\rightarrow\sigma^{vk} =(s/u)^{vk}=(b^{sk}/u)^{vk}=(H(m)^{vk*sk}r^{vk*sk-1})^{vk}=1$$

说明转换后的签名 $\sigma$ 是可以验证通过为原信息的签名的。由于 r 是随机数，签名方也很难通过还原后的签名确认是自己的哪次签名转来的。这一巧妙的设计成为了整个投票系统 FOO 方案的基础。

EOF