2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – István András Seres Jul 2 at 17:57
  • $\begingroup$ 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. $\endgroup$ – user2900219 Jul 5 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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