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.

in Bilinear pairings, what is the difference between Type 2 and Type 3?

I understand in Type 2, there exists an efficiently computable homomorphic function $\phi : G_2 \rightarrow G_1$ , which is not present in Type 3 pairings.

But what I don't understand is what is the use of the homomorphism in cryptography?


For those who might need a refresher, for a bilinear pairing $e : G_1 \times G_2 \rightarrow G_T$ , we define

  • Type 2: $G_1 \neq G_2$ and there is an efficiently computable homomorphic function $\phi : G_2 \rightarrow G_1$

  • Type 3: $G_1 \neq G_2$ and there is NO efficiently computable homomorphic function

share|improve this question

2 Answers 2

up vote 5 down vote accepted

Note that you do not have an efficiently computable homomorphism from $G_1$ to $G_2$, but in Type-2 you have an efficiently computable homomorphism $\psi: G_2 \rightarrow G_1$ and in Type-3 you do not have one.

But what I don't understand is what is the use of the homomorphism in cryptography?

Well, if you have a tuple $(aP',bP',cP')\in G_2^3$ with $P'$ being a generator of $G_2$, you can check if $e(\psi(aP'),bP')=e(\psi(P'),cP')$ holds. Consequently, the decisional Diffie Hellman (DDH) problem is easy in $G_2$, but remains hard in $G_1$. In cryptography, this is typically formalized as the so called external Diffie Hellman (XDH) assumption.

In a Type-3 setting, as you can not map between $G_2$ and $G_1$, the DDH seems to be hard in $G_1$ and in $G_2$. In cryptography, this is typically formalized as the so called symmetric XDH (SXDH) assumption.

So if you have a Type-2 pairing, then you have the XDH setting and if you have a Type-3 pairing, you have the SXDH setting.

share|improve this answer
    
brilliant.. thanks :) –  Subhayan May 2 at 22:00

The paper Pairings for Cryptographers talks about the use of the homomorphisms.

Specifically:

This distinction into types is relevant for the design of cryptographic schemes. In particular, the existence of maps between $G_2$ and $G_1$ is sometimes required to get a security proof to work (see for example [6] and [17] for a general discussion on this point). There exist many primitives in pairing-based cryptography whose security proof does not apply if the cryptosystem is implemented using pairings of the third type.

I haven't followed the PBC literature close enough to give concrete examples of primitives whose security proof does not apply when using the third type. Hopefully someone else can chime in there.

share|improve this answer
    
thanks, but this paper talks ABOUT pairings .. my questions asks the use of homomorphism. –  Subhayan May 2 at 21:58
    
@Subhayan the paper talks about pairings yes, but there is relevant information in the paper about the differences in the types of pairings. This gives information on the uses of the homomorphisms (since some of the primary differences are the fact that the homomorphisms exist or do not exist). –  mikeazo May 5 at 13:34
    
yes, of course, I agree... I have already read that (in fact, almost anyone beginning PBC starts here).. I was actually haveing a little trouble understanding why one might want to use homomorphisms .. now (thanks to DrLecter and your answers), i understand it trivially :) –  Subhayan May 5 at 21:21
    
also, this paper is now a bit out of date.. it does not talk a lot about type 4 pairings, recent works of Chatterjee et al (2010), now make type 4 pairings very much accessible.. also, type 1 pairings now are not very efficient because of recent works of Zhang et al (2014) and Granger et al(2014). –  Subhayan May 5 at 21:25

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.