Research and publications

  If you have a general idea about my research, you can go straight to my preprints. There is also a (more or less) complete list of my papers since 1993. You can download most of them.
  In any case, I hope the following brief description of my research might be of interest.
 I have done research in several areas of pure and applied mathematics, from group theory to complexity theory to information security. Currently I am mostly working on applications of group theory and statistics to information security. More specifically, my research right now is focused on post-quantum cryptography, i.e., I am trying to create various cryptographic protocols secure against attackers who can use a (still hypothetical) quantum computer.
  A naturally related area is algorithmic problems in algebra and group theory and their complexity, including ``traditional" worst-case complexity as well as the average-case complexity and generic-case complexity (i.e., complexity on random inputs).
  Previously, I have been splitting most of my time between combinatorial group theory and affine algebraic geometry. These areas may look unrelated to the naked eye but, as it turns out, they have a lot in common.  

Books:

A. A. Mikhalev, V. Shpilrain and J.-T. Yu, Combinatorial Methods: Free Groups, Polynomials, and Free Algebras, Springer, New York, 2003.
A.G. Myasnikov, V. Shpilrain and A. Ushakov, Group-based Cryptography, Birkhauser, 2008.
A.G. Myasnikov, V. Shpilrain and A. Ushakov, Non-commutative Cryptography and Complexity of Group-theoretic Problems, Amer. Math. Soc. Surveys and Monographs, 2011.
F. Bassino, I. Kapovich, M. Lohrey, A.G. Myasnikov, C. Nicaud, A. Nikolaev, I. Rivin, V. Shpilrain, A. Ushakov, P. Weil, Complexity and Randomness in Group Theory: GAGTA Book 1, Walter de Gruyter, 2020.

These are my publications related to information security:

Patent: D. Kahrobaei, B. Cavallo, V. Shpilrain, Method and apparatus for secure delegation of computation, U.S. Patent number 9,825,926.
Patent: D. Kahrobaei, H. Lam, V. Shpilrain, System and method for private-key fully homomorphic encryption and private search between rings, U.S. Patent number 9,942,031.

