Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
I don't see how this answers the question. The question is about bilinear maps. –  mikeazo Oct 2 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. –  Vadym Fedyukovych Oct 5 at 11:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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