我们将基于以下signature构造介绍如何用RO做证明，体会RO的优劣之处。

, 

①randomly samples , compute 

②compute 

③compute 

Output 

①compute 

②test 

可以看到，

下面将展示，若H为RO，如何将这个signature reduce到Dlog上去 Theorem.

Scheme  is UF-CMA secure under the assumption DLOG in ROM.

Reduction:R需要在不知道x，也就是sk，的情况下完成signature，并提取出x

由于A具有问询，问询两项能力，因此R需要控制这两个部分。

控制

R（对A来说的Challenger）：收到（目的是输出x）

A（在R内部）：问询，问询收到，即pk 输出信息m

R向A输入随机选择的

A计算，并向R模拟的H query

R返回e

以上reduction保证了e的分布与真实情况一致，并且验证成立。

控制,如Idealized Model Ⅰ中所介绍，R需要存两个表：T1（random table），T2（R回应的）

A每次query，R查T1中是否存有该值，若有则回答对应值，若无则查T2是否存有该值，若有则回答对应值。

A最后输出,若A的输出通过了验证，则其对应的大

概率出现在T1中。若不出现在T1中，则猜中的概率可忽略。

假设query出现在T1中的第100个，即，我们将替换成，我们期望第二次rewind时，仍出现在第100的位置上。

定义，则第一轮出现概率为，第二轮出现的概率也是。

则碰撞的概率为

此时，可以通过解方程组,得到sk

许多算法都是基于assumption，如果能够确认它在Stand Model下确实是困难的，那么就能得到无条件的安全。然而这会得出one-way function的存在，也就是P≠NP，而这时暂时无法解决的。因此我们需要进行弱化限制。这就是需要Generic Group Model（GGM）的原因。下面给出GGM的定义。Shoup’s GGM:

  定义一个随机映射，为所有满足映射的函数，从中随机.      选一个f来进行映射，用表示这个随机映射。GGM需要提供两个接口:       Labeling和Addition。

If Then return

Else

在这个模型中，攻击者可以看到，能力较强，下面给出一种攻击者较弱的模型。

初始化一张空表，仅有序号。

A调用，就将x放入表中。A调用，就将y+z存入表中。这两个query都没有回复。

GGM还有一种调用称为Equaling Test，query两个序号，若内容相同，则回答1，不同则回答0.

然而对于前两种调用没有回应，作为一个程序来说总是有点怪怪的。因此对他们做一些调整，回应放入的表中position序号。

往期推荐