简介Generic Group Model

密码学

直观上看，所谓generic group model（通用群模型）就是在考虑群计算的时候不考虑群本身的特定结构，而是通过一种理想化的（类似RO的访问方法）Query来进行群元素的操作。Generic group model首先是Shoup在EuroCrypt97提出的，用于证明DLG问题的下界是q^(1/2)，其中q是所求DLG问题的群的最大素阶子群的阶（order）。

简单而言，通用群的操作（Query）只有两种（给定安全参数与生成元g）：

1、给定$i$，Oracle返回$g^i$，实际上Oracle并不做群计算，只是返回一个随机数串，然后记录一张查询列表，如果查询过的$i$，直接返回表中的值。

2、给定群上的元$\sigma_1$和$\sigma_2$（记住，这两个值可通过上面的查询获得，比如，$\sigma_1$对应序号$i$，$\sigma_2$对应序号$j$），和两个小于$q$的值$r$，$s$，返回一个群上的元 $r*i + s*j$ 。
Oracle是这样做的，首先根据$\sigma_1$和$\sigma_2$得到相应的序号$i$和$j$，查表可得！然后算$r*i + s*j \; mod \; q$。再查表，如果表里面有相应的元，则返回表中的值，否则选一个随机值，然后保存列表。

在定义了以上操作之后，解离散对数问题在Generic group model下等于做什么呢？其实就是通过Oracel查询，找到两组不同的数值，使得 $r_0*i + s_0*j = r_1×i + s_1*j \; mod \; q$。一旦得到这两对值，通过线性方程组可解出$i$，$j$。攻击者当然是ppt的TM，假设做了t此查询，那么在t次查询下，最多t取2的组合个的值会相同，且与q的阶相同，即t^2 = q，即t =q^(1/2)。

Koblitz等人对Generic group model进行了详细的分析，指出这个模型也许比RO还要“强”（糟糕！），详情见another look at generic group model。

需要指出的是，在KE与id scheme中，安全证明常常严重依赖generic group model，请在阅读与以后的工作中注意。