2
$\begingroup$

Is there any group in which not only discrete logarithm and finding square root are believed to be hard, but also finding the inverse of a given element?

$\endgroup$
2
  • $\begingroup$ How about the group consisting of operations $m \mapsto m^e \mod pq$ where $p$ and $q$ are fixed primes and $e$ is any integer such that $\gcd(e,(p-1)(q-1))=1$. Can somebody confirm if that works? $\endgroup$
    – wlad
    May 4, 2018 at 10:08
  • 1
    $\begingroup$ @ogogmad: kind-of. For starters, we need to define what a group element looks like, and what the group operator is. Having the group element be represented as $m^e$ with the operator $m^e \odot m^d = m^{ed}$ doesn't work. What might work is have the representation be $e$, and the group operation $e \odot d = e \times d$ (no modulus), and the equality test $g^e \equiv g^d \pmod{pq}$. The issues with this representation is that the size grows unbounded as we do more operations, and some problems are unexpectedly easy; if someone computes $a \odot b$ and gives us that and $a$, we can recover $b$ $\endgroup$
    – poncho
    May 4, 2018 at 14:31

2 Answers 2

6
$\begingroup$

Not to my knowledge. However, there are braid group and other nonabelian group-based cryptosystems proposed where the difficult problem is the conjugacy problem in a nonabelian group $G$, i.e., given $g$ and $h$ in $G$, determine whether they are conjugate. This means finding an $x$ in $G$ such that $$g=xhx^{-1}.$$

Clearly inverses play a key part in these systems. You can search eprint.iacr.org for some papers. One notable paper in this field is the one below:

Cheon, J. H., & Jun, B: *A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem*, CRYPTO 2003.

None of these systems have been widely adopted, however. One of their attraction is resistance to quantum computing-based attacks.

$\endgroup$
3
$\begingroup$

How about the multiplicative group $\mathbb{Z}_{\phi(n)}^*$, where $n=pq$ is an RSA modulus? Under the hardness of factoring, this is a hidden order group, and computing inverses in this group is as hard as factoring. One can still sample elements from the group given a bound B on $\phi(n)$, and discrete log should be hard in there as well.

Using a hidden order group feels mostly unavoidable (if you want, say, a finite cyclic group): if you know the group order $d$, you can always invert any $g \in \mathbb{G}$ by computing $g^{d-1}$.

$\endgroup$
2
  • 1
    $\begingroup$ Problems with this are that representations of elements of the group can't be unique or even finite;computation in the group leads to exponentially larger representations; and we can't publicly compare representations for equality. I attempted to fix the finite representation issue to answer that related (but different) question using the Paillier cryptosystem, but that made computing inverse easy. I'm stuck. $\endgroup$
    – fgrieu
    Nov 23 at 18:43
  • 1
    $\begingroup$ I agree, but I would say that these downsides are unavoidable, because hardness of computing inverse implies a hidden order group, which implies all of the problems you outlined. Note that in some contexts, one can partially get around the limitations by doing the operations "in the exponent": fix a generator $u$ of the quadratic residues mod $n$, then if you can somehow work in the exponent of $u$, you're properly working modulo $\phi(n)/4$. It seems contrived but multiple cryptography applications actually use this strategy. $\endgroup$ Nov 24 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.