In this note we describe a security weakness in pairing- based protocols when the group order is composite and the imbedding degree k is greater than 2. In pairing-based protocols, as in elliptic curve cryptography more gen- erally, one usually works in a prime-order subgroup of an elliptic curve E(Fq). However, starting in 2005 with work of Boneh, Goh, and Nissim (1), composite-order groups have been used in pairing-based protocols to achieve certain cryptographic objectives in such areas as traitor tracing (3) and group signatures (4, 5). Let N = Q r=1 pi i be an odd composite number whose factorization needs to be kept secret. Suppose that N is the order of the group G in a pairing- based protocol with imbedding degree k > 2, and let E be the elliptic curve over Fq that is being used to implement the protocol. With no loss of generality we suppose that g.c.d.(q,N) = 1. It is well-known (see, for example, Remark 4.5 of (2)) that one needs q to have exact multiplicative order k not only modulo N, but also modulo pi i for each i in order to avoid a simple attack that factors N; in particular, this means that pi � 1 (mod k) for i = 1,2,... ,r. Theorem 1. In the above setting, an attacker who observes two indepen- dent implementations (with the same N and k but different E and q) has probability at least 1 �(k) 1 r � 1 2 1 r of factoring N, where r � 2 is the number of distinct prime factors of N. Proof. Let Fq1 and Fq2 be the finite fields in the two implementations. Because each qj must have exact order k modulo pi
['Neal Koblitz']
A SECURITY WEAKNESS IN COMPOSITE-ORDER PAIRING-BASED PROTOCOLS WITH IMBEDDING DEGREE k > 2