Selected publications and preprints

Preprints

V. Shpilrain, B. Sosnovski, Cayley hashing with cookies, preprint.
V. Shpilrain, Complexity of some algorithmic problems in groups: a survey, preprint.
J. Chen, D. Grigoriev, V. Shpilrain, Tropical cryptography III: digital signatures, preprint.
V. Shpilrain, On isomorphism to a free group and beyond, preprint.
A. Olshanskii, V. Shpilrain, Linear average-case complexity of algorithmic problems in groups, preprint.
N. Rahman, V. Shpilrain, MOBS (Matrices Over Bit Strings) public key exchange, preprint. Python code   Challenge (You need Python 3.8.0 or higher to run it)
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.

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).

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).
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

book:  
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), 409417.
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

book:  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), 194200.
V. Shpilrain, Search and witness problems in group theory, Groups, Complexity, and Cryptology 2 (2010), 231246.

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

book:  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), 252260.
V. Shpilrain, Cryptanalysis of Stickel's key exchange scheme, in: Computer Science in Russia 2008, Lecture Notes Comp. Sc. 5010 (2008), 283288.
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

book:  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.