BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vladimir Shpilrain

Vladimir Shpilrain appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Cryptography and Securitymath.GRmath.AGmath.ACmath.RAComputational ComplexityInformation Theorymath.ITmath.LOphysics.class-phphysics.comp-phphysics.pop-ph

Catalog footprint

What is connected

23works
12topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

23 published item(s)

preprint2022arXiv

Average-case complexity of the Whitehead problem for a free group

The worst-case complexity of group-theoretic algorithms has been studied for a long time. Generic-case complexity, or complexity on random inputs, was introduced and studied relatively recently. In this paper, we address the average-case complexity (i.e., the expected runtime) of algorithms that solve a well-known problem, the Whitehead problem in a free group, which is: given two elements of a free group, find out whether there is an automorphism that takes one element to the other. First we address a special case of the Whitehead problem, namely deciding if a given element of a free group is part of a free basis. We show that there is an algorithm that, on a cyclically reduced input word, solves this problem and has constant (with respect to the length of the input) average-case complexity. For the general Whitehead problem, we show that the classical Whitehead algorithm has linear average-case complexity if the rank of the free group is 2. We argue that the same should be true in a free group of any rank but point out obstacles to establishing this general result.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

RSA and redactable blockchains

A blockchain is redactable if a private key holder (e.g. a central authority) can change any single block without violating integrity of the whole blockchain, but no other party can do that. In this paper, we offer a simple method of constructing redactable blockchains inspired by the ideas underlying the well-known RSA encryption scheme. Notably, our method can be used in conjunction with any reasonable hash function that is used to build a blockchain. Public immutability of a blockchain in our construction is based on the computational hardness of the RSA problem and not on properties of the underlying hash function. Corruption resistance is based on the computational hardness of the discrete logarithm problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Using semidirect product of (semi)groups in public key cryptography

In this survey, we describe a general key exchange protocol based on semidirect product of (semi)groups (more specifically, on extensions of (semi)groups by automorphisms), and then focus on practical instances of this general idea. This protocol can be based on any group or semigroup, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when this protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. The focus then shifts to selecting an optimal platform (semi)group, in terms of security and efficiency. We show, in particular, that one can get a variety of new security assumptions by varying an automorphism used for a (semi)group extension.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Navigating in the Cayley graph of $SL_2(F_p)$ and applications to hashing

Cayley hash functions are based on a simple idea of using a pair of (semi)group elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with $2 \times 2$ matrices over $F_p$. Since there are many known pairs of $2 \times 2$ matrices over $Z$ that generate a free monoid, this yields numerous pairs of matrices over $F_p$, for a sufficiently large prime $p$, that are candidates for collision-resistant hashing. However, this trick can "backfire", and lifting matrix entries to $Z$ may facilitate finding a collision. This "lifting attack" was successfully used by Tillich and Zémor in the special case where two matrices $A$ and $B$ generate (as a monoid) the whole monoid $SL_2(Z_+)$. However, in this paper we show that the situation with other, "similar", pairs of matrices from $SL_2(Z)$ is different, and the "lifting attack" can (in some cases) produce collisions in the group generated by $A$ and $B$, but not in the positive monoid. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from $SL_2(F_p)$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Public Key Exchange Using Matrices Over Group Rings

We offer a public key exchange protocol in the spirit of Diffie-Hellman, but we use (small) matrices over a group ring of a (small) symmetric group as the platform. This "nested structure" of the platform makes computation very efficient for legitimate parties. We discuss security of this scheme by addressing the Decision Diffie-Hellman (DDH) and Computational Diffie-Hellman (CDH) problems for our platform.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Public key exchange using semidirect product of (semi)groups

In this paper, we describe a brand new key exchange protocol based on a semidirect product of (semi)groups (more specifically, on extension of a (semi)group by automorphisms), and then focus on practical instances of this general idea. Our protocol can be based on any group, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when our protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. Here we also suggest a particular non-commutative semigroup (of matrices) as the platform and show that security of the relevant protocol is based on a quite different assumption compared to that of the standard Diffie-Hellman protocol.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Secrecy without one-way functions

We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious "$P \ne NP$" conjecture. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal "intermediate results" of a computation. For example, when we compute the sum of $k$ numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of Yao's "millionaires' problem". Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our (bit) commitment scheme for 3 parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a "dummy" (e.g., a computer) as the third party. We explain how our concept of a "dummy" is different from a well-known concept of a "trusted third party". We also suggest a protocol, without using a one-way function, for "mental poker", i.e., a fair card dealing (and playing) over distance. We also propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Yao's millionaires' problem and decoy-based public key encryption by classical physics

