• 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 proof of the conjectured run time of the Hafner-McCurley class group algorithm
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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[10]

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

[11]

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

[12]

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

[13]

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

[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.

[15]

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

[16]

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

[17]

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

[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.

[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.

[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.

[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.

[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.

[23]

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

[24]

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

[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.

[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.

[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.

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

show all references

References:
[1]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[10]

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

[11]

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

[12]

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

[13]

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

[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.

[15]

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

[16]

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

[17]

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

[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.

[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.

[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.

[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.

[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.

[23]

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

[24]

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

[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.

[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.

[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.

[28] J. S. Wilson, Profinite Groups, London Mathematical Society Monographs, New Series, 19, The Clarendon Press, Oxford University Press, New York, 1998. 
[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, 2021, 29 (5) : 3243-3260. 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 and 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 and 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 and 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 and 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 and Related Fields, 2013, 3 (4) : 467-487. doi: 10.3934/mcrf.2013.3.467

[16]

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

[17]

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

[18]

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

[19]

Robert McOwen, Peter Topalov. Groups of asymptotic diffeomorphisms. Discrete and Continuous Dynamical Systems, 2016, 36 (11) : 6331-6377. doi: 10.3934/dcds.2016075

[20]

Steven T. Piantadosi. Symbolic dynamics on free groups. Discrete and Continuous Dynamical Systems, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (354)
  • HTML views (290)
  • Cited by (0)

Other articles
by authors

[Back to Top]