#  Intractable Group-theoretic Problems Around Zero-knowledge Proofs

Cansu Betin Onur
Institute of Applied Mathematics
Middle East Technical University
06800 Ankara Turkey EMail<EMAIL_ADDRESS>
###### Abstract

This paper gives a brief overview of zero-knowledge proof systems and
enumerates the existing intractable problems in group theory with their usage
in cryptography mainly in the scope of zero-knowledge proofs.

###### Contents

  1. 1 Zero Knowledge Proof Systems
    1. 1.1 Basic Concept
    2. 1.2 A Brief History of ZKP
    3. 1.3 Group Theory in ZKP
  2. 2 Group Theoretic Algorithmic Problems
    1. 2.1 Basic Decision Problems Defined on Groups
    2. 2.2 Word Problem
    3. 2.3 Generalizations of the Word Problem
    4. 2.4 Knapsack type problems:
    5. 2.5 The Conjugacy Problem
    6. 2.6 The Generalizations of The Conjugacy Problem
      1. 2.7 Intersection Problems
      2. 2.8 Miscellaneous Problems
      3. 2.9 The Post’s Correspondence Problem in Groups
        1. 2.10 The Endomorphism Problem
          1. 2.11 The Group Isomorphism Problem
            1. 2.12 The Hidden Subgroup Problem

##  1 Zero Knowledge Proof Systems

In this section, an overview of zero knowledge systems is given. The concern
of group theoretic problems in zero knowledge proofs is given intiutively.

###  1.1 Basic Concept

Zero-knowledge proofs  (ZKP) are cryptographic protocols where a party (called
the prover) may convince the other party (called the verifier) that a certain
statement is true revealing no additional information about that knowledge
[1]. The requirements for ZKP are

  * •

Completeness: Whenever the statement is TRUE, the prover convinces the
verifier.

  * •

Soundness: Whenever the statement is FALSE, a dishonest prover will not be
able to convince the verifier.

  * •

Zero-knowledge: The verifier will not learn anything from the proof procedure
but the statement is true.

The zero knowledge property, the verifier will not gain any extra information
from the interaction, is formulated by means of a simulator (a probabilistic
polynomial-time algorithm). The simulation paradigm [2] postulates that
“whatever a party can do by itself cannot be considered a gain from
interaction with the outside.” The simulator’s output and the verifier’s
output are expected to be indistinguishable.

For practical purposes, the definition of zero knowledge is relaxed by
allowing the simulator to fail. Mainly there are three variants of zero
knowledge property; perfect (no information is leaked), statistical (some
information is leaked to the verifier but it is a negligible amount regardless
of the computational resources the verifier) and computational (the amount of
information leaked is negligible if the verifier is probabilistic polynomial-
time Turing machine). That is to say, in perfect and statistical (a.k.a.
almost-perfect) zero knowledge, it is not possible to notice the difference in
outputs of the verifier and the simulator in information-theoretic sense. On
the other hand, in computational zero-knowledge this distinction cannot be
done not theoretically but by any computationally efficient procedure. A zero-
knowledge protocol without any of these attributes is used for the most
general class computational zero-knowledge.

###  1.2 A Brief History of ZKP

Zero-knowledge proof systems are a technology that can be vastly employed for
privacy preservation and data ownership. Goldwasser, Micali and Rackoff
introduced this concept in [3]. Originally ZKP systems are designed to be
interactive; the messages are sent between the prover and the verifier back
and forth. Efficiency considerations leads a variant of ZKP that require no
interaction, namely non-interactive zero-knowledge proofs (NIZKP). In this
case, the prover conveys only to the verifier.

Blum et all. showed that a common reference string (CRS) shared by a trusted
party to the prover and the verifier is sufficient to achieve computational-
NIZKP [4]. An alternative to the CRS model is the Random Oracle (RO) model
which assumes that a perfect random function is available to both the prover
and the verifier. Fiat and Shamir [5] introduced a method that can transform
any sigma protocol into a NIZK proof by the use of a hash function as a
simulator. Goldreich and Oren showed that NIZKP is impossible to achieve (in
the standard model) without any further assumption, like the CRS model or the
RO model [6].

In the literature, the most popular protocol which is one of the first
examples of zero knowledge proof is Fiat-Shamir (1987) protocol. This protocol
is based on the RSA encryption system. In other words, it is based on the
difficulty of the prime factorization problem. Since then, a variety of
protocols were developed following the Fiat-Shamir protocol such as the Chaum-
Evertse-van de Graaf [7], the Feige-Fiat-Shamir [8], the Beth [9], the
Guillou-Quisquater [10], the Desmedt [11] and the Schnorr [12] protocol. These
protocols rely on computational hardness of either RSA algorithm, finding
square-root in composite modulo with unknown factorization or discrete
logarithm problem.

State-of-the-art new generation ZKP systems are mainly zk-SNARKs [13],
BulletProofs [14] and zk- STARKs [15] and “MPC-in- the-head” approach [16].
These are non-interactive or can be realized as non-interactive through Fiat-
Shamir transform. Constructions of SNARKs mostly rely on bilinear maps or
lattices. They require trusted setup. An improvement from SNARKS to STARKS is
removing the need for a trusted setup. STARKS rely on collision-resistant hash
functions. STARK friendly hash function [17] [18] is the subject of extensive
research. A prominent disadvantage of STARKS is the proof size compared to
STARKS. In the MPC-in-the-head approach, a ZKP-protocol designed for NP-
relations from secure multiparty computation (MPC) protocols. Bulletproof
relies on the hardness of discrete logarithm problem and has no trusted setup.

###  1.3 Group Theory in ZKP

In 1991, Goldreich, Micali, and Wigderson showed that any NP problem could be
used to implement a zero-knowledge proof system [19], and this result made ZKP
central. A decision problem is in NP when a possible solution to the problem
is given, one can efficiently (in polynomial time) check whether it is
correct. Note that finding a solution is not always easy for an NP problem,
but verification is straightforward.

Fenner and Zhang [20] showed that the group intersection and double coset
membership problems have honest verifier zero knowledge proof systems. In
particular, they proved that these problems are in the statistical zero-
knowledge proof class.

Arvind and Das classified several algorithmic problems in group theory with
perfect and statistical zero-knowledge proofs [21]. They showed that the
permutation group problems Coset Intersection, Double Coset Membership, Group
Conjugacy are in perfect zero-knowledge class. Sdroievski et al. showed that
the hidden subgroup problem has a statistical zero-knowledge proof [22].

##  2 Group Theoretic Algorithmic Problems

The security of open cryptographic structures relies heavily on the difficulty
of the underlying mathematical problem. Commonly used among these problems are
the discrete logarithm problem and the prime factorization problem of an
integer. Since the subject of this study is group theoretic problems, we will
not examine the later problem.

Discrete Logarithm Problem (DLP)  Given a finite single-generator (cyclic)
group $G=\langle g\rangle$ and an element $h$ from this group. The question is
finding an integer $x$ that will satisfy the equality $h=g^{x}.$

Note that the definition is written in multiplicative notation. One may prefer
to use additive notation instead, as in the case $G$ is the group of multiples
of a point $P$ on an elliptic curve defined over a finite field.

The first public key cryptosystem, the Diffie-Hellman key exchange, is based
on the computational difficulty of DLP [23]. Following this protocol, RSA [24]
and ElGamal [25] cryptosystems were developed in chronological order. While
RSA is based on the difficulty of prime factorization of an integer, ElGamal
again uses the discrete logarithm problem. Although, from a group theoretical
perspective, two cyclic groups of the same order are isomorphic, the existence
of an algorithm that efficiently computes the discrete logarithm problem in
one of these groups does not imply that there is an algorithm which solves the
problem efficiently in the other group. For this reason, the trend to develop
efficient cryptographic methods where discrete logarithms are difficult on a
cyclic group has been adopted by various researchers. For example; cyclic
subgroups of matrix groups (the problem is not more difficult on these group
than on the multiplicative group of finite fields [26]), critical groups of
graphs (shown to be unsafe [27], [28] ), the group of multiples of a point on
an elliptic curve defined over a finite field is used. Among these examples,
elliptic curve cryptography is an actively studied research area,
distinguished from other candidates by its efficiency in application and high
security in small key size.

DLP draws attention in the literature with its structure suitable for creating
efficient zero knowledge systems. Discrete-log based ZKP schemes include the
Groth’s protocol [29], the work of Bayer and Groth [30], a scheme of Bootle et
al. [31] and Bulletproof [14].

The variant of DLP involved in the Diffie-Hellman key exchange protocol later
named as Diffie-Hellman Problem.