We use various laws of classical physics to offer several solutions of Yao's millionaires' problem without using any one-way functions. We also describe several informationally secure public key encryption protocols, i.e., protocols secure against passive computationally unbounded adversary. This introduces a new paradigm of decoy-based cryptography, as opposed to "traditional" complexity-based cryptography. In particular, our protocols do not employ any one-way functions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Secret Sharing Scheme Based on Group Presentations and the Word Problem

A (t,n)-threshold secret sharing scheme is a method to distribute a secret among n participants in such a way that any t participants can recover the secret, but no t-1 participants can. In this paper, we propose two secret sharing schemes using non-abelian groups. One scheme is the special case where all the participants must get together to recover the secret. The other one is a (t,n)-threshold scheme that is a combination of Shamir's scheme and the group-theoretic scheme proposed in this paper.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Sublinear time algorithms in the theory of groups and semigroups

Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a small portion of the input. The most typical situation where sublinear time algorithms are considered is property testing. There are several interesting contexts where one can test properties in sublinear time. A canonical example is graph colorability. To tell that a given graph is not k-colorable, it is often sufficient to inspect just one vertex with incident edges: if the degree of a vertex is greater than k, then the graph is not k-colorable. It is a challenging and interesting task to find algebraic properties that could be tested in sublinear time. In this paper, we address several algorithmic problems in the theory of groups and semigroups that may admit sublinear time solution, at least for "most" inputs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Authentication from matrix conjugation

We propose an authentication scheme where forgery (a.k.a. impersonation) seems infeasible without finding the prover's long-term private key. The latter would follow from solving the conjugacy search problem in the platform (noncommutative) semigroup, i.e., to recovering X from X^{-1}AX and A. The platform semigroup that we suggest here is the semigroup of nxn matrices over truncated multivariable polynomials over a ring.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Search and witness problems in group theory

Decision problems are problems of the following nature: given a property P and an object O, find out whether or not the object O has the property P. On the other hand, witness problems are: given a property P and an object O with the property P, find a proof of the fact that O indeed has the property P. On the third hand(?!), search problems are of the following nature: given a property P and an object O with the property P, find something "material" establishing the property P; for example, given two conjugate elements of a group, find a conjugator. In this survey our focus is on various search problems in group theory, including the word search problem, the subgroup membership search problem, the conjugacy search problem, and others.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Thompson's group and public key cryptography

Recently, several public key exchange protocols based on symbolic computation in non-commutative (semi)groups were proposed as a more efficient alternative to well established protocols based on numeric computation. Notably, the protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al. exploited the conjugacy search problem in groups, which is a ramification of the discrete logarithm problem. However, it is a prevalent opinion now that the conjugacy search problem alone is unlikely to provide sufficient level of security no matter what particular group is chosen as a platform. In this paper we employ another problem (we call it the decomposition problem), which is more general than the conjugacy search problem, and we suggest to use R. Thompson's group as a platform. This group is well known in many areas of mathematics, including algebra, geometry, and analysis. It also has several properties that make it fit for cryptographic purposes. In particular, we show here that the word problem in Thompson's group is solvable in almost linear time.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

The conjugacy search problem in public key cryptography: unnecessary and insufficient

The conjugacy search problem in a group G is the problem of recovering an x in G from given g in G and h=x^{-1}gx. This problem is in the core of several recently suggested public key exchange protocols, most notably the one due to Anshel, Anshel, and Goldfeld, and the one due to Ko, Lee at al. In this note, we make two observations that seem to have eluded most people's attention. The first observation is that solving the conjugacy search problem is not necessary for an adversary to get the common secret key in the Ko-Lee protocol. It is sufficient to solve an apparently easier problem of finding x, y in G such that h=ygx for given g, h in G. Another observation is that solving the conjugacy search problem is not sufficient for an adversary to get the common secret key in the Anshel-Anshel-Goldfeld protocol.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

Birational morphisms of the plane

Let A^2 be the affine plane over a field K of characteristic 0. Birational morphisms of A^2 are mappings A^2 \to A^2 given by polynomial mappings ϕof the polynomial algebra K[x,y] such that for the quotient fields, one has K(ϕ(x), ϕ(y)) = K(x,y). Polynomial automorphisms are obvious examples of such mappings. Another obvious example is the mapping τ_x given by x \to x, y \to xy. For a while, it was an open question whether every birational morphism is a product of polynomial automorphisms and copies of τ_x. This question was answered in the negative by P. Russell (in an informal communication). In this paper, we give a simple combinatorial solution of the same problem. More importantly, our method yields an algorithm for deciding whether a given birational morphism can be factored that way.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

