在通用组模型中，一个更多的离散日志问题很难解决吗？

Question

在泛型组模型( Generic，GGM)中，将(已知) order n的具体循环组替换为理想化的版本:选择组元素的随机编码，而敌手只能访问任何输入组元素的编码形式(例如生成器/公钥/.)，以及应用组操作的甲骨文。编码是唯一的，因此可以测试组元素是否相等。它可以看作是对组的随机Oracle模型的模拟，而不是散列。

众所周知，离散对数问题在GGM中是困难的：舒普证明了任何一般算法都需要\Omega(\sqrt{p})群运算，其中p是n的最大素因子。

我的问题是，一个更多的离散对数问题(OMDL)在GGM中是否也很难解决。要打破OMDL，对手会被赋予k+1随机组元素，可以对DL oracle进行k查询，然后必须成功地找到所有k+1输入的离散对数。

Answer 1

Bauer等人最近的工作。BFP声称先前的回答中的证明是有缺陷的(并且Coretti等人)。证实了这一点)。然而，Bauer等人。证明OMDL在GGM中的硬度。它们表明，对手在素数级N的泛型组中解决OMDL (不需要预计算)并最多进行T oracle查询的概率至多是T^2/(N - T^2) + 1/N。

BFP：鲍尔，富什鲍尔，普卢维兹，广义群模型中的一次多离散对数假设

Answer 2

是的，这一点在科雷蒂等人CDG最近的一项工作中得到了证明。粗略地说，下限声明，最多向GGM oracle提出T查询的对手最多以T^2/N的概率成功，其中N是组的大小。事实上，他们考虑的是一个更强的模型，在GGM中允许对手任意预先计算。更精确的说明见第5节，结果摘要见表2。

CDG：Coretti，Dodis和郭，随机置换、理想密码和泛型群模型中的非一致界，Crypto'18