# Bilinear Map over group of unknown order

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.

• This paper offers a relaxation of bilinear maps, namely bilinear maps with auxiliary inputs in groups of unknown order. It uses iO, so I guess it is not really useful in practice...eprint.iacr.org/2015/128.pdf – István András Seres Jul 2 at 17:57
• Right, thanks! For what I had in mind, any bilinear map over a group of unknown order would work. I've edited the question accordingly. – user2900219 Jul 5 at 19:11