Charles V. Schaefer, Jr. School of Engineering and Science
 
 
SES Home » Algebraic Cryptography Center » Selected publications

Selected publications

A selection of publications by ACC members. For preprints and additional publications consult the Cryptology ePrint Archive, and arXiv.org.
Books
Algorithmic Problems of Group Theory, Their Complexity, and Applications to Cryptography, Delaram Kahrobaei and Vladimir Shpilrain eds., Contemporary Mathematics, 633, American Mathematical Society 2015.
http://dx.doi.org/10.1090/conm/633
Computational and Combinatorial Group Theory and Cryptography, Benjamin Fine, Delaram Kahrobaei and Gerhard Rosenberger eds., Contemporary Mathematics, 582, American Mathematical Society 2012.
http://dx.doi.org/10.1090/conm/582
Non-Commutative Cryptography and Complexity of Group-Theoretic Problems, Alexei Myasnikov, Vladimir Shpilrain and Alexander Ushakov, Mathematical Surveys and Monographs, 177, American Mathematical Society 2011.
http://dx.doi.org/10.1090/surv/177
Public Key Cryptography -- PKC 2011, Dario Catalano, Nelly Fazio, Rosario Gennaro and Antonio Nicolosi, eds., Lecture Notes in Computer Science 6571, Springer 2011.
http://dx.doi.org/10.1007/978-3-642-19379-8
Group-based Cryptography. Alexei Myasnikov, Vladimir Shpilrain and Alexander Ushakov. Advanced Courses in Mathematics CRM Barcelona, Birkhäuser 2008.
Articles
2017
  • Volker Diekert, Alexei G. Myasnikov and Armin Weiß. Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem. J. Symbolic Comput. 83 (2017), 147-165.
    https://doi.org/10.1016/j.jsc.2016.11.009

  • Albert Garreta, Alexei G. Miasnikov and Denis Ovchinnikov. Random nilpotent groups, polycyclic presentations, and Diophantine problems. Groups Complex. Cryptol. 9 (2017), 99-115.
    https://doi.org/10.1515/gcc-2017-0007

  • Funda Gul, Alexei G. Myasnikov and Mahmood Sohrabi. Distortion of embeddings of a torsion-free finitely generated nilpotent group into a unitriangular group. Internat. J. Algebra Comput. 27 (2017), 633-653.
    https://doi.org/10.1142/S021819671750031X

  • Funda Gul, Mahmood Sohrabi and Alexander Ushakov. Magnus embedding and algorithmic properties of groups F/N^d. Trans. Amer. Math. Soc. 369 (2017), 6189-6206.
    https://doi.org/10.1090/tran/6880

  • Olga Kharlampovich, Alexei Miasnikov and Pascal Weil. Stallings graphs for quasi-convex subgroups. J. Algebra 488 (2017), 442-483.
    https://doi.org/10.1016/j.jalgebra.2017.05.037

  • Olga Kharlampovich, Alexei Myasnikov and Mark Sapir. Algorithmically complex residually finite groups. Bull. Math. Sci. 7 (2017), 309-352.
    https://doi.org/10.1007/s13373-017-0103-z

  • Andrei Malyutin, Tatiana Nagnibeda and Denis Serbin. Boundaries of Z^n-free groups. Groups, graphs and random walks, 355-390, London Math. Soc. Lecture Note Ser., 436, Cambridge Univ. Press, Cambridge, 2017.

  • Alexei Miasnikov and Paul Schupp. Computational complexity and the conjugacy problem. Computability 6 (2017), 307-318.

  • Alexei Miasnikov and Svetla Vassileva. Log-space conjugacy problem in the Grigorchuk group. Groups Complex. Cryptol. 9 (2017), 77-85.
    https://doi.org/10.1515/gcc-2017-0005

  • Alexei Miasnikov, Svetla Vassileva and Armin Weiß. The conjugacy problem in free solvable groups and wreath products of abelian groups is in TC0. Computer science—theory and applications, 217-231, Lecture Notes in Comput. Sci., 10304, Springer, 2017.

