## CryptoDB

#### Publications

Year
Venue
Title
2015
EPRINT
2015
EPRINT
2014
EPRINT
2010
EPRINT
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
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
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.
2006
PKC
2005
CRYPTO
2005
EPRINT
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
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 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
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.