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

Selected publications

A selection of publications by ACC members. For preprints and additional publications consult members' websites (accessible from the Members web page by clicking on names), the Cryptology ePrint Archive, and arXiv.org.
Books
Computational and Combinatorial Group Theory and Cryptography, Benjamin Fine, Delaram Kahrobaei and Gerhard Rosenberger eds., Contemporary Mathematics, 582, American Mathematical Society 2012.
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.
Public Key Cryptography -- PKC 2011, Dario Catalano, Nelly Fazio, Rosario Gennaro and Antonio Nicolosi, editors), Lecture Notes in Computer Science 6571, Springer 2011.
Group-based Cryptography, Alexei Myasnikov, Vladimir Shpilrain and Alexander Ushakov, Advanced Courses in Mathematics - CRM Barcelona, Birkhäuser 2008.
Articles
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.

  • 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