Diffie-Hellman Problem (DHP)  Given a finite cyclic group $G=\langle g\rangle$
and two elements $h=g^{x},k=g^{y}$ from this group where $x$ and $y$ are
randomly chosen secret integers. Find the element $s=g^{xy}.$

The above problem is sometimes called as the Computational Diffie-Hellman
problem to distinguish it from its decision version.

Decision Diffie-Hellman Problem  Given a cyclic group $G=\langle g\rangle$ of
order $n$ and three elements $h,k,s$ from this group satisfying
$h=g^{x},k=g^{y},s=g^{z}$ where $x,y,z$ are secret integers. Determine
wheteher $z=xy$ mod $n.$

In [32], Koblitz and Menezes examine several variants of and the reductions
between the DHP and DLP. Clearly, to solve DLP implies the ability to solve
DHP. Also over many groups the DHP is almost as hard as the DLP [33]. In the
literature, groups on which cryptographic protocols are defined are called
_platform groups_. On a well chosen platform group, DLP and DHP are classical
intractable problems.

In 1994, Shor [34] developed a quantum algorithm that solves the factorization
and discrete logarithm problems in polynomial time. Following this
development, the necessity of creating alternative methods to design
encryption systems has emerged. One of these methods is to develop non-
commutative cryptographic structures. The complexity of algorithmic problems
defined on non-commutative groups has made these algebraic structures suitable
tools for cryptographic protocols.

###  2.1 Basic Decision Problems Defined on Groups

A problem that can be answered with Yes or No is called Decision Problem.
Three basic decision problems defined on groups were proposed by Max Dehn in
1911 [35]. These problems are called word problem, conjugate problem and
isomorphism problem.

  * •

Word decision problem: Let a group $G$ with finite presentation and $g\in G$
be given. Decide if $g=1$.

  * •

Conjugacy decision problem: Given a finitely presented group $G$ and two
elements $a,b$ from $G.$ Determine whether $a$ and $b$ are conjugate in $G$?
In other words, is there $x\in G$ that satisfies $x^{-1}ax=b$?

  * •

(Group) Isomorphism decision problem: Let two groups with finite presentations
$G_{1},G_{2}$ be given. Decide if these groups are isomorphic.

These problems, which are defined on groups with finite presentation, can be
generalized to countable groups by numbering their generators. In the most
general sense, Dehn’s decision problems given above are undecidable. In other
words, they are not algorithmically solvable (Novikov [36], Adian [37])

In the case where the answer to the decision problem is yes, the question of
searching for values satisfying the questioned property is called Search
Problem. Search problems have a large place in the construction of
cryptographic structures. Below, the problems are defined in the categories of
decision problems and search problems and their place in the literature is
given.

###  2.2 Word Problem

We have defined the word decision problem above and stated that there is no
algorithm to solve the word problem in general. On the other hand, group
classes where the word problem is NP (can be solved in polynomial time with a
non-deterministic Turing machine) are quite broad. For example, finitely
generated matrix groups defined on a field, polycyclic groups, finitely
generated metabelian groups, Automatic groups, Thompson group, finitely
generated subgroups of diagram groups, free Burnside groups $B(m,n)$ for a
large enough number $n$ is in this class [38]. There are also groups with
finite presentations on which the word problem is NP-complete [39] or coNP-
complete. Birget et all [38] obtained a group theoretic characterization of
NP-problems. They observed that the word problem on a finitely generated group
$G$ is in NP if and only if the group $G$ can be embedded into a finitely
presented group with polynomial Dehn function.

Word search problem: Let it be known that $g=1$ for $g\in G$ in a given group
$G$. Express this element $g$ as the product of the conjugates of the
descriptive relations given in the group presentation.

To the best of our knowledge, there is no ZKP relying on the word problem. The
first attempt to establish an encryption system using the word problem was
given in 1984 by Magyarik-Wagner [40]. This approach is also the first example
of using non-commutative groups. The method used here is based on a problem
that is actually easier to secure since it restricts the word problem. In
[41], Vasco and Steinwandt show that for the group proposed the secret key can
be found by monitoring the performance of a legitimate buyer, on the other
hand, it is emphasized that the word problem in groups with finite
presentation is an attractive candidate for deriving one-way functions and
thus establishing a public key system. Then, Birget et al. [42] analyzed the
Magyarik-Wagner system and proposed a new public-key encryption system
inspired by it. In the new method, the deciphering phase uses the group
actions on the words.

One of the early attempts to use the problem was to obtain a one-way function
by repeatedly adding new relations to the word produced by the two
elements[43]. This method has remained cumbersome in practice.

The system proposed by Garzon and Zalcstein used the word problem on
Grigorchuk groups. It is similar to the Magyarik-Wagner system. The security
of this example, which is the first application of the Grigorchuk groups in
cryptography, is known to be weak.[44]

Panagopoulos [45] has developed a $(t,n)$-threshold secret sharing scheme
using group presentations and the word problem. A $(t,n)$-threshold secret
sharing is a method of distributing a confidential information to $n$
participants in a way that while any $t$ participants can reach the secret,
less than $t$ participants cannot. In the first part of the two-stage scheme,
the confidential information to be used in solving the word problem, such as
the defining relations of the group, is distributed to the participants over
the secure channel. In the second stage, the actual secret is sent over open
channels. The prominent difference of this method from the previously
developed $(t,n)$-threshold secret sharing schemes is that the real secret
does not have to be transmitted over the secure channel. Habeeb et al. [46]
make this method more practical and gave schemes for sharing confidential
information based on group presentations and word problem.

###  2.3 Generalizations of the Word Problem

Various generalizations of the word problem have been presented in the
literature. The main ones are subgroup membership problem, order problem,
power problem and root problem.

  * •

The Subgroup Membership Decision/Search Problem:
Given a group $G,$ an element $g\in G$ and a finitely generated subgroup
$H=\langle h_{1},\dots,h_{k}\rangle$ of $G$.
Decision problem: Decide whether $g$ is an element of $H$.
Search problem: It is known that $g\in H$. Find the integer values $t_{i}$
that satisfy $g=h_{1}^{t_{1}},\dots,h_{k}^{t_{k}}$.

This problem is also known as the uniform generalized word problem or
occurrence problem.

  * •

The Order Problem:  McCool
Given a group $G$ in terms of generators and defining relations and an element
$g\in G.$ Decision problem: Determine whether $g$ has a finite order.
Search problem: It is known that $g$ has a finite order. Find the order.

  * •

The Power Problem:  McCool
Given a group $G$ and two elements $x,y\in G,$
Decision problem: Determine whether there exists an integer $n$ that satisfies
$y=x^{n}?$
Search problem: It is known that there is an integer $n$ that satisfies
$y=x^{n}$. Find a value of $n$ that satisfies this equation.

The power problem is a special case of the subgroup membership problem. This
is clear when the subgroup is taken as $H=\langle x\rangle$.

  * •

The Root Problem:  Lipschutz-Miller
If the pair $a,b$ given from a group $G$ satisfies $b=a^{n}$ for a natural
number $n$, then the element $a$ is said to be the $n$th root of $b$. Given a
group $G,$ an element $b\in G$ and a natural number $n.$
Decision problem: Is there an element $a$ in the group $G$ that satisfies
$b=a^{n}$?
Search problem: It is known that such element exists. Find an element $a$ in
group $G$ that satisfies $b=a^{n}$.

Word problem can be reduced from the order problem by considering the order of
the element as one. Again, taking the element $x=1$ in the power problem and
choosing $n=0$ in the root problem, one gets the word problem [47]. These
generalizations are harder than the word problem [48], [49], [47].

In [50] a key exchange protocol is given based on the difficulty of finding
the square root in $2$-Engel groups. $2$-Engel groups are nilpotent groups.
The difficulty of the $n$th root problem in nilpotent groups is given in [50]
by Sze et al. As emphasized here, the difficulty of the problem in nilpotent
groups comes from the difficulty of embedding the studied group in the group
of upper-triangular matrices defined on rational numbers.

A zero knowledge scheme relying on the root problem [51] is mentioned in 2.5.

###  2.4 Knapsack type problems:

The knapsack problem is one of the most well-known NP-complete problems. The
classic knapsack and subset sum problems are discrete optimization problems
concerning integers. Myasnikov et al. [52] generalized these problems to
arbitrary groups by calling them knapsack-type problems. They examined the
computational complexity of these problems and their variations.

It turns out that such problems are indeed variations of the subgroup
membership problem. In each of the below problems a group $G,$ an element $a$
and a subset $S=\\{g_{1},g_{2},\dots,g_{n}\\}$ from the group $G$ are given.

  * •

The Subset Sum Problem:
Decision problem: Determine whether $a=g_{1}^{k_{1}}\dots g_{n}^{k_{n}}$ for
some $k_{i}\in\\{0,1\\}$
Search problem: It is known that answer of the decision problem is Yes. Find
the values of the exponents.

  * •

