diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index 5497aac..89ce64e 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -1070,6 +1070,38 @@
   return 1;
 }
 
+int ec_init_precomp(const EC_GROUP *group, EC_PRECOMP *out,
+                    const EC_RAW_POINT *p) {
+  if (group->meth->init_precomp == NULL) {
+    OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+    return 0;
+  }
+
+  return group->meth->init_precomp(group, out, p);
+}
+
+int ec_point_mul_scalar_precomp(const EC_GROUP *group, EC_RAW_POINT *r,
+                                const EC_PRECOMP *p0, const EC_SCALAR *scalar0,
+                                const EC_PRECOMP *p1, const EC_SCALAR *scalar1,
+                                const EC_PRECOMP *p2,
+                                const EC_SCALAR *scalar2) {
+  if (group->meth->mul_precomp == NULL) {
+    OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+    return 0;
+  }
+
+  group->meth->mul_precomp(group, r, p0, scalar0, p1, scalar1, p2, scalar2);
+
+  // Check the result is on the curve to defend against fault attacks or bugs.
+  // This has negligible cost compared to the multiplication.
+  if (!ec_GFp_simple_is_on_curve(group, r)) {
+    OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
+    return 0;
+  }
+
+  return 1;
+}
+
 void ec_point_select(const EC_GROUP *group, EC_RAW_POINT *out, BN_ULONG mask,
                       const EC_RAW_POINT *a, const EC_RAW_POINT *b) {
   ec_felem_select(group, &out->X, mask, &a->X, &b->X);
@@ -1083,6 +1115,15 @@
   ec_felem_select(group, &out->Y, mask, &a->Y, &b->Y);
 }
 
+void ec_precomp_select(const EC_GROUP *group, EC_PRECOMP *out, BN_ULONG mask,
+                       const EC_PRECOMP *a, const EC_PRECOMP *b) {
+  OPENSSL_STATIC_ASSERT(sizeof(out->comb) == sizeof(*out),
+                        "out->comb does not span the entire structure");
+  for (size_t i = 0; i < OPENSSL_ARRAY_SIZE(out->comb); i++) {
+    ec_affine_select(group, &out->comb[i], mask, &a->comb[i], &b->comb[i]);
+  }
+}
+
 int ec_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p,
                         const EC_SCALAR *r) {
   return group->meth->cmp_x_coordinate(group, p, r);
diff --git a/crypto/fipsmodule/ec/ec_montgomery.c b/crypto/fipsmodule/ec/ec_montgomery.c
index 8e94f30..e9a0958 100644
--- a/crypto/fipsmodule/ec/ec_montgomery.c
+++ b/crypto/fipsmodule/ec/ec_montgomery.c
@@ -509,6 +509,8 @@
   out->mul_base = ec_GFp_mont_mul_base;
   out->mul_batch = ec_GFp_mont_mul_batch;
   out->mul_public = ec_GFp_mont_mul_public;
+  out->init_precomp = ec_GFp_mont_init_precomp;
+  out->mul_precomp = ec_GFp_mont_mul_precomp;
   out->felem_mul = ec_GFp_mont_felem_mul;
   out->felem_sqr = ec_GFp_mont_felem_sqr;
   out->felem_to_bytes = ec_GFp_mont_felem_to_bytes;
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index a30af1c..278c071 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -334,6 +334,52 @@
                               const EC_RAW_POINT *p1, const EC_SCALAR *scalar1,
                               const EC_RAW_POINT *p2, const EC_SCALAR *scalar2);
 
+#define EC_MONT_PRECOMP_COMB_SIZE 5
+
+// An |EC_PRECOMP| stores precomputed information about a point, to optimize
+// repeated multiplications involving it. It is a union so different
+// |EC_METHOD|s can store different information in it.
+typedef union {
+  EC_AFFINE comb[(1 << EC_MONT_PRECOMP_COMB_SIZE) - 1];
+} EC_PRECOMP;
+
+// ec_init_precomp precomputes multiples of |p| and writes the result to |out|.
+// It returns one on success and zero on error. The resulting table may be used
+// with |ec_point_mul_scalar_precomp|. This function will fail if |p| is the
+// point at infinity.
+//
+// This function is not implemented for all curves. Add implementations as
+// needed.
+int ec_init_precomp(const EC_GROUP *group, EC_PRECOMP *out,
+                    const EC_RAW_POINT *p);
+
+// ec_point_mul_scalar_precomp sets |r| to |p0| * |scalar0| + |p1| * |scalar1| +
+// |p2| * |scalar2|. |p1| or |p2| may be NULL to skip the corresponding term.
+// The points are represented as |EC_PRECOMP| and must be initialized with
+// |ec_init_precomp|. This function runs faster than |ec_point_mul_scalar_batch|
+// but requires setup work per input point, so it is only appropriate for points
+// which are used frequently.
+//
+// The inputs are treated as secret, however, this function leaks information
+// about whether intermediate computations add a point to itself. Callers must
+// ensure that discrete logs between |p0|, |p1|, and |p2| are uniformly
+// distributed and independent of the scalars, which should be uniformly
+// selected and not under the attackers control. This ensures the doubling case
+// will occur with negligible probability.
+//
+// This function is not implemented for all curves. Add implementations as
+// needed.
+//
+// TODO(davidben): This function does not use base point tables. For now, it is
+// only used with the generic |EC_GFp_mont_method| implementation which has
+// none. If generalizing to tuned curves, we should add a parameter for the base
+// point and arrange for the generic implementation to have base point tables
+// available.
+int ec_point_mul_scalar_precomp(const EC_GROUP *group, EC_RAW_POINT *r,
+                                const EC_PRECOMP *p0, const EC_SCALAR *scalar0,
+                                const EC_PRECOMP *p1, const EC_SCALAR *scalar1,
+                                const EC_PRECOMP *p2, const EC_SCALAR *scalar2);
+
 // ec_point_mul_scalar_public sets |r| to
 // generator * |g_scalar| + |p| * |p_scalar|. It assumes that the inputs are
 // public so there is no concern about leaking their values through timing.
