  We propose a new computational problem over the noncommutative group, called
the twin conjugacy search problem. This problem is related to the conjugacy
search problem and can be used for almost all of the same cryptographic
constructions that are based on the conjugacy search problem. However, our new
problem is at least hard as the conjugacy search problem. Moreover, the twin
conjugacy search problem have many applications. One of the most important
applications, we propose a trapdoor test which can replace the function of the
decision oracle. We also show other applications of the problem, including: a
non-interactive key exchange protocol and a key exchange protocol, a new
encryption scheme which is secure against chosen ciphertext attack, with a very
simple and tight security proof and short ciphertexts, under a weak assumption,
in the random oracle model.