The Knapsack Problem:
This is a one step generalization of the subset sum problem. The exponents are
allowed to be chosen from non-negative integers.

Decision problem: Determine whether $a=g_{1}^{k_{1}}\dots g_{n}^{k_{n}}$ for
some $k_{i}\in\\{0\\}\cup\mathbb{Z}^{+}$
Search problem: It is known that such exponents exists. Find the values of the
exponents.

  * •

The Submonoid Membership Problem:
Decision problem: Determine whether $a=g_{i_{1}}\dots g_{i_{s}}$ for some
$g_{i_{k}}\in S$ with repetition allowed.
Search problem: It is known that there exists such elements. Find values of
$g_{i_{k}}$’s that satisfies this equation.

Note that if the given group $G$ is abelian, the last two problems are
equivalent.

###  2.5 The Conjugacy Problem

In the conjugacy decision problem, one is asked to determine whether the given
elements $a,b$ from a group $G$ are conjugate. Notice that if there exists an
algorithm which can decide the conjugacy problem, then that algorithm decides
whether a given element $g$ is conjugate to identity. In other words, solving
the conjugacy problem implies solving the word problem. Therefore, we deal
this problem under the restriction that the word problem is solvable on the
considered group. let us state the search version of the problem. A computably
presented group with NP-complete conjugacy problem given in [53].

The Conjugacy Search Problem:  Let it be known that in a given $G$ group, the
elements $a,b$ are conjugates of each other. Find an element $x\in G$ that
satisfies the equality $b=xax^{-1}$.

The computational difficulty of this problem in appropriately selected groups
has enabled it to be used in various public-key protocols. The most popular
platform used in the conjugacy problem is the braid group. Braid groups are
non-commutative infinite groups that arise naturally from geometric braids.
While the group operations on it can be easily calculated, the difficulty of
various algorithmic problems such as the conjugacy search problem makes braid
groups attractive.

The idea to implement the braid group as a platform for cryptosystems was
introduced in 1999 by Ansel-Ansel-Goldfeld. Then, various cryptographic
schemes such as Ko-Lee and Sibert-Dehornoy-Girault used the conjugacy search
problem on braid groups.

The Ansel-Ansel-Goldfeld (AAG) key exchange protocol is based on the conjugacy
search problem on non-commutative groups [54]. Although this protocol can be
applied to any non-commutative group, the authors specifically emphasize that
braid groups are promising. In the proposed scheme, in order to exchange
information between Alice and Bob over the public channel, the word problem
must be easily solved efficiently. The security of this scheme is based on the
difficulty of solving the system of conjugates
$xu_{1}x^{-1}=v_{1},\dots,xu_{m}x^{-1}=v_{m}$ given from the group
simultaneously.

In 2019, Grigorchuk and Grigoriev proposed some automaton groups, where the
word problem is in polynomial time complexity and it is difficult to solve
their conjugate systems, as the platform group for the AAG scheme [55]. These
are Grigorchuk group, Basilica group, Universal Grigorchuk group, Three Towers
Hanoi group, affine group $Aff_{4}(\mathbb{Z})$ and certain subgroups of
$Aff_{6}(\mathbb{Z})$.

Ko, Lee et al. have proposed a key agreement protocol based on the conjugacy
search problem on [56] braid groups. Shpilrain and Ushakov [57] showed that an
adversary need not to solve the conjugacy search problem to get the common
secret key. They showed that it is enough to solve the decomposition problem,
which is a comparatively easier problem. A heuristic attack solving the
decomposition problem in Ko-Lee protocol has been developed in [58], which is
much more efficient than any known attack based on solving the conjugacy
search problem.

Sibert, Dehornoy, and Girault have proposed three authentication schemes
designed for [51] braid groups. The first one is a two-step (challenge -
response) authentication scheme based on the (Diffie-Hellman-Like) conjugacy
problem, while the other two are authentication schemes based on the conjugacy
search problem, which repeats a three-step process several times to guarantee
the required level of security. The root finding problem is also used in
Scheme III. The authors demonstrated that these schemes they designed are
zero-knowledge proofs. On the other hand, Mosina and Ushakov [59] show that
the Scheme II given here is practically not a computationally zero-knowledge
proof.

An algorithmic solution to the conjugacy decision and search problems in braid
groups was first given by Garside [60]. Although this algorithm is not
efficient, it has opened the door to the solution of this problem. Then, many
deterministic algorithms have been developed to solve the conjugacy search
problem in braid groups [61, 62, 63, 64]. In addition, in [65], a polynomial
time algorithm is given for the Diffie-Hellman type conjugacy search problem
in braid groups, and an efficient solution to this problem under certain
conditions is proposed in [66]. Apart from that, notable success has been
achieved in various length-based or heuristic attacks [67, 68]. However, braid
groups are still one of the alternatives with potential advantages against
quantum attacks.

###  2.6 The Generalizations of The Conjugacy Problem

  * •

The Twisted Conjugacy Problem:
Given a group $G$ and an endomorphism $\varphi$ defined on $G$ and given two
elements $a,b\in G$.

Decision problem: Determine whether the equality $b=x^{-1}a\varphi(x)$ holds
for some $x\in G$.
Search problem: It is known that answer of the decision problem is Yes. Find
the element $x$.

This problem is a generalization of the conjugacy problem. When the function
$\varphi=id$ is taken, the conjugacy problem is obtained. The problem is
decidable for a polycyclic groups[69], for automorphims of finitely generated
free groups[70], for closed surface groups [71] etc. The set of twisted
conjugates of an element in a group is called the twisted conjugacy
(Reidemeister) class. The twisted conjugacy classes are based on the Nielsen-
Reidemeister fixed point theory. We can also ask the problem as: Is the
element $b$ in the Reidemeister class of $a$? (decision) Find a value $x$ that
allows $b$ to belong to this class (search). In [72] an iterative three-pass
authentication scheme is proposed, such as the Fiat-Shamir protocol, based on
the difficulty of the twisted conjugacy problem. Here, they named the problem
as the double-twisted conjugacy problem and defined it for endomorphism pairs
as follows:

Given a group $G,$ two endomorphisms $\varphi,\psi$ on $G$ and two elements
$a,b\in G$.
Decision problem: Determine if the equality $b=\psi(x^{-1})a\varphi(x)$ holds
for some $x\in G$.
Search problem: It is known that such element exists. Find the element $x$.

The protocol proposed by Ushakov and Shpilrain is given on the semigroup of
all $2\times 2$ matrices over truncated one-variable polynomials over $F_{2}.$
However, a successful attack was developed for the proposed protocol [73], and
then another study [74] showed that this protocol is vulnerable in both
theoretical and practical terms.

  * •

The Decomposition Problem:
Let two elements $a,b$ and two subsets $H,K$ from a group $G$ be given.
Decision problem: Is the equality $hak=b$ holds for some $h\in H$ and $k\in
K$.
Search problem: It is known that $hak=b$ holds for some $h\in H$ and $k\in K.$
Find such elements.

In this problem, when subsets are selected as subgroups, the problem is called
the double coset problem.

  * •

Double Coset Membership Problem:  (Hoffmann)
Let two subgroups $H,K$ and two elements $a,b$ from a group $G$ be given.
Decision problem: Decide whether the double coset $HaK$ contains the element
$b.$ Search problem: It is known that $b\in HaK.$ Find elements $h\in H$ and
$k\in K$ such that $hak=b.$

In the double coset problem choose $a=1,$ you get the factorization problem.

  * •

The Factorization Problem:  (Hoffmann)
Let two subgroups $H,K$ and an element $g$ from a group $G$ be given.
Decision problem: Decide whether the equality $g=hk$ holds for some $h\in H$
and $k\in K$.
Search problem: Given that $g$ is an element in the set $HK.$ Find elements
$h\in H$ and $k\in K$ such that $g=hk.$

  * •

The Number of Factorizations Problem:  (Hoffmann)
Let two subgroups $H,K$ and an element $g$ from a group $G$ be given.
Determine the number $k\geq 0$ of distinct factorizations $g=hk$ of $g$ where
$h\in H$ and $k\in K$.

  * •

The Diffie-Hellman-Like Conjugacy Problem:  Given a group $G$ and elements
$g,h,k\in G$ such that $h=a^{-1}ga$ and $k=b^{-1}gb$ for some commuting secret
elements $a,b\in G.$ Find the element $b^{-1}a^{-1}gab.$

  * •

