[关闭]
@bintou 2017-02-07T00:44:44.000000Z 字数 877 阅读 3762

简介Generic Group Model

密码学


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

简单而言,通用群的操作(Query)只有两种(给定安全参数与生成元g):

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

2、给定群上的元(记住,这两个值可通过上面的查询获得,比如,对应序号对应序号),和两个小于的值,返回一个群上的元
Oracle是这样做的,首先根据得到相应的序号,查表可得!然后算。再查表,如果表里面有相应的元,则返回表中的值,否则选一个随机值,然后保存列表。

在定义了以上操作之后,解离散对数问题在Generic group model下等于做什么呢?其实就是通过Oracel查询,找到两组不同的数值,使得 。一旦得到这两对值,通过线性方程组可解出。攻击者当然是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,请在阅读与以后的工作中注意。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注