• Previous Article
    On the number of factorizations of $ t $ mod $ N $ and the probability distribution of Diffie-Hellman secret keys for many users
  • AMC Home
  • This Issue
  • Next Article
    A new class of optimal wide-gap one-coincidence frequency-hopping sequence sets
doi: 10.3934/amc.2021041
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Cryptographic multilinear maps using pro-p groups

1. 

University of York, Deramore Lane, YO10 5GH York, United Kingdom

2. 

The City University of New York, Queens College, Mathematics and Computer Science Departments and Graduate Center, New York, NY, USA

3. 

Max-Planck-Institut für Mathematik in den Naturwissenschaften, Inselstraße 22, 04103 Leipzig, Germany

Received  February 2021 Revised  July 2021 Early access September 2021

In [18], the authors show how, to any nilpotent group of class $ n $, one can associate a non-interactive key exchange protocol between $ n+1 $ users. The multilinear commutator maps associated to nilpotent groups play a key role in this protocol. In the present paper, we explore some alternative platforms, such as pro-$ p $ groups.

Citation: Delaram Kahrobaei, Mima Stanojkovski. Cryptographic multilinear maps using pro-p groups. Advances in Mathematics of Communications, doi: 10.3934/amc.2021041
References:
[1]

N. Blackburn, On a special class of p-groups, Acta Math., 100 (1958), 45-92.  doi: 10.1007/BF02559602.  Google Scholar

[2]

D. Boneh and A. Silverberg, Applications of multilinear forms to cryptography, in Topics in Algebraic and Noncommutative Geometry, Contemp. Math., 324, Amer. Math. Soc., Providence, RI, 2003, 71–90. doi: 10.1090/conm/324/05731.  Google Scholar

[3]

J.-S. Coron, T. Lepoint and M. Tibouchi, Practical multilinear maps over the integers, in Advances in Cryptology–-CRYPTO 2013. Part I, Lecture Notes in Comput. Sci., 8042, Springer, Heidelberg, 2013,476–493. doi: 10.1007/978-3-642-40041-4_26.  Google Scholar

[4]

B. den Boer, Diffie-Hellman is as strong as discrete log for certain primes, in Advances in Cryptology–-CRYPTO '88, Lecture Notes in Comput. Sci., 403, Springer, Berlin, 1990,530–539. doi: 10.1007/0-387-34799-2_38.  Google Scholar

[5]

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, 22 (1976), 644-654.  doi: 10.1109/tit.1976.1055638.  Google Scholar

[6]

E. S. V. Freire, D. Hofheinz, E. Kiltz and K. G. Paterson, Non-interactive key exchange, in Public-Key Cryptography – PKC 2013, Lecture Notes in Comput. Sci., 7778, Springer, Berlin, Heidelberg, 2013,254–271. doi: 10.1007/978-3-642-36362-7_17.  Google Scholar

[7]

S. Garg, C. Gentry and S. Halevi, Candidate multilinear maps from ideal lattices, in Advances in Cryptology–-EUROCRYPT 2013, Lecture Notes in Comput. Sci., 7881, Springer, Heidelberg, 2013, 1–17. doi: 10.1007/978-3-642-38348-9_1.  Google Scholar

[8]

C. Gentry, S. Gorbunov and S. Halevi, Graph-induced multilinear maps from lattices, in Theory of Cryptography. Part II, Lecture Notes in Comput. Sci., 9015, Springer, Heidelberg, 2015,498–527. doi: 10.1007/978-3-662-46497-7_20.  Google Scholar

[9]

J. González-Sánchez and B. Klopsch., Analytic pro-p groups of small dimensions, J. Group Theory, 12 (2009), 711-734.  doi: 10.1515/JGT.2009.006.  Google Scholar

[10]

M.-D. A. Huang, Algebraic blinding and cryptographic trilinear maps, preprint, arXiv: 2002.07923. Google Scholar

[11]

M.-D. A. Huang, Trilinear maps for cryptography, preprint, arXiv: 1803.10325. Google Scholar

[12]

M.-D. A. Huang, Trilinear maps for cryptography Ⅱ, preprint, arXiv: 1810.03646. Google Scholar

[13]

M.-D. A. Huang, Weil descent and cryptographic trilinear maps, preprint, arXiv: 1908.06891. Google Scholar

[14]