The Power Conjugacy Problem:  Two elements $a,b$ in a group $G$ are said to be
power-conjugate if there exists integers $n,m$ such that $a^{n}$ and $b^{m}$
are conjugate in $G.$ Given a group $G$ and two elements $a,b\in G.$
Decision problem: Decide whether $a^{n}$ and $b^{m}$ are conjugate in $G$ for
some integers $n,m.$
Search problem: Given that $a$ and $b$ are power-conjugate in $G.$ Find two
integers $n,m$ and an element $x\in G$ such that $b^{m}=x^{-1}a^{n}x.$

###  2.7 Intersection Problems

  * •

Subgroup Intersection Problem: (Hoffmann) Given a group $G$ and its two
finitely generated subgroups $H,K$ by generating sets. Decision problem: Is
the intersection of subgroups $H$ and $K$ finitely generated?
Search problem: Given that $H\cap K$ is finitely generated. Find a generating
set of the intersection.

  * •

Coset Intersection Problem: (Hoffmann) A group $G,$ an element $a\in G$ and
generating sets of two subgroups $H,K$ of $G$ are given. Decision problem:
Decide whether the intersection $Ha\cap K$ is empty.
Search problem: Given that $Ha\cap K$ is non-empty. Find a generating set of
the intersection.

It is easy to see that the factorization problem and the coset intersection
problems are equivalent. For the convince of the reader, the observation of
the equivalence is given: an element $a\in G$ is of the form $a=hk$ for some
$h\in H$ and $k\in K$ only if $k=h^{-1}a\in Ha\cap K.$

  * •

Setwise Stabilizer Problem: Let a group $G$ act on a finite set $\Omega$. For
a given subset $\Delta$ of $\Omega.$ Find the set $Stab_{G}(\Delta)=\\{g\in
G|\Delta^{g}=\Delta\\}$.

###  2.8 Miscellaneous Problems

  * •

Centralizer Problem: Given a group $G$ with an element $x$ and a subgroup $H$.
Find the centralizer $C_{H}(x)=\\{h\in H\ |\ hx=xh\\}$ of the element $x$ in
$H$.

  * •

Centralizer in Another Subgroup Problem: Let a group $G,$ and two subgroups
$H,K\leq G$ be given. Find a generating set for the centralizer
$C_{H}(K)=\\{h\in H\ |\ hk=kh\text{ for all }k\in K\\}.$

  * •

Set Transporter Problem: Let a group $G$ act on the set $\Omega$. Determine
whether there is an element $g\in G$ that satisfies
$\Delta_{1}^{g}=\Delta_{2}$ for the given subsets $\Delta_{1},\Delta_{2}$ of
$\Omega$ .

  * •

Restricted Graph Automorphism: Given a graph $G=(V,E)$ and a permutation group
$H\leq Sym(V).$ Find a generating set for $A\cap Aut(X).$

In [75], Hoffmann presented eight group theoretic problems defined on
permutation groups. These are double coset membership, group factorization,
number of factorizations, coset intersection, subgroup intersection, setwise
stabilizer, centralizer in another subgroup, restricted graph automorphism
problem. We give these problems above in generic sense. The problems that
Hoffmann introduced are translated from combinatorial problems including graph
isomorphism. It is given that all of these problems are NP. He also proved
that finding generating set for intersection of commuting permutation group
given by generating set is the class NP $\cap$ coNP

E.M. Luks stated that with the Karp reduction method, the group isomorphism
decision problem on permutation groups in polynomial time can be reduced to
the graph isomorphism problem and this problem can be reduced to the set
stabilizer problem; He also demonstrated the equivalence of various problems
in polynomial time over permutation groups named as Luk’s equivalent class
[76]. This class includes the subgroup intersection problem, the set
stabilizer problem, the centralizer problem, the set transporter problem, the
double coset decision problem and many more. In 2016, it was shown that these
problems can be solved in quasipolynomial $exp(logn)^{O(1)}$ time [77].

###  2.9 The Post’s Correspondence Problem in Groups

Another classic undecidable problem that Myasnikov et al. [52] generalized to
arbitrary groups is the Post’s correspondence problem (PCP)[78]. It is known
that bounded PCP is NP-complete (SR11 in [79]). They study this problem
together with its variations and examined the computational complexity of
these problems.

    * –

The Post’s Correspondence Problem in a Group PCP(G):  Given a finitely
generated group $G$ and and a finite set of pairs
$(g_{1},h_{1}),\dots,(g_{n},h_{n})$ of elements in $G.$ Determine if there is
a word $w(x_{1},\dots,x_{n})$ in the free group $F(X)$ with basis
$X=\\{x_{1},\dots,x_{n}\\},$ which is not identity of $G$, such that
$w(g_{1},\dots,g_{n})=w(h_{1},\dots,h_{n})$ in $G.$

    * –

The non-homogeneous Post’s Correspondence Problem in a Group NPCP(G):  Given a
finitely generated group $G$ and and a finite set of pairs
$(g_{1},h_{1}),\dots,(g_{n},h_{n}),(a_{1},a_{2}),(b_{1},b_{2})$ of elements in
$G.$ Determine if there is a word $w(x_{1},\dots,x_{n})$ in the free group
$F(X)$ with basis $X=\\{x_{1},\dots,x_{n}\\},$ such that
$a_{1}w(g_{1},\dots,g_{n})b_{1}=a_{2}w(h_{1},\dots,h_{n})b_{2}$ in $G.$ Here
the pairs $(a_{1},a_{2}),(b_{1},b_{2})$ are called the constants of the
instance.

Notice that in NPCP(G), $w$ need not to be non-identity. As in the original
PCP, the problems PCP(G) and NPCP(G) are also considered in the case where the
number of pairs given from the group is bounded above.

Specifically in [52], it is given that the bounded NPCP(G) is NP-complete in
the case that $G$ is a non-abelian free group of finite rank. As a corollary,
it is given that NPCP(G) is NP-hard if $G$ contains a free abelian subgroup
$F_{2}.$

###  2.10 The Endomorphism Problem

Given a group $G$ and two elements $g,h\in G$.
Decision problem: Determine whether there is an endomorphism $\phi$ of $G$
such that $\phi(g)=h$.
Search problem: It is known that there is an endomorphism $\phi$ sending $g$
to $h.$ Find $\phi$.

The endomorphism decision problem is unsolvable for a number of groups [80,
81]. It is observed that [82] for well-chosen platform groups, like free
metabelian group of rank two, the problem is NP-hard. In [82] general
framework for a zero-knowledge authentication scheme in the form Feige-Fiat-
Shamir-like construction is given. Here the idea is to use a hard-to-invert
action of a semigroup on a set. In particular, when a free metabelian group is
used as the platform this study gives a zero-knowledge proof relying on the
hardness of endomorphism problem. Later Roman’kov and Erofeev [83] present a
method for constructing a possibly one-way function on a group with the
decidable word problem and undecidable endomorphism problem. As an
application, a zero-knowledge authentication protocol is given.

###  2.11 The Group Isomorphism Problem

The last Dehn’s decision problem we discuss is the group isomorphism problem.
This problem has been proved to be undecidable in general. On the other hand,
when the groups are given in other ways the problem arises with different
complexities. For example, if the groups are given in multiplication tables,
this problem can be reduced by polynomial reduction to well known NP-problem
the graph isomorphism problem [84].

###  2.12 The Hidden Subgroup Problem

Let $G$ be a group, $H$ be a subgroup of $G,$ $S$ be a finite set. A function
$f:G\rightarrow S$ is said to hide $H$ if for any $g_{1},g_{2}\in G$, the
equality $f(g_{1})=f(g_{2})$ is true if and only if $g_{1}H=g_{2}H$.

The Hidden Subgroup Problem - HSP: Given a group $G$ and oracle access to a
function $f:G\rightarrow S$ which hides a subgroup $H$ of $G.$ Find a
generating set for $H.$

HSP has very interesting instances like well known computational hard problems
on which today’s cryptographic structures are based: the integer factorization
problem, the discrete logarithm problem, the period-finding problem, the graph
isomorphism problem, the shortest vector problem, etc. It appears in most of
the quantum algorithms developed to date. For example, Simon’s problem is the
problem of distinguishing the trivial subgroup from an order two subgroup in
the group $Z_{2}^{n}$ and can be solved on quantum computers. Shor’s algorithm
is inspired by Simon’s problem. Shor’s integer factorization and discrete
logarithm quantum algorithm solves a special case of the HSP. Shor’s algorithm
for integer factorization is basically equivalent to the Abelian HSP problem.
Shor’s applications to the graph isomorphism problem and the shortest vector
problem on the lattice are equivalent to the HSP problem over other non-
Abelian groups.

