多方计算与ECDSA签名变体的安全分析

### 多方计算与ECDSA签名变体的安全分析 #### 1. 多方计算模拟中的问题 在多方计算的模拟过程中，存在一个关键问题。如果模拟器在首次看到包含先前已见索引集的记录时就停止，那么模拟器输出的记录分布会偏向于在早期回溯中更频繁出现的索引。这就导致模拟视图与对手的真实视图无法达到不可区分的效果。 在一个四轮零知识协议的模拟场景中，能更清晰地看到这个问题。该协议中，验证者在第一轮对挑战进行承诺，第三轮公开挑战，证明者在第四轮对挑战进行回应。模拟器代表诚实的证明者，需要应对验证者公开的所有实例索引。为了实现这一点，模拟器会对恶意验证者进行回溯操作。当验证者公开的每个索引都至少在一次早期回溯中出现过（即发生碰撞）时，模拟器才算成功。然而，当模拟器未能成功作弊时，它会至少学到一个在之前回溯中从未出现过的新索引。 如果模拟器一旦能够成功模拟就停止，那么模拟视图可能会因为上述原因与恶意验证者的真实世界视图产生可区分性。在不经意传输（OT）的场景中，恶意接收者打开索引的策略与上述验证者的策略存在对应关系。假设底层的OT'实例被标记为{1, ..., nB}，恶意接收者打开的n个索引k1, ..., kn，每个kj的值仅在{(j - 1) · B + 1, ..., j · B}范围内，这对应着验证者的一种策略，即对于每个ij，验证者仅在{j - 1 · (N/t) + 1, ..., j · N/t}范围内选择值。 下面用一个mermaid流程图来展示这个模拟过程： ```mermaid graph TD; A[开始模拟] --> B[进行回溯操作]; B --> C{是否发生碰撞}; C -- 是 --> D[模拟成功，停止]; C -- 否 --> E[学习新索引]; E --> B; ``` #### 2. ECDSA签名方案概述 ECDSA签名方案是基于椭圆曲线的数字签名算法。设E是定义在Zp上、由素数阶q的点G生成的椭圆曲线，E*是曲线上除无穷远点O之外的点集。未约简的转换函数C : E* → Zp将点P映射到其x坐标，约简的转换函数¯C : E* → Zq将点P映射到C(P)的规范代表（即范围在[0, p)内的整数模q）。 ECDSA的秘密密钥是随机的d ∈ Z∗q，公钥是D = dG ∈ E。该方案使用哈希函数Hash : {0, 1}∗