V. Shpilrain, Assessing security of some group based cryptosystems, Contemp. Math., Amer. Math. Soc. 360 (2004), 167-177.
V. Shpilrain and A.Ushakov, Thompson's group and public key cryptography, Lecture Notes Comp. Sc. 3531 (2005), 151-164.
A. G. Myasnikov, V. Shpilrain and A.Ushakov, A practical attack on some braid group based cryptographic protocols, in CRYPTO 2005, Lecture Notes Comp. Sc. 3621 (2005), 86-96.
A. G. Myasnikov, V. Shpilrain and A.Ushakov, Random subgroups of braid groups: an approach to cryptanalysis of a braid group based cryptographic protocol, in PKC 2006, Lecture Notes Comp. Sc. 3958 (2006), 302-314.
V. Shpilrain and A.Ushakov, The conjugacy search problem in public key cryptography: unnecessary and insufficient, Applicable Algebra in Engineering, Communication and Computing 17 (2006), 285-289.
V. Shpilrain and G.Zapata, Combinatorial group theory and public key cryptography, Applicable Algebra in Engineering, Communication and Computing 17 (2006), 291-302.
V. Shpilrain and G. Zapata, Using the subgroup membership search problem in public key cryptography, Contemp. Math., Amer. Math. Soc. 418 (2006), 169-179.
V. Shpilrain and A.Ushakov, A new key exchange protocol based on the decomposition problem, Contemp. Math., Amer. Math. Soc. 418 (2006), 161-167.
V. Shpilrain, Hashing with polynomials, in: ICISC 2006, Lecture Notes Comp. Sc. 4296 (2006), 22-28.
V. Shpilrain and A.Ushakov, An authentication scheme based on the twisted conjugacy problem, in: ACNS 2008, Lecture Notes Comp. Sc. 5037 (2008), 366-372.
D. Osin and V. Shpilrain, Public key encryption and encryption emulation attacks, version for group theorists     version for cryptographers, in: Computer Science in Russia 2008, Lecture Notes Comp. Sc. 5010 (2008), 252–260.
V. Shpilrain, Cryptanalysis of Stickel's key exchange scheme, in: Computer Science in Russia 2008, Lecture Notes Comp. Sc. 5010 (2008), 283–288.
V. Shpilrain and G. Zapata, Using decision problems in public key cryptography, Groups, Complexity, and Cryptology 1 (2009), 33-49.
D. Grigoriev and V. Shpilrain, Authentication from matrix conjugation, Groups, Complexity, and Cryptology 1 (2009), 199-206.
D. Grigoriev and V. Shpilrain, Zero-knowledge authentication schemes from actions on graphs, groups, or rings, Ann. Pure Appl. Logic 162 (2010), 194–200.
G. Baumslag, N. Fazio, A. Nicolosi, V. Shpilrain, W. E. Skeith III, Generalized learning problems and applications to non-commutative cryptography, in: ProvSec 2011, Lecture Notes Comp. Sc. 6980 (2011), 324-339.
D. Grigoriev and V. Shpilrain, No-leak authentication by the Sherlock Holmes method, Groups, Complexity, and Cryptology 4 (2012), 177-189.
M. Habeeb, D. Kahrobaei, and V. Shpilrain, A secret sharing scheme based on group presentations and the word problem, Contemp. Math., Amer. Math. Soc. 582 (2012), 143-150.
D. Grigoriev and V. Shpilrain, Secrecy without one-way functions, Groups, Complexity, and Cryptology 5 (2013), 31-52.
D. Kahrobaei, C. Koupparis, and V. Shpilrain, Public key exchange using matrices over group rings, Groups, Complexity, and Cryptology 5 (2013), 97-115.
M. Habeeb, D. Kahrobaei, C. Koupparis, and V. Shpilrain, Public key exchange using semidirect product of (semi)groups, in: ACNS 2013, Lecture Notes Comp. Sc. 7954 (2013), 475-486.
D. Grigoriev and V. Shpilrain, Secure information transmission based on physical principles, in: UCNC 2013, Lecture Notes Comp. Sc. 7956 (2013), 113-124.
D. Grigoriev and V. Shpilrain, Tropical cryptography, Comm. Algebra 42 (2014), 2624-2632.
D. Grigoriev and V. Shpilrain, Yao's millionaires' problem and decoy-based public key encryption by classical physics, Int. J. Foundations Comp. Sci. 25 (2014), 409–417.
V. Shpilrain, Decoy-based information security, Groups, Complexity, and Cryptology 6 (2014), 149-155.
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.
D. Kahrobaei, H. Lam, V. Shpilrain, Public key exchange using extensions by endomorphisms and matrices over a Galois field, preprint.
B. Cavallo, G. Di Crescenzo, D. Kahrobaei, V. Shpilrain, Efficient and secure delegation of group exponentiation to a single server, in: RFIDsec 2015, Lecture Notes Comp. Sc. 9440 (2015), 156-173.
L. Bromberg, V. Shpilrain, A. Vdovina, Navigating in the Cayley graph of SL_2(F_p) and applications to hashing, Semigroup Forum 94 (2017), 314-324.
D. Kahrobaei and V. Shpilrain, Using semidirect product of (semi)groups in public key cryptography, in: CiE 2016, Lecture Notes Comp. Sc. 9709 (2016), 132-141.
V. Shpilrain, B.Sosnovski, Compositions of linear functions and applications to hashing, Groups, Complexity, and Cryptology 8 (2016), 155-161.
D. Grigoriev and V. Shpilrain, Secure multiparty computation without one-way functions, Journal of Logics and their Applications 4 (2017), 993--1010.
D. Grigoriev, L. Kish, V. Shpilrain, Yao's millionaires' problem and public-key encryption without computational assumptions, Int. J. Foundations Comp. Sci. 28 (2017), 379--389.
G. Di Crescenzo, M. Khodjaeva, D. Kahrobaei, V. Shpilrain, Computing Multiple Exponentiations in Discrete Log and RSA Groups: From Batch Verification to Batch Delegation, in: IEEE CNS 2017, 3rd Workshop on Security and Privacy in the Cloud (SPC).
G. Di Crescenzo, M. Khodjaeva, D. Kahrobaei, V. Shpilrain, Practical and Secure Outsourcing of Discrete Log Group Exponentiation to a Single Malicious Server, in: CCSW 2017, 9th ACM Cloud Computing Security Workshop.
A. Gribov, D. Kahrobaei, V. Shpilrain, Practical private-key fully homomorphic encryption in rings,, Groups, Complexity, and Cryptology 10 (2018), 17-27.

