Selected publications and preprints
Preprints
V. Shpilrain, Growth in products of matrices:
fastest, average, and generic, preprint.
G. Di Crescenzo, D. Kahrobaei, M. Khodjaeva, V. Shpilrain, Batch delegation of exponentiation in discrete logarithm and RSA groups, preprint.
V. Shpilrain, Problems in group theory motivated by cryptography, preprint.
D. Kahrobaei, H. Lam, V. Shpilrain,
Public key exchange using extensions by endomorphisms and matrices over a
Galois field, preprint.
2025
A. Olshanskii, V. Shpilrain, Linear average-case complexity of algorithmic problems in groups, J. Algebra 668 (2025), 390--419.
V. Shpilrain, Girth of the Cayley graph and Cayley hash functions, London Math. Soc. Newsletter 514 (2025), 27--30.
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 28 (2025), 423--430.
V. Shpilrain, B. Sosnovski, Cayley hashing with cookies, in: Future of Information and Communication Conference (FICC 2025), Springer Lecture Notes in Networks and Systems 1284 (2025), 706–718.
2024
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, Digital signature schemes using non-square matrices or scrap automorphisms, Int. J. Computer Math.: Computer Systems Theory 9 (2024), 65--73.
V. Shpilrain, On isomorphisms to a free group and beyond, Groups, Complexity, Cryptology 16 (2024).
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.
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)
J. Chen, D. Grigoriev, V. Shpilrain, Tropical cryptography III: digital signatures, J. Math. Cryptology 18 (2024), paper No. 20240005.
2023
V. Shpilrain, Average-case complexity of the Whitehead problem for a free group, Comm. Algebra 51 (2023), 799--806.
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.
2022
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)
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.
2021
D. Grigoriev and V. Shpilrain, RSA and redactable blockchains, Int. J. Computer Math.: Computer Systems Theory 6 (2021), 1--6.
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.
V. Shpilrain, Randomness and complexity in matrix groups, J. Math. Sci. 257 (2021), 919--925.
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, 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).
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.
2020
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.
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.
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).
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, 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.
2019
D. Grigoriev and
V. Shpilrain, Tropical cryptography II: extensions by homomorphisms, Comm. Algebra 47 (2019), 4224--4229.
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.
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.
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.
2018
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.
A. Gribov, D. Kahrobaei, V. Shpilrain, Practical private-key fully homomorphic encryption in rings, Groups, Complexity, and Cryptology 10 (2018), 17-27.
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.
2017
Patent: D. Kahrobaei, B. Cavallo, V. Shpilrain,
Method and apparatus for secure delegation of computation, U.S.
Patent number 9,825,926.
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.
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).
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.
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. 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.
2016
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.
2015
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.
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.
2014
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.
D. Grigoriev and
V. Shpilrain, Tropical cryptography, Comm.
Algebra 42 (2014), 2624-2632.
V. Shpilrain, Decoy-based information
security, Groups, Complexity, and Cryptology 6 (2014), 149-155.
2013
D. Grigoriev and
V. Shpilrain, Secure
information transmission based on physical principles, in: UCNC
2013, Lecture Notes Comp. Sc. 7956 (2013), 113-124.
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, 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.
2012
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.
2011
A.G.Myasnikov, V.
Shpilrain and A.Ushakov,
Non-commutative Cryptography and Complexity
of
Group-theoretic Problems, Amer. Math. Soc. Surveys and Monographs, 2011.
V. Shpilrain, Sublinear time
algorithms
in the theory of groups and semigroups, Illinois J. Math. 54 (2011), 187-197.
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.
2010
D. Grigoriev and
V. Shpilrain, Zero-knowledge authentication
schemes from actions on graphs, groups, or rings, Ann. Pure Appl. Logic 162 (2010),
194–200.
V. Shpilrain, Search and
witness problems in group theory, Groups, Complexity, and Cryptology 2 (2010), 231–246.
2009
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.
2008
A.G.Myasnikov, V.
Shpilrain and A.Ushakov,
Group-based cryptography, Birkhauser, 2008.
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
A.Ushakov,
An authentication scheme based on the twisted conjugacy problem, in:
ACNS 2008, Lecture Notes Comp. Sc. 5037 (2008), 366-372.
2007
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.
I. Kapovich, G. Levitt, P. Schupp,
and V.Shpilrain,
Translation equivalence in free groups, Trans. Amer. Math. Soc.
359 (2007), 1527-1546.
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.
C. M. Lam,
V. Shpilrain, and J.-T.Yu,
Recognizing and parametrizing curves isomorphic to a line, J. Symb.
Comput.
42 (2007), 751-756.
2006
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 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.
A.G.Myasnikov,
V. Shpilrain,
Some metric properties of automorphisms of groups, J. Algebra 304
(2006), 782-792.
V. Shpilrain,
Hashing with polynomials, in: ICISC 2006, Lecture Notes Comp. Sc., 4296 (2006),
22-28.
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.
2005
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 and J.-T.Yu, Test polynomials, retracts, and the
Jacobian conjecture, Contemp. Math., Amer. Math. Soc. 369 (2005), 253-259.
V. Bardakov,
V. Shpilrain, V. Tolstykh,
On the palindromic and primitive widths of a free
group, J. Algebra 285 (2005), 574-585.
V. Shpilrain,
Counting primitive elements of a free group,
Contemp. Math., Amer. Math. Soc. 372 (2005), 91-97.
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.
2004
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.
A.A.Mikhalev, V.
Shpilrain, and U.U.Umirbaev,
On isomorphism of Lie algebras
with one defining relation, Internat. J. Algebra and
Comput. 14 (2004), 389-393.
V. Shpilrain,
Assessing security of some
group based cryptosystems, Contemp. Math., Amer. Math. Soc.
360 (2004), 167-177.
2003
A.A.Mikhalev, V.
Shpilrain and J.-T. Yu,
Combinatorial Methods: Free Groups, Polynomials, and Free Algebras,
Springer, 2003, 315 pp.
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.
V. Shpilrain and J.-T. Yu,
Factor algebras of free algebras: on a problem of G. Bergman,
Bull. London Math. Soc. 35 (2003), 706-710.
A.G.Myasnikov,
V. Shpilrain,
Automorphic orbits in free groups, J.
Algebra 269 (2003), 18-27.
2002
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.D.Myasnikov,
A.G.Myasnikov and V.Shpilrain,
On
the Andrews-Curtis equivalence, Contemp. Math.,
Amer. Math. Soc. 296 (2002), 183-198.
V. Shpilrain and
J.-T.Yu,
Affine varieties with equivalent cylinders, J.
Algebra 251 (2002), 295-307.
A.Borovik, A.G.Myasnikov,
V. Shpilrain,
Measuring sets in infinite groups,
Contemp. Math., Amer. Math. Soc. 298 (2002), 21-42.
V. Shpilrain and J.-T.Yu,
Non-extendable isomorphisms between affine varieties, J. Pure Appl. Algebra 172 (2002), 285-291.
2001
V. Shpilrain and J.-T.
Yu, Embeddings
of hypersurfaces in affine spaces, J.Algebra
239 (2001), 161-173.
V. Shpilrain, Representing braids by automorphisms, Internat. J. Algebra and
Comput. 11 (2001), 773-778.
2000
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.
A.A.Mikhalev, V.
Shpilrain and J.-T. Yu,
Combinatorial
problems about free groups and algebras,
in: Lie algebras, rings
and related topics, 80-107. Springer, 2000.
V. Shpilrain and J.-T.
Yu, Peak
reduction technique in commutative algebra: a survey. Contemp. Math.,
Amer. Math. Soc. 264 (2000), 237-247.
1997-99
V. Shpilrain,
Non-commutative
determinants and automorphisms of groups, Comm. Algebra 25 (1997),
559-574.
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 and J.-T.
Yu,
On generators of polynomial algebras in two commuting or non-commuting
variables, J. Pure Appl. Algebra 132 (1998), 309-315.
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,
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,
Automorphisms
of one-relator groups, Math. Proc. Cambridge Phil. Soc. 26
(1999), 499--504.
V. Shpilrain and J.-T.
Yu, Embeddings
of curves in the plane, J.Algebra 217 (1999), 668-678.
G.Baumslag, A.G.Myasnikov
and V.Shpilrain,
Open problems in combinatorial group theory,
Contemp. Math., Amer. Math. Soc. 250 (1999), 1-27.
1993-96
N. Gupta, V.
Shpilrain,
Nielsen's commutator test for two-generator groups,
Math. Proc. Cambridge Phil. Soc. 114 (1993), 295-301.
V. Shpilrain,
On generators of L/R^2 Lie algebras, Proc. Amer. Math. Soc.
119 (1993), 1039-1043.
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.
A.A.Mikhalev, V.
Shpilrain and A.A.Zolotyh,
Subalgebras of free algebras, Proc. Amer. Math. Soc.
124 (1996), 1977-1984.
V. Shpilrain, Magnus embeddings
for semigroups, Internat. J. Algebra and Comput. 6 (1996),
155-163.