# when do we need composite order groups for bilinear maps and when prime order?

Why we need bilinear groups of composite order? What's the special security property of the composite order group in comparison with one of prime order?To put it in another way when do we need composite order groups for bilinear maps and when prime order?

-

A composite order group is like having a 2-dimensional vector space, because of the Chinese Remainder Theorem. More concretely in the context of a bilinear map, if $g$ is a generator with order $N=pq$, then $g_p = g^q$ generates an order-$p$ subgroup, and $g_q = g^p$ generates an order-$q$, and $e(g_p, g_q) = 1$. They cancel each other out, and so you can think of $\{g_q, g_p\}$ as an orthogonal basis for the a 2-dimensional vector space.

The way this is typically used is that the bilinear "functionality" of a scheme is carried out in one dimension (e.g., in the exponent of $g_p$) while the other dimension (e.g., the exponent of $g_q$) is used for "blinding". Orthogonality ensures that the blinding factors just disappear after the bilinear map.

Recently, Okamoto & Takashima have developed a framework for cryptographic constructions using prime-order bilinear groups (called dual-pairing vector spaces, DPVS). It is a nice abstraction that allows you to build (from prime-order groups) $n$-dimensional orthogonal vector spaces that have a suitable pairing. It's like having the above effect, but now even with of a product of $n$ primes! I think most people in the field believe that prime-order constructions can be "ported" to prime-order groups, using these DPVS techniques.

-

In most cases it seems protocols initially described in the context of composite order groups can be converted to prime order groups, thanks to the work of David Freeman and others. Which is just as well as calculating pairings over composite order groups is impossibly slow, in part because only a few pairing-friendly curves of low embedding degree are suitable for use with composite order groups. So the answer to the second part of your question is that (hopefully) composite order groups for bilinear maps are never needed (although they might be continue to be used in academic papers to initially describe a new protocol).

-
"Which is just as well as calculating pairings over composite order groups is impossibly slow, in part because only a few pairing-friendly curves of low embedding degree are suitable for use with composite order groups" check your english... i can't understand – curious Sep 27 '12 at 9:53
I checked his English, and it's fine. $\:$ It might sound better it he replaced the $\hspace{1.8 in}$ second "as" with "since" or "because". $\;\;$ – Ricky Demer Sep 27 '12 at 15:24