20162015
  • Tullio Ceccherini-Silberstein, Michel Coornaert, Francsca Fiorenzi, Paul E. Schupp and Nicholas W. M. Touikan, Nicholas. Multipass automata and group word problems. Theoret. Comput. Sci. 600 (2015), 19--33.
    http://dx.doi.org/10.1016/j.tcs.2015.06.054

  • Volker Diekert, Olga Kharlampovich and Atefeh Mohajeri Moghaddam. SLP compression for solutions of equations with constraints in free and hyperbolic groups. Internat. J. Algebra Comput. 25 (2015) 81--111.
    http://dx.doi.org/10.1142/S0218196715400056

  • Volker Diekert, Akexei G. Myasnikov and Armin Weiß. Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem. In ISSAC'15—Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, 141--148, ACM, 2015.
    http://dx.doi.org/10.1145/2755996.2756644

  • D. Kahrobaei, C. Koupparis, and V. Shpilrain. A CCA secure cryptosystem using matrices over group rings. Contemp. Math., Amer. Math. Soc. 633 (2015), 73-80.
    http://dx.doi.org/10.1090/conm/633/12652

  • Matvei Kotov and Alexander Ushakov. Analysis of a certain polycyclic-group-based cryptosystem. J. Math. Cryptol. 9 (2015), 161--167.
    http://dx.doi.org/10.1515/jmc-2015-0013

  • Pavel Morar and Alexander Ushakov. Search problems in groups and branching processes. Internat. J. Algebra Comput. 25 (2015) 445--480.
    http://dx.doi.org/10.1142/S0218196715500058

  • Alexei Myasnikov and Vitaliĭ Roman'kov. A linear decomposition attack. Groups Complex. Cryptol. 7 (2015) 81--94.
    http://dx.doi.org/10.1515/gcc-2015-0007

2014
  • Volker Diekert, Alexei G. Myasnikov and Armin Weiß. Conjugacy in Baumslag's group, generic case complexity, and division in power circuits. Algorithmica (2016), 1--28.
    http://dx.doi.org/10.1007/s00453-016-0117-z

  • Nelly Fazio, Antonio R. Nicolosi and Irippuge Milinda Perera. Broadcast steganography. In Topics in Cryptology -- CT-RSA 2014, vol. 8366 of Lecture Notes in Computer Science 64--84 Springer 2014.
    http://dx.doi.org/10.1007/978-3-319-04852-9_4

  • Dima Grigoriev and Vladimir Shpilrain. Yao's millionaires' problem and decoy-based public key encryption by classical physics. Journal of Foundations of Computer Science 25 (2014), 409--417.
    http://dx.doi.org/10.1142/S0129054114400036 /p>

  • Martin Kreuzer, Alexei D. Myasnikov and Alexander Ushakov. A linear algebra attack to group-ring-based key exchange protocols. Applied cryptography and network security. In vol. 8479 of Lecture Notes in Computer Science, 37--43, Springer, 2014.
    http://dx.doi.org/10.1007/978-3-319-07536-5_3

  • Alexei Myasnikov, Andrey Nikolaev and Alexander Ushakov. The Post correspondence problem in groups. J. Group Theory 17 (2014), 991--1008.
    http://dx.doi.org/10.1515/jgth-2014-0022

  • Alexei Myasnikov, Andrey Nikolaev, Alexander Ushakov. Knapsack Problems in Groups. Mathematics of Computation 84 (2014) 987--1016.
    http://dx.doi.org/10.1090/S0025-5718-2014-02880-9

  • A. G. Myasnikov and V. N. Remeslennikov. Generic theories as a method for approximating elementary theories. (Russian). Algebra Logika 53 (2014), 779--789. Translation in Algebra and Logic 53 (2014), 512--519.
    http://dx.doi.org/10.1007/s10469-015-9314-0

  • Alexei Myasnikov, and Vitalĭ Roman'kov. Diophantine cryptography in free metabelian groups: theoretical base. Groups Complex. Cryptol. 6 (2014) 103--120.
    http://dx.doi.org/10.1515/gcc-2014-0011

  • Alexey D. Myasnikov and Alexander Ushakov. Cryptanalysis of matrix conjugation schemes. J. Math. Cryptol. 8 (2014), 95--114.
    http://dx.doi.org/10.1515/jmc-2012-0033

  • Alexey D Myasnikov and Alexander Ushakov. Quantum algorithm for discrete logarithm problem for matrices over finite group rings. Groups Complex. Cryptol. 6 (2014) 31--36.
    http://dx.doi.org/10.1515/gcc-2014-0003

  • Georg Neugebauer, Lucas Brutschy, Ulrike Meyer and Susanne Wetzel. Privacy-preserving multi-party reconciliation secure in the malicious model. In Data Privacy Management and Autonomous Spontaneous Security, vol. 8247 of Lect. Notes in Comp. Sci., 178--193, Springer 2014.
    http://dx.doi.org/10.1007/978-3-642-54568-9_12