V. Shpilrain, Problems in group theory motivated by cryptography, preprint.
G. Di Crescenzo, D. Kahrobaei, M. Khodjaeva, V. Shpilrain, Efficient and secure delegation to a single malicious server: exponentiation over non-abelian groups, in: International Congress on Mathematical Software -- ICMS 2018, Lecture Notes Comp. Sc. 10931 (2018), 137--146.
A. Wood, V. Shpilrain, K. Najarian, A. Mostashari, D. Kahrobaei, Private-key fully homomorphic encryption for private classification, in: International Congress on Mathematical Software -- ICMS 2018, Lecture Notes Comp. Sc. 10931 (2018), 475--481.
M. Bessonov, D. Grigoriev, V. Shpilrain, A framework for unconditionally secure public-key encryption (with possible decryption errors), in: International Congress on Mathematical Software -- ICMS 2018, Lecture Notes Comp. Sc. 10931 (2018), 45--54.
D. Grigoriev and V. Shpilrain, Tropical cryptography II: extensions by homomorphisms, Comm. Algebra 47 (2019), 4224--4229.
A. Gribov, K. Horan, J. Gryak, D. Kahrobaei, R. Soroushmehr, V. Shpilrain, K. Najarian, Medical diagnostics based on encrypted medical data, in: Bio-inspired Information and Communications Technologies (BICT 2019), Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering 289 (2019), 98--111.
A. Wood, D. Kahrobaei, V. Shpilrain, K. Najarian, Private naive Bayes classification of personal biomedical data: application in cancer data analysis, Computers in Biology and Medicine 105 (2019), 144--150.
G. Di Crescenzo, D. Kahrobaei, M. Khodjaeva, V. Shpilrain, Batch delegation of exponentiation in discrete logarithm and RSA groups, preprint.
G. Di Crescenzo, M. Khodjaeva, D. Kahrobaei, V. Shpilrain, Secure delegation to a single malicious server: exponentiation in RSA-type groups, in: IEEE Conference on Communications and Network Security (CNS 2019), IEEE Xplore Digital Library.
M. Bessonov, D. Grigoriev, V. Shpilrain, Probabilistic solution of Yao's millionaires' problem, in: Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy, etc. Methods and Their Applications, pp. 401--411. Springer 2020.
G. Di Crescenzo, D. Kahrobaei, M. Khodjaeva, V. Shpilrain, Secure and efficient delegation of elliptic curve pairing, in: ACNS 2020, Lecture Notes Comp. Sc. 12147 (2020).
G. Di Crescenzo, D. Kahrobaei, M. Khodjaeva, V. Shpilrain, Delegating a product of group exponentiations with application to signature schemes, in: Number-Theoretic Methods in Cryptology (NuTMiC 2019), J. Math. Cryptology 14 (2020), 438--459.
G. Di Crescenzo, D. Kahrobaei, M. Khodjaeva, V. Shpilrain, Efficient and secure delegation of exponentiation in general groups to a single malicious server, Math. in Computer Science 14 (2020), 641-–656.
D. Grigoriev and V. Shpilrain, RSA and redactable blockchains, Int. J. Computer Math.: Computer Systems Theory 6 (2021), 1--6.
M. Bessonov, D. Grigoriev, V. Shpilrain, Probability theory and public-key cryptography, Int. J. Computer Math.: Computer Systems Theory 6 (2021), 285--290.
G. Di Crescenzo, D. Kahrobaei, M. Khodjaeva, V. Shpilrain, Secure and efficient delegation of pairings with online inputs, in CARDIS 2020, Lecture Notes Comp. Sc. 12609 (2021), 84--98.
N. Rahman, V. Shpilrain, MAKE: a Matrix Action Key Exchange, J. Math. Cryptology 16 (2022), 64--72. Python code   Challenge (You need Python 3.8.0 or higher to run it)
N. Rahman, V. Shpilrain, MOBS (Matrices Over Bit Strings) public key exchange, La Mathematica 3 (2024), 1198–1206. Python code   Challenge (You need Python 3.8.0 or higher to run it)
D. Kahrobaei, V. Shpilrain, A note on fully homomorphic encryption of real-life data, Int. J. Computer Math.: Computer Systems Theory 6 (2021), 381--385.
G. Di Crescenzo, M. Khodjaeva, V. Shpilrain, D. Kahrobaei, R. Krishnan, Single-server delegation of ring multiplications from quasilinear-time clients, in: 14th International Conference on Security of Information and Networks (SINCONF 2021).
G. Di Crescenzo, M. Khodjaeva, D. Kahrobaei, V. Shpilrain, A survey on delegated computation, in: Developments in Language Theory (DLT 2022), Lecture Notes Comp. Sc. 13257 (2022), 33--53.
V. Roman'kov, A. Ushakov, V. Shpilrain, Algebraic and quantum attacks on two digital signature schemes, J. Math. Cryptology 17 (2023), paper No. 20220023.
G. Di Crescenzo, M. Khodjaeva, T. Chen, R. Krishnan, D. Shur, D. Kahrobaei, V. Shpilrain, On single-server delegation of RSA, in: 15th International Conference on Security for Information Technology and Communications (SecITC 2022), Lecture Notes Comp. Sc. 13809 (2023), 81--101.
J. Chen, D. Grigoriev, V. Shpilrain, Digital signature schemes using non-square matrices or scrap automorphisms, Int. J. Computer Math.: Computer Systems Theory 9 (2024), 65--73.
D. Grigoriev, I. Ilmer, A. Ovchinnikov, V. Shpilrain, BASS: Boolean Automorphisms Signature Scheme, in: 16th International Conference on Security for Information Technology and Communications (SecITC 2023), Lecture Notes Comp. Sc. 14534 (2024), 1--12.
J. Chen, D. Grigoriev, V. Shpilrain, Tropical cryptography III: digital signatures, J. Math. Cryptology 18 (2024), paper No. 20240005.
V. Shpilrain, Girth of the Cayley graph and Cayley hash functions, London Math. Soc. Newsletter 514 (2025), 27--30.
V. Shpilrain, B. Sosnovski, Cayley hashing with cookies, in: Future of Information and Communication Conference (FICC 2025), Springer Lecture Notes in Networks and Systems, to appear.