There are polynomial-time efficient quantum solutions for the Abelian HSP
[85]. The solution of the HSP problem in non-Abelian groups will revolutionize
the quantum world. Because this solution will also solve the graph isomorphism
problem and the shortest vector problem on lattices. As is known, lattice-
based problems are used in most of the methods proposed by NIST as quantum-
safe. If the shortest vector problem on lattices is solved, the quantum
security of most solutions submitted to NIST’s competition will also be
questioned. For this reason, HSP is a well-studied problem among quantum
researchers.

The complexity of problems such as HSP can be measured in two ways. The first
metric is query complexity. The query complexity of an algorithm is the number
of times the function $f$ is evaluated by an oracle, which is developed as a
black box. The other measure is computational (or time) complexity.
Computational complexity indicates how many times basic operations such as
addition and multiplication are performed in the algorithm. An algorithm
developed for solving HSP is accepted as efficient if its both query and
computational complexity is polynomial in $log(|G|)$ [86].

Ettinger et all. [87] gave a quantum algorithm which identifies a hidden
subgroup of an arbitrary finite group in polynomial query complexity. But it
has exponential time complexity. Yet, it is an open problem whether there is
an efficient solution for HSP on arbitrary non-abelian group. Instances of the
non-Abelian HSP that are not known to have efficient quantum algorithms
includes the dihedral hidden subgroup problem (DHSP) and the symmetric hidden
subgroup problem.

Regev[88] gave a solution to the unique shortest vector problem (SVP) , which
lies in NP and coNP, under the assumption that there exists an algorithm that
solves DHSP by coset sampling. The best results for DHSP is the Kupenberg’s
quantum algorithm [89], which runs in time and query complexity
$2^{\emph{O}(\sqrt{log|G|})}$ where $|G|$ is the order of the group. In other
words, it is subexponential. Also the space requirement of this algorithm is
also subexponential. Regev [90] described a modified algorithm whose space
requirement is polynomial and running time is still subexponential and but
slightly higher than Kuperberg’s algorithm. It is known that efficient quantum
algorithm for the symmetric hidden subgroup problem implies to an efficient
quantum algorithm for graph isomorphism [91],[92].

Hidden Shift Problem:
Given a finite group $G,$ a set $X$ and oracle access to two injective
functions $f,g:G\rightarrow X$ with the property that there exists an element
$s\in G$ such that the equality $g(x)=f(xs)$ holds for all $x\in G$. Find the
secret shift element $s.$

The hidden shift problem is also known as the hidden subgroup problem. For the
abelian group $G=\mathbb{Z}_{n}$ this problem is equivalent to DHSP. For
arbitrary non-Abelian group $G,$ the hidden shift problem on $G$ with secret
$s$ gives HSP on the wreath product $G\wr S_{2}$ with the hidden subgroup
$H=\langle(s,s^{-1},1)\rangle.$ Indeed symmetric groups, the hidden shift and
the hidden subgroup problems are equivalent [93].