2013
  • Rodney G. Downey, Carl G. Jockusch, Jr. and Paul E. Schupp. Asymptotic density and computably enumerable sets. J. Math. Log. 13 (2013), 1350005, 43 pp.
    http://dx.doi.org/10.1142/S0219061313500050

  • D. Kahrobaei, C. Koupparis, and V. Shpilrain. Public key exchange using matrices over group rings. Groups, Complexity, and Cryptology 5 (2013), 97-115.
    http://dx.doi.org/10.1515/gcc-2013-0007

  • Olga Kharlampovich, Alexei Myasnikov and Denis Serbin. Actions, length functions, and non-Archimedean words. Internat. J. Algebra Comput. 23 (2013) 325--455.
    http://dx.doi.org/10.1142/S0218196713400031

  • Chunyu Tang, David A. Naumann and Susanne Wetzel. Analysis of authentication and key establishment in inter-generational mobile telephony. 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing.
    http://dx.doi.org/10.1109/HPCC.and.EUC.2013.226

2012
  • Volker Diekert, Jonathan Kausch and Markus Lohrey. Logspace computations in Coxeter groups and graph groups. In Computational and combinatorial group theory and cryptography, vol. 582 of Contemp. Math., 77--94. Amer. Math. Soc., Providence, RI, 2012.
    http://dx.doi.org/10.1090/conm/582/11553

  • Robert H. Gilman, Alexei Myasnikov and Vitalii Roman'kov. Random equations in nilpotent groups. J. Algebra, 352 (2012) 192--214.
    http://dx.doi.org/10.1016/j.jalgebra.2011.11.007

  • Dima Grigoriev and Vladimir Shpilrain. No-leak authentication by the Sherlock Holmes method. Groups Complex. Cryptol., 4 (2012)(1) 177--189.
    http://dx.doi.org/10.1515/gcc-2012-0009

  • Maggie Habeeb, Delaram Kahrobaei and Vladimir Shpilrain. A secret sharing scheme based on group presentations and the word problem. In Computational and combinatorial group theory and cryptography, vol. 582 of Contemp. Math., 143--150. Amer. Math. Soc., Providence, RI, 2012.
    http://dx.doi.org/10.1090/conm/582/11557

  • Carl G. Jockusch, Jr. and Paul E. Schupp. Generic computability, Turing degrees, and asymptotic density. J. Lond. Math. Soc. (2), 85 (2012)(2) 472--490.
    http://dx.doi.org/10.1112/jlms/jdr051

  • Delaram Kahrobaei and Elizabeth Vidaurre. Publicly verifiable secret sharing using non-abelian groups. In Computational and combinatorial group theory and cryptography, vol. 582 of Contemp. Math., 175--179. Amer. Math. Soc., Providence, RI, 2012.
    http://dx.doi.org/10.1090/conm/582/11561

  • Alexei G. Miasnikov, Alexander Ushakov and Dong Wook Won. Power circuits, exponential algebra, and time complexity. Internat. J. Algebra Comput., 22 (2012)(6) 1250047, 51.
    http://dx.doi.org/10.1142/S0218196712500476

