Conjugacy Search in Some Cryptographic Platform Groups

Abstract: The construction and realization of public-key protocols that resist known quantum attacks comprise a pressing problem in cryptography. Apart from lattice-based, multivariate, and code-based cryptography, nonabelian group-based cryptography has been proposed recently as a viable post-quantum paradigm. Under this, the most prominent algorithmic problem employed has been the Conjugacy Search Problem. While several protocol-specific attacks have been devised to retrieve the private keys without solving the underlying algorithmic problems, much remains to be said about the general complexity of the conjugacy search problem. This talk will present several results on the complexity of conjugacy search in various nonabelian platform groups, including some p-groups, polycyclic groups and matrix groups. In particular, it demonstrates a polynomial time solution of the conjugacy search problem in an important class of nonabelian groups, the extraspecial p-groups, and a general reduction method in certain types of central products. Further, in the group of invertible matrices over a finite field and in polycyclic groups with two generators, it is shown that a restricted version of conjugacy search is reducible to a set of polynomially many discrete log problems. The cryptanalysis of a few independently proposed cryptosystems are also presented as a consequence of these results.

Back to Search Research Symposium Abstracts