B. Huppert, Endliche Gruppen. I, Die Grundlehren der mathematischen Wissenschaften, 134, Springer-Verlag, Berlin-New York, 1967. doi: 10.1007/978-3-642-64981-3.  Google Scholar

[15]

I. M. Isaacs, Finite Group Theory, Graduate Studies in Mathematics, 92, American Mathematical Society, Providence, RI, 2008. doi: 10.1090/gsm/092.  Google Scholar

[16]

D. Kahrobaei and M. Noce, Algorithmic problems in Engel groups and cryptographic applications, Int. J. Group Theory, 9 (2020), 231-250.   Google Scholar

[17]

D. Kahrobaei, A. Tortora and M. Tota, A closer look at multilinear cryptography using nilpotent groups, preprint, arXiv: 2102.04120. Google Scholar

[18]

D. Kahrobaei, A. Tortora and M. Tota, Multilinear cryptography using nilpotent groups, in Elementary Theory of Groups and Group Rings, and Related Topics, De Gruyter Proc. Math., De Gruyter, Berlin, 2020,127–134. doi: 10.1515/9783110638387-013.  Google Scholar

[19]

A. Mahalanobis and P. Shinde, Bilinear cryptography using groups of nilpotency class 2, in Cryptography and Coding, Lecture Notes in Comput. Sci., 10655, Springer, Cham, 2017,127–134. doi: 10.1007/978-3-319-71045-7_7.  Google Scholar

[20]

U. M. Maurer, Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, in Advances in Cryptology–-CRYPTO '94, Lecture Notes in Comput. Sci., 839, Springer, Berlin, 1994,271–281. doi: 10.1007/3-540-48658-5_26.  Google Scholar

[21]

S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inform. Theory, 24 (1978), 106-110.  doi: 10.1109/tit.1978.1055817.  Google Scholar

[22]

L. Ribes and P. Zalesskii, Profinite Groups, A Series of Modern Surveys in Mathematics, 40, Springer-Verlag, Berlin, 2010. doi: 10.1007/978-3-642-01642-4.  Google Scholar

[23]

M. Stanojkovski, Intense automorphisms of finite groups, preprint, arXiv: 1710.08979. Google Scholar

[24]

A. V. Sutherland, Order Computations in Generic Groups, Ph.D thesis, Massachusetts Institute of Technology, 2007.  Google Scholar

[25]

A. V. Sutherland, Structure computation and discrete logarithms in finite abelian p-groups, Math. Comp., 80 (2011), 477-500.  doi: 10.1090/S0025-5718-10-02356-2.  Google Scholar

[26]

E. Teske, The Pohlig-Hellman method generalized for group structure computation, J. Symbolic Comput., 27 (1999), 521-534.  doi: 10.1006/jsco.1999.0279.  Google Scholar

[27]

M. Tibouchi, Cryptographic Multilinear Maps: A Status Report, CRYPTREC Technical Report, volume 2603, 2016, 1–54. Available from: https://www.cryptrec.go.jp/exreport/cryptrec-ex-2603-2016.pdf. Google Scholar

[28] J. S. Wilson, Profinite Groups, London Mathematical Society Monographs, New Series, 19, The Clarendon Press, Oxford University Press, New York, 1998.   Google Scholar

show all references

References:
[1]

N. Blackburn, On a special class of p-groups, Acta Math., 100 (1958), 45-92.  doi: 10.1007/BF02559602.  Google Scholar

[2]

D. Boneh and A. Silverberg, Applications of multilinear forms to cryptography, in Topics in Algebraic and Noncommutative Geometry, Contemp. Math., 324, Amer. Math. Soc., Providence, RI, 2003, 71–90. doi: 10.1090/conm/324/05731.  Google Scholar

[3]

J.-S. Coron, T. Lepoint and M. Tibouchi, Practical multilinear maps over the integers, in Advances in Cryptology–-CRYPTO 2013. Part I, Lecture Notes in Comput. Sci., 8042, Springer, Heidelberg, 2013,476–493. doi: 10.1007/978-3-642-40041-4_26.  Google Scholar

[4]

B. den Boer, Diffie-Hellman is as strong as discrete log for certain primes, in Advances in Cryptology–-CRYPTO '88, Lecture Notes in Comput. Sci., 403, Springer, Berlin, 1990,530–539. doi: 10.1007/0-387-34799-2_38.  Google Scholar

[5]

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, 22 (1976), 644-654.  doi: 10.1109/tit.1976.1055638.  Google Scholar