## References

  * [1] J. Bootle, A. Cerulli, P. Chaidos, and J. Groth, “Efficient zero-knowledge proof systems,” in _Foundations of security analysis and design VIII_. Springer, 2016, pp. 1–31.
  * [2] G. Oded, _Foundations of cryptography basic tools_. Cambridge University Press, 2001.
  * [3] S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” _SIAM Journal on computing_ , vol. 18, no. 1, pp. 186–208, 1989.
  * [4] M. Blum, P. Feldman, and S. Micali, “Non-interactive zero-knowledge and its applications. stoc 1988,” 1988.
  * [5] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” in _Conference on the theory and application of cryptographic techniques_. Springer, 1986, pp. 186–194.
  * [6] O. Goldreich and Y. Oren, “Definitions and properties of zero-knowledge proof systems,” _Journal of Cryptology_ , vol. 7, no. 1, pp. 1–32, 1994.
  * [7] D. Chaum, J.-H. Evertse, and J. Van De Graaf, “An improved protocol for demonstrating possession of discrete logarithms and some generalizations,” in _Workshop on the Theory and Application of of Cryptographic Techniques_. Springer, 1987, pp. 127–141.
  * [8] U. Feige, A. Fiat, and A. Shamir, “Zero-knowledge proofs of identity,” _Journal of cryptology_ , vol. 1, no. 2, pp. 77–94, 1988.
  * [9] T. Beth, “A fiat-shamir-like authentication protocol for the el-gamal-scheme,” in _Advances in Cryptology-proceedings of EUROCRYPT_ , vol. 88, 1988, pp. 77–86.
  * [10] L. C. Guillou and J.-J. Quisquater, “A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory,” in _Workshop on the theory and application of of cryptographic techniques_. Springer, 1988, pp. 123–128.
  * [11] Y. Desmedt, “Subliminal-free authentication and signature,” in _Workshop on the Theory and Application of of Cryptographic Techniques_. Springer, 1988, pp. 23–33.
  * [12] C.-P. Schnorr, “Efficient signature generation by smart cards,” _Journal of cryptology_ , vol. 4, no. 3, pp. 161–174, 1991.
  * [13] E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza, “Succinct $\\{$Non-Interactive$\\}$ zero knowledge for a von neumann architecture,” in _23rd USENIX Security Symposium (USENIX Security 14)_ , 2014, pp. 781–796.
  * [14] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell, “Bulletproofs: Short proofs for confidential transactions and more,” in _2018 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2018, pp. 315–334.
  * [15] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev, “Scalable, transparent, and post-quantum secure computational integrity,” _Cryptology ePrint Archive_ , 2018.
  * [16] Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Zero-knowledge from secure multiparty computation,” in _Proceedings of the thirty-ninth annual ACM symposium on Theory of computing_ , 2007, pp. 21–30.
  * [17] E. Ben-Sasson, L. Goldberg, and D. Levit, “Stark friendly hash–survey and recommendation,” _Cryptology ePrint Archive_ , 2020.
  * [18] A. Canteaut, T. Beyne, I. Dinur, M. Eichlseder, G. Leander, G. Leurent, M. Naya-Plasencia, L. Perrin, Y. Sasaki, Y. Todo _et al._ , “Report on the security of stark-friendly hash functions (version 2.0),” _HAL Id: hal-02883253_ , 2020.
  * [19] O. Goldreich, S. Micali, and A. Wigderson, “Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems,” _J. ACM_ , vol. 38, no. 3, p. 690–728, Jul. 1991.
  * [20] S. A. Fenner and Y. Zhang, “Quantum algorithms for a set of group theoretic problems,” in _Italian Conference on Theoretical Computer Science_. Springer, 2005, pp. 215–227.
  * [21] V. Arvind and B. Das, “SZK proofs for black-box group problems,” _Theory of Comp. Sys._ , vol. 43, no. 2, 2008.
  * [22] N. M. Sdroievski, M. V. da Silva, and A. L. Vignatti, “The hidden subgroup problem and MKTP,” _Theoretical Computer Science_ , vol. 795, pp. 204 – 212, 2019.
  * [23] W. Diffie and M. Hellman, “New directions in cryptography,” _IEEE transactions on Information Theory_ , vol. 22, no. 6, pp. 644–654, 1976.
  * [24] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” _Communications of the ACM_ , vol. 21, no. 2, pp. 120–126, 1978.
  * [25] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” _IEEE transactions on information theory_ , vol. 31, no. 4, pp. 469–472, 1985.
  * [26] A. J. Menezes and S. A. Vanstone, “A note on cyclic groups, finite fields, and the discrete logarithm problem,” _Applicable Algebra in Engineering, communication and computing_ , vol. 3, no. 1, pp. 67–74, 1992.
  * [27] S. R. Blackburn, “Cryptanalysing the critical group: efficiently solving biggs’s discrete logarithm problem,” _Journal of Mathematical Cryptology_ , vol. 3, no. 3, pp. 199–203, 2009.
  * [28] F. Shokrieh, “The monodromy pairing and discrete logarithm on the jacobian of finite graphs,” _Journal of Mathematical Cryptology_ , vol. 4, no. 1, pp. 43–56, 2010.
  * [29] J. Groth, “Linear algebra with sub-linear zero-knowledge arguments,” in _Annual International Cryptology Conference_. Springer, 2009, pp. 192–208.
  * [30] S. Bayer and J. Groth, “Efficient zero-knowledge argument for correctness of a shuffle,” in _Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2012, pp. 263–280.
  * [31] J. Bootle, A. Cerulli, P. Chaidos, J. Groth, and C. Petit, “Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting,” in _Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2016, pp. 327–357.
  * [32] N. Koblitz and A. Menezes, “Intractable problems in cryptography,” in _Proceedings of the 9th Conference on Finite Fields and Their Applications. Contemporary Mathematics_ , vol. 518, 2010, pp. 279–300.
  * [33] U. M. Maurer and S. Wolf, “The diffie–hellman protocol,” _Designs, Codes and Cryptography_ , vol. 19, no. 2, pp. 147–171, 2000.
  * [34] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in _Proceedings 35th annual symposium on foundations of computer science_. Ieee, 1994, pp. 124–134.
  * [35] M. Dehn, “Über unendliche diskontinuierliche gruppen,” _Mathematische Annalen_ , vol. 71, no. 1, pp. 116–144, 1911.
  * [36] P. S. Novikov, “Algorithmic unsolvability of the word problem in group theory,” _Journal of Symbolic Logic_ , vol. 23, no. 1, 1958.
  * [37] S. Adian, “Unsolvability of several algorithmic problems in group theory,” _Tr. Mos. Mat. Obshch_ , vol. 6, pp. 231–298, 1957.
  * [38] J.-C. Birget, A. Y. Ol’shanskii, E. Rips, and M. V. Sapir, “Isoperimetric functions of groups and computational complexity of the word problem,” _Annals of Mathematics_ , pp. 467–518, 2002.
  * [39] M. V. Sapir, J.-C. Birget, and E. Rips, “Isoperimetric and isodiametric functions of groups,” _Annals of Mathematics_ , pp. 345–466, 2002.
  * [40] N. R. Wagner and M. R. Magyarik, “A public-key cryptosystem based on the word problem,” in _Workshop on the Theory and Application of Cryptographic Techniques_. Springer, 1984, pp. 19–36.
  * [41] M. I. G. Vasco and R. Steinwandt, “A reaction attack on a public key cryptosystem based on the word problem,” _Applicable Algebra in Engineering, Communication and Computing_ , vol. 14, no. 5, pp. 335–340, 2004\.
  * [42] J.-C. Birget, S. S. Magliveras, and M. Sramka, “On public-key cryptosystems based on combinatorial group theory.” _IACR Cryptol. ePrint Arch._ , vol. 2005, p. 70, 2005.
  * [43] A. J. Do Long Van, R. Siromony, and K. Subramanian, “Public key cryptosystems based on word problems,” in _ICOMIDC Symp. Math. of Computations, Ho Chi Minh City_ , 1988.
  * [44] G. Petrides, “Cryptanalysis of the public key cryptosystem based on the word problem on the grigorchuk groups,” in _IMA International Conference on Cryptography and Coding_. Springer, 2003, pp. 234–244.
  * [45] D. Panagopoulos, “A secret sharing scheme using groups,” _arXiv preprint arXiv:1009.0026_ , 2010.
  * [46] M. Habeeb, D. Kahrobaei, and V. Shpilrain, “A secret sharing scheme based on group presentations and the word problem,” _Contemp. Math., Amer. Math. Soc_ , vol. 582, pp. 143–150, 2012.
  * [47] S. Lipschutz and C. F. Miller III, “Groups with certain solvable and unsolvable decision problems,” _Communications on Pure and Applied Mathematics_ , vol. 24, no. 1, pp. 7–15, 1971.
  * [48] K. Mikhailova, “The occurrence problem for direct products of groups,” _Matematicheskii Sbornik_ , vol. 112, no. 2, pp. 241–251, 1966.
  * [49] J. McCool, “Unsolvable problems in groups with solvable word problem,” _Canadian Journal of Mathematics_ , vol. 22, no. 4, pp. 836–838, 1970.
  * [50] S. Sze, D. Kahrobaei, R. Dambreville, and M. Dupas, “Finding $n$-th roots in nilpotent groups and applications in cryptology,” _International Journal of Pure and Applied Mathematics_ , vol. 70, no. 4, p. 571, 2011.
  * [51] H. Sibert, P. Dehornoy, and M. Girault, “Entity authentication schemes using braid word reduction,” _Discrete Applied Mathematics_ , vol. 154, no. 2, pp. 420–436, 2006.
  * [52] A. Myasnikov, A. Nikolaev, and A. Ushakov, “Knapsack problems in groups,” _Mathematics of Computation_ , vol. 84, no. 292, pp. 987–1016, 2015.
  * [53] A. Miasnikov and P. Schupp, “Computational complexity and the conjugacy problem,” _Computability_ , vol. 6, no. 4, pp. 307–318, 2017.
  * [54] I. Anshel, M. Anshel, and D. Goldfeld, “An algebraic method for public-key cryptography,” _Mathematical Research Letters_ , vol. 6, no. 3, pp. 287–291, 1999.
  * [55] R. Grigorchuk and D. Grigoriev, “Key agreement based on automaton groups,” _Groups Complexity Cryptology_ , vol. 11, no. 2, pp. 77–81, 2019.
  * [56] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J.-s. Kang, and C. Park, “New public-key cryptosystem using braid groups,” in _Annual International Cryptology Conference_. Springer, 2000, pp. 166–183.
  * [57] V. Shpilrain and A. Ushakov, “The conjugacy search problem in public key cryptography: unnecessary and insufficient,” _Applicable Algebra in Engineering, Communication and Computing_ , vol. 17, no. 3-4, pp. 285–289, 2006\.
  * [58] A. Myasnikov, V. Shpilrain, and A. Ushakov, “A practical attack on a braid group based cryptographic protocol,” in _Annual International Cryptology Conference_. Springer, 2005, pp. 86–96.
  * [59] N. Mosina and A. Ushakov, “Mean-set attack: cryptanalysis of sibert et al. authentication protocol,” _Journal of Mathematical Cryptology_ , vol. 4, no. 2, pp. 149–174, 2010.
  * [60] F. A. Garside, “The braid group and other groups,” _The Quarterly Journal of Mathematics_ , vol. 20, no. 1, pp. 235–254, 1969.
  * [61] J. Birman, K. H. Ko, and S. J. Lee, “A new approach to the word and conjugacy problems in the braid groups,” _Advances in Mathematics_ , vol. 139, no. 2, pp. 322–353, 1998.
  * [62] E. A. Elrifai and H. R. Morton, “Algorithms for positive braids,” _The Quarterly Journal of Mathematics_ , vol. 45, no. 4, pp. 479–497, 1994.
  * [63] N. Franco and J. González-Meneses, “Conjugacy problem for braid groups and garside groups,” _Journal of Algebra_ , vol. 266, no. 1, pp. 112–132, 2003\.
  * [64] V. Gebhardt, “A new approach to the conjugacy problem in garside groups,” _Journal of Algebra_ , vol. 292, no. 1, pp. 282–302, 2005.
  * [65] J. H. Cheon and B. Jun, “A polynomial time algorithm for the braid diffie-hellman conjugacy problem,” in _Annual International Cryptology Conference_. Springer, 2003, pp. 212–225.
  * [66] E. Lee and J. H. Park, “Cryptanalysis of the public-key encryption based on braid groups,” in _International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2003, pp. 477–490.
  * [67] D. Garber, S. Kaplan, M. Teicher, B. Tsaban, and U. Vishne, “Length-based conjugacy search in the braid group,” _arXiv preprint math/0209267_ , 2002\.
  * [68] D. Hofheinz and R. Steinwandt, “A practical attack on some braid group based cryptographic primitives,” in _International Workshop on Public Key Cryptography_. Springer, 2003, pp. 187–198.
  * [69] V. Roman’kov, “The twisted conjugacy problem for endomorphisms of polycyclic groups,” _Journal of Group Theory_ , vol. 13, no. 3, pp. 355–364, 2010.
  * [70] O. Bogopolski, A. Martino, O. Maslakova, and E. Ventura, “The conjugacy problem is solvable in free-by-cyclic groups,” _Bulletin of the London Mathematical Society_ , vol. 38, no. 5, pp. 787–794, 2006.
  * [71] J.-P. Préaux, “The conjugacy problem in groups of non-orientable 3-manifolds,” _Groups, Geometry, and Dynamics_ , vol. 10, no. 1, pp. 473–522, 2016.
  * [72] V. Shpilrain and A. Ushakov, “An authentication scheme based on the twisted conjugacy problem,” in _International Conference on Applied Cryptography and Network Security_. Springer, 2008, pp. 366–372.
  * [73] M. Grassl and R. Steinwandt, “Cryptanalysis of an authentication scheme using truncated polynomials,” _Information processing letters_ , vol. 109, no. 15, pp. 861–863, 2009.
  * [74] M. N. Gornova, E. G. Kukina, and V. A. Roman’kov, “Cryptanalysis of ushakov–shpilrain’s authentication protocol based on the twisted conjugacy problem,” _Prikladnaya Diskretnaya Matematika_ , vol. 2, pp. 46–53, 2015\.
  * [75] C. M. Hoffmann, “Subcomplete generalizations of graph isomorphism,” _Journal of Computer and System Sciences_ , vol. 25, no. 3, pp. 332–359, 1982\.
  * [76] E. M. Luks, “Permutation groups and polynomial-time computation,” _DIMACS Series in Discrete Mathematics and Theoretical Computer Science_ , vol. 11, pp. 139–175, 1993.
  * [77] L. Babai, “Graph isomorphism in quasipolynomial time,” in _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , 2016, pp. 684–697.
  * [78] E. L. Post, “A variant of a recursively unsolvable problem,” _Bulletin of the American Mathematical Society_ , vol. 52, no. 4, pp. 264–268, 1946.
  * [79] M. R. Garey and D. S. Johnson, _Computers and intractability: A Guide to the Theory of NP-Completeness_. Freeman San Francisco, 1978, vol. 174.
  * [80] V. Roman’kov, “Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings,” _Algebra and Logic_ , vol. 16, no. 4, pp. 310–320, 1977.
  * [81] V. A. Roman’kov, “Equations in free metabelian groups,” _Siberian Mathematical Journal_ , vol. 20, no. 3, pp. 469–471, 1979.
  * [82] D. Grigoriev and V. Shpilrain, “Zero-knowledge authentication schemes from actions on graphs, groups, or rings,” _arXiv preprint arXiv:0802.1661_ , 2008\.
  * [83] S. Y. Erofeev and V. A. Roman’kov, “On constructing possibly one-way functions based on the non-decidability of the endomorphism problem in groups,” _Prikladnaya Diskretnaya Matematika_ , vol. 3, pp. 13–24, 2012.
  * [84] G. L. Miller, “Graph isomorphism, general remarks,” _Journal of Computer and System Sciences_ , vol. 18, no. 2, pp. 128–142, 1979.
  * [85] S. Hallgren, A. Russell, and A. Ta-Shma, “The hidden subgroup problem and quantum computation using group representations,” _SIAM Journal on Computing_ , vol. 32, no. 4, pp. 916–934, 2003.
  * [86] P. Koiran, V. Nesme, and N. Portier, “The quantum query complexity of the abelian hidden subgroup problem,” _Theoretical computer science_ , vol. 380, no. 1-2, pp. 115–126, 2007.
  * [87] M. Ettinger, P. Høyer, and E. Knill, “The quantum query complexity of the hidden subgroup problem is polynomial,” _Information Processing Letters_ , vol. 91, no. 1, pp. 43–48, 2004.
  * [88] O. Regev, “Quantum computation and lattice problems,” _SIAM Journal on Computing_ , vol. 33, no. 3, pp. 738–760, 2004.
  * [89] G. Kuperberg, “A subexponential-time quantum algorithm for the dihedral hidden subgroup problem,” _SIAM Journal on Computing_ , vol. 35, no. 1, pp. 170–188, 2005.
  * [90] O. Regev, “A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space,” _arXiv preprint quant-ph/0406151_ , 2004\.
  * [91] D. Boneh and R. J. Lipton, “Quantum cryptanalysis of hidden linear functions,” in _Annual International Cryptology Conference_. Springer, 1995, pp. 424–437.
  * [92] M. Ettinger and P. Hoyer, “A quantum observable for the graph isomorphism problem,” _arXiv preprint quant-ph/9901029_ , 1999.
  * [93] S. Hallgren, C. Moore, M. Rötteler, A. Russell, and P. Sen, “Limitations of quantum coset states for graph isomorphism,” _Journal of the ACM (JACM)_ , vol. 57, no. 6, pp. 1–33, 2010.


