3 Search Results for "Myasnikov, Alexei"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.52
Diffie-Hellman Key Exchange from Commutativity to Group Laws

Authors: Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In Diffie-Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie-Hellman key exchange in the group action framework (Brassard-Yung, Crypto'90; Ji-Qiao-Song-Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.
Cite as

Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang. Diffie-Hellman Key Exchange from Commutativity to Group Laws. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duong_et_al:LIPIcs.ITCS.2026.52,
  author =	{Duong, Dung Hoang and Qiao, Youming and Zhang, Chuanqi},
  title =	{{Diffie-Hellman Key Exchange from Commutativity to Group Laws}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{52:1--52:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.52},
  URN =		{urn:nbn:de:0030-drops-253396},
  doi =		{10.4230/LIPIcs.ITCS.2026.52},
  annote =	{Keywords: Diffie-Hellman, Key Exchange, Group Laws, Group Actions, Code Equivalence}
}
Document
DOI: 10.4230/DagRep.9.3.83
Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131)

Authors: Volker Diekert, Olga Kharlampovich, Markus Lohrey, and Alexei Myasnikov

Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)

Abstract
Since its early days, combinatorial group theory was deeply interwoven with computability theory. In the last 20 years we have seen many new successful interactions between group theory and computer science. On one hand, groups played an important rule in many developments in complexity theory and automata theory. On the other hand, concepts from these computer science fields as well as efficient algorithms, cryptography, and data compression led to the formulation of new questions in group theory. The Dagstuhl Seminar Algorithmic Problems in Group Theory was aimed at bringing together researchers from group theory and computer science so that they can share their expertise. This report documents the material presented during the course of the seminar.
Cite as

Volker Diekert, Olga Kharlampovich, Markus Lohrey, and Alexei Myasnikov. Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131). In Dagstuhl Reports, Volume 9, Issue 3, pp. 83-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{diekert_et_al:DagRep.9.3.83,
  author =	{Diekert, Volker and Kharlampovich, Olga and Lohrey, Markus and Myasnikov, Alexei},
  title =	{{Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131)}},
  pages =	{83--110},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{3},
  editor =	{Diekert, Volker and Kharlampovich, Olga and Lohrey, Markus and Myasnikov, Alexei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.83},
  URN =		{urn:nbn:de:0030-drops-112939},
  doi =		{10.4230/DagRep.9.3.83},
  annote =	{Keywords: algorithmic group theory; generic-case complexity; circuit complexity; diophantine theories}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.23
TC^0 Circuits for Algorithmic Problems in Nilpotent Groups

Authors: Alexei Myasnikov and Armin Weiß

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Recently, Macdonald et. al. showed that many algorithmic problems for finitely generated nilpotent groups including computation of normal forms, the subgroup membership problem, the conjugacy problem, and computation of subgroup presentations can be done in LOGSPACE. Here we follow their approach and show that all these problems are complete for the uniform circuit class TC^0 - uniformly for all r-generated nilpotent groups of class at most c for fixed r and c. Moreover, if we allow a certain binary representation of the inputs, then the word problem and computation of normal forms is still in uniform TC^0, while all the other problems we examine are shown to be TC^0-Turing reducible to the problem of computing greatest common divisors and expressing them as linear combinations.
Cite as

Alexei Myasnikov and Armin Weiß. TC^0 Circuits for Algorithmic Problems in Nilpotent Groups. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{myasnikov_et_al:LIPIcs.MFCS.2017.23,
  author =	{Myasnikov, Alexei and Wei{\ss}, Armin},
  title =	{{TC^0 Circuits for Algorithmic Problems in Nilpotent Groups}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.23},
  URN =		{urn:nbn:de:0030-drops-81089},
  doi =		{10.4230/LIPIcs.MFCS.2017.23},
  annote =	{Keywords: nilpotent groups, TC^0, abelian groups, word problem, conjugacy problem, subgroup membership problem, greatest common divisors}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2019
  • 1 2017

  • Refine by Author
  • 2 Myasnikov, Alexei
  • 1 Diekert, Volker
  • 1 Duong, Dung Hoang
  • 1 Kharlampovich, Olga
  • 1 Lohrey, Markus
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 DagRep

  • Refine by Classification
  • 1 Security and privacy → Mathematical foundations of cryptography

  • Refine by Keyword
  • 1 Code Equivalence
  • 1 Diffie-Hellman
  • 1 Group Actions
  • 1 Group Laws
  • 1 Key Exchange
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact