简介
最早由Uriel Feige、Amos Fiat、Adi Shamir提出，一种利用用户身份完成认证和签名的方案
该方案的目的是构造一个认证和签名方案，使任何用户能够在没有共享或公开密钥的情况下向任何其他用户证明其身份和消息的真实性
方案基于整数分解的困难性，如果选择一个足够大的整数作为模数，则可以证明该方案对任何已知攻击或选择消息攻击都是安全的
该方案实现简单，计算速度快（与RSA相比，需要的模乘的次数仅为RSA的1%~4%），且具有足够的安全性，因此非常适用于各种基于微处理器的设备，如智能卡，个人计算机和远程控制系统
一、概述
基于新兴的智能卡技术创建不可原谅的身份证是众多商业和军事应用中的一个重要问题。当双方(证明者A和验证者B)是对手时，我们希望让B在见证和验证任意许多由A产生的身份证明之后。典型的应用程序包括护照（通常由敌对政府检查和复印）、信用卡（其号码可以复制到空白卡或通过电话使用）、计算机密码（易被黑客和电报员攻击）和军事指挥控制系统（其终端可能落入敌人手中）。我们区分了三个级别的保护
- 认证方案：A可以向B证明他是A，但其他人不能向B证明他是A
- 识别方案：A可以向B证明他是A，但B不能向别人证明他是A
- 签名方案：A可以向B证明他是A，但B甚至不能向自己证明他是A
当A和B合作时，身份验证方案只对外部威胁有用。识别和签名方案之间的区别是微妙的，主要表现在证明是交互的和验证者后来想证明其存在法官：识别方案B可以创建一个可信的记录一个虚构的通信通过仔细选择问题和答案的对话框，而在签名方案只有真正的沟通可以产生一个可信的记录。然而，在许多商业和军事应用中，主要的问题是实时检测伪造品，并拒绝伪造者想要的服务、访问或响应。在这些情况下，文字记录和法官是无关的，这两种类型的方案可以互换使用
二、交互式认证
背景
新的识别方案是零知识交互证明(Goldwasser、Micali和Rackoff[1985])和基于身份的方案(Shamir[1984])的组合。它是基于在n的分解未知情况下提取模平方根的困难。Micali和Rackoff在Eurocrypt84提出了一个证明数字二次剩余的相关协议（它没有出现在程序中），但新协议更快，需要的通信更少。本文的主要贡献是展示了这些协议与实际识别和签名问题的相关性
该计划假设存在一个可信的中心（政府、信用卡公司、计算机中心、军事总部等）。在正确检查了用户的身体身份后，就会向用户发送智能卡。不需要与中心进行进一步的交互来产生或验证身份证明。无限数量的用户可以在不降低系统性能的情况下加入该系统，甚至不必保留所有有效用户的列表。与智能卡的互动将不会使验证者复制它们，即使完全了解该中心发行的所有智能卡的秘密内容，也不会使对手创建新的身份或修改现有的身份。由于在交互过程中没有泄露任何信息，因此无论使用频率如何，这些卡片都可以使用一生
方案
在中心开始发卡之前，它选择并公开一个模数$n$和一个伪随机函数$f$，它将任意字符串映射到范围$[0,n)$。模量$n$是两个秘密素数$p$和$q$的乘积，但与RSA格式不同的是，只有中心知道模量的因式分解，因此每个人都可以使用相同的$n$。函数$f$在多项式有界条件下与真随机函数无法区分。Goldwasser和Micali描述了一种特殊的函数族，它在这个意义上被证明是强大的，但我们相信，在实践中，人们可以在不危及方案安全的情况下使用更简单、更快的函数(例如多个DES)
当一个符合条件的用户申请智能卡时，该中心会准备一个字符串$I$，其中包含有关该用户的所有相关信息（他的姓名、地址、身份证号码、物理描述、安全许可等）。以及关于信用卡（有效期、有效期限制等）。由于这是由方案验证的信息，所以详细说明和反复检查其正确性是很重要的。然后，该中心将执行以下步骤：
- 计算$v_j=f(I,j)$
- 通过步骤1的方式，计算$k$个不同的$v_j$，使得每个$v_j$都是$mod\ n$的二次剩余，并对每个$v_j$而言，求其在mod n下的逆$v_j^{-1}$的平方根$s_j$，也即计算$\sqrt{v_j^{-1}} \equiv s_j \ mod \ n$
- 将相关信息$I$和这$k$个值$\{s_1,...s_k\}$写入到智能卡中
该方案需要注意以下几点
- 出于安全性考虑，建议在个人信息$I$后加上一串随机串$R$，这个串$R$由中心生成，随着消息$I$一起保存在卡内
- $k$的取值通常在1-18之间，越大的k值意味着越少的通信复杂度（通信量）
- 模数$n$至少是512 bit（1986年的论文），现在来说至少是1024 bit（至少是难分解的程度）
对于验证设备，具体的零知识证明协议如下
- P将$I$（或$(I||R)$）发送给V
- V根据收到的$I$，计算$v_j=f(I,j),j=1,2,...,k$
重复执行步骤1-4，共$t$次，对于第$i$次执行，有
- P选择一个随机的$r_i\in [0,n)$，计算$x_i\equiv r_i^2 \ mod \ n$，并将$x_i$发送给V
- V生成一个随机的二元向量$E_i=(e_{i1},e_{i2},...,e_{ik})$，将$E_i$发送给P
- P根据收到的$E_i$，计算$y_i$，并将$y_i$发送给V
$$ y_i=r_i\prod_{e_{ij}=1} s_j \ mod \ n $$
- V收到$y_i$后，计算$x_i$，并与步骤1中收到的$x_i$比较，检查两者是否一致，若一致，则本次执行通过
$$ x_i=y_i^2\prod_{e_{ij}=1}v_j \ mod \ n $$
说明：
- 对于V，当且仅当t次执行均通过时，接受P
- 为了减少P和V之间的通信量，P可以采取将步骤1中的$x_i$进行hash的方式发送给V（比如发送$hash(x_i)$的前128 bit），V在第四步计算完毕后，将得到的结果进行hash计算并截取前128 bit进行比较
安全性
完备性
如果P和V均为诚实的参与方，则有
$$ y_i^2\prod_{e_{ij}=1}v_j \equiv (r_i\prod_{e_{ij}=1}s_j)^2\prod_{e_{ij}=1}v_j\equiv r_i^2\prod_{e_{ij}=1}s^2_jv_j \equiv r_i^2\prod_{e_{ij}=1}v_j^{-1}v_j \equiv r_i^2 \equiv x_i \ mod \ n $$
可靠性
如果P没有$s_j$，则其无法在多项式时间内计算模$n$条件下$v_j$或$v_j^{-1}$的平方根，则此时V接受P的概率上界为$2^{-kt}$
因为P没有$s_j$，因此对于二元向量$E_i=(e_{i1},e_{i2},...,e_{ik})$，其只能通过猜测的方式，对于第$i$轮执行，P正确猜对一个E的概率为$2^{-k}$，对于整个协议而言，连续t次执行后，P每次都猜对$E_i$的概率为$2^{-kt}$
零知识性
对于任意的$t$和合适的$k$而言，协议是零知识的
由于r_i是随机选择的，因此x_i是模n的一个随机的二次剩余，因此x_i实际上并没有泄露关于s_j的信息，而y_i是由一个独立的随机变量构成的，因此也掩盖了s_j的值，从而P发送给V的消息看起来就像是一致均匀分布的随机数，V无论如何选择E_i都无法改变这一事实
复杂度
协议每次执行需要完成$\frac{t(k+2)}{2}$次模乘，$k=5$时，需要的通信量为643 Bytes（$5*(512*2+5 ) bit$），需要320 Bytes的卡存储空间（保存五个$s_j$），时间、空间、通信量三者可以通过调节$k$和$t$的取值来权衡
三、签名方案
方案
对于待签名的消息m，有如下签名方案
- P选择t个随机的值$r_1,...,r_t\in [0,n)$，满足$x_i\equiv r_i^2 \ mod \ n\ (i=1,2,...,t)$
- P计算$f(m,x_1,x_2,...,x_t)$，截取前$kt \ bit$作为二元向量$E$的值$(v\leq i\leq t,1\leq j\leq k )$
- 对于$i=1,2,...,t$，P计算
$$ y_i=r_i\prod_{e_{ij}=1} s_j \ mod \ n $$
令数组$Y=[y_1,y_2,...,y_t]$
计算完毕后P向V发送个人信息$I$，签名消息$m$，签名值$(E||Y)$
验证
- V根据收到的I，计算$v_j=f(I,j),j=1,2,...,k$
- V根据$v_j$和收到的$Y=[y_1,y_2,...,y_t]$，对$i=1,2,...,t$，计算
$$ z_i=y_i^2\prod_{e_{ij}=1}v_j \ mod \ n $$
- V计算$f(m,z_1,z_2,...,z_t)$并截取前$kt \ bit$，与收到的$E_i$比较是否一致，若一致则接受消息$m$
和之前的一样，容易验证签名的可行性
安全性
需要假设模数n足够大且函数f足够安全，如$n\geq 512 \ bit$以及利用强密钥多次迭代使用DES（1986），现在应该是$n\geq1024$和$f\geq SHA256$
基于安全性考虑，需要$kt\geq 72$
复杂度
需要的模乘次数仍然为$\frac{t(k+2)}{2}$次， 通信量同样取决于$t$