Paper Info
Title
Generic hardness of inversion on ring and its relation to self-bilinear map
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 Zp 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. Namely, we give a construction of a self-bilinear map based on a ring on which the inversion problem is hard, and prove that natural complexity assumptions including the multilinear computational Diffie-Hellman (MCDH) assumption hold w.r.t. the resulting sef-bilinear map.
Year
DOI
Venue
2018
10.1016/j.tcs.2020.03.009
Theoretical Computer Science
Keywords
Field
DocType
Cryptography,Generic ring,Straight-line program,Self-bilinear map,Multilinear map
Bilinear map,Mathematical analysis,Inversion (meteorology),Mathematics
Journal
Volume
ISSN
Citations 
820
0304-3975
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Takashi Yamakawa1129.35
Shota Yamada29418.10
Goichiro Hanaoka3910101.53
Noboru Kunihiro442545.72