# 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 composite-order constructions can be "ported" to prime-order groups, using these DPVS techniques.

: Hierarchical Predicate Encryption for Inner-Products, by Okamoto, Tatsuaki and Takashima, Katsuyuki, in Advances in Cryptology -- ASIACRYPT 2009, 2009

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 since 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).

One specific example of a multiplicative group of a composite order is RSA. Group order could be not known to a proving party (hidden from). With this setup, one can prove relations over integers, not residues modulo group order. Proof based on Lagrange 4-squares theorem is a well-known example. No efficient implementation is known for a proof of "more" relation for a secret committed with a group of a known prime order. The best implementation of such a proof with a prime-order group assumes commitments to bits of the secret.

• I don't see how this answers the question. The question is about bilinear maps. Oct 2, 2015 at 12:20
• Reagrdless of bilinear maps, composite order can be made unknown (just like RSA) resulting in efficient proofs for integers (not field elements). One particular example is "more" proof designed from four-squares theorem. One would expect even more interesting proof protocols with bilinear maps of hidden order. Oct 5, 2015 at 11:37