@@ -352,6 +398,10 @@
 void ec_affine_select(const EC_GROUP *group, EC_AFFINE *out, BN_ULONG mask,
                       const EC_AFFINE *a, const EC_AFFINE *b);
 
+// ec_precomp_select behaves like |ec_point_select| but acts on |EC_PRECOMP|.
+void ec_precomp_select(const EC_GROUP *group, EC_PRECOMP *out, BN_ULONG mask,
+                       const EC_PRECOMP *a, const EC_PRECOMP *b);
+
 // ec_cmp_x_coordinate compares the x (affine) coordinate of |p|, mod the group
 // order, with |r|. It returns one if the values match and zero if |p| is the
 // point at infinity of the values do not match.
@@ -437,6 +487,15 @@
                      const EC_SCALAR *g_scalar, const EC_RAW_POINT *p,
                      const EC_SCALAR *p_scalar);
 
+  // init_precomp implements |ec_init_precomp|.
+  int (*init_precomp)(const EC_GROUP *group, EC_PRECOMP *out,
+                      const EC_RAW_POINT *p);
+  // mul_precomp implements |ec_point_mul_scalar_precomp|.
+  void (*mul_precomp)(const EC_GROUP *group, EC_RAW_POINT *r,
+                      const EC_PRECOMP *p0, const EC_SCALAR *scalar0,
+                      const EC_PRECOMP *p1, const EC_SCALAR *scalar1,
+                      const EC_PRECOMP *p2, const EC_SCALAR *scalar2);
+
   // felem_mul and felem_sqr implement multiplication and squaring,
   // respectively, so that the generic |EC_POINT_add| and |EC_POINT_dbl|
   // implementations can work both with |EC_GFp_mont_method| and the tuned
@@ -555,6 +614,12 @@
                            const EC_RAW_POINT *p0, const EC_SCALAR *scalar0,
                            const EC_RAW_POINT *p1, const EC_SCALAR *scalar1,
                            const EC_RAW_POINT *p2, const EC_SCALAR *scalar2);
+int ec_GFp_mont_init_precomp(const EC_GROUP *group, EC_PRECOMP *out,
+                             const EC_RAW_POINT *p);
+void ec_GFp_mont_mul_precomp(const EC_GROUP *group, EC_RAW_POINT *r,
+                             const EC_PRECOMP *p0, const EC_SCALAR *scalar0,
+                             const EC_PRECOMP *p1, const EC_SCALAR *scalar1,
+                             const EC_PRECOMP *p2, const EC_SCALAR *scalar2);
 
 // ec_compute_wNAF writes the modified width-(w+1) Non-Adjacent Form (wNAF) of
 // |scalar| to |out|. |out| must have room for |bits| + 1 elements, each of
diff --git a/crypto/fipsmodule/ec/simple_mul.c b/crypto/fipsmodule/ec/simple_mul.c
index 02063df..127e2b3 100644
--- a/crypto/fipsmodule/ec/simple_mul.c
+++ b/crypto/fipsmodule/ec/simple_mul.c
@@ -167,3 +167,104 @@
     ec_GFp_simple_point_set_to_infinity(group, r);
   }
 }
