Take the 2-minute tour ×
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
add comment

2 Answers

up vote 1 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
add comment

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

share|improve this answer
    
"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
1  
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
add comment

Your Answer

 
discard

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.