Paper 2018/463

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

Takashi Yamakawa, Shota Yamada, 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.

Note: Revised introduction and fixed typos in Appendix A. (2019/5/20)

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Contact author(s)
takashi yamakawa ga @ hco ntt co jp
History
2019-05-20: last of 3 revisions
2018-05-21: received
See all versions
Short URL
https://ia.cr/2018/463
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/463,
      author = {Takashi Yamakawa and Shota Yamada and Goichiro Hanaoka and Noboru Kunihiro},
      title = {Generic Hardness of Inversion on Ring and Its Relation to Self-Bilinear Map},
      howpublished = {Cryptology ePrint Archive, Paper 2018/463},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/463}},
      url = {https://eprint.iacr.org/2018/463}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.