The Stable Equivalence and Cancellation Problems

Let $K$ be an arbitrary field of characteristic 0, and $\Aff^n$ the $n$-dimensional affine space over $K$. A well-known cancellation problem asks, given two algebraic varieties $V_1, V_2 \subseteq \Aff^n$ with isomorphic cylinders $V_1 \times \Aff^1$ and $V_2 \times \Aff^1$, whether $V_1$ and $V_2$ themselves are isomorphic. In this paper, we focus on a related problem: given two varieties with equivalent (under an automorphism of $\Aff^{n+1}$) cylinders $V_1 \times \Aff^1$ and $V_2 \times \Aff^1$, are $V_1$ and $V_2$ equivalent under an automorphism of $\Aff^n$? We call this stable equivalence problem. We show that the answer is positive for any two curves $V_1, V_2 \subseteq \Aff^2$. For an arbitrary $n \ge 2$, we consider a special, arguably the most important, case of both problems, where one of the varieties is a hyperplane. We show that a positive solution of the stable equivalence problem in this case implies a positive solution of the cancellation problem.

0 citations0 reviewsNo code linkedOpen access
preprint2001arXiv

Non-extendable isomorphisms between affine varieties

In this paper, we report several large classes of affine varieties (over an arbitrary field $K$ of characteristic 0) with the following property: each variety in these classes has an isomorphic copy such that the corresponding isomorphism cannot be extended to an automorphism of the ambient affine space $K^n$. This implies, in particular, that each of these varieties has at least two inequivalent embeddings in $K^n$. The following application of our results seems interesting: we show that lines in $K^2$ are distinguished among irreducible algebraic retracts by the property of having a unique embedding in $K^2$.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

Embeddings of hypersurfaces in affine spaces

In this paper, we address the following two general problems: given two algebraic varieties in ${\bf C}^n$, find out whether or not they are (1) isomorphic; (2) equivalent under an automorphism of ${\bf C}^n$. Although a complete solution of either of these problems is out of the question at this time, we give here some handy and useful invariants of isomorphic as well as of equivalent varieties. Furthermore, and more importantly, we give a universal procedure for obtaining all possible algebraic varieties isomorphic to a given one, and use it to construct numerous examples of isomorphic, but inequivalent algebraic varieties in ${\bf C}^n$. Among other things, we establish the following interesting fact: for isomorphic hypersurfaces $\{p(x_1,...,x_n)=0\}$ and $\{q(x_1,...,x_n)=0\}$, the number of zeros of $grad(p)$ might be different from that of $grad(q)$.

0 citations0 reviewsNo code linkedOpen access
preprint1997arXiv

Combinatorial problems about free groups and algebras

This is a survey of recent progress in several areas of combinatorial algebra. We consider combinatorial problems about free groups, polynomial algebras, free associative and Lie algebras. Our main idea is to study automorphisms and, more generally, homomorphisms of various algebraic systems by means of their action on ``very small" sets of elements, as opposed to a traditional approach of studying their action on subsystems (like subgroups, normal subgroups; subalgebras, ideals, etc.) We will show that there is a lot that can be said about a homomorphism, given its action on just a single element, if this element is ``good enough". Then, we consider somewhat bigger sets of elements, like, for example, automorphic orbits, and study a variety of interesting problems arising in that framework. One more point that we make here is that one can use similar combinatorial ideas in seemingly distant areas of algebra, like, for example, group theory and commutative algebra. In particular, we use the same language of ``elementary transformations" in different contexts and show that this approach appears to be quite fruitful for all the areas involved.

0 citations0 reviewsNo code linkedOpen access
preprint1997arXiv

Polynomial Retracts and the Jacobian Conjecture

Let $ K[x, y]$ be the polynomial algebra in two variables over a field $K$ of characteristic $0$. A subalgebra $R$ of $K[x, y]$ is called a retract if there is an idempotent homomorphism (a {\it retraction}, or {\it projection}) $φ: K[x, y] \to K[x, y]$ such that $φ(K[x, y]) = R$. The presence of other, equivalent, definitions of retracts provides several different methods of studying them, and brings together ideas from combinatorial algebra, homological algebra, and algebraic geometry. In this paper, we characterize all the retracts of $ K[x, y]$ up to an automorphism, and give several applications of this characterization, in particular, to the well-known Jacobian conjecture. Notably, we prove that if a polynomial mapping $φ$ of $K[x,y]$ has invertible Jacobian matrix {\it and } fixes a non-constant polynomial, then $φ$ is an automorphism.

0 citations0 reviewsNo code linkedOpen access