# Orbital Stability of Proposed NY Virginis Exoplanets

Xinyu Mai,1 Robert L. Mutel1
1Department of Physics and Astronomy, University of Iowa, Iowa City, IA 52242,
USA
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
(Accepted XXX. Received YYY; in original form ZZZ)

###### Abstract

Er et al. (2021) recently proposed a two-planet solution to account for
eclipse timing variations (ETVs) observed from the sdB binary NY Virginis. We
tested the proposed planetary system for orbit stability using both numerical
simulations and chaotic behavior analysis. The best-fit orbits, as well as
those with parameters varying by the published uncertainty range in each
parameter, were unstable on a timescale much less than the presumed lifetime
of the PCEB phase ($\sim$100 Myr). suggesting that the proposed circumbinary
companions fail to provide a complete explanation for the observed ETVs.

###### keywords:

binaries: close - binaries: eclipsing - stars: individual: NY Virginis -
planetary systems

††pubyear: 2022††pagerange: Orbital Stability of Proposed NY Virginis
Exoplanets–Orbital Stability of Proposed NY Virginis Exoplanets

##  1 Introduction

Eclipse timing variations (ETVs) have been used to infer the existence of
orbiting sub-stellar companions in more than a dozen short-period binaries,
the majority of which are post-common binaries with hot sub-luminous primaries
with orbital periods 2 – 3 hours (Heber, 2016). Since the substellar
components perturb the center of the mass of the binary, their masses and
orbital elements can be inferred by fitting the O-C plot, i.e., the time
difference history between the observed times of eclipse minima and a linear
ephemeris, ideally over a timescale longer than the orbital period of the most
distant companion.

This scheme has proven to be problematic for several reasons. First, typical
timing offsets caused by a Jovian size planet are relatively small, of order
one percent of the orbital period i.e., tens of seconds. This is not much
larger than many published timing uncertainties, which are obtained using
small telescopes that typically perform synoptic observations of these
systems. The corresponding fitted model parameters have large uncertainties
and/or degeneracies. Second, several other physical mechanisms can contribute
to timing variations in these binaries (e.g., angular momentum transfer,
apsidal motion, relativistic gravitational radiation), making even the
existence of substellar components somewhat conjectural (Applegate, 1992;
Lanza et al., 1998; Zorotovic & Schreiber, 2013; Lanza, 2020; Mai & Mutel,
2022; Pulley et al., 2022). Third, several published multi-component models
have been subsequently shown to be highly unstable on timescales that are
short compared with the expected lifetimes of the post-common envelope phase,
vitiating the viability of the respective sub-component models. (e.g., Tinney
et al., 2012; Wittenmyer et al., 2012; Wittenmyer et al., 2013; Brown-Sevilla
et al., 2021; Esmer et al., 2021).

In this letter, we examine orbit stability of the two-component model recently
reported by Er et al. (2021) for the sdB binary NY Virginis. Their model is
based on previously published O-C timing plus 51 new mid-eclipse times,
extending the timeline to 25 years. Their model comprises two planets with
masses of 2.74 MJup and 5.59 MJup with semi-major axes 3.64 and 7.64 AU and
eccentricities of 0.12 and 0.19 respectively (see Table1 for full orbital
elements). Their derived planetary masses are similar to those of Song et al.
(2019), but with a higher eccentricity for the outer planet. The best-fit
orbits, along with neighboring orbits encompassing Er et al.’s uncertainty
range in each parameter, are plotted in Fig.1.

Table 1: NY Vir Two Component Model (Er et al. 2021)

[b]  Parameter Fitted Values Unit Inner Binary T0 2453174.442636 BJD P0
0.1010159686 day $\dot{P}$ ${2.64}$ $10^{-12}$ s/s Substellar Components LTT 1
LTT 2 $P$ $8.97_{-0.24}^{+0.36}$ $27.2_{-1.2}^{+1.3}$ yr $e$
$0.12_{-0.12}^{+0.12}$ $0.19_{-0.07}^{+0.09}$ $K$ $7.9_{-0.8}^{+1.0}$
$33.8_{-2.9}^{+2.4}$ sec $a\cdot$sin($i$)1 $3.64_{-0.37}^{+0.41}$
$7.64_{-0.43}^{+0.45}$ AU $\omega$ $351_{-52}^{+69}$ $38_{-34}^{+42}$ degree
Min. Mass $2.74_{-0.34}^{+0.37}$ $5.59_{-0.49}^{+0.51}$ MJup

  * 1

Planetary semi-major axes calculated from mass and period for each planet from
the Er et al. (2021) Table 3 using Kepler’s third law.

Figure 1: Best-fit two-planet orbits proposed by Er et al. (2021) around the
PCEB NY Vir , and neighboring orbits using best-fit parameters, but varying by
the uncertainty range given by Er et al. in each parameter. The trajectory in
red indicates for proposed inner body, trajectory in blue for the outer body.
Orbits associated with the change of one uncertainty are shown as black lines.
The binary star position is shown as a star at the center. This figure is made
by orbit simulation software rebound (Rein & Liu, 2012) using best-fit
parameters for each component in Table 1.

##  2 Orbit Stability Analysis