+
+static unsigned ec_GFp_mont_comb_stride(const EC_GROUP *group) {
+  return (BN_num_bits(&group->field) + EC_MONT_PRECOMP_COMB_SIZE - 1) /
+         EC_MONT_PRECOMP_COMB_SIZE;
+}
+
+int ec_GFp_mont_init_precomp(const EC_GROUP *group, EC_PRECOMP *out,
+                             const EC_RAW_POINT *p) {
+  // comb[i - 1] stores the ith element of the comb. That is, if i is
+  // b4 * 2^4 + b3 * 2^3 + ... + b0 * 2^0, it stores k * |p|, where k is
+  // b4 * 2^(4*stride) + b3 * 2^(3*stride) + ... + b0 * 2^(0*stride). stride
+  // here is |ec_GFp_mont_comb_stride|. We store at index i - 1 because the 0th
+  // comb entry is always infinity.
+  EC_RAW_POINT comb[(1 << EC_MONT_PRECOMP_COMB_SIZE) - 1];
+  unsigned stride = ec_GFp_mont_comb_stride(group);
+
+  // We compute the comb sequentially by the highest set bit. Initially, all
+  // entries up to 2^0 are filled.
+  comb[(1 << 0) - 1] = *p;
+  for (unsigned i = 1; i < EC_MONT_PRECOMP_COMB_SIZE; i++) {
+    // Compute entry 2^i by doubling the entry for 2^(i-1) |stride| times.
+    unsigned bit = 1 << i;
+    ec_GFp_mont_dbl(group, &comb[bit - 1], &comb[bit / 2 - 1]);
+    for (unsigned j = 1; j < stride; j++) {
+      ec_GFp_mont_dbl(group, &comb[bit - 1], &comb[bit - 1]);
+    }
+    // Compute entries from 2^i + 1 to 2^i + (2^i - 1) by adding entry 2^i to
+    // a previous entry.
+    for (unsigned j = 1; j < bit; j++) {
+      ec_GFp_mont_add(group, &comb[bit + j - 1], &comb[bit - 1], &comb[j - 1]);
+    }
+  }
+
+  // Store the comb in affine coordinates to shrink the table. (This reduces
+  // cache pressure and makes the constant-time selects faster.)
+  OPENSSL_STATIC_ASSERT(
+      OPENSSL_ARRAY_SIZE(comb) == OPENSSL_ARRAY_SIZE(out->comb),
+      "comb sizes did not match");
+  return ec_jacobian_to_affine_batch(group, out->comb, comb,
+                                     OPENSSL_ARRAY_SIZE(comb));
+}
+
+static void ec_GFp_mont_get_comb_window(const EC_GROUP *group,
+                                        EC_RAW_POINT *out,
+                                        const EC_PRECOMP *precomp,
+                                        const EC_SCALAR *scalar, unsigned i) {
+  const size_t width = group->order.width;
+  unsigned stride = ec_GFp_mont_comb_stride(group);
+  // Select the bits corresponding to the comb shifted up by |i|.
+  unsigned window = 0;
+  for (unsigned j = 0; j < EC_MONT_PRECOMP_COMB_SIZE; j++) {
+    window |= bn_is_bit_set_words(scalar->words, width, j * stride + i)
+              << j;
+  }
+
+  // Select precomp->comb[window - 1]. If |window| is zero, |match| will always
+  // be zero, which will leave |out| at infinity.
+  OPENSSL_memset(out, 0, sizeof(EC_RAW_POINT));
+  for (unsigned j = 0; j < OPENSSL_ARRAY_SIZE(precomp->comb); j++) {
+    BN_ULONG match = constant_time_eq_w(window, j + 1);
+    ec_felem_select(group, &out->X, match, &precomp->comb[j].X, &out->X);
+    ec_felem_select(group, &out->Y, match, &precomp->comb[j].Y, &out->Y);
+  }
+  BN_ULONG is_infinity = constant_time_is_zero_w(window);
+  ec_felem_select(group, &out->Z, is_infinity, &out->Z, &group->one);
+}
+
+void ec_GFp_mont_mul_precomp(const EC_GROUP *group, EC_RAW_POINT *r,
+                             const EC_PRECOMP *p0, const EC_SCALAR *scalar0,
+                             const EC_PRECOMP *p1, const EC_SCALAR *scalar1,
+                             const EC_PRECOMP *p2, const EC_SCALAR *scalar2) {
+  unsigned stride = ec_GFp_mont_comb_stride(group);
+  int r_is_at_infinity = 1;
+  for (unsigned i = stride - 1; i < stride; i--) {
+    if (!r_is_at_infinity) {
+      ec_GFp_mont_dbl(group, r, r);
+    }
+
+    EC_RAW_POINT tmp;
+    ec_GFp_mont_get_comb_window(group, &tmp, p0, scalar0, i);
+    if (r_is_at_infinity) {
+      ec_GFp_simple_point_copy(r, &tmp);
+      r_is_at_infinity = 0;
+    } else {
+      ec_GFp_mont_add(group, r, r, &tmp);
+    }
+
+    if (p1 != NULL) {
+      ec_GFp_mont_get_comb_window(group, &tmp, p1, scalar1, i);
+      ec_GFp_mont_add(group, r, r, &tmp);
+    }
+
+    if (p2 != NULL) {
+      ec_GFp_mont_get_comb_window(group, &tmp, p2, scalar2, i);
+      ec_GFp_mont_add(group, r, r, &tmp);
+    }
+  }
+  if (r_is_at_infinity) {
+    ec_GFp_simple_point_set_to_infinity(group, r);
+  }
+}
diff --git a/crypto/trust_token/internal.h b/crypto/trust_token/internal.h
index 6c9904d..db9d0cf 100644
--- a/crypto/trust_token/internal.h
+++ b/crypto/trust_token/internal.h
@@ -42,6 +42,8 @@
 #define PMBTOKEN_NONCE_SIZE 64
 
 typedef struct {
+  // TODO(https://crbug.com/boringssl/334): These should store |EC_PRECOMP| so
+  // that |TRUST_TOKEN_finish_issuance| can use |ec_point_mul_scalar_precomp|.
   EC_AFFINE pub0;
   EC_AFFINE pub1;
   EC_AFFINE pubs;
@@ -55,8 +57,11 @@
   EC_SCALAR xs;
   EC_SCALAR ys;
   EC_AFFINE pub0;
+  EC_PRECOMP pub0_precomp;
   EC_AFFINE pub1;
+  EC_PRECOMP pub1_precomp;
   EC_AFFINE pubs;
+  EC_PRECOMP pubs_precomp;
 } PMBTOKEN_ISSUER_KEY;
 
 // PMBTOKEN_PRETOKEN represents the intermediate state a client keeps during a
