Generalized Hardness Assumption for Self-bilinear Map with Auxiliary Information
Generalized Hardness Assumption for Self-bilinear Map with Auxiliary Information
复制标题
DOI：
10.1007/978-3-319-40367-0_17
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Takashi Yamakawa;Goichiro Hanaoka;N. Kunihiro
中科院分区：
文献类型：
--
作者：
Takashi Yamakawa;Goichiro Hanaoka;N. Kunihiro
自双线性映射（self-bilinear map，SBM）是一种双线性映射，其中源组和目标组是相同的。SBM自然地产生多线性映射，其在密码学中有许多应用。尽管它的有用性，有已知的一个强有力的负面结果存在一个理想的SBM。另一方面，Yamakawa等人（2014年）引入了带有辅助信息的自双线性映射（AI-SBM）的概念，这是SBM的一个较弱的变体，并基于因子分解假设和不可混淆性（）构建了它。在他们的工作中，他们证明了他们的AI-SBM满足辅助信息多线性计算Diffie-Hellman（AI-MCDH）假设，这是多线性计算Diffie-Hellman（MCDH）假设的自然模拟。多重线性映射然后，他们表明，他们可以取代多线性映射与AI-SBM在一些多线性映射为基础的原语，被证明是安全的MCDH assumptions.In这项工作中，我们进一步研究什么硬度假设举行w.r.t.他们的AI SBM具体来说，我们引入了一个新的硬度假设称为辅助信息广义多线性Diffie-Hellman（AI-GMDH）假设。AI-GMDH由一些参数参数化，因此可以被看作是一系列硬度假设。我们给出了一个充分的条件下，AI-GMDH假设成立的参数在以前的工作相同的假设。基于这个结果，我们可以很容易地证明AI-SBM满足一定的硬度假设，不仅包括AI-GMDH假设，但更复杂的假设。这使我们能够将一个在复杂的硬度假设下被证明是安全的基于多线性映射的原语转换为基于AI-SBP的原语（因此是基于因子分解和的原语）。作为一个例子，我们将Catalano et al.的基于多线性映射的同态签名（SPITPTO '14）到基于AI-SBP的签名。
A self-bilinear map (SBM) is a bilinear map where source and target groups are identical. An SBM naturally yields a multilinear map, which has numerous applications in cryptography. In spite of its usefulness, there is known a strong negative result on the existence of an ideal SBM. On the other hand, Yamakawa et al. (CRYPTO’14) introduced the notion of a self-bilinear map with auxiliary information (AI-SBM), which is a weaker variant of SBM and constructed it based on the factoring assumption and an indistinguishability obfuscation (). In their work, they proved that their AI-SBM satisfies the Auxiliary Information Multilinear Computational Diffie-Hellman (AI-MCDH) assumption, which is a natural analogue of the Multilinear Computational Diffie-Hellman (MCDH) assumption w.r.t. multilinear maps. Then they show that they can replace multilinear maps with AI-SBMs in some multilinear-map-based primitives that is proven secure under the MCDH assumption.In this work, we further investigate what hardness assumptions hold w.r.t. their AI-SBM. Specifically, we introduce a new hardness assumption called the Auxiliary Information Generalized Multilinear Diffie-Hellman (AI-GMDH) assumption. The AI-GMDH is parameterized by some parameters and thus can be seen as a family of hardness assumptions. We give a sufficient condition of parameters for which the AI-GMDH assumption holds under the same assumption as in the previous work. Based on this result, we can easily prove the AI-SBM satisfies certain hardness assumptions including not only the AI-GMDH assumption but also more complicated assumptions. This enable us to convert a multilinear-map-based primitive that is proven secure under a complicated hardness assumption to AI-SBP-based (and thus the factoring and-based) one. As an example, we convert Catalano et al.’s multilinear-map-based homomorphic signatures (CRYPTO’14) to AI-SBP-based ones.