Subgroup Membership Testing. In almost all key agreement schemes an assumption is made that all values passed from one party to another lie in the correct groups. Such assumptions are often implicit within security proofs. However, one needs to actually check that either given message flows lie within the correct group, or force the messages to lie in the group via additional computation, or by choosing parameters carefully so as the problem does not arise. Indeed some attacks on key agreement schemes, such as the small subgroup attack [20], are possible because implementors do not test for subgroup membership. For pairing based systems one needs to be careful whether and how one implements these subgroup membership tests as it is not as clear as for standard discrete logarithm based protocols.
Subgroup Membership Testing. In almost all key agreement schemes an assumption is made that all values passed from one party to another lie in the correct groups. Such assumptions are often implicit within security proofs. However, one needs to actually check that either given message flows lie within the correct group, or force the messages to lie in the group via additional computation, or by choosing parameters carefully so as the problem does not arise. Indeed some attacks on key agreement schemes, such as the small subgroup attack [20], are possible because implementors do not test for subgroup membership. For pairing based systems one needs to be careful whether and how one implements these subgroup membership tests as it is not as clear as for standard discrete logarithm based protocols. Subgroup membership testing in G1 = G1, GT , G, and G2 is done in the standard way via multiplica- tion and by inspection of the representation. If the cofactor is smaller than q one can test membership via cofactor multiplication, however in many pairing based situations the cofactor is larger than q in which case membership of the group of exponent q is tested by multiplication by q. Note, that depending on the security parameter this membership test may be quite expensive, as one may need to perform quite a large multiplication. k In the Type 2 and 4 situations there are other subgroup tests may need to be performed, which cannot be performed as above, namely testing whether a given point Q is a multiple of P2 = 1 P1 + P2. In other words we wish to test whether Q ∈ ⟨P2⟩. We first test whether Q has order q by testing, via multiplication as above, whether it is in G. Then we write Q = aP1 + bP2, for unknown a and b; one can compute aP1 and bP2 from Q via aP1 = k Tr(Q) and bP2 = Q − aP1, which requires one multiplication in G1. We need to test whether a = b/k, which can be done by performing the following test eˆ(Tr(Q), P2) = eˆ(kaP1, P2) = eˆ(P1, bP2) = eˆ(P1, Q − k Tr(Q)). In the Type 4 situation another situation occurs when we wish to test whether a point Q = aP1 + bP2 is a multiple of a point P = cP1 + dP2 without knowing a, b, c or d. We first test whether P, Q ∈ G as above. Then we test whether a = tc and b = td for some unknown t by testing whether eˆ(Tr(Q), P − Tr(P )) = eˆ(Tr(P ), Q − Tr(Q)). k In what follows we will implicitly assume within our security proofs that certain subgroup membership testing is performed. This is a common simplifying assumption in the literature but one wh...