diff --git a/crypto/trust_token/pmbtoken.c b/crypto/trust_token/pmbtoken.c
index 0407537..7eca5bb 100644
--- a/crypto/trust_token/pmbtoken.c
+++ b/crypto/trust_token/pmbtoken.c
@@ -30,36 +30,70 @@
 #include "internal.h"
 
 
+typedef int (*hash_t_func_t)(const EC_GROUP *group, EC_RAW_POINT *out,
+                             const uint8_t t[PMBTOKEN_NONCE_SIZE]);
+typedef int (*hash_s_func_t)(const EC_GROUP *group, EC_RAW_POINT *out,
+                             const EC_AFFINE *t,
+                             const uint8_t s[PMBTOKEN_NONCE_SIZE]);
+typedef int (*hash_c_func_t)(const EC_GROUP *group, EC_SCALAR *out,
+                             uint8_t *buf, size_t len);
+
 typedef struct {
   const EC_GROUP *group;
+  EC_PRECOMP g_precomp;
+  EC_PRECOMP h_precomp;
   EC_RAW_POINT h;
-  // hash_t implements the H_t operation in PMBTokens. It returns on on success
+  // hash_t implements the H_t operation in PMBTokens. It returns one on success
   // and zero on error.
-  int (*hash_t)(const EC_GROUP *group, EC_RAW_POINT *out,
-                const uint8_t t[PMBTOKEN_NONCE_SIZE]);
-  // hash_s implements the H_s operation in PMBTokens. It returns on on success
+  hash_t_func_t hash_t;
+  // hash_s implements the H_s operation in PMBTokens. It returns one on success
   // and zero on error.
-  int (*hash_s)(const EC_GROUP *group, EC_RAW_POINT *out, const EC_AFFINE *t,
-                const uint8_t s[PMBTOKEN_NONCE_SIZE]);
-  // hash_c implements the H_c operation in PMBTokens. It returns on on success
+  hash_s_func_t hash_s;
+  // hash_c implements the H_c operation in PMBTokens. It returns one on success
   // and zero on error.
-  int (*hash_c)(const EC_GROUP *group, EC_SCALAR *out, uint8_t *buf,
-                size_t len);
+  hash_c_func_t hash_c;
 } PMBTOKEN_METHOD;
 
 static const uint8_t kDefaultAdditionalData[32] = {0};
 