2011
  • Gilbert Baumslag, Nelly Fazio, Antonio R. Nicolosi, Vladimir Shpilrain and William E. Skeith, III. Generalized learning problems and applications to non-commutative cryptography (extended abstract). In Provable security, vol. 6980 of Lecture Notes in Comput. Sci., 324--339. Springer, Heidelberg, 2011.
    http://dx.doi.org/10.1007/978-3-642-24316-5_23

  • Volker Diekert and Alexei G. Myasnikov. Solving word problems in group extensions over infinite words. In Developments in language theory, vol. 6795 of Lecture Notes in Comput. Sci., 192--203. Springer, Heidelberg, 2011.
    http://dx.doi.org/10.1007/978-3-642-22321-1_17

  • Benjamin Fine, Maggie Habeeb, Delaram Kahrobaei and Gerhard Rosenberger. Aspects of nonabelian group based cryptography: a survey and open problems. JP J. Algebra Number Theory Appl., 21 (2011)(1) 1--40.

  • Robert H. Gilman, Alexei Myasnikov and Vitalii Roman'kov. Random equations in free groups. Groups Complex. Cryptol., 3 (2011)(2) 257--284.
    http://dx.doi.org/10.1515/gcc.2011.010

  • I. G. Lysenok and A. G. Myasnikov. A polynomial bound for solutions of quadratic equations in free groups. Tr. Mat. Inst. Steklova, 274 (2011)(Algoritmicheskie Voprosy Algebry i Logiki) 148--190.
    http://dx.doi.org/10.1134/S0081543811060101

  • Natalia Mosina and Alexander Ushakov. Strong law of large numbers on graphs and groups. Groups Complex. Cryptol., 3 (2011)(1) 67--103.
    http://dx.doi.org/10.1515/GCC.2011.004

  • Alexei Myasnikov and Denis Osin. Algorithmically finite groups. J. Pure Appl. Algebra, 215 (2011)(11) 2789--2796.
    http://dx.doi.org/10.1016/j.jpaa.2011.03.019

  • Alexei Myasnikov and Alexander Ushakov. Random van Kampen diagrams and algorithmic problems in groups. Groups Complex. Cryptol., 3 (2011)(1) 121--185.
    http://dx.doi.org/10.1515/GCC.2011.006

  • Alexei Myasnikov, Alexander Ushakov and Dong Wook Won. The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable. J. Algebra, 345 (2011) 324--342.
    http://dx.doi.org/10.1016/j.jalgebra.2011.07.024

  • Jad Naous, Michael Walfish, Antonio Nicolosi, David Mazières, Michael Miller and Arun Seehra. Verifying and enforcing network paths with icing. In Kenjiro Cho and Mark Crovella, eds., CoNEXT, 30. ACM, 2011.
    http://dl.acm.org/citation.cfm?id=2079296

2010200920082007
  • Alexandre V. Borovik, Alexei G. Myasnikov and Vladimir N. Remeslennikov. The conjugacy problem in amalgamated products. i. regular elements and black holes. Internat. J. Algebra Comput., 17 (2007)(7) 1299--1333.
    http://dx.doi.org/10.1142/S0218196707003652

  • Alexandre V. Borovik, Alexei G. Myasnikov and Vladimir N. Remeslennikov. Generic complexity of the conjugacy problem in {HNN}-extensions and algorithmic stratification of Miller's groups. Internat. J. Algebra Comput., 17 (2007)(5-6) 963--997.
    http://dx.doi.org/10.1142/S0218196707003913

  • Inna Bumagin, Olga Kharlampovich and Alexei Miasnikov. The isomorphism problem for finitely generated fully residually free groups. J. Pure Appl. Algebra, 208 (2007)(3) 961--977.
    http://dx.doi.org/10.1016/j.jpaa.2006.03.025

  • Nelly Fazio, Antonio Nicolosi and Duong Hieu Phan. Traitor tracing with optimal transmission rate. In Juan A. Garay, Arjen K. Lenstra, Masahiro, Mambo and Renè, eds., ISC, vol. 4779. Springer, 2007.

  • Michael J. Freedman and Antonio Nicolosi. Efficient private techniques for verifying social proximity. In John R. Douceur and Roger Wattenhofer, eds., IPTPS. 2007.
    http://www.iptps.org/papers-2007/FreedmanNicolosi.pdf

  • Ilya Kapovich, Igor Rivin, Paul Schupp and Vladimir Shpilrain. Densities in free groups and zk, visible points and test elements. Math. Res. Lett., 14 (2007)(2) 263--284.

  • Alex D. Myasnikov and Alexander Ushakov. Length based attack and braid groups: cryptanalysis of anshel-anshel-goldfeld key exchange protocol. In Public key cryptography---PKC 2007, vol. 4450 of Lecture Notes in Comput. Sci., 76--88. Springer, Berlin, 2007.
    http://dx.doi.org/10.1007/978-3-540-71677-8_6

