Algebraic Distinguishers: From Discrete Logarithms to Decisional Uber Assumptions
Algebraic Distinguishers: From Discrete Logarithms to Decisional Uber Assumptions
复制标题
代数区分符：从离散对数到决策性 Uber 假设
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
G. Segev
中科院分区：
文献类型：
--
作者：
Lior Rotem;G. Segev
由Fuchsbauer，Kiltz和Loss（1998年）引入的代数群模型是通用群模型捕获算法的实质性放松，可以利用底层群的表示。这个理想化但现实的模型被证明对于通过计算问题定义的密码假设和安全属性的推理是有用的。然而，它通常不捕获通过决策问题定义的假设和属性。由于这些问题在密码学的基础和应用中起着关键作用，这在限制性通用群模型和标准模型之间留下了一个巨大的差距。我们提出了代数群的概念，通过使其能够捕获决策问题来加强代数群模型。在我们的框架内，我们揭示了各种各样的决策假设之间的代数相互作用的新见解。这些假设包括决定性的狄仁杰-赫尔曼假设、多线性群中的线性假设族和双线性群中的尤伯杯假设族。我们的主要技术结果建立，从代数的角度来看，这些决策假设实际上都多项式等价于最基本的离散对数假设或其高阶变体，q -离散对数假设。一方面，这些结果增加了这些强决策假设的可信度，而另一方面，它们使密码分析工作能够直接用于提取离散代数或显著偏离标准代数技术。
The algebraic group model, introduced by Fuchsbauer, Kiltz and Loss (CRYPTO ’18), is a substantial relaxation of the generic group model capturing algorithms that may exploit the representation of the underlying group. This idealized yet realistic model was shown useful for reasoning about cryptographic assumptions and security properties defined via computational problems. However, it does not generally capture assumptions and properties defined via de-cisional problems. As such problems play a key role in the foundations and applications of cryptography, this leaves a significant gap between the restrictive generic group model and the standard model. We put forward the notion of algebraic distinguishers , strengthening the algebraic group model by enabling it to capture decisional problems. Within our framework we then reveal new insights on the algebraic interplay between a wide variety of decisional assumptions. These include the decisional Diffie-Hellman assumption, the family of Linear assumptions in multilinear groups, and the family of Uber assumptions in bilinear groups. Our main technical results establish that, from an algebraic perspective, these decisional assumptions are in fact all polynomially equivalent to either the most basic discrete logarithm assumption or to its higher-order variant, the q -discrete logarithm assumption. On the one hand, these results increase the confidence in these strong decisional assumptions, while on the other hand, they enable to direct cryptanalytic efforts towards either extracting discrete logarithms or significantly deviating from standard algebraic techniques.