认证协议 (Identification Protocols)

认证协议中一般包含两方，即证明方 $\mathcal{P}$ （Prover）和验证方 $\mathcal{V}$ （Verifier）。验证通常是为了进行访问控制（Access Control），比如你输入自己的账号和密码以管理员的身份登录某个网站（Password-based），或者按下自己的指纹开启办公室的大门（Biometrics）。这些都是不同的认证方式，或者称之为认证协议。

一般我们在设计协议的时候，通常以 $\mathcal{P}$ 能够让 $\mathcal{V}$ 相信自己拥有某个密钥（Secret Key）作为例子。典型的有基于密码（password-based）的方式，对隐私要求高的有零知识认证（zero-knowledge）的方式。

Quote

Compared to message authentication, an important difference is that there is some notion of fressness to be fulfilled . On the other hand, compared to digital signatures, there is no such thing as non-repudiation: it is not required that the verifier is able to convince an outsider at a later point in time that a prover indeed successfully identified itself to the verifier.

与数字签名相比，最大的不同在于它不需要满足不可否认性（non-repudiation），与 MAC 相比，它不用事先进行密钥协商。

1. Intro

认证协议可以看做认证机制中的重要组成部分，在这个机制中，主要包含两个协议：注册（registration）和认证（identification）。现实生活中最简单的例子就是使用密码登录网站，也就是所谓的 password-based schemes。由于双方都会得到相同的 secret，所以这也是一种对称式的认证机制。

很显然，如果通信中明文传输密码是不可靠的，甚至连最简单的窃听攻击都防御不了。密码明文存储在服务端也是不建议的，实际中一般存储密码的哈希值，这样即使服务器的信息遭到泄漏，也不会泄漏密码的原文。当然简单的密码可以通过跑彩虹表的方式暴力破解，所以通常建议使用复杂的密码以及采用加盐哈希的方式。

哈希链更是将这种思想发挥到了极致。对于一个长度为 $\ell$ 的序列 $x_i$ ， $0\leq i \leq \ell$ ，满足 $x_{i+1}=H(x_i)$ ，其中 $H$ 是一个密码哈希函数 $H:\{0,1\}^*\rightarrow\{0,1\}^k$ 。

one-way hash chain

在基于哈希链的机制中，注册的过程就是 $\mathcal{P}$ 首先选取 $x_0\in_R\{0,1\}^k$ ，然后计算 $x_\ell=H^\ell(x_0)$ 并把 $x_\ell$ 发送给 $\mathcal{V}$ . $\mathcal{V}$ 将 $x_\ell$ 记作 $v$ 。

双方都需要同步一个计数器（counter） $i$ ，这样每次需要认证的时候， $\mathcal{P}$ 只需要发送 $x_{\ell-i}=H^{\ell-i}(x_0)$ 给 $\mathcal{V}$ ， $\mathcal{V}$ 再验证 $H(x_{\ell-i})\overset{?}{=}v$ 。通过的话，再将 $x_{\ell-i}$ 记作 $v$ 。

2. 零知识的认证协议

零知识的意思就是，无论 $\mathcal{V}$ 如何与 $\mathcal{P}$ 交互，它得到的信息仅凭自己也能得到。

2-1. Schnorr zero-knowledge protocol

$\mathcal{P}$ 需要证明自己知道 $x$ 且满足 $x=log_gh$ ，需要三步：

$\mathcal{P}$ -> $\mathcal{V}$ : $\mathcal{P}$ 选择 $u\in_R\mathbb{Z}_n$ ，计算 $a=g^u$ ，并将 $a$ 发送给 $\mathcal{V}$ ；
$\mathcal{P}$ <- $\mathcal{V}$ ： $\mathcal{V}$ 随机选择 $c=$ 0 或 1，并发送给 $\mathcal{P}$ ；
$\mathcal{P}$ -> $\mathcal{V}$ ：如果 $c=0$ ， $\mathcal{P}$ 直接将 $u$ 发送给 $\mathcal{V}$ ，否则发送 $u+x$ 。

最后，当 $c=0$ ， $\mathcal{V}$ 只需要判断 $g^r\overset{?}{=}a$ ；当 $c=1$ ， $\mathcal{V}$ 只需要判断 $g^r\overset{?}{=}ah$

Note

一般 $a$ 指代 announcement， $c$ 指代 challenge， $r$ 指代 responce。

Soundness ：如果 $\mathcal{P}$ 不知道 $x$ ，那么一定（很大概率）无法完成认证。要证明上面的协议是 soundness 的话，我们可以考虑反证法的思路。如果 $\mathcal{P}$ 能完成这个证明，那么就说明对于他已经发送的值 $a$ ，无论 $\mathcal{V}$ 发送的是 0 还是 1，他都能够做出正确的回复。即

$g^{r_0}=a, g^{r_1}=ah$

这样的话，其实就可以将 $x$ 计算出来，即 $x=r_1-r_1\ \mathsf{mod}\ n$

Zero knowledge ：零知识的证明在于构造一个 simulator，作为观察者，在认证过程中，我们观察到的是一组 $(a;c;r)$ ，因此我们需要做的是，不依赖 $x$ 的值，构造出满足条件的 $(a;c;r)$ 。

这也分为两种情况，第一种是诚实的验证者（honest verifier），另一种是不怀好意的验证者（cheating verifier），两种在构造 simulator 的时候有一些区别。

Honest 的情况：

构造一组 $(a;c;r)$ ，首先 $c$ 是从 $\{0,1\}$ 中随机选取， $r$ 是从 $\mathbb{Z}_n$ 中随机选取，那么 $a=g^rh^{-c}$ ，刚好满足条件。

