{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T17:54:35Z","timestamp":1762019675225,"version":"build-2065373602"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T00:00:00Z","timestamp":1577923200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T00:00:00Z","timestamp":1577923200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2020,7]]},"abstract":"Abstract<\/jats:title>We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\\text {DDH}} $$<\/jats:tex-math>DDH<\/mml:mtext><\/mml:math><\/jats:alternatives><\/jats:inline-formula> assumption hold for them. Our first construction is symmetric<\/jats:italic> and comes with a $$\\kappa $$<\/jats:tex-math>\u03ba<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-linear map $$\\mathbf{e }: {{\\mathbb {G}}}^\\kappa \\longrightarrow {\\mathbb {G}}_T$$<\/jats:tex-math>e<\/mml:mi>:<\/mml:mo>G<\/mml:mi><\/mml:mrow>\u03ba<\/mml:mi><\/mml:msup>\u27f6<\/mml:mo>G<\/mml:mi>T<\/mml:mi><\/mml:msub><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> for prime-order groups $${\\mathbb {G}}$$<\/jats:tex-math>G<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $${\\mathbb {G}}_T$$<\/jats:tex-math>G<\/mml:mi>T<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. To establish the hardness of the $$\\kappa $$<\/jats:tex-math>\u03ba<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-linear $${\\text {DDH}} $$<\/jats:tex-math>DDH<\/mml:mtext><\/mml:math><\/jats:alternatives><\/jats:inline-formula> problem, we rely on the existence of a base group for which the $$\\kappa $$<\/jats:tex-math>\u03ba<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-strong $${\\text {DDH}} $$<\/jats:tex-math>DDH<\/mml:mtext><\/mml:math><\/jats:alternatives><\/jats:inline-formula> assumption holds. Our second construction is for the asymmetric<\/jats:italic> setting, where $$\\mathbf{e }: {\\mathbb {G}}_1 \\times \\cdots \\times {\\mathbb {G}}_{\\kappa } \\longrightarrow {\\mathbb {G}}_T$$<\/jats:tex-math>e<\/mml:mi>:<\/mml:mo>G<\/mml:mi>1<\/mml:mn><\/mml:msub>\u00d7<\/mml:mo>\u22ef<\/mml:mo>\u00d7<\/mml:mo>G<\/mml:mi>\u03ba<\/mml:mi><\/mml:msub>\u27f6<\/mml:mo>G<\/mml:mi>T<\/mml:mi><\/mml:msub><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> for a collection of $$\\kappa +1$$<\/jats:tex-math>\u03ba<\/mml:mi>+<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> prime-order groups $${\\mathbb {G}}_i$$<\/jats:tex-math>G<\/mml:mi>i<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $${\\mathbb {G}}_T$$<\/jats:tex-math>G<\/mml:mi>T<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and relies only on the 1-strong $${\\text {DDH}} $$<\/jats:tex-math>DDH<\/mml:mtext><\/mml:math><\/jats:alternatives><\/jats:inline-formula> assumption in its base group. In both constructions, the linearity $$\\kappa $$<\/jats:tex-math>\u03ba<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\\mathbb {Z}_N^{+}$$<\/jats:tex-math>Z<\/mml:mi>N<\/mml:mi>+<\/mml:mo><\/mml:msubsup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. At a high level, we enable \u201cbootstrapping\u201d multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.<\/jats:p>","DOI":"10.1007\/s00145-019-09340-0","type":"journal-article","created":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T19:04:30Z","timestamp":1577991870000},"page":"1080-1113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Multilinear Maps from Obfuscation"],"prefix":"10.1007","volume":"33","author":[{"given":"Martin R.","family":"Albrecht","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pooya","family":"Farshim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuai","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dennis","family":"Hofheinz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enrique","family":"Larraia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenneth G.","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,2]]},"reference":[{"key":"9340_CR1","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Z. Brakerski, Obfuscating circuits via composite-order graded encoding. in Dodis and Nielsen [18], pp. 528\u2013556","DOI":"10.1007\/978-3-662-46497-7_21"},{"key":"9340_CR2","doi-asserted-by":"crossref","unstructured":"T. Agrikola, D. Hofheinz, Interactively secure groups from obfuscation. in Proc. PKC 2018, volume 10770 of Lecture Notes in Computer Science, (Springer, 2018), pp. 341\u2013370","DOI":"10.1007\/978-3-319-76581-5_12"},{"key":"9340_CR3","doi-asserted-by":"crossref","unstructured":"P. Ananth, A. Sahai. Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps. in J.-S. Coron, J.B. Nielsen, editors, EUROCRYPT\u00a02017, Part\u00a0I, LNCS, vol. 10210 (Springer, Heidelberg, May 2017), pp. 152\u2013181","DOI":"10.1007\/978-3-319-56620-7_6"},{"key":"9340_CR4","doi-asserted-by":"crossref","unstructured":"D. Boneh, X. Boyen, H. Shacham, Short group signatures, in M. Franklin, editor, CRYPTO\u00a02004, LNCS, vol. 3152, (Springer, Heidelberg, August 2004), pp. 41\u201355","DOI":"10.1007\/978-3-540-28628-8_3"},{"key":"9340_CR5","doi-asserted-by":"crossref","unstructured":"D. Boneh, K. Lewi, M. Raykova, A. Sahai, M. Zhandry, J. Zimmerman, Semantically secure order-revealing encryption: Multi-input functional encryption without obfuscation. in Oswald and Fischlin [38], pp. 563\u2013594","DOI":"10.1007\/978-3-662-46803-6_19"},{"key":"9340_CR6","doi-asserted-by":"crossref","unstructured":"X. Boyen. The uber-assumption family (invited talk). in S.D. Galbraith, K.G. Paterson, editors, PAIRING 2008, LNCS, vol. 5209 (Springer, Heidelberg, September 2008), pp. 39\u201356","DOI":"10.1007\/978-3-540-85538-5_3"},{"key":"9340_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1090\/conm\/324\/05731","volume":"324","author":"Dan Boneh","year":"2003","unstructured":"D. Boneh, A. Silverberg, Applications of multilinear forms to cryptography. Contemporary Mathematics, 324, 71\u201390 (2003)","journal-title":"Contemporary Mathematics"},{"key":"9340_CR8","doi-asserted-by":"crossref","unstructured":"D. Boneh, B. Waters, M. Zhandry, Low overhead broadcast encryption from multilinear maps. in J.A. Garay, R. Gennaro, editors, CRYPTO\u00a02014, Part\u00a0I, LNCS, vol. 8616, (Springer, Heidelberg, August 2014), pp. 206\u2013223","DOI":"10.1007\/978-3-662-44371-2_12"},{"key":"9340_CR9","doi-asserted-by":"crossref","unstructured":"J.H. Cheon, P.-A. Fouque, C. Lee, B. Minaud, H. Ryu, Cryptanalysis of the new CLT multilinear map over the integers. in Fischlin and Coron [20], pp. 509\u2013536.","DOI":"10.1007\/978-3-662-49890-3_20"},{"key":"9340_CR10","unstructured":"R. Canetti, J.A. Garay, editors, CRYPTO\u00a02013, Part\u00a0I, LNCS, vol. 8042. (Springer, Heidelberg, August 2013)"},{"key":"9340_CR11","unstructured":"R. Canetti, J.A. Garay, editors, CRYPTO\u00a02013, Part\u00a0II, LNCS, vol. 8043 (Springer, Heidelberg, August 2013)"},{"key":"9340_CR12","doi-asserted-by":"crossref","unstructured":"J.-S. Coron, C. Gentry, S. Halevi, T. Lepoint, H.K. Maji, E. Miles, M. Raykova, A. Sahai, M. Tibouchi, Zeroizing without low-level zeroes: New MMAP attacks and their limitations. in Gennaro and Robshaw [28], pp. 247\u2013266","DOI":"10.1007\/978-3-662-47989-6_12"},{"key":"9340_CR13","doi-asserted-by":"crossref","unstructured":"J.H. Cheon, K. Han, C. Lee, H. Ryu, D. Stehl\u00e9. Cryptanalysis of the multilinear map over the integers. in E. Oswald, M. Fischlin, editors, EUROCRYPT\u00a02015, Part\u00a0I, LNCS, vol. 9056 (Springer, Heidelberg, April 2015), pp. 3\u201312","DOI":"10.1007\/978-3-662-46800-5_1"},{"key":"9340_CR14","doi-asserted-by":"crossref","unstructured":"J.-S. Coron, M.S. Lee, T. Lepoint, M. Tibouchi, Cryptanalysis of GGH15 multilinear maps. in Robshaw and Katz [41], pp. 607\u2013628","DOI":"10.1007\/978-3-662-53008-5_21"},{"key":"9340_CR15","doi-asserted-by":"crossref","unstructured":"J.-S. Coron, T. Lepoint, M. Tibouchi, Practical multilinear maps over the integers. in Canetti and Garay [10], pp. 476\u2013493","DOI":"10.1007\/978-3-642-40041-4_26"},{"key":"9340_CR16","doi-asserted-by":"crossref","unstructured":"J.-S. Coron, T. Lepoint, M. Tibouchi. New multilinear maps over the integers. in Gennaro and Robshaw [28], pp. 267\u2013286","DOI":"10.1007\/978-3-662-47989-6_13"},{"key":"9340_CR17","doi-asserted-by":"crossref","unstructured":"R. Canetti, H. Lin, S. Tessaro, V. Vaikuntanathan, Obfuscation of probabilistic circuits and applications. in Dodis and Nielsen [18], pp. 468\u2013497","DOI":"10.1007\/978-3-662-46497-7_19"},{"key":"9340_CR18","unstructured":"Y. Dodis, J.B. Nielsen, editors. TCC\u00a02015, Part\u00a0II, LNCS, vol. 9015 (Springer, Heidelberg, March 2015)"},{"key":"9340_CR19","doi-asserted-by":"crossref","unstructured":"A. Escala, G. Herold, E. Kiltz, C. R\u00e0fols, J. Villar. An algebraic framework for Diffie-Hellman assumptions. in Canetti and Garay [11], pp. 129\u2013147","DOI":"10.1007\/978-3-642-40084-1_8"},{"key":"9340_CR20","unstructured":"M. Fischlin, J.-S. Coron, editors. EUROCRYPT\u00a02016, Part\u00a0I, LNCS, vol. 9665 (Springer, Heidelberg, May 2016)"},{"key":"9340_CR21","doi-asserted-by":"crossref","unstructured":"P. Farshim, J. Hesse, D. Hofheinz, E. Larraia. Graded encoding schemes from obfuscation. in Proc. PKC 2018, LNCS, vol. 10770 (Springer, 2018), pp. 371\u2013400","DOI":"10.1007\/978-3-319-76581-5_13"},{"key":"9340_CR22","doi-asserted-by":"crossref","unstructured":"E.S.V. Freire, D. Hofheinz, K.G. Paterson, C. Striecks. Programmable hash functions in the multilinear setting. in Canetti and Garay [10], pp. 513\u2013530","DOI":"10.1007\/978-3-642-40041-4_28"},{"key":"9340_CR23","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, S. Halevi. Candidate multilinear maps from ideal lattices. in T.J. Phong, Q. Nguyen, editors, EUROCRYPT\u00a02013, LNCS, vol. 7881 (Springer, Heidelberg, May 2013), pp. 1\u201317","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"9340_CR24","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, B. Waters, Candidate indistinguishability obfuscation and functional encryption for all circuits. in 54th FOCS, (IEEE Computer Society Press, October 2013), pp. 40\u201349","DOI":"10.1109\/FOCS.2013.13"},{"key":"9340_CR25","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, S. Halevi, A. Sahai, B. Waters, Attribute-based encryption for circuits from multilinear maps. in Canetti and Garay [11], pp. 479\u2013499","DOI":"10.1007\/978-3-642-40084-1_27"},{"key":"9340_CR26","doi-asserted-by":"crossref","unstructured":"C. Gentry, S. Gorbunov, S. Halevi, Graph-induced multilinear maps from lattices. in Dodis and Nielsen [18], pp. 498\u2013527","DOI":"10.1007\/978-3-662-46497-7_20"},{"key":"9340_CR27","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, A. Sahai, B. Waters, Witness encryption and its applications. in D. Boneh, T. Roughgarden, J. Feigenbaum, editors, 45th ACM STOC (ACM Press, June 2013), pp. 467\u2013476","DOI":"10.1145\/2488608.2488667"},{"key":"9340_CR28","unstructured":"R. Gennaro, M.J.B. Robshaw, editors, CRYPTO\u00a02015, Part\u00a0I, LNCS, vol. 9215 (Springer, Heidelberg, August 2015)"},{"key":"9340_CR29","doi-asserted-by":"crossref","unstructured":"J. Groth, A. Sahai. Efficient non-interactive proof systems for bilinear groups. in N.P. Smart, editor, EUROCRYPT\u00a02008, LNCS, vol. 4965 (Springer, Heidelberg, April 2008), pp. 415\u2013432","DOI":"10.1007\/978-3-540-78967-3_24"},{"key":"9340_CR30","doi-asserted-by":"crossref","unstructured":"Y. Hu, H. Jia, Cryptanalysis of GGH map. in Fischlin and Coron [20], pp. 537\u2013565","DOI":"10.1007\/978-3-662-49890-3_21"},{"key":"9340_CR31","doi-asserted-by":"crossref","unstructured":"S. Hohenberger, A. Sahai, B. Waters. Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. in Canetti and Garay [10], pp. 494\u2013512","DOI":"10.1007\/978-3-642-40041-4_27"},{"key":"9340_CR32","unstructured":"J. Katz, H. Shacham, editors. CRYPTO\u00a02017, Part\u00a0I, LNCS, vol. 10401 (Springer, Heidelberg, August 2017)"},{"key":"9340_CR33","doi-asserted-by":"crossref","unstructured":"H. Lin, Indistinguishability obfuscation from constant-degree graded encoding schemes. in Fischlin and Coron [20], pp. 28\u201357","DOI":"10.1007\/978-3-662-49890-3_2"},{"key":"9340_CR34","doi-asserted-by":"crossref","unstructured":"H. Lin, Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. in Katz and Shacham [32], pp. 599\u2013629","DOI":"10.1007\/978-3-319-63688-7_20"},{"key":"9340_CR35","doi-asserted-by":"crossref","unstructured":"H. Lin, S. Tessaro, Indistinguishability obfuscation from trilinear maps and block-wise local PRGs. In Katz and Shacham [32], pp. 630\u2013660","DOI":"10.1007\/978-3-319-63688-7_21"},{"key":"9340_CR36","doi-asserted-by":"crossref","unstructured":"E. Miles, A. Sahai, M. Zhandry. Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. in Robshaw and Katz [41], pp. 629\u2013658","DOI":"10.1007\/978-3-662-53008-5_22"},{"key":"9340_CR37","doi-asserted-by":"crossref","unstructured":"M. Naor, M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks. in 22nd ACM STOC (ACM Press, May 1990), pp. 427\u2013437","DOI":"10.1145\/100216.100273"},{"key":"9340_CR38","unstructured":"E. Oswald, M. Fischlin, editors. EUROCRYPT\u00a02015, Part\u00a0II, LNCS, vol. 9057 (Springer, Heidelberg, April 2015)"},{"key":"9340_CR39","unstructured":"O. Paneth, A. Sahai, On the equivalence of obfuscation and multilinear maps. Cryptology ePrint Archive, Report 2015\/791, (2015). http:\/\/eprint.iacr.org\/2015\/791"},{"key":"9340_CR40","doi-asserted-by":"crossref","unstructured":"C. Papamanthou, R. Tamassia, N. Triandopoulos, Optimal authenticated data structures with multilinear forms. in M. Joye, A. Miyaji, A. Otsuka, editors, PAIRING 2010, LNCS, vol. 6487 (Springer, Heidelberg, December 2010), pp. 246\u2013264","DOI":"10.1007\/978-3-642-17455-1_16"},{"key":"9340_CR41","unstructured":"M. Robshaw, J. Katz, editors. CRYPTO\u00a02016, Part\u00a0II, LNCS, vol. 9815 (Springer, Heidelberg, August 2016)"},{"key":"9340_CR42","doi-asserted-by":"crossref","unstructured":"F. Tang, H. Li, B. Liang, Attribute-based signatures for circuits from multilinear maps. in S.S.M. Chow, J. Camenisch, L.C.K. Hui, S.-M. Yiu, editors, ISC\u00a02014, LNCS, vol. 8783 (Springer, Heidelberg, October 2014), pp. 54\u201371","DOI":"10.1007\/978-3-319-13257-0_4"},{"key":"9340_CR43","doi-asserted-by":"crossref","unstructured":"T. Yamakawa, S. Yamada, G. Hanaoka, N. Kunihiro. Self-bilinear map on unknown order groups from indistinguishability obfuscation and its applications. in J.A. Garay, R. Gennaro, editors, CRYPTO\u00a02014, Part\u00a0II, LNCS, vol. 8617(Springer, Heidelberg, August 2014), pp. 90\u2013107","DOI":"10.1007\/978-3-662-44381-1_6"},{"key":"9340_CR44","unstructured":"T. Yamakawa, S. Yamada, G. Hanaoka, N. Kunihiro. Self-bilinear map on unknown order groups from indistinguishability obfuscation and its applications. Cryptology ePrint Archive, Report 2015\/128, (2015). http:\/\/eprint.iacr.org\/2015\/128"},{"key":"9340_CR45","doi-asserted-by":"crossref","unstructured":"J. Zimmerman. How to obfuscate programs directly. in Oswald and Fischlin [38], pp. 439\u2013467","DOI":"10.1007\/978-3-662-46803-6_15"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09340-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-019-09340-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09340-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:12:44Z","timestamp":1609459964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-019-09340-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,2]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["9340"],"URL":"https:\/\/doi.org\/10.1007\/s00145-019-09340-0","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2020,1,2]]},"assertion":[{"value":"1 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}