Is it possible to build a bilinear map where the underlying group is of unknown order?
To maintain context, the original question appears below. As per poncho's excellent answer, my original idea is infeasible:
Is it possible to build a bilinear map where the underlying group is an RSA group? I.e. $e: \mathbb{Z}_N \times \mathbb{Z}_N \rightarrow \mathbb{Z}_N$ where N is an RSA modulo?
Alternatively, a bilinear map where the underlying group is of unknown order?
Is it possible to build a bilinear map where the underlying group is an RSA group?
I.e. $e: \mathbb{Z}_N \times \mathbb{Z}_N \rightarrow \mathbb{Z}_N$ where N is an RSA modulo?
If we can build a nontrivial bilinear map over arbitrary RSA groups, then we can solve the DDH problem over a prime field. Here's how:
The DDH problem is: given $g, p, g^a \bmod p, g^b \bmod p, g^c \bmod p$, is $g^{ab} \bmod p = g^c \bmod p$ ?
To solve this, we select a prime $q$ and compute $n = pq$, and then construct a bilinear map $e$ over that ring.
Then, you find the value $h$ with $h \equiv g \pmod p$ and $h \equiv 1 \pmod q$; this is a simple application of CRT
Then, the same process allows you to find $h^a$ from $g^a$ (as $h^a \equiv g^a \pmod p$ and $h^a \equiv 1 \pmod q$, and similarly $h^b$ and $h^c$
Then, you compute both $e(h^a, h^b) = e(h, h)^{ab}$ and $e(h, h^c) = e(h, h)^c$; if they're the same, then $ab \equiv c \pmod{p-1}$
We do not know how to solve the DDH problem over arbitrary prime fields, hence there is no known way to generate nontrivial bilinear maps over RSA groups.