+static int pmbtoken_init_method(PMBTOKEN_METHOD *method, int curve_nid,
+                                const uint8_t *h_bytes, size_t h_len,
+                                hash_t_func_t hash_t, hash_s_func_t hash_s,
+                                hash_c_func_t hash_c) {
+  method->group = EC_GROUP_new_by_curve_name(curve_nid);
+  if (method->group == NULL) {
+    return 0;
+  }
+
+  method->hash_t = hash_t;
+  method->hash_s = hash_s;
+  method->hash_c = hash_c;
+
+  EC_AFFINE h;
+  if (!ec_point_from_uncompressed(method->group, &h, h_bytes, h_len)) {
+    return 0;
+  }
+  ec_affine_to_jacobian(method->group, &method->h, &h);
+
+  if (!ec_init_precomp(method->group, &method->g_precomp,
+                       &method->group->generator->raw) ||
+      !ec_init_precomp(method->group, &method->h_precomp, &method->h)) {
+    return 0;
+  }
+  return 1;
+}
+
 // generate_keypair generates a keypair for the PMBTokens construction.
 // |out_x| and |out_y| are set to the secret half of the keypair, while
 // |*out_pub| is set to the public half of the keypair. It returns one on
 // success and zero on failure.
 static int generate_keypair(const PMBTOKEN_METHOD *method, EC_SCALAR *out_x,
                             EC_SCALAR *out_y, EC_RAW_POINT *out_pub) {
-  const EC_RAW_POINT *g = &method->group->generator->raw;
   if (!ec_random_nonzero_scalar(method->group, out_x, kDefaultAdditionalData) ||
       !ec_random_nonzero_scalar(method->group, out_y, kDefaultAdditionalData) ||
-      !ec_point_mul_scalar_batch(method->group, out_pub, g, out_x, &method->h,
-                                 out_y, NULL, NULL)) {
+      !ec_point_mul_scalar_precomp(method->group, out_pub, &method->g_precomp,
+                                   out_x, &method->h_precomp, out_y, NULL,
+                                   NULL)) {
     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
     return 0;
   }
@@ -178,13 +212,15 @@
   // Recompute the public key.
   EC_RAW_POINT pub[3];
   EC_AFFINE pub_affine[3];
-  const EC_RAW_POINT *g = &group->generator->raw;
-  if (!ec_point_mul_scalar_batch(group, &pub[0], g, &key->x0, &method->h,
-                                 &key->y0, NULL, NULL) ||
-      !ec_point_mul_scalar_batch(group, &pub[1], g, &key->x1, &method->h,
-                                 &key->y1, NULL, NULL) ||
-      !ec_point_mul_scalar_batch(group, &pub[2], g, &key->xs, &method->h,
-                                 &key->ys, NULL, NULL) ||
+  if (!ec_point_mul_scalar_precomp(group, &pub[0], &method->g_precomp, &key->x0,
+                                   &method->h_precomp, &key->y0, NULL, NULL) ||
+      !ec_init_precomp(group, &key->pub0_precomp, &pub[0]) ||
+      !ec_point_mul_scalar_precomp(group, &pub[1], &method->g_precomp, &key->x1,
+                                   &method->h_precomp, &key->y1, NULL, NULL) ||
+      !ec_init_precomp(group, &key->pub1_precomp, &pub[1]) ||
+      !ec_point_mul_scalar_precomp(group, &pub[2], &method->g_precomp, &key->xs,
+                                   &method->h_precomp, &key->ys, NULL, NULL) ||
+      !ec_init_precomp(group, &key->pubs_precomp, &pub[2]) ||
       !ec_jacobian_to_affine_batch(group, pub_affine, pub, 3)) {
     return 0;
   }
@@ -357,7 +393,6 @@
                          const EC_RAW_POINT *S, const EC_RAW_POINT *W,
                          const EC_RAW_POINT *Ws, uint8_t private_metadata) {
   const EC_GROUP *group = method->group;
-  const EC_RAW_POINT *g = &group->generator->raw;
 
   // We generate a DLEQ proof for the validity token and a DLEQOR2 proof for the
   // private metadata token. To allow amortizing Jacobian-to-affine conversions,
@@ -383,8 +418,9 @@
       !ec_random_nonzero_scalar(group, &ks0, kDefaultAdditionalData) ||
       !ec_random_nonzero_scalar(group, &ks1, kDefaultAdditionalData) ||
       // Ks = ks0*(G;T) + ks1*(H;S)
-      !ec_point_mul_scalar_batch(group, &jacobians[idx_Ks0], g, &ks0,
-                                 &method->h, &ks1, NULL, NULL) ||
+      !ec_point_mul_scalar_precomp(group, &jacobians[idx_Ks0],
+                                   &method->g_precomp, &ks0, &method->h_precomp,
+                                   &ks1, NULL, NULL) ||
       !ec_point_mul_scalar_batch(group, &jacobians[idx_Ks1], T, &ks0, S, &ks1,
                                  NULL, NULL)) {
     return 0;
@@ -394,21 +430,21 @@
   // to the private metadata value) and pubo (public key corresponding to the
   // other value) in constant time.
   BN_ULONG mask = ((BN_ULONG)0) - (private_metadata & 1);
-  EC_AFFINE pubo_affine;
-  EC_RAW_POINT pubo;
+  EC_PRECOMP pubo_precomp;
   EC_SCALAR xb, yb;
   ec_scalar_select(group, &xb, mask, &priv->x1, &priv->x0);
   ec_scalar_select(group, &yb, mask, &priv->y1, &priv->y0);
-  ec_affine_select(group, &pubo_affine, mask, &priv->pub0, &priv->pub1);
-  ec_affine_to_jacobian(group, &pubo, &pubo_affine);
+  ec_precomp_select(group, &pubo_precomp, mask, &priv->pub0_precomp,
+                    &priv->pub1_precomp);
 
   EC_SCALAR k0, k1, minus_co, uo, vo;
   if (// k0, k1 <- Zp
       !ec_random_nonzero_scalar(group, &k0, kDefaultAdditionalData) ||
       !ec_random_nonzero_scalar(group, &k1, kDefaultAdditionalData) ||
       // Kb = k0*(G;T) + k1*(H;S)
-      !ec_point_mul_scalar_batch(group, &jacobians[idx_Kb0], g, &k0, &method->h,
-                                 &k1, NULL, NULL) ||
+      !ec_point_mul_scalar_precomp(group, &jacobians[idx_Kb0],
+                                   &method->g_precomp, &k0, &method->h_precomp,
+                                   &k1, NULL, NULL) ||
       !ec_point_mul_scalar_batch(group, &jacobians[idx_Kb1], T, &k0, S, &k1,
                                  NULL, NULL) ||
       // co, uo, vo <- Zp
@@ -416,8 +452,9 @@
       !ec_random_nonzero_scalar(group, &uo, kDefaultAdditionalData) ||
       !ec_random_nonzero_scalar(group, &vo, kDefaultAdditionalData) ||
       // Ko = uo*(G;T) + vo*(H;S) - co*(pubo;W)
-      !ec_point_mul_scalar_batch(group, &jacobians[idx_Ko0], g, &uo, &method->h,
-                                 &vo, &pubo, &minus_co) ||
+      !ec_point_mul_scalar_precomp(group, &jacobians[idx_Ko0],
+                                   &method->g_precomp, &uo, &method->h_precomp,
+                                   &vo, &pubo_precomp, &minus_co) ||
       !ec_point_mul_scalar_batch(group, &jacobians[idx_Ko1], T, &uo, S, &vo, W,
                                  &minus_co)) {
     return 0;
@@ -823,21 +860,30 @@
     return 0;
   }
 
-  EC_RAW_POINT S_jacobian, calculated;
-  // Check the validity of the token.
+  // We perform three multiplications with S and T. This is enough that it is
+  // worth using |ec_point_mul_scalar_precomp|.
+  EC_RAW_POINT S_jacobian;
+  EC_PRECOMP S_precomp, T_precomp;
   ec_affine_to_jacobian(group, &S_jacobian, &S);
-  if (!ec_point_mul_scalar_batch(group, &calculated, &T, &key->xs, &S_jacobian,
-                                 &key->ys, NULL, NULL) ||
-      !ec_affine_jacobian_equal(group, &Ws, &calculated)) {
+  if (!ec_init_precomp(group, &S_precomp, &S_jacobian) ||
+      !ec_init_precomp(group, &T_precomp, &T)) {
+    return 0;
+  }
+
+  EC_RAW_POINT Ws_calculated;
+  // Check the validity of the token.
+  if (!ec_point_mul_scalar_precomp(group, &Ws_calculated, &T_precomp, &key->xs,
+                                   &S_precomp, &key->ys, NULL, NULL) ||
+      !ec_affine_jacobian_equal(group, &Ws, &Ws_calculated)) {
     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_BAD_VALIDITY_CHECK);
     return 0;
   }
 
   EC_RAW_POINT W0, W1;
-  if (!ec_point_mul_scalar_batch(group, &W0, &T, &key->x0, &S_jacobian,
-                                 &key->y0, NULL, NULL) ||
-      !ec_point_mul_scalar_batch(group, &W1, &T, &key->x1, &S_jacobian,
-                                 &key->y1, NULL, NULL)) {
+  if (!ec_point_mul_scalar_precomp(group, &W0, &T_precomp, &key->x0, &S_precomp,
+                                   &key->y0, NULL, NULL) ||
+      !ec_point_mul_scalar_precomp(group, &W1, &T_precomp, &key->x1, &S_precomp,
+                                   &key->y1, NULL, NULL)) {
     return 0;
   }
 
@@ -952,16 +998,11 @@
 if __name__ == "__main__":
   gen_point(SEED_H)
 */
-static int pmbtoken_exp0_init_method(PMBTOKEN_METHOD *method) {
-  method->group = EC_GROUP_new_by_curve_name(NID_secp521r1);
-  if (method->group == NULL) {
-    return 0;
-  }
+static int pmbtoken_exp0_ok = 0;
+static PMBTOKEN_METHOD pmbtoken_exp0_method;
+static CRYPTO_once_t pmbtoken_exp0_method_once = CRYPTO_ONCE_INIT;
 
-  method->hash_t = pmbtoken_exp0_hash_t;
-  method->hash_c = pmbtoken_exp0_hash_c;
-  method->hash_s = pmbtoken_exp0_hash_s;
-
+static void pmbtoken_exp0_init_method_impl(void) {
   static const uint8_t kH[] = {
       0x04, 0x01, 0xf0, 0xa9, 0xf7, 0x9e, 0xbc, 0x12, 0x6c, 0xef, 0xd1, 0xab,
       0x29, 0x10, 0x03, 0x6f, 0x4e, 0xf5, 0xbd, 0xeb, 0x0f, 0x6b, 0xc0, 0x5c,
@@ -977,81 +1018,81 @@
       0xcd,
   };
 
-  EC_AFFINE h;
-  if (!ec_point_from_uncompressed(method->group, &h, kH, sizeof(kH))) {
+  pmbtoken_exp0_ok = pmbtoken_init_method(
+      &pmbtoken_exp0_method, NID_secp521r1, kH, sizeof(kH),
+      pmbtoken_exp0_hash_t, pmbtoken_exp0_hash_s, pmbtoken_exp0_hash_c);
+}
+
+static int pmbtoken_exp0_init_method(void) {
+  CRYPTO_once(&pmbtoken_exp0_method_once, pmbtoken_exp0_init_method_impl);
+  if (!pmbtoken_exp0_ok) {
+    OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_INTERNAL_ERROR);
     return 0;
   }
-  ec_affine_to_jacobian(method->group, &method->h, &h);
   return 1;
 }
 
 int pmbtoken_exp0_generate_key(CBB *out_private, CBB *out_public) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp0_init_method(&method)) {
+  if (!pmbtoken_exp0_init_method()) {
     return 0;
   }
 
-  return pmbtoken_generate_key(&method, out_private, out_public);
+  return pmbtoken_generate_key(&pmbtoken_exp0_method, out_private, out_public);
 }
 
 int pmbtoken_exp0_client_key_from_bytes(PMBTOKEN_CLIENT_KEY *key,
                                         const uint8_t *in, size_t len) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp0_init_method(&method)) {
+  if (!pmbtoken_exp0_init_method()) {
     return 0;
   }
-  return pmbtoken_client_key_from_bytes(&method, key, in, len);
+  return pmbtoken_client_key_from_bytes(&pmbtoken_exp0_method, key, in, len);
 }
 
 int pmbtoken_exp0_issuer_key_from_bytes(PMBTOKEN_ISSUER_KEY *key,
                                         const uint8_t *in, size_t len) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp0_init_method(&method)) {
+  if (!pmbtoken_exp0_init_method()) {
     return 0;
   }
-  return pmbtoken_issuer_key_from_bytes(&method, key, in, len);
+  return pmbtoken_issuer_key_from_bytes(&pmbtoken_exp0_method, key, in, len);
 }
 
 STACK_OF(PMBTOKEN_PRETOKEN) * pmbtoken_exp0_blind(CBB *cbb, size_t count) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp0_init_method(&method)) {
+  if (!pmbtoken_exp0_init_method()) {
     return NULL;
   }
-  return pmbtoken_blind(&method, cbb, count);
+  return pmbtoken_blind(&pmbtoken_exp0_method, cbb, count);
 }
 
 int pmbtoken_exp0_sign(const PMBTOKEN_ISSUER_KEY *key, CBB *cbb, CBS *cbs,
                        size_t num_requested, size_t num_to_issue,
                        uint8_t private_metadata) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp0_init_method(&method)) {
+  if (!pmbtoken_exp0_init_method()) {
     return 0;
   }
-  return pmbtoken_sign(&method, key, cbb, cbs, num_requested, num_to_issue,
-                       private_metadata);
+  return pmbtoken_sign(&pmbtoken_exp0_method, key, cbb, cbs, num_requested,
+                       num_to_issue, private_metadata);
 }
 
 STACK_OF(TRUST_TOKEN) *
     pmbtoken_exp0_unblind(const PMBTOKEN_CLIENT_KEY *key,
-                          const STACK_OF(PMBTOKEN_PRETOKEN) *pretokens,
+                          const STACK_OF(PMBTOKEN_PRETOKEN) * pretokens,
                           CBS *cbs, size_t count, uint32_t key_id) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp0_init_method(&method)) {
+  if (!pmbtoken_exp0_init_method()) {
     return NULL;
   }
-  return pmbtoken_unblind(&method, key, pretokens, cbs, count, key_id);
+  return pmbtoken_unblind(&pmbtoken_exp0_method, key, pretokens, cbs, count,
+                          key_id);
 }
 
 int pmbtoken_exp0_read(const PMBTOKEN_ISSUER_KEY *key,
                        uint8_t out_nonce[PMBTOKEN_NONCE_SIZE],
                        uint8_t *out_private_metadata, const uint8_t *token,
                        size_t token_len) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp0_init_method(&method)) {
+  if (!pmbtoken_exp0_init_method()) {
     return 0;
   }
-  return pmbtoken_read(&method, key, out_nonce, out_private_metadata, token,
-                       token_len);
+  return pmbtoken_read(&pmbtoken_exp0_method, key, out_nonce,
+                       out_private_metadata, token, token_len);
 }
 
 
