zbMATH — the first resource for mathematics

Generic hardness of inversion on ring and its relation to self-bilinear map. (English) Zbl 1455.94198
Summary: 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. 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.

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
Full Text: DOI
[1] Shoup, V., Lower bounds for discrete logarithms and related problems, (EUROCRYPT (1997)), 256-266
[2] Babai, L.; Szemerédi, E., On the complexity of matrix group problems I, (FOCS (1984)), 229-240
[3] Nechaev, V. I., Complexity of a determinate algorithm for the discrete logarithm, Math. Notes, 55, 2, 91-101 (1994) · Zbl 0831.11065
[4] Rivest, R. L.; Shamir, A.; Adleman, L. M., A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21, 2, 120-126 (1978) · Zbl 0368.94005
[5] Damgård, I.; Koprowski, M., Generic lower bounds for root extraction and signature schemes in general groups, (EUROCRYPT (2002)), 256-271 · Zbl 1055.94026
[6] Leander, G.; Rupp, A., On the equivalence of RSA and factoring regarding generic ring algorithms, (ASIACRYPT (2006)), 241-251 · Zbl 1172.94582
[7] Aggarwal, D.; Maurer, U. M., Breaking RSA generically is equivalent to factoring, (EUROCRYPT (2009)), 36-53 · Zbl 1239.94031
[8] Jager, T.; Schwenk, J., On the analysis of cryptographic assumptions in the generic ring model, (ASIACRYPT (2009)), 399-416 · Zbl 1267.94068
[9] Aggarwal, D.; Maurer, U.; Shparlinski, I., The equivalence of strong RSA and factoring in the generic ring model of computation, (WCC. WCC, Paris, France (2011)), 17-26
[10] Kim, J.; Kim, S.; Seo, J. H., Multilinear map via scale-invariant FHE: enhancing security and efficiency (2015), 992
[11] Cheon, J. H.; Lee, D. H., A note on self-bilinear maps, Bull. Korean Math. Soc., 46, 2, 303-309 (2009) · Zbl 1160.94010
[12] Yamakawa, T.; Yamada, S.; Hanaoka, G.; Kunihiro, N., Self-bilinear map on unknown order groups from indistinguishability obfuscation and its applications, Algorithmica, 79, 4, 1286-1317 (2017) · Zbl 1405.94091
[13] Boneh, D.; Silverberg, A., Applications of multilinear forms to cryptography, Contemp. Math., 324, 71-90 (2002) · Zbl 1030.94032
[14] Catalano, D.; Fiore, D.; Warinschi, B., Homomorphic signatures with efficient verification for polynomial functions, (CRYPTO (2014)), 371-389 · Zbl 1345.94049
[15] Barak, B.; Goldreich, O.; Impagliazzo, R.; Rudich, S.; Sahai, A.; Vadhan, S. P.; Yang, K., On the (im)possibility of obfuscating programs, (CRYPTO (2001)), 1-18 · Zbl 1001.68511
[16] Altmann, K.; Jager, T.; Rupp, A., On black-box ring extraction and integer factorization, (ICALP 2008 (2008)), 437-448 · Zbl 1155.94362
[17] Brown, D. R.L., Breaking RSA may be as difficult as factoring, J. Cryptol., 29, 1, 220-241 (2016) · Zbl 1351.94030
[18] Albrecht, M. R.; Farshim, P.; Hofheinz, D.; Larraia, E.; Paterson, K. G., Multilinear maps from obfuscation, (TCC 2016-A Part I (2016)), 446-473 · Zbl 1388.94030
[19] Farshim, P.; Hesse, J.; Hofheinz, D.; Larraia, E., Graded encoding schemes from obfuscation, (PKC (2018)) · Zbl 1420.94061
[20] Hohenberger, S., The cryptographic impact of groups with infeasible inversion (2003), Massachusetts Institute of Technology, Master’s thesis
[21] Molnar, D., Homomorphic signature schemes (2003), Harvard College, Bachelor’s thesis
[22] Irrer, J.; Lokam, S.; Opyrchal, L.; Prakash, A., Infeasible group inversion and broadcast encryption (2004), University of Michigan Electrical Engineering and Computer Science, Tech Note CSE-TR-485-04
[23] Altug, S. A.; Chen, Y., A candidate group with infeasible inversion (2018), Cryptology ePrint Archive, Report 2018/926
[24] Lee, H.-S., A self-pairing map and its applications to cryptography, Appl. Math. Comput., 151, 3, 671-678 (2004) · Zbl 1046.94009
[25] J.H. Seo, personal communication, 2017.
[26] Paneth, O.; Sahai, A., On the equivalence of obfuscation and multilinear maps (2015), 791
[27] Bartusek, J.; Ma, F.; Zhandry, M., The distinction between fixed and random generators in group-based assumptions, (CRYPTO 2019 (2020)), in press · Zbl 07178471
[28] Shub, M.; Smale, S., On the intractability of hilbertfs nullstellensatz and an algebraic version of g \(n p \neq p\)? h, Duke Math. J., 81, 1, 47-54 (1995) · Zbl 0882.03040
[29] Cheng, Q., On the ultimate complexity of factorials, Theor. Comput. Sci., 326, 1-3, 419-429 (2004) · Zbl 1079.11060
[30] Markström, K., The straight line complexity of small factorials and primorials (2013), CoRR · Zbl 1347.11086
[31] Shamir, A., Factoring numbers in o(log n) arithmetic steps, Inf. Process. Lett., 8, 1, 28-31 (1979) · Zbl 0401.68018
[32] Shmuely, Z., Composite diffie-hellman public-key generating systems are hard to break (1985), Computer Science Department: Computer Science Department Technion, Israel, Tech. Rep. 356
[33] McCurley, K. S., A key distribution system equivalent to factoring, J. Cryptol., 1, 2, 95-105 (1988) · Zbl 0659.94003
[34] Hofheinz, D.; Kiltz, E., The group of signed quadratic residues and applications, (CRYPTO (2009)), 637-653 · Zbl 1252.94073
[35] Seurin, Y., New constructions and applications of trapdoor DDH groups, (Public Key Cryptography (2013)), 443-460 · Zbl 1314.94093
[36] Garg, S.; Gentry, C.; Halevi, S., Candidate multilinear maps from ideal lattices, (EUROCRYPT (2013)), 1-17 · Zbl 1300.94055
[37] Bitansky, N.; Canetti, R.; Chiesa, A.; Tromer, E., From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again, (ITCS (2012)), 326-349 · Zbl 1347.68129
[38] Lipton, R. J., Straight-line complexity and integer factorization, (ANTS-I (1994)), 71-79 · Zbl 0842.11045
[39] Lenstra, J.; W, H., Factoring integers with elliptic curves, Ann. Math., 126, 3, 649-673 (1987) · Zbl 0629.10006
[40] Yamakawa, T.; Hanaoka, G.; Kunihiro, N., Generalized hardness assumption for self-bilinear map with auxiliary information, (ACISP (2016)), 269-284 · Zbl 1346.94135
[41] Boneh, D.; Zhandry, M., Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation, (CRYPTO (2014)) · Zbl 1310.94130
[42] Khurana, D.; Rao, V.; Sahai, A., Multi-party key exchange for unbounded parties from indistinguishability obfuscation, (ASIACRYPT 2015 I (2015)), 52-75 · Zbl 1337.94044
[43] Goldreich, O.; Levin, L. A., A hard-core predicate for all one-way functions, (STOC (1989)), 25-32
[44] Gorbunov, S.; Vaikuntanathan, V.; Wichs, D., Leveled fully homomorphic signatures from standard lattices, (STOC 2015 (2015)), 469-477 · Zbl 1321.94062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.