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?
$\begingroup$
$\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$– wladMay 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$– ponchoMay 4, 2018 at 14:31
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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}$.
answered Nov 23 at 12:10
-
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