因为我们知道 $c$ 和 $r$ 都是随机选择的，因此找到一组 $(A;C;R)$ 满足 $g^R=Ah^C$ 的概率 $\Pr[(a;c;r)=(A;C;R)]=\frac{1}{2n}$ 。

Cheating 的情况：

在 cheating 的情况下， $\mathcal{V}^*$ 可以在看到 challenge 的取值后倒带（rewind）并对以前的值进行修正。

2-2. Schnorr protocol

上面的协议对于 cheating prover 总是有 50% 的概率能验证成功。因此需要重复多次才能确保 cheating prover 成功的概率为 negligible。但这样也加大了计算次数，在现实中不太可行。

在这里只需要把 $c\in \{0,1\}$ 改为 $c\in \mathbb{Z}_n$ ，即可实现进行一次协议达到认证的目的。

Soundness ：类似的，这里证明的目标还是 “对于 cheating prover 接收到的 $c$ ，他最多只能成功回复一次 $r$ ”，换句话说，对于 $(a;c;r)$ 和 $(a;c';r')$ ，其中 $c\neq c'$ ，那么根据这一组值一定能够还原出 $x$ 。

Zero-knowledge ：如果是 honest verifier 的话，跟前面的证明差不多，可以简单认为两个分布的概率是一样的：

$\begin{equation*} \{(a;c;r):u,c\in_R\mathbb{Z}_n;a\leftarrow g^u;r\leftarrow_n u+cx\} \\ \{(a;c;r):c,r\in_r\mathbb{Z}_n;a\leftarrow g^rh^{-c}\} \end{equation*}$

但这样一来，同时带来了另外一个问题，如果是 cheating verifier 的情况，将没有办法进行 zero knowledge 的证明。

（为什么？）

Hint

Simulator 的计算时间是 $O(n)$ ，而 $n$ 是一个很大的数。

Note

At this point, we remark that if one could prove that Schnorr's protocol is zero-knowledge then it would follow that Schnorr signatures can be forged.

2-3. Witness hiding

也就是说，让 $c$ 在 $\{0,1\}$ 中任意取在现实中是不太可能的，因为需要 $k$ 此才能完全证明。因此很多时候我们又引入了一个新概念： witeness hiding.

Witness hiding 是比 zero knowledge 更弱的一种定义，它要求的是 cheating verifier 获取不到完整的 prover 的私钥。下面来看一个 witness hiding 的例子。

Okamoto's protocol ：

$\mathcal{P}$ 需要证明自己知道 $x_1,x_2$ 且满足 $h=g_1^{x_1}g_2^{x_2}$ ，（其中 $log_{g_1}g_2$ 是未知的），需要三步：

$\mathcal{P}$ -> $\mathcal{V}$ : $\mathcal{P}$ 选择 $u_1,u_2\in_R\mathbb{Z}_n$ ，计算 $a=g_1^{u_1}g_2^{u_2}$ ，并将 $a$ 发送给 $\mathcal{V}$ ；
$\mathcal{P}$ <- $\mathcal{V}$ ： $\mathcal{V}$ 随机选择 $c\in_R\mathcal{Z}_n$ ，并发送给 $\mathcal{P}$ ；
$\mathcal{P}$ -> $\mathcal{V}$ ： $\mathcal{P}$ 计算 $r_1\leftarrow u_1+cx_1$ ， $r_2\leftarrow u_2+cx_2$ ，并将 $r_1,r_2$ 发送给 $\mathcal{V}$ 。

$\mathcal{V}$ 只需要计算 $g_1^{r_1}g_2^{r_2}\overset{?}{=}ah^c$ 。

这个协议与 Schnorr's protocol 最大的不同在于我们能够证明它满足 witness hiding，即使在 cheating verifier 的条件下。

witness hiding ：

什么是 witness

witness 翻译过来就是证据，证明，在这里 $\mathcal{P}$ 的秘密值就是 witness。比如说 $\mathcal{P}$ 知道 $h=g^x \mbox{mod} n$ 中的 $x$ ，那么 $x$ 就称为 witness。在这个协议里，witness 指得就是 $(x_1,x_2)$

首先说一下证明的目的，我们需要证明 honest $\mathcal{P}$ 在与 cheating $\mathcal{V}^*$ 进行交互多次之后， $\mathcal{V}^*$ 不能生成一组 $(x_1',x_2')$ 满足 $h=g^{x_1'}g^{x_2'}$ 。

注： $(x_1',x_2')\neq (x_1,x_2)$

用反证法，如果能找出这一组 $(x_1',x_2')$ ，那么我们知道：

$g_2=g_1^{(x_1'-x_1)/(x_2'-x_2)}$

这也表明 $(x_1'-x_1)/(x_2'-x_2)$ 是 $g_2$ 的离散对数。因为求解离散对数问题是困难的，因此要找到 $(x_1',x_2')$ 也是困难的。

witness indistinguishable

witness 不可区分，直观上说就是给出一组不同的 $(x_1,x_2)$ 和 $(x_1',x_2')$ ，他们的 conversation $(a;c;r_1,r_2)$ 和 $(a';c;r_1',r_2')$ 可以是相等的。比如我们只需要令： $u_1'\leftarrow u_1 + c (x_1 - x_1')$ , $u_2'\leftarrow u_2 + c (x_2 - x_2')$ ，那么很容易推出 $a=a', (r_1,r_2)=(r_1',r_2')$ 。