**Generic Hardness of Inversion on Ring and Its Relation to Self-Bilinear Map**

*Takashi Yamakawa and Shota Yamada and Goichiro Hanaoka and Noboru Kunihiro*

**Abstract: **In this paper, we study the generic hardness of the inversion problem on a ring, which is a problem to compute the inverse of a given prime $c$ by just using additions, subtractions and multiplications on the ring. If the characteristic of an underlying ring is public and coprime to $c$, then it is easy to compute the inverse of $c$ by using the extended Euclidean algorithm. On the other hand, if the characteristic is hidden, it seems difficult to compute it. For discussing the generic hardness of the inversion problem, we first extend existing generic ring models to capture a ring of an unknown characteristic. Then we prove that there is no generic algorithm to solve the inversion problem in our model when the underlying ring is isomorphic to $\mathbb{Z}_p$ for a randomly chosen prime $p$ assuming the hardness of factorization of an unbalanced modulus. We also study a relation between the inversion problem on a ring and a self-bilinear map. We give a ring-based construction of a self-bilinear map, and prove that natural complexity assumptions including the multilinear computational Diffie-Hellman (MCDH) assumption hold w.r.t the resulting sef-bilinear map if the inversion problem is hard on the underlying ring.

**Category / Keywords: **foundations /

**Date: **received 17 May 2018, last revised 22 Oct 2018

**Contact author: **yamakawa takashi at lab ntt co jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20181023:032738 (All versions of this report)

**Short URL: **ia.cr/2018/463

[ Cryptology ePrint archive ]