Primitives based on PairingsIEEE P1363.3 working groupDRAFT, 22 Oct 2006Hovav ShachamWeizmann Institute of Sciencehovav@cs.stanford.eduP-DHI-G:========Pairing-based crypto Diffie-Hellman inversion, generation.Input:- the P parameters p, G = <g>, e();- the DHI secret key x and public key X- the message mAssumptions: the P parameters describe a valid bilinear group; x isthe private key corresponding to X, so that X = g^x; and m is anelement of \Zp.Output: the derived secret d_m, an element of G.Operation: Use the following steps.1. If m+x = 0 mod p, output "error" and stop.2. Compute d_m = g^{1/(m+x)}.3. Output d_m.P-RDHI-G:========Pairing-based crypto Diffie-Hellman inversion, randomized generation.Input:- the P parameters p, G = <g>, e();- the RDHI secret key (x,y) and public key (X,Y)- the message mAssumptions: the P parameters describe a valid bilinear group; (x,y)is the private key corresponding to (X,Y), so that X = g^x and Y =g^y; and m is an element of \Zp.Output: the derived secret (r, d_m), where r is an element of \Zp andd_m is an element of G.Operation: Use the following steps.1. Choose at random an element r of \Zp.2. If m+x+ry = 0 mod p, restart from step 1.3. Compute d_m = g^{1/(m+x+ry)}.4. Output r and d_m.P-DHI-GV:========Pairing-based crypto Diffie-Hellman inversion, verification ofgenerated value.Input:- the P parameters p, G = <g>, e();- the DHI public key X- the message m- the purported generated value d_mAssumptions: the P parameters describe a valid bilinear group; X is apublic key, an element of G; m is an element of \Zp; and d_m is anelement of G.Output: "valid" if d_m is consistent with X and m; "invalid" otherwise.Operation: Use the following steps.1. Compute T1 = e(d_m, g^m X).2. Compute T2 = e(g,g).2. If T1 = T2, output "valid"; otherwise, output "invalid".Notes: The value T2 = e(g,g) is a group parameter, and can beprecomputed once and cached, saving a pairing operation.P-RDHI-GV:========Pairing-based crypto Diffie-Hellman inversion, verification ofrandomized generated value.Input:- the P parameters p, G = <g>, e();- the RDHI public key (X, Y)- the message m- the purported generated value (r, d_m)Assumptions: the P parameters describe a valid bilinear group; (X,Y)is a public key, so that X and Y are both elements of G; m is anelement of \Zp; r is an element of \Zp, and d_m is an element of G.Output: "valid" if (r,d_m) is consistent with (X,Y) and m; "invalid"otherwise.Operation: Use the following steps.1. Compute T1 = e(d_m, g^m X Y^r).2. Compute T2 = e(g,g).3. If T1 = T2, output "valid"; otherwise, output "invalid".Notes: The value T2 = e(g,g) is a group parameter, and can beprecomputed once and cached, saving a pairing operation.P-DHI-E:========Pairing-based crypto Diffie-Hellman inversion, encryption.Input:- the P parameters p, G = <g>, e();- the DHI public key X- the identity m- randomness sAssumptions: the P parameters describe a valid bilinear group; X is apublic key, an element of G; and m and s are elements of \Zp.Output: an encryption E, where E is an element of G, along with ablinding factor B, an element of \GT.Operation: Use the following steps.1. Compute E = [g^m X]^s.2. Compute B = e(g,g)^s.2. Output E and B.Notes: The blinding factor B is the same as that obtained in P-DHI-D,below.P-DHI-D:========Pairing-based crypto Diffie-Hellman inversion, decryption.Input:- the P parameters p, G = <g>, e();- the DHI public key X- the identity m- the generated value d_m- an encryption EAssumptions: the P parameters describe a valid bilinear group; X is apublic key, an element of G; m is an element of \Zp; d_m, an elementof G, is a valid generated value for m according to P-DHI-GV; and E isan element of G.Output: a blinding factor B, an element of \GT.Operation: Use the following steps.1. Compute B = e(d_m, E).2. Output B.Notes: If both parties follow the algorithms specified, the value Bcomputed here is e(g,g)^s, the same as that obtained in P-DHI-E,above.P-RDHI-E:========Pairing-based crypto Diffie-Hellman inversion, randomized encryption.Input:- the P parameters p, G = <g>, e();- the RDHI public key (X,Y)- the identity m- randomness sAssumptions: the P parameters describe a valid bilinear group; (X,Y)is a RDHI public key, so that X and Y are both elements of G; and mand s are elements of \Zp.Output: an encryption (E1,E2), where E1 and E2 are elements of G,along with a blinding factor B, an element of \GT.Operation: Use the following steps.1. Compute E1 = [g^m X]^s.2. Compute E2 = Y^s.3. Compute B = e(g,g)^s.4. Output (E1,E2) and B.Notes: As is the case with P-DHI-E and P-DHI-D, the blinding factor Bis the same as that obtained in P-RDHI-D, below.P-RDHI-D:========Pairing-based crypto Diffie-Hellman inversion, decryption.Input:- the P parameters p, G = <g>, e();- the RDHI public key (X,Y)- the identity m- the generated value (r,d_m)- an encryption (E1,E2)Assumptions: the P parameters describe a valid bilinear group; (X,Y)is an RDHI public key, so that both X and Y are elements of G; m is anelement of \Zp; r, an element of \Zp, and d_m, an element of G, are --taken together -- a valid generated value for m according toP-RDHI-GV; and E1 and E2 are elements of G.Output: a blinding factor B, an element of \GT.Operation: Use the following steps.1. Compute B = e(d_m, E1 E2^r).2. Output B.Notes: If both parties follow the algorithms specified, the value Bcomputed here is e(g,g)^s, the same blinding factor obtained inP-RDHI-E, above.P-CB-G:========Pairing-based crypto commutative blinding, generation.Input:- the P parameters p, G = <g>, e();- the CB secret key a and public key A- an encoded identity UAssumptions: the P parameters describe a valid bilinear group; a isthe private key corresponding to A, so that A = e(g,g)^a; and U is anelement of G.Output: the derived secret (d0, d1), where d0 and d1 are elements ofG.Operation: Use the following steps.1. Choose at random an element r of \Zp.2. Compute d0 = g^a U^r.3. Compute d1 = g^r.4. Output (d0, d1).Notes: The details of encoding identities into values U vary dependingon the construction that employs the P-CB primitives.  Not allpossible encoding methods will yield secure schemes.  Someconstructions will include additional elements in the CB public key tobe used in computing U.P-CB-GV:========Pairing-based crypto commutative blinding, verification of generatedvalue.Input:- the P parameters p, G = <g>, e();- the CB public key A- an encoded identity U- the purported generated value (d0, d1)Assumptions: the P parameters describe a valid bilinear group; A is aCB public key, and thus an element of \GT; U is an element of G; andd0 and d1 are elements of G.Output: "valid" if (d0,d1) is consistent with A and U; "invalid"otherwise.Operation: Use the following steps.1. Compute T1 = e(d0, g).2. Compute T2 = e(d1, U).3. If T1/T2 = A, output "valid"; otherwise, output "invalid".P-CB-E:========Pairing-based crypto commutative blinding, encryption.Input:- the P parameters p, G = <g>, e();- the CB public key A- an encoded identity U- randomness sAssumptions: the P parameters describe a valid bilinear group; A is aCB public key, and thus an element of \GT; U is an element of G; ands is an element of \Zp.Output: an encryption (E0,E1), where E0 and E1 are elements of G,along with a blinding factor B, an element of \GT.Operation: Use the following steps.1. Compute E0 = g^s.2. Compute E1 = U^s.3. Compute B = A^s.4. Output (E0,E1) and B.Notes: The blinding factor B is the same as that obtained in P-CB-D,below.P-CB-D:========Pairing-based crypto commutative blinding, decryption.Input:- the P parameters p, G = <g>, e();- the CB public key A- an encoded identity U- the generated value (d0,d1)- an encryption (E0,E1)Assumptions: the P parameters describe a valid bilinear group; A is aCB public key, and thus an element of \GT; U is an element of G; d_0and d_1, both elements of G, are -- taken together -- a validgenerated value for U according to P-CB-GV; and E0 and E1 are elementsof G.Output: a blinding factor B, an element of \GT.Operation: Use the following steps.1. Compute B = e(d0, E0) / e(d1, E1).2. Output B.Notes: If both parties follow the algorithms specified, the value Bcomputed here is A^s, the same blinding factor obtained in P-CB-E,above.P-FDH-G:========Pairing-based crypto full domain hash, generation.Input:- the P parameters p, G = <g>, e();- the FDH secret key x and public key X- an encoded identity UAssumptions: the P parameters describe a valid bilinear group; x isthe private key corresponding to X, so that X = g^x; and U is anelement of G.Output: the derived secret d, an element of G.Operation: Use the following steps.1. Compute d = U^x.2. Output d.Notes: The details of encoding identities into values U vary dependingon the construction that employs the P-FDH primitives.  Not allpossible encoding methods will yield secure schemes.  Someconstructions will include additional elements in the FDH public keyto be used in computing U.P-FDH-GV:========Pairing-based crypto full domain hash, verification ofgenerated value.Input:- the P parameters p, G = <g>, e();- the FDH public key X- an encoded identity U- the purported generated value dAssumptions: the P parameters describe a valid bilinear group; X is anFDH public key, and thus an element of G; U is an element of G; and dis an element of G.Output: "valid" if d is consistent with X and U; "invalid" otherwise.Operation: Use the following steps.1. Compute T1 = e(d, g).2. Compute T2 = e(U, X).3. If T1 = T2, output "valid"; otherwise, output "invalid".P-FDH-E:========Pairing-based crypto full domain hash, encryption.Input:- the P parameters p, G = <g>, e();- the FDH public key X- an encoded identity U- randomness sAssumptions: the P parameters describe a valid bilinear group; X is anFDH public key, and thus an element of G; U is an element of G; and sis an element of \Zp.Output: an encryption E, an element of G, along with a blinding factorB, an element of \GT.Operation: Use the following steps.1. Compute E = g^s.2. Compute B = e(U, X)^s.3. Output E and B.Notes: The blinding factor B is the same as that obtained in P-FDH-D,below.P-FDH-D:========Pairing-based crypto full domain hash, decryption.Input:- the P parameters p, G = <g>, e();- the FDH public key X- an encoded identity U- the generated value d- an encryption EAssumptions: the P parameters describe a valid bilinear group; X is anFDH public key, and thus an element of G; U is an element of G; d, anelement of G, is a valid generated value for U according to P-FDH-GV;and E is an element of G.Output: a blinding factor B, an element of \GT.Operation: Use the following steps.1. Compute B = e(E, d)2. Output B.Notes: If both parties follow the algorithms specified, the value Bcomputed here is e(U,X)^s, the same blinding factor obtained inP-FDH-E, above.