@@ -1097,16 +1138,11 @@
       group, out, kHashCLabel, sizeof(kHashCLabel), buf, len);
 }
 
-static int pmbtoken_exp1_init_method(PMBTOKEN_METHOD *method) {
-  method->group = EC_GROUP_new_by_curve_name(NID_secp384r1);
-  if (method->group == NULL) {
-    return 0;
-  }
+static int pmbtoken_exp1_ok = 0;
+static PMBTOKEN_METHOD pmbtoken_exp1_method;
+static CRYPTO_once_t pmbtoken_exp1_method_once = CRYPTO_ONCE_INIT;
 
-  method->hash_t = pmbtoken_exp1_hash_t;
-  method->hash_c = pmbtoken_exp1_hash_c;
-  method->hash_s = pmbtoken_exp1_hash_s;
-
+static void pmbtoken_exp1_init_method_impl(void) {
   // This is the output of |ec_hash_to_scalar_p384_xmd_sha512_draft07| with DST
   // "PMBTokens Experiment V1 HashH" and message "generator".
   static const uint8_t kH[] = {
@@ -1121,90 +1157,90 @@
       0x87, 0xc3, 0x95, 0xd0, 0x13, 0xb7, 0x0b, 0x5c, 0xc7,
   };
 
-  EC_AFFINE h;
-  if (!ec_point_from_uncompressed(method->group, &h, kH, sizeof(kH))) {
+  pmbtoken_exp1_ok = pmbtoken_init_method(
+      &pmbtoken_exp1_method, NID_secp384r1, kH, sizeof(kH),
+      pmbtoken_exp1_hash_t, pmbtoken_exp1_hash_s, pmbtoken_exp1_hash_c);
+}
+
+static int pmbtoken_exp1_init_method(void) {
+  CRYPTO_once(&pmbtoken_exp1_method_once, pmbtoken_exp1_init_method_impl);
+  if (!pmbtoken_exp1_ok) {
+    OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_INTERNAL_ERROR);
     return 0;
   }
-  ec_affine_to_jacobian(method->group, &method->h, &h);
   return 1;
 }
 
 int pmbtoken_exp1_generate_key(CBB *out_private, CBB *out_public) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp1_init_method(&method)) {
+  if (!pmbtoken_exp1_init_method()) {
     return 0;
   }
 
-  return pmbtoken_generate_key(&method, out_private, out_public);
+  return pmbtoken_generate_key(&pmbtoken_exp1_method, out_private, out_public);
 }
 
 int pmbtoken_exp1_client_key_from_bytes(PMBTOKEN_CLIENT_KEY *key,
                                         const uint8_t *in, size_t len) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp1_init_method(&method)) {
+  if (!pmbtoken_exp1_init_method()) {
     return 0;
   }
-  return pmbtoken_client_key_from_bytes(&method, key, in, len);
+  return pmbtoken_client_key_from_bytes(&pmbtoken_exp1_method, key, in, len);
 }
 
 int pmbtoken_exp1_issuer_key_from_bytes(PMBTOKEN_ISSUER_KEY *key,
                                         const uint8_t *in, size_t len) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp1_init_method(&method)) {
+  if (!pmbtoken_exp1_init_method()) {
     return 0;
   }
-  return pmbtoken_issuer_key_from_bytes(&method, key, in, len);
+  return pmbtoken_issuer_key_from_bytes(&pmbtoken_exp1_method, key, in, len);
 }
 
 STACK_OF(PMBTOKEN_PRETOKEN) * pmbtoken_exp1_blind(CBB *cbb, size_t count) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp1_init_method(&method)) {
+  if (!pmbtoken_exp1_init_method()) {
     return NULL;
   }
-  return pmbtoken_blind(&method, cbb, count);
+  return pmbtoken_blind(&pmbtoken_exp1_method, cbb, count);
 }
 
 int pmbtoken_exp1_sign(const PMBTOKEN_ISSUER_KEY *key, CBB *cbb, CBS *cbs,
                        size_t num_requested, size_t num_to_issue,
                        uint8_t private_metadata) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp1_init_method(&method)) {
+  if (!pmbtoken_exp1_init_method()) {
     return 0;
   }
-  return pmbtoken_sign(&method, key, cbb, cbs, num_requested, num_to_issue,
-                       private_metadata);
+  return pmbtoken_sign(&pmbtoken_exp1_method, key, cbb, cbs, num_requested,
+                       num_to_issue, private_metadata);
 }
 
 STACK_OF(TRUST_TOKEN) *
     pmbtoken_exp1_unblind(const PMBTOKEN_CLIENT_KEY *key,
-                          const STACK_OF(PMBTOKEN_PRETOKEN) *pretokens,
+                          const STACK_OF(PMBTOKEN_PRETOKEN) * pretokens,
                           CBS *cbs, size_t count, uint32_t key_id) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp1_init_method(&method)) {
+  if (!pmbtoken_exp1_init_method()) {
     return NULL;
   }
-  return pmbtoken_unblind(&method, key, pretokens, cbs, count, key_id);
+  return pmbtoken_unblind(&pmbtoken_exp1_method, key, pretokens, cbs, count,
+                          key_id);
 }
 
 int pmbtoken_exp1_read(const PMBTOKEN_ISSUER_KEY *key,
                        uint8_t out_nonce[PMBTOKEN_NONCE_SIZE],
                        uint8_t *out_private_metadata, const uint8_t *token,
                        size_t token_len) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp1_init_method(&method)) {
+  if (!pmbtoken_exp1_init_method()) {
     return 0;
   }
-  return pmbtoken_read(&method, key, out_nonce, out_private_metadata, token,
-                       token_len);
+  return pmbtoken_read(&pmbtoken_exp1_method, key, out_nonce,
+                       out_private_metadata, token, token_len);
 }
 
 int pmbtoken_exp1_get_h_for_testing(uint8_t out[97]) {
-  PMBTOKEN_METHOD method;
-  if (!pmbtoken_exp1_init_method(&method)) {
+  if (!pmbtoken_exp1_init_method()) {
     return 0;
   }
   EC_AFFINE h;
-  return ec_jacobian_to_affine(method.group, &h, &method.h) &&
-         ec_point_to_bytes(method.group, &h, POINT_CONVERSION_UNCOMPRESSED, out,
-                           97) == 97;
+  return ec_jacobian_to_affine(pmbtoken_exp1_method.group, &h,
+                               &pmbtoken_exp1_method.h) &&
+         ec_point_to_bytes(pmbtoken_exp1_method.group, &h,
+                           POINT_CONVERSION_UNCOMPRESSED, out, 97) == 97;
 }