Statistical and asymptotic group theory

  During 2001-2007, I have participated in several projects in statistical and asymptotic group theory, starting with an attempt to expand the very definition of a probability measure from finite to infinite groups (see paper #1 on the list below).
  Together with I. Kapovich, A.G.Myasnikov, and P. Schupp, I have applied probabilistic methods to the study of generic- and average-case complexity of various decision problems in group theory. This direction of research brings together mathematics, statistics, and theoretical computer science by providing statistical analysis and, at the same time, rigorous mathematical justification of the successful performance of various non-deterministic algorithms widely used in real-life applications, in particular, to cryptography.

These are my papers on statistical and asymptotic group theory:

A.Borovik, A.G.Myasnikov, V. Shpilrain, Measuring sets in infinite groups,   Contemp. Math., Amer. Math. Soc. 298 (2002), 21-42.  
I. Kapovich, A. G. Myasnikov, P. Schupp, and V.Shpilrain, Generic-case complexity, decision problems in group theory and random walks, J. Algebra 264 (2003), 665-694.
I. Kapovich, A. G. Myasnikov, P. Schupp, and V.Shpilrain, Average-case complexity and decision problems in group theory, Advances in Math. 190 (2005), 343-359.
V. Shpilrain, Counting primitive elements of a free group, Contemp. Math., Amer. Math. Soc. 372 (2005).
I. Kapovich, P. Schupp, and V.Shpilrain, Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups, Pacific J. Math. 223 (2006), 113-140.
A.G.Myasnikov, V. Shpilrain, Some metric properties of automorphisms of groups, J. Algebra 304 (2006), 782-792.

I. Kapovich, I. Rivin, P. Schupp, and V.Shpilrain, Densities in free groups and Z^k, visible points and test elements, Math. Res. Lett. 14 (2007), 263-284.
V. Shpilrain, Sublinear time algorithms in the theory of groups and semigroups, Illinois J. Math. 54 (2011), 187-197.
V. Shpilrain, Randomness and complexity in matrix groups, J. Math. Sci. 257 (2021), 919--925.
V. Shpilrain, Average-case complexity of the Whitehead problem for a free group, Comm. Algebra 51 (2023), 799--806.
V. Shpilrain, Complexity of some algorithmic problems in groups: a survey, in: Finitely presented groups, with applications in post-quantum cryptography and artificial intelligence, pp. 138-152. De Gruyter, 2024.
A. Olshanskii, V. Shpilrain, Linear average-case complexity of algorithmic problems in groups, J. Algebra 668 (2025), 390--419.
V. Shpilrain, Growth in products of matrices: fastest, average, and generic, preprint.
L. Hyde, S. O'Connor, V. Shpilrain, Orbit-blocking words and the average-case complexity of Whitehead's problem in the free group of rank 2, J. Group Theory, to appear.


Combinatorial group theory

  During 1993-2000, my research in group theory was primarily focused on free groups and their automorphisms; in particular, on various properties of orbits under the action of the group of automorphisms of a free group. Especially fruitful and inspiring to many people turned out to be the concept of a test element introduced in paper #2 on the list below. The idea was to distinguish, for example, automorphisms among arbitrary endomorphisms by means of their action on a single element, a test element. The same goal of distinguishing automorphisms, but in a different context, led me to introducing non-commutative determinants (see paper #5 on the list below).
  I also have interest in braid groups. I find the class of braid groups fascinating because it brings together many different areas of mathematics (and physics!): algebra, topology, differential equations, to name just a few. Braid groups have been also used in cryptography, as platforms for several public-key protocols.
  Occasionally, I looked also at free associative and Lie algebras for inspiration. Many combinatorial properties of free Lie algebras are very similar to those of free groups, but to work with free Lie algebras is easier, so I occasionally turned to free Lie algebras to try one or another conjecture originally made for free groups.

These are my papers on combinatorial group theory:

N. Gupta, V. Shpilrain, Nielsen's commutator test for two-generator groups, Math. Proc. Cambridge Phil. Soc. 114 (1993), 295-301.
V. Shpilrain, Recognizing automorphisms of the free groups, Arch. Math. 62 (1994), 385-392.
V. Shpilrain, Test elements for endomorphisms of free groups and algebras, Israel J. Math. 92 (1995), 307-316.
V. Shpilrain, On monomorphisms of free groups, Arch. Math. 64 (1995), 465-470.
V. Shpilrain, Non-commutative determinants and automorphisms of groups, Comm. Algebra 25 (1997), 559-574.
V. Shpilrain, Fixed points of endomorphisms of a free metabelian group, Math. Proc. Cambridge Phil. Soc. 123 (1998), 77-85.
V. Shpilrain, Generalized primitive elements of a free group, Arch. Math. 71 (1998), 270-278.
V. Shpilrain, Automorphisms of one-relator groups, Math. Proc. Cambridge Phil. Soc. 26 (1999), 499--504.
V. Shpilrain, Representing braids by automorphisms,  Internat. J. Algebra and Comput. 11 (2001), 773-778.
A.D.Myasnikov, A.G.Myasnikov and V.Shpilrain, On the Andrews-Curtis equivalence,  Contemp. Math., Amer. Math. Soc. 296 (2002), 183-198.
G.Baumslag, A.G.Myasnikov and V.Shpilrain, Open problems  in combinatorial group theory. Second edition, Contemp. Math., Amer. Math. Soc. 296 (2002), 1-38.
A.G.Myasnikov, V. Shpilrain, Automorphic orbits in free groups,  J. Algebra 269 (2003), 18-27.
V. Bardakov, V. Shpilrain, V. Tolstykh, On the palindromic and primitive widths of a free group, J. Algebra 285 (2005), 574-585.
I. Kapovich, G. Levitt, P. Schupp, and V.Shpilrain, Translation equivalence in free groups, Trans. Amer. Math. Soc. 359 (2007), 1527-1546.
V. Shpilrain, Search and witness problems in group theory, Groups, Complexity, and Cryptology 2 (2010), 231–246.
A. Chorna, K. Geller, and V. Shpilrain, On two-generator subgroups of SL_2(Z), SL_2(Q), and SL_2(R), J. Algebra 478 (2017), 367-381.
A. Olshanskii, V. Shpilrain, Linear average-case complexity of algorithmic problems in groups, preprint.
V. Shpilrain, On isomorphisms to a free group and beyond, Groups, Complexity, Cryptology 16 (2024).


Affine algebraic geometry

  Affine algebraic geometry is a fascinating area of mathematics that studies polynomials and polynomial mappings. An interesting thing about this area is that most of the research here is focused on five or six outstanding problems. The statements of these problems are rather elementary and can be understood by an average high school student. However, some methods that have been employed so far for attacking these problems are rather sophisticated, and, more importantly, they come from several different areas of mathematics, which stimulates additional interest.

These are my papers on affine algebraic geometry:

V. Shpilrain and J.-T. Yu, Polynomial automorphisms and Groebner reductions, J. Algebra 197 (1997), 546--558.
A. van den Essen, V. Shpilrain, Some combinatorial questions about polynomial mappings, J. Pure Appl. Algebra 119 (1997), 47-52.
V. Shpilrain, Combinatorial methods: from groups to polynomial algebras, Groups '97  Bath/St. Andrews, Vol. 2  (Bath, 1997), 679-688,  London Math. Soc. Lecture Note Ser. 261, Cambridge Univ. Press, Cambridge, 1999.
V. Shpilrain and J.-T. Yu, Embeddings of curves in the plane, J.Algebra 217 (1999), 668-678.
V. Shpilrain and J.-T. Yu, Polynomial retracts and the Jacobian conjecture, Trans. Amer. Math. Soc. 352 (2000), 477-484.
V.Drensky, V. Shpilrain and J.-T. Yu, On the density of the set of generators of a polynomial algebra, Proc. Amer. Math. Soc. 128 (2000), 3465-3469.
V. Shpilrain and J.-T. Yu, Peak reduction technique in commutative algebra: a survey. Contemp. Math., Amer. Math. Soc. 264 (2000), 237-247.
V. Shpilrain and J.-T. Yu, Embeddings of hypersurfaces in affine spaces,  J.Algebra 239 (2001), 161-173.
V. Shpilrain and J.-T. Yu, Non-extendable isomorphisms between affine varieties,  J. Pure Appl. Algebra 172 (2002), 285-291.
V. Shpilrain and J.-T. Yu, Affine varieties with equivalent cylinders,  J. Algebra 251 (2002), 295-307.
V. Shpilrain and J.-T.Yu, Birational morphisms of the plane, Proc. Amer. Math. Soc. 132 (2004), 2511-2515.
L. Makar-Limanov, P. van Rossum, V. Shpilrain and J.-T.Yu, The stable equivalence and cancellation problems, Comment. Math. Helv. 79 (2004), 341-349.
V. Shpilrain and J.-T.Yu, Test polynomials, retracts, and the Jacobian conjecture, Contemp. Math., Amer. Math. Soc. 369 (2005), 253-259.
L. Makar-Limanov, V. Shpilrain and J.-T.Yu, Equivalence of polynomials under automorphisms of K[x,y], J. Pure Appl. Algebra 209 (2007), 71-78.
C. M. Lam, V. Shpilrain, and J.-T.Yu, Recognizing and parametrizing curves isomorphic to a line, J. Symb. Comput. 42 (2007), 751-756.