## CryptoDB

### Vladimir Shpilrain

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Authentication schemes from actions on graphs, groups, or rings
Abstract

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include Graph Colorability, Diophantine Problem, and many others.

2008

EPRINT

Public key encryption and encryption emulation attacks
Abstract

The main purpose of this paper is to suggest that public key encryption can be secure against the "encryption emulation" attack (on the sender's encryption) by computationally unbounded adversary, with one reservation: a legitimate receiver decrypts correctly with probability that can be made arbitrarily close to 1, but not equal to 1.

2007

EPRINT

Using decision problems in public key cryptography
Abstract

There are several public key establishment protocols as well as complete public key cryptosystems based on allegedly hard problems from combinatorial (semi)group theory known by now. Most of these problems are search problems, i.e., they are of the following nature: given a property P and the information that there are objects with the property P, find at least one particular object with the property P. So far, no cryptographic protocol based on a search problem in a non-commutative (semi)group has been recognized as secure enough to be a viable alternative to established protocols (such as RSA) based on commutative (semi)groups, although most of these protocols are more efficient than RSA is.
In this paper, we suggest to use decision problems from combinatorial group theory as the core of a public key establishment protocol or a public key cryptosystem. By using a popular decision problem, the word problem, we design a cryptosystem with the following features: (1) Bob transmits to Alice an encrypted binary sequence which Alice decrypts correctly with probability "very close" to 1; (2) the adversary, Eve, who is granted arbitrarily high (but fixed) computational speed, cannot positively identify (at least, in theory), by using a "brute force attack", the "1" or "0" bits in Bob's binary sequence. In other words: no matter what computational speed we grant Eve at the outset, there is no guarantee that her "brute force attack" program will give a conclusive answer (or an answer which is correct with overwhelming probability) about any bit in Bob's sequence.

2005

EPRINT

A new key exchange protocol based on the decomposition problem
Abstract

In this paper we present a new key establishment protocol based on the decomposition problem in non-commutative groups which is: given two elements w, w_1 of the platform group G and two subgroups A, B of G (not necessarily distinct), find elements a in A, b in B such that w_1 = a w b. Here we introduce two new ideas that improve the security of key establishment protocols based on the decomposition problem.
In particular, we conceal (i.e., do not publish explicitly) one of the subgroups A, B, thus introducing an additional computationally hard problem for the adversary, namely, finding the centralizer of a given
finitely generated subgroup.

2004

EPRINT

Combinatorial group theory and public key cryptography
Abstract

After some excitement generated by recently suggested public key exchange protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al., it is a prevalent opinion now that the conjugacy search problem is unlikely to provide sufficient level of security if a braid group is used as the platform. In this paper we address the following questions: (1) whether choosing a different group, or a class of groups, can remedy the situation; (2) whether some other ``hard" problem from combinatorial group theory can be used, instead of the conjugacy search problem, in a public key exchange protocol. Another question that we address here, although somewhat vague, is likely to become a focus of the future research in public key cryptography based on symbolic computation: (3) whether one can efficiently disguise an element of a given group (or a semigroup) by using defining relations.

2004

EPRINT

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

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.

2003

EPRINT

Assessing security of some group based cryptosystems
Abstract

One of the possible generalizations of the discrete logarithm
problem to arbitrary groups is the so-called conjugacy search
problem. The computational difficulty of this problem in some
particular groups has been used in several group based cryptosystems.
Recently, a few preprints have been in circulation that suggest
various heuristic attacks on the conjugacy search problem.
The goal of the present survey is to stress a (probably well known)
fact that these heuristic attacks alone are not a threat to the
security of a cryptosystem, and, more importantly, to suggest a more
credible approach to assessing security of group based cryptosystems.
Such an approach should be necessarily based on the concept of the
average case complexity (or expected running time) of an algorithm.
These arguments support the following conclusion: although it is
generally feasible to base the security of a cryptosystem on the
difficulty of the conjugacy search problem, the group itself
(the ``platform") has to be chosen very carefully. In particular,
experimental as well as theoretical evidence collected so far
makes it appear likely that braid groups are not a good choice
for the platform. We also reflect on possible replacements.

#### Coauthors

- Bren Cavallo (1)
- Giovanni Di Crescenzo (1)
- Dima Grigoriev (2)
- Delaram Kahrobaei (1)
- Alexei G. Myasnikov (2)
- Denis Osin (1)
- Bianca Sosnovski (1)
- Alexander Ushakov (4)
- Gabriel Zapata (2)