ON THE SECURITY OF GENERALIZED MULTILINEAR MAPS BASED ON WEIL PAIRING

DOI: https://doi.org/10.30598/barekengvol19iss2pp1307-1316
Keywords: Cryptography, Diffie-Hellman Assumption, Multilinear Map, Multiparty Key Exchange, Weil Pairing

Abstract

In 2017, Tran et al. proposed a multilinear map based on Weil pairings to realize the Boneh-Silverberg scheme. They proposed an algorithm to evaluate the Boneh-Silverberg multilinear map and showed that it could be used to establish a shared key in multipartite key exchange for five users. They claimed their scheme was secure and computable in establishing a shared key between 5 users. Unfortunately, they did not prove that their scheme meets three additional computational assumptions proposed by Boneh and Silverberg. In this paper, with some computational modifications, we show that the algorithm proposed by Tran et al. does not satisfy three security assumptions proposed by Boneh and Silverberg. Therefore, every user involved in this multipartite key exchange can obtain the shared key and other users' secret values. We also show that the computation to obtain a shared key is inefficient because it requires a lot of computation and time.

Downloads

References

D. Moody, R. Peralta, R. Perlner, A. Regenscheid, A. Roginsky, and L. Chen, “REPORT ON PAIRING-BASED CRYPTOGRAPHY,” vol. 120, pp. 11–27, 2015.

D. Boneh and M. Franklin, “IDENTITY-BASED ENCRYPTION FROM THE WEIL PAIRING,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 2139 LNCS, no. 3, pp. 213–229, 2001, doi: 10.1007/3-540-44647-8_13.

D. Boneh, B. Lynn, and H. Shacham, “SHORT SIGNATURES FROM THE WEIL PAIRING,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 2248, pp. 514–532, 2001, doi: 10.1007/3-540-45682-1_30.

A. Joux, “A ONE ROUND PROTOCOL FOR TRIPARTITE DIFFIE-HELLMAN,” J. Cryptol., vol. 17, no. 4, pp. 263–276, 2004, doi: 10.1007/s00145-004-0312-y.

J. H. Hoffstein, Jeffrey; Pipher, Jill; Silverman, AN INTRODUCTION TO MATHEMATICAL CRYPTOGRAPHY. Springer Science+Bussiness Media, LLC., 2008. [Online]. Available: https://link.springer.com/book/10.1007/978-0-387-77993-5

D. Boneh and A. Silverberg, “APPLICATIONS OF MULTILINEAR FORMS TO CRYPTOGRAPHY,” vol. 0000, pp. 71–90, 2003, doi: 10.1090/conm/324/05731.

S. Arita and S. Handa, “TWO APPLICATIONS OF MULTILINEAR MAPS: GROUP KEY EXCHANGE AND WITNESS ENCRYPTION,” ASIAPKC 2014 - Proc. 2nd ACM Work. ASIA Public-Key Cryptogr., pp. 13–22, 2014, doi: 10.1145/2600694.2600699.

H. Lin and S. Tessaro, “INDISTINGUISHABILITY OBFUSCATION FROM TRILINEAR MAPS AND BLOCK-WISE LOCAL PRGS,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 10401 LNCS, pp. 630–660, 2017, doi: 10.1007/978-3-319-63688-721.

S. Garg, C. Gentry, and S. Halevi, “CANDIDATE MULTILINEAR MAPS FROM IDEAL LATTICES,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 7881 LNCS, pp. 1–17, 2013, doi: 10.1007/978-3-642-38348-9_1.

H. Jia and Y. Hu, “CRYPTANALYSIS OF MULTILINEAR MAPS FROM IDEAL LATTICES: REVISITED,” Des. Codes, Cryptogr., vol. 84, no. 3, pp. 311–324, 2017, doi: 10.1007/s10623-016-0266-8.

J. S. Coron, T. Lepoint, and M. Tibouchi, “PRACTICAL MULTILINEAR MAPS OVER THE INTEGERS,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 8042 LNCS, no. PART 1, pp. 476–493, 2013, doi: 10.1007/978-3-642-40041-4_26.

J. H. Cheon, K. Han, C. Lee, H. Ryu, and D. Stehlé, “CRYPTANALYSIS OF THE CLT13 MULTILINEAR MAP,” J. Cryptol., vol. 32, no. 2, pp. 547–565, 2019, doi: 10.1007/s00145-018-9307-y.

M. H. T. Tran, T. T. Ton, T. D. Nguyen, N. T. Nguyen, N. V. Nguyen, and B. T. Nguyen, “MULTILINEAR MAPPINGS BASED ON WEIL PAIRING OVER ELLIPTIC CURVES,” 2017 4th NAFOSTED Conf. Inf. Comput. Sci. NICS 2017 - Proc., vol. 2017-Janua, pp. 138–143, 2017, doi: 10.1109/NAFOSTED.2017.8108053.

M. A. Huang, “TRILINEAR MAPS FOR CRYPTOGRAPHY,” Arxiv Cornell Univ., vol. 1, pp. 1–11, 2018, [Online]. Available: https://arxiv.org/abs/1803.10325

D. Kahrobaei, A. Tortora, and M. Tota, “MULTILINEAR CRYPTOGRAPHY USING NILPOTENT GROUPS,” Gruyter Proc. Math., pp. 127–133, 2020, doi: 10.1515/9783110638387-013.

A. Menezes, “AN INTRODUCTION TO PAIRING-BASED CRYPTOGRAPHY,” pp. 47–65, 2009, doi: 10.1090/conm/477/09303.

S. S. Carita and H. Kabetta, “MODIFICATION OF POLLARD RHO ALGORITHM USING NEGATION MAPPING,” BAREKENG J. Ilmu Mat. dan Terap., vol. 16, no. 4, pp. 1159–1166, 2022, doi: 10.30598/barekengvol16iss4pp1159-1166.

C. Boyd, A. Mathuria, and D. Stebila, PROTOCOLS FOR AUTHENTICATION AND KEY ESTABLISHMENT. 2020.

Published
2025-04-01
How to Cite
[1]
A. D. Handayani, I. E. Wijayanti, U. Isnaini, and P. Fauzi, “ON THE SECURITY OF GENERALIZED MULTILINEAR MAPS BASED ON WEIL PAIRING”, BAREKENG: J. Math. & App., vol. 19, no. 2, pp. 1307-1316, Apr. 2025.
Issue
Vol 19 No 2 (2025): BAREKENG: Journal of Mathematics and Its Application
Section
Articles

Copyright (c) 2025 Annisa Dini Handayani, Indah Emilia Wijayanti, Uha Isnaini, Prastudy Fauzi

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Authors who publish with this Journal agree to the following terms:

  1. Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
  2. Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
  3. Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.