If you have a general idea about my research, you can go straight to my preprints. Or, perhaps, you would like to see a (more or less) complete list of my papers since 1993. You can download most of them.

If you are here for the first time, I hope the following
brief description of my research might be of interest.

I have done research in several areas of mathematics and theoretical computer science;
currently I am mostly working on cryptography (more specifically, on
using
non-commutative groups in public key cryptography). A naturally related area is algorithmic group theory, in
particular complexity of group-theoretic problems.

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. I occasionally 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.

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.

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.

A.G.Myasnikov, V. Shpilrain and A.Ushakov,

A.G.Myasnikov, V. Shpilrain and A.Ushakov,

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, D. Kahrobaei, M. Khodjaeva, 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, D. Kahrobaei, M. Khodjaeva, 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. Wood, D. Kahrobaei, V. Shpilrain, A. Mostashari, K. Najarian,* Private naive Bayes classification
of personal biomedical data: application in cancer data analysis,* preprint.

A. Gribov, K. Horan, J. Gryak, D. Kahrobaei, R.
Soroushmehr, V. Shpilrain, K. Najarian,*
Medical diagnostics based on encrypted medical data,* preprint.

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. Springer 2018, to appear.

V. Shpilrain, *Problems in group theory motivated by cryptography,* preprint.

A. Gribov, D. Kahrobaei, V. Shpilrain, *Practical private-key fully homomorphic encryption in rings,,* Groups, Complexity, and Cryptology ** 10 ** (2018).

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 (at least 30) 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 a thing for *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. Recently, braid groups have been also used in cryptography.

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.

V. Shpilrain, * Randomness and complexity in matrix groups,* preprint.

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. If you would like to learn more about these problems, you can download this file.

V. Shpilrain and J.-T. Yu,

A. van den Essen, V. Shpilrain,

V. Shpilrain,

V. Shpilrain and J.-T. Yu,

V. Shpilrain and J.-T. Yu,

V.Drensky, V. Shpilrain and J.-T. Yu,

V. Shpilrain and J.-T. Yu,

V. Shpilrain and J.-T. Yu,

V. Shpilrain and J.-T. Yu,

V. Shpilrain and J.-T. Yu,

V. Shpilrain and J.-T.Yu,

L. Makar-Limanov, P. van Rossum, V. Shpilrain and J.-T.Yu,

V. Shpilrain and J.-T.Yu,

L. Makar-Limanov, V. Shpilrain and J.-T.Yu,

C. M. Lam, V. Shpilrain, and J.-T.Yu,