[6]

E. S. V. Freire, D. Hofheinz, E. Kiltz and K. G. Paterson, Non-interactive key exchange, in Public-Key Cryptography – PKC 2013, Lecture Notes in Comput. Sci., 7778, Springer, Berlin, Heidelberg, 2013,254–271. doi: 10.1007/978-3-642-36362-7_17.  Google Scholar

[7]

S. Garg, C. Gentry and S. Halevi, Candidate multilinear maps from ideal lattices, in Advances in Cryptology–-EUROCRYPT 2013, Lecture Notes in Comput. Sci., 7881, Springer, Heidelberg, 2013, 1–17. doi: 10.1007/978-3-642-38348-9_1.  Google Scholar

[8]

C. Gentry, S. Gorbunov and S. Halevi, Graph-induced multilinear maps from lattices, in Theory of Cryptography. Part II, Lecture Notes in Comput. Sci., 9015, Springer, Heidelberg, 2015,498–527. doi: 10.1007/978-3-662-46497-7_20.  Google Scholar

[9]

J. González-Sánchez and B. Klopsch., Analytic pro-p groups of small dimensions, J. Group Theory, 12 (2009), 711-734.  doi: 10.1515/JGT.2009.006.  Google Scholar

[10]

M.-D. A. Huang, Algebraic blinding and cryptographic trilinear maps, preprint, arXiv: 2002.07923. Google Scholar

[11]

M.-D. A. Huang, Trilinear maps for cryptography, preprint, arXiv: 1803.10325. Google Scholar

[12]

M.-D. A. Huang, Trilinear maps for cryptography Ⅱ, preprint, arXiv: 1810.03646. Google Scholar

[13]

M.-D. A. Huang, Weil descent and cryptographic trilinear maps, preprint, arXiv: 1908.06891. Google Scholar

[14]

B. Huppert, Endliche Gruppen. I, Die Grundlehren der mathematischen Wissenschaften, 134, Springer-Verlag, Berlin-New York, 1967. doi: 10.1007/978-3-642-64981-3.  Google Scholar

[15]

I. M. Isaacs, Finite Group Theory, Graduate Studies in Mathematics, 92, American Mathematical Society, Providence, RI, 2008. doi: 10.1090/gsm/092.  Google Scholar

[16]

D. Kahrobaei and M. Noce, Algorithmic problems in Engel groups and cryptographic applications, Int. J. Group Theory, 9 (2020), 231-250.   Google Scholar

[17]

D. Kahrobaei, A. Tortora and M. Tota, A closer look at multilinear cryptography using nilpotent groups, preprint, arXiv: 2102.04120. Google Scholar

[18]

D. Kahrobaei, A. Tortora and M. Tota, Multilinear cryptography using nilpotent groups, in Elementary Theory of Groups and Group Rings, and Related Topics, De Gruyter Proc. Math., De Gruyter, Berlin, 2020,127–134. doi: 10.1515/9783110638387-013.  Google Scholar

[19]

A. Mahalanobis and P. Shinde, Bilinear cryptography using groups of nilpotency class 2, in Cryptography and Coding, Lecture Notes in Comput. Sci., 10655, Springer, Cham, 2017,127–134. doi: 10.1007/978-3-319-71045-7_7.  Google Scholar

[20]

U. M. Maurer, Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, in Advances in Cryptology–-CRYPTO '94, Lecture Notes in Comput. Sci., 839, Springer, Berlin, 1994,271–281. doi: 10.1007/3-540-48658-5_26.  Google Scholar

[21]

S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inform. Theory, 24 (1978), 106-110.  doi: 10.1109/tit.1978.1055817.  Google Scholar

[22]

L. Ribes and P. Zalesskii, Profinite Groups, A Series of Modern Surveys in Mathematics, 40, Springer-Verlag, Berlin, 2010. doi: 10.1007/978-3-642-01642-4.  Google Scholar

[23]

M. Stanojkovski, Intense automorphisms of finite groups, preprint, arXiv: 1710.08979. Google Scholar

[24]

A. V. Sutherland, Order Computations in Generic Groups, Ph.D thesis, Massachusetts Institute of Technology, 2007.  Google Scholar

[25]

A. V. Sutherland, Structure computation and discrete logarithms in finite abelian p-groups, Math. Comp., 80 (2011), 477-500.  doi: 10.1090/S0025-5718-10-02356-2.  Google Scholar

