Schnorr签名再思考

Schnorr签名可以理解为：对一个实例化为基于离散对数问题的Schnorr身份识别方案的-协议，在Random Oracle模型下应用Fiat-Shamir转换得到。以上是事后反过来站在理论高度上的正统教科书式理解，不见得是Schnorr本人在发明其签名方案时的原始逻辑。下文试图还原原始逻辑，让读者也能自己重新发明Schnorr签名。

假设已知椭圆曲线离散对数问题（ECDLP）是困难的，签名者的私钥为，公钥自然可以想到设定为。

数字签名需要满足下述几条性质，这几条性质也应成为设计方案时心中谨记的原则：

1. 数字签名是对签名者私钥和签名消息的一个承诺（不一定是密码学承诺），将二者有效的绑定起来。
2. 数字签名不会泄漏关于私钥的任何信息（即底层身份识别方案/-协议满足可模拟/HVZK 性质）
3. 数字签名可以使用公开信息进行验证（公开可验证性）
4. 数字签名不可以被伪造（EUF-CMA 安全）
5. （可选）数字签名满足线性性

由于私钥和消息都被编码为有限域中的两个数，很自然地想到可以用有限域中的两个操作组合绑定这两个数：

二者皆满足性质1，但是由于有限域中的加/乘法都是可逆的，敌手在得到签名后只需减去或乘上就能得到，不满足性质2。

于是想到由签名者在有限域中均匀随机采样一个盲/混淆因子，将和,三者有机的混合在一起。只要得到的签名满足均匀分布，又由于非签名者不知道，则此签名满足性质2。

可能的组合方式如下表：

关于是否满足性质3（即公开可验证性）。记。公开的信息有。则要想满足性质3，一个明显的观察是两个私有信息绝不能用乘法组合在一起，否则无法用公开信息验证。

性质5线性性的定义如下

对于上述剩余三种方案是否满足性质2可模拟性（HVZK），需要考察各自的真实脚本分布与模拟脚本分布（按乘法语法来写）：

只剩下第二个满足真实分布和模拟分布不可区分。

，由于一般是很长的字符串，需要在应用哈希函数后压缩为有限域里的数，所以修改为。

此签名方案满足性质1/2/3/5，但是不满足性质4（不可伪造性），因为敌手在得到公开信息后，可以通过均匀随机选取，计算，然后将()输出为伪造的签名。

于是自然想到在签名生成时需要使得依赖，从而避免掉上述敌手的伪造攻击路径。一种建立依赖的方法就是修改为。如此一来随机选取后，找到满足方程的将会变得非常困难（没有比暴力尝试更好的算法）

通过以上初步的筛选、尝试与分析，我们得到了唯一的一个满足性质1/3，似乎满足性质2/4的签名方案。对于性质2/4，目前只是排除了几种明显的攻击路径，而想要确信满足相应性质，必须要在安全模型中使用安全归约得到的形式化的安全证明。

整个归约可以分为两个子归约：

DLOG is hard Schnorr Identification Scheme is secure against passive impersonation attack

这个归约里用到了两点，对于同样的

1. 能成功应答一个就能成功应答两个（Forking Lemma，也是所谓"square-root barrier"的来源）
2. 能成功应答两个就能算出离散对数 (Special Soundness)

Schnorr Identification Scheme is secure against passive impersonation attack Schnorr Signature is EUF-CMA secure

这个归约是在ROM下的，其实就是Fiat-Shamir转换的标准安全证明，如下图：