2006
  • Michael Batty, Andrew J. Duncan and Samuel L. Braunstein. Extending the promise of the Deutsch-Jozsa-{H}øyer algorithm for finite groups. LMS J. Comput. Math., 9 (2006) 40--63 (electronic).

  • Alexandre V. Borovik and Alexei G. Myasnikov. Quotient tests and random walks in computational group theory. In Topological and asymptotic aspects of group theory, vol. 394 of Contemp. Math., 31--45. Amer. Math. Soc., Providence, RI, 2006.
    http://dx.doi.org/10.1090/conm/394/07432

  • Ivan Damgård, Nelly Fazio and Antonio Nicolosi. Non-interactive zero-knowledge from homomorphic encryption. In Shai Halevi and Tal Rabin, eds., TCC, vol. 3876 of Lecture Notes in Computer Science, 41--59. Springer, 2006.
    http://dx.doi.org/10.1007/11681878_3

  • Ivan Damgård, Nelly Fazio and Antonio Nicolosi. Non-iterative zero-knowledge from homomorphic encryption. In Theory of cryptography, vol. 3876 of Lecture Notes in Comput. Sci., 41--59. Springer, Berlin, 2006.
    http://dx.doi.org/10.1007/11681878_3

  • Joel David Hamkins and Alexei Miasnikov. The halting problem is decidable on a set of asymptotic probability one. Notre Dame J. Formal Logic, 47 (2006)(4) 515--524 (electronic).
    http://dx.doi.org/10.1305/ndjfl/1168352664

  • Ilya Kapovich, Paul Schupp and Vladimir Shpilrain. Generic properties of whitehead's algorithm and isomorphism rigidity of random one-relator groups. Pacific J. Math., 223 (2006)(1) 113--140.
    http://dx.doi.org/10.2140/pjm.2006.223.113

  • Martin Kreuzer, Alexei Myasnikov, Gerhard Rosenberger and Alexander Ushakov. Quotient tests and Gröbner bases. In Combinatorial group theory, discrete groups, and number theory, vol. 421 of Contemp. Math., 187--200. Amer. Math. Soc., Providence, RI, 2006.
    http://dx.doi.org/10.1090/conm/421/08037

  • A. D. Myasnikov and R. M. Haralick. A hybrid search algorithm for the Whitehead minimization problem. J. Symbolic Comput., 41 (2006)(7) 818--834.
    http://dx.doi.org/10.1016/j.jsc.2006.04.001

  • Alexei Myasnikov, Vladimir Shpilrain and Alexander Ushakov. Random subgroups of braid groups: an approach to cryptanalysis of a braid group based cryptographic protocol. In Public key cryptography---PKC 2006, vol. 3958 of Lecture Notes in Comput. Sci., 302--314. Springer, Berlin, 2006.
    http://dx.doi.org/10.1007/11745853_20

  • Vladimir Shpilrain. Hashing with polynomials. In Information security and cryptology---ICISC 2006, vol. 4296 of Lecture Notes in Comput. Sci., 22--28. Springer, Berlin, 2006.
    http://dx.doi.org/10.1007/11927587_4

  • Vladimir Shpilrain and Alexander Ushakov. The conjugacy search problem in public key cryptography: unnecessary and insufficient. Appl. Algebra Engrg. Comm. Comput., 17 (2006)(3-4) 285--289.
    http://dx.doi.org/10.1007/s00200-006-0009-6

  • Vladimir Shpilrain and Alexander Ushakov. A new key exchange protocol based on the decomposition problem. In Algebraic methods in cryptography, vol. 418 of Contemp. Math., 161--167. Amer. Math. Soc., Providence, RI, 2006.
    http://dx.doi.org/10.1090/conm/418/07954

  • Vladimir Shpilrain and Gabriel Zapata. Combinatorial group theory and public key cryptography. Appl. Algebra Engrg. Comm. Comput., 17 (2006)(3-4) 291--302.
    http://dx.doi.org/10.1007/s00200-006-0006-9

  • Vladimir Shpilrain and Gabriel Zapata. Using the subgroup membership search problem in public key cryptography. In Algebraic methods in cryptography, vol. 418 of Contemp. Math., 169--178. Amer. Math. Soc., Providence, RI, 2006.
    http://dx.doi.org/10.1090/conm/418/07955

2005
  • Ilya Kapovich and Paul Schupp. Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups. Math. Ann., 331 (2005)(1) 1--19.
    http://dx.doi.org/10.1007/s00208-004-0570-x

  • Alexei Myasnikov, Vladimir Shpilrain and Alexander Ushakov. A practical attack on a braid group based cryptographic protocol. In Advances in cryptology---CRYPTO 2005, vol. 3621 of Lecture Notes in Comput. Sci., 86--96. Springer, Berlin, 2005.
    http://dx.doi.org/10.1007/11535218_6