[26]

E. Teske, The Pohlig-Hellman method generalized for group structure computation, J. Symbolic Comput., 27 (1999), 521-534.  doi: 10.1006/jsco.1999.0279.  Google Scholar

[27]

M. Tibouchi, Cryptographic Multilinear Maps: A Status Report, CRYPTREC Technical Report, volume 2603, 2016, 1–54. Available from: https://www.cryptrec.go.jp/exreport/cryptrec-ex-2603-2016.pdf. Google Scholar

[28] J. S. Wilson, Profinite Groups, London Mathematical Society Monographs, New Series, 19, The Clarendon Press, Oxford University Press, New York, 1998.   Google Scholar
[1]

Boris Khots, Dmitriy Khots. P-groups applications in genetics. Conference Publications, 2001, 2001 (Special) : 224-228. doi: 10.3934/proc.2001.2001.224

[2]

Sikhar Patranabis, Debdeep Mukhopadhyay. Identity-based key aggregate cryptosystem from multilinear maps. Advances in Mathematics of Communications, 2019, 13 (4) : 759-778. doi: 10.3934/amc.2019044

[3]

Raf Cluckers, Julia Gordon, Immanuel Halupczok. Motivic functions, integrability, and applications to harmonic analysis on $p$-adic groups. Electronic Research Announcements, 2014, 21: 137-152. doi: 10.3934/era.2014.21.137

[4]

Jinguo Zhang, Dengyun Yang. Fractional $ p $-sub-Laplacian operator problem with concave-convex nonlinearities on homogeneous groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021036

[5]

Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046

[6]

Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247

[7]

S. R. Bullett and W. J. Harvey. Mating quadratic maps with Kleinian groups via quasiconformal surgery. Electronic Research Announcements, 2000, 6: 21-30.

[8]

L. F. Cheung, C. K. Law, M. C. Leung. On a class of rotationally symmetric $p$-harmonic maps. Communications on Pure & Applied Analysis, 2017, 16 (6) : 1941-1955. doi: 10.3934/cpaa.2017095

[9]

Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052

[10]

A. Yu. Ol'shanskii and M. V. Sapir. Non-amenable finitely presented torsion-by-cyclic groups. Electronic Research Announcements, 2001, 7: 63-71.

[11]

Feng Rong. Non-algebraic attractors on $\mathbf{P}^k$. Discrete & Continuous Dynamical Systems, 2012, 32 (3) : 977-989. doi: 10.3934/dcds.2012.32.977

[12]

Aihua Fan, Shilei Fan, Lingmin Liao, Yuefei Wang. Minimality of p-adic rational maps with good reduction. Discrete & Continuous Dynamical Systems, 2017, 37 (6) : 3161-3182. doi: 10.3934/dcds.2017135

[13]

Tatsuya Arai. The structure of dendrites constructed by pointwise P-expansive maps on the unit interval. Discrete & Continuous Dynamical Systems, 2016, 36 (1) : 43-61. doi: 10.3934/dcds.2016.36.43

[14]

Mohammad Sadeq Dousti, Rasool Jalili. FORSAKES: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. Advances in Mathematics of Communications, 2015, 9 (4) : 471-514. doi: 10.3934/amc.2015.9.471

[15]

Ludovic Rifford. Ricci curvatures in Carnot groups. Mathematical Control & Related Fields, 2013, 3 (4) : 467-487. doi: 10.3934/mcrf.2013.3.467

[16]

Eduard Duryev, Charles Fougeron, Selim Ghazouani. Dilation surfaces and their Veech groups. Journal of Modern Dynamics, 2019, 14: 121-151. doi: 10.3934/jmd.2019005

[17]

Sergei V. Ivanov. On aspherical presentations of groups. Electronic Research Announcements, 1998, 4: 109-114.

[18]

Benjamin Weiss. Entropy and actions of sofic groups. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3375-3383. doi: 10.3934/dcdsb.2015.20.3375

[19]

Emmanuel Breuillard, Ben Green, Terence Tao. Linear approximate groups. Electronic Research Announcements, 2010, 17: 57-67. doi: 10.3934/era.2010.17.57

[20]

Neal Koblitz, Alfred Menezes. Another look at generic groups. Advances in Mathematics of Communications, 2007, 1 (1) : 13-28. doi: 10.3934/amc.2007.1.13

2020 Impact Factor: 0.935

Article outline

[Back to Top]