Paper 2018/463
Generic Hardness of Inversion on Ring and Its Relation to SelfBilinear 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 selfbilinear map. We give a ringbased construction of a selfbilinear map, and prove that natural complexity assumptions including the multilinear computational DiffieHellman (MCDH) assumption hold w.r.t the resulting sefbilinear 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)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Contact author(s)
 takashi yamakawa ga @ hco ntt co jp
 History
 20190520: last of 3 revisions
 20180521: received
 See all versions
 Short URL
 https://ia.cr/2018/463
 License

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 SelfBilinear 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} }