To examine the orbital stability of the proposed planetary system, we
performed dynamical simulation using the best-fit planetary masses and orbital
elements listed in Er et al. (2021) Table 3. In particular, we converted the
projected semi-major axis of the binary star due to two additional companions
$a_{1,2}\sin_{i_{3,4}}$ into planetary semi-major axes using the given mass
and period for each planet. In addition, we tested models for which each mass
and orbital parameter were varied by the uncertainty ranges given in Table 3
of Er et al. from their best-fit value, for a total of 24 parameter sets.

We used both the N-body orbital integration package REBOUND (Rein & Liu, 2012)
and the chaotic indicator program, the Mean Exponential Growth factor of
Nearby Orbits (MEGNO) (Cincotta & Simó, 2000; Hinse et al., 2010). We first
tested dynamical stability by numerically integrating the component orbits
using MERCURIUS (Rein et al., 2019), a hybrid symplectic integrator similar to
MERCURY (Chambers, 1999). It uses WHFast, a Wisdom-Holman symplectic
integrator (Rein & Tamayo, 2015) for long term integrations, but switches to
IAS15, an adaptive non-symplectic integrator (Rein & Spiegel, 2015) for close
encounters.

We used an initial time step of 0.1 yr and integrated for 100 Myr. We treated
the binary star as a single mass $M_{tot}=0.59M_{\odot}$ Vucković et al.
(2009) and restricted the model to co-planar orbits. In addition, we tested
chaotic behavior of each parameter set using the MEGNO indicator with a time
interval 10 Myr to search for chaotic phase-space regions. For a given
integration time, MEGNO numerically evaluates a dimensionless quantitative
measure of chaos in the system, and generates a mapping of phase-space regions
with MEGNO values (Go´zdziewski, K. et al., 2001; Hinse et al., 2010). For the
MEGNO calculations, we varied two orbital parameters, the semi-major axis and
the eccentricity. We ran simulations for a range of 128 semi-major axes and
128 eccentricity values for the inner and outer planets.

##  3 Results

As shown in Figure 2, our simulated dynamical result shows that the proposed
best-fit planetary system of Er et al. becomes unstable for evolutionary times
longer than $\sim$3 Myr, which is much less than the timescale of the PCEB
phase for second-generation planets. In addition, the MEGNO chaos parameter,
shown in Fig. 3, is greater than 10 at the proposed solution coordinates
(white dots) for both planets, implying highly chaotic behavior (N.B. values
less than 2 imply non-chaotic behavior, (e.g., Hinse et al., 2010)).

Figure 2: NY Vir stability plot using the best-fit two-component planetary
model of Er et al. (2021). (a) Time history of the eccentricities of both
circumbinary companions over 10 Myr. (b) time history of semi-major axes of
both circumbinary companions over 10 Myr. Note that the outer planet (orange
line) escapes the planetary system after 3.5 Myr. Figure 3: MEGNO chaos
parameter surface map for Er et al. (2021) two-planet solution for a range of
eccentricities and semi-major axes for the (a) inner planet and (b) outer
planet. The best-fit model parameter values (Table 1) are indicated by white
dots with black borders. Both points lie in highly chaotic regions. The shaded
red regions are the approximate posterior probability distribution functions
for eccentricity and semi-major axis of each planet based on Er et al. (2021)
Figure 4. ${\it Note}$: MEGNO values less than 2 are consistent with non-
chaotic behavior (e.g., Hinse et al., 2010).

##  4 Discussion and Conclusion

We find that the proposed two-planet model for the binary NY Virginis proposed
by Er et al. (2021) becomes unstable after $\sim$3 Myr, a timescale much less
than the estimated lifetime of the PCEB phase (100 Myr) of sdB binaries, and
is therefore untenable. In addition, we find that all solutions that vary from
the best-fit solution by the uncertainty range in each parameter are also
unstable on similar or shorter timescales. This conclusion is supported by an
independent stability indicator, the chaos metric MEGNO. We evaluated the
MEGNO map chaotic behavior in parameter space over 10 Myr and found that both
planets have orbital parameters than lie in regions of highly chaotic
behavior.

The previous two-planet solution for NY Vir proposed by Song et al. (2019),
although stable over more than 10 Myr, does not fit more recent O-C data, as
shown both by (Er et al., 2021, Fig.3) and (Pulley et al., 2022, Fig.2).
Hence, the situation for NY Vir is very similar to at least two other sdB
binaries, HW Vir and HS0705+67: Sub-stellar component models that provide an
adequate fit to the ETV historical data are dynamically unstable. Likewise,
solutions that are constrained to be long-term stable do not result in
adequate fits to the ETV data, as we have recently demonstrated (Mai & Mutel,
2022).

As the number of these confounding systems increases, it is becoming clear
that interpreting ETV variations in sdB binaries as resulting solely from
gravitational perturbations from orbiting sub-stellar objects is untenable,
and that the observed ETV signatures must be at least in part a result of
other physical mechanisms.

## Acknowledgements

This research made use of astropy, a community-developed core python package
for Astronomy (Astropy Collaboration et al., 2013, 2018). Numerical orbit
integrations in this paper made use of the rebound N-body code (Rein & Liu,
2012). The simulations were integrated using whfast, a Wisdom-Holman
symplectic integrator (Rein & Tamayo, 2015). This work is supported by the
National Science Foundation (NSF) under grant 1517412.

## Data Availability

There are no new data associated with this letter.

## References

  * Applegate (1992) Applegate J. H., 1992, ApJ, 385, 621
  * Astropy Collaboration et al. (2013) Astropy Collaboration et al., 2013, A&A, 558, A33
  * Astropy Collaboration et al. (2018) Astropy Collaboration et al., 2018, AJ, 156, 123
  * Brown-Sevilla et al. (2021) Brown-Sevilla S. B., et al., 2021, Monthly Notices of the Royal Astronomical Society, 506, 2122
  * Chambers (1999) Chambers J. E., 1999, MNRAS, 304, 793
  * Cincotta & Simó (2000) Cincotta P. M., Simó C., 2000, Astron. Astrophys. Suppl. Ser., 147, 205
  * Er et al. (2021) Er H., Özdönmez A., Nasiroglu I., 2021, MNRAS, 507, 809
  * Esmer et al. (2021) Esmer E. M., Baştürk Ö., Hinse T. C., Selam S. O., Correia A. C. M., 2021, Astronomy & Astrophysics, 648, A85
  * Go´zdziewski, K. et al. (2001) Go´zdziewski, K. Bois, E. Maciejewski, A. J. Kiseleva-Eggleton, L. 2001, A&A, 378, 569
  * Heber (2016) Heber U., 2016, Publications of the Astronomical Society of the Pacific, 128, 082001
  * Hinse et al. (2010) Hinse T. C., Christou A. A., Alvarellos J. L. A., Goździewski K., 2010, MNRAS, 404, 837
  * Lanza (2020) Lanza A. F., 2020, MNRAS, 491, 1820
  * Lanza et al. (1998) Lanza A. F., Rodono M., Rosner R., 1998, Monthly Notices of the Royal Astronomical Society, 296, 893
  * Mai & Mutel (2022) Mai X., Mutel R. L., 2022, Monthly Notices of the Royal Astronomical Society, 513, 2478
  * Pulley et al. (2022) Pulley D., Sharp I. D., Mallett J., vonÂ Harrach S., 2022, Monthly Notices of the Royal Astronomical Society, 514, 5725
  * Rein & Liu (2012) Rein H., Liu S. F., 2012, A&A, 537, A128
  * Rein & Spiegel (2015) Rein H., Spiegel D. S., 2015, MNRAS, 446, 1424
  * Rein & Tamayo (2015) Rein H., Tamayo D., 2015, Monthly Notices of the Royal Astronomical Society, 452, 376
  * Rein et al. (2019) Rein H., et al., 2019, MNRAS, 485, 5490
  * Song et al. (2019) Song S., Mai X., Mutel R. L., Pulley D., Faillace G., Watkins A., 2019, The Astronomical Journal, 157, 184
  * Tinney et al. (2012) Tinney C. G., Wittenmyer R. A., Horner J., Hinse T. C., 2012, Monthly Notices of the Royal Astronomical Society, 425, 749
  * Vucković et al. (2009) Vucković M., Østensen R. H., Aerts C., Telting J. H., Heber U., Oreiro R., 2009, A&A, 505, 239
  * Wittenmyer et al. (2012) Wittenmyer R. A., Horner J., Marshall J. P., Butters O. W., Tinney C. G., 2012, Monthly Notices of the Royal Astronomical Society, 419, 3258
  * Wittenmyer et al. (2013) Wittenmyer R. A., Horner J., Marshall J. P., 2013, Monthly Notices of the Royal Astronomical Society, 431, 2150
  * Zorotovic & Schreiber (2013) Zorotovic M., Schreiber M. R., 2013, Astronomy and Astrophysics, 549, A95