3

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?

user2900219
  • 31
  • 3

1 Answers1

4

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.

poncho
  • 147,019
  • 11
  • 229
  • 360
  • 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...https://eprint.iacr.org/2015/128.pdf – István András Seres Jul 02 '20 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 05 '20 at 19:11