Cryptanalysis of GGH Map
Cryptanalysis of GGH Map
复制标题
DOI：
10.1007/978-3-662-49890-3_21
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Yu-pu Hu;Huiwen Jia
中科院分区：
文献类型：
--
作者：
Yu-pu Hu;Huiwen Jia
多线性映射是一种新的本原映射，在密码学中有着广泛的应用，而GGH映射是K-线性映射的一个主要候选。GGH映射有两类应用程序，它们是具有用于编码的公共工具和具有用于编码的隐藏工具的应用程序。在本文中，我们证明了GGH映射的应用程序与公共工具的编码是不安全的，和一个应用程序的GGH映射与隐藏的工具的编码是不安全的。在作者提出的弱DL攻击的基础上，针对多方密钥交换（MKE）和基于X3 C问题的证人加密（WE）实例，提出了几种对GGH映射的有效攻击。首先，我们使用特殊的模块化操作，我们称之为修改的编码/零测试，以大大减少噪音。这样的减少足以打破MKE。此外，这种减少否定了K-GMDDH假设，这是一个基本的安全性假设。该过程主要涉及简单的代数操作，很少需要使用任何格约简工具。关键是我们用于模块化操作的专用工具。其次，在公共编码工具的条件下，针对X3 C问题的困难性，对WE实例进行了破解。为此，我们不仅使用了改进的编码/零测试，而且引入并解决了“组合X3 C问题”，这是一个不难解决的问题。与多线性映射不可分割的假设不同，该攻击包含了一个除法运算，即由模某个主理想的线性方程求解一个等价秘密。商（等效秘密）并不小，因此需要修改编码/零测试来减小大小。这种攻击是在假设某些两个向量互质的情况下进行的，这似乎是合理的。第三，对于隐藏的编码工具，我们根据X3 C问题的难度，对WE实例进行了破解。为此，我们构造了0的2级编码，它被用作编码的替代工具。然后，我们打破了该计划，应用修改后的编码/零测试和组合X3 C，其中修改后的编码/零测试是一个扩展版本。这种攻击是在两个假设下进行的，这两个假设似乎是合理的。最后，针对MKE，给出了对GGH映射的两个简单修改的密码分析。我们表明，MKE对这两个修订可以打破的假设下，thatis多项式大。为此，我们进一步扩展了我们修改后的编码/零测试。
Multilinear map is a novel primitive which has many cryptographic applications, and GGH map is a major candidate ofK-linear maps for. GGH map has two classes of applications, which are applications with public tools for encoding and with hidden tools for encoding. In this paper, we show that applications of GGH map with public tools for encoding are not secure, and that one application of GGH map with hidden tools for encoding is not secure. On the basis of weak-DL attack presented by the authors themselves, we present several efficient attacks on GGH map, aiming at multipartite key exchange (MKE) and the instance of witness encryption (WE) based on the hardness of exact-3-cover (X3C) problem. First, we use special modular operations, which we call modified Encoding/zero-testing to drastically reduce the noise. Such reduction is enough to break MKE. Moreover, such reduction negatesK-GMDDH assumption, which is a basic security assumption. The procedure involves mostly simple algebraic manipulations, and rarely needs to use any lattice-reduction tools. The key point is our special tools for modular operations. Second, under the condition of public tools for encoding, we break the instance of WE based on the hardness of X3C problem. To do so, we not only use modified Encoding/zero-testing, but also introduce and solve “combined X3C problem”, which is a problem that is not difficult to solve. In contrast with the assumption that multilinear map cannot be divided back, this attack includes a division operation, that is, solving an equivalent secret from a linear equation modular some principal ideal. The quotient (the equivalent secret) is not small, so that modified Encoding/zero-testing is needed to reduce size. This attack is under an assumption that some two vectors are co-prime, which seems to be plausible. Third, for hidden tools for encoding, we break the instance of WE based on the hardness of X3C problem. To do so, we construct level-2 encodings of 0, which are used as alternative tools for encoding. Then, we break the scheme by applying modified Encoding/zero-testing and combined X3C, where the modified Encoding/zero-testing is an extended version. This attack is under two assumptions, which seem to be plausible. Finally, we present cryptanalysis of two simple revisions of GGH map, aiming at MKE. We show that MKE on these two revisions can be broken under the assumption thatis polynomially large. To do so, we further extend our modified Encoding/zero-testing.