  We present a general framework for constructing families of elliptic curves
of prime order with prescribed embedding degree. We demonstrate this method by
constructing curves with embedding degree k = 10, which solves an open problem
posed by Boneh, Lynn, and Shacham. We show that our framework incorporates
existing constructions for k = 3, 4, 6, and 12, and we give evidence that the
method is unlikely to produce infinite families of curves with embedding degree
k > 12.
