### The Twin Conjugacy Search Problem and Applications

Xiaoming Chen and Weiqing You

##### Abstract

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 as hard as the conjugacy search problem. Moreover, the twin conjugacy search problem has 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.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
The twin conjugacy search problemtrapdoor testCCAnoncommutative groupassumptioncrypto
Contact author(s)
894572560 @ qq com
History
2018-07-07: revised
See all versions
Short URL
https://ia.cr/2018/590

CC BY

BibTeX

@misc{cryptoeprint:2018/590,
author = {Xiaoming Chen and Weiqing You},
title = {The Twin Conjugacy Search Problem and Applications},
howpublished = {Cryptology ePrint Archive, Paper 2018/590},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/590}},
url = {https://eprint.iacr.org/2018/590}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.