diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index 89ce64e..ab2fd89 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -1006,10 +1006,27 @@
     return 0;
   }
 
+  if (group->meth->mul_public == NULL) {
+    return group->meth->mul_public_batch(group, r, g_scalar, p, p_scalar, 1);
+  }
+
   group->meth->mul_public(group, r, g_scalar, p, p_scalar);
   return 1;
 }
 
+int ec_point_mul_scalar_public_batch(const EC_GROUP *group, EC_RAW_POINT *r,
+                                     const EC_SCALAR *g_scalar,
+                                     const EC_RAW_POINT *points,
+                                     const EC_SCALAR *scalars, size_t num) {
+  if (group->meth->mul_public_batch == NULL) {
+    OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+    return 0;
+  }
+
+  return group->meth->mul_public_batch(group, r, g_scalar, points, scalars,
+                                       num);
+}
+
 int ec_point_mul_scalar(const EC_GROUP *group, EC_RAW_POINT *r,
                         const EC_RAW_POINT *p, const EC_SCALAR *scalar) {
   if (p == NULL || scalar == NULL) {
diff --git a/crypto/fipsmodule/ec/ec_montgomery.c b/crypto/fipsmodule/ec/ec_montgomery.c
index e9a0958..21d5d40 100644
--- a/crypto/fipsmodule/ec/ec_montgomery.c
+++ b/crypto/fipsmodule/ec/ec_montgomery.c
@@ -508,7 +508,7 @@
   out->mul = ec_GFp_mont_mul;
   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->mul_public_batch = ec_GFp_mont_mul_public_batch;
   out->init_precomp = ec_GFp_mont_init_precomp;
   out->mul_precomp = ec_GFp_mont_mul_precomp;
   out->felem_mul = ec_GFp_mont_felem_mul;
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index 278c071..836d3ca 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -389,6 +389,19 @@
                                               const EC_RAW_POINT *p,
                                               const EC_SCALAR *p_scalar);
 
+// ec_point_mul_scalar_public_batch sets |r| to the sum of generator *
+// |g_scalar| and |points[i]| * |scalars[i]| where |points| and |scalars| have
+// |num| elements. It assumes that the inputs are public so there is no concern
+// about leaking their values through timing. |g_scalar| may be NULL to skip
+// that term.
+//
+// This function is not implemented for all curves. Add implementations as
+// needed.
+int ec_point_mul_scalar_public_batch(const EC_GROUP *group, EC_RAW_POINT *r,
+                                     const EC_SCALAR *g_scalar,
+                                     const EC_RAW_POINT *points,
+                                     const EC_SCALAR *scalars, size_t num);
+
 // ec_point_select, in constant time, sets |out| to |a| if |mask| is all ones
 // and |b| if |mask| is all zeros.
 void ec_point_select(const EC_GROUP *group, EC_RAW_POINT *out, BN_ULONG mask,
@@ -483,9 +496,15 @@
   // mul_public sets |r| to |g_scalar|*generator + |p_scalar|*|p|. It assumes
   // that the inputs are public so there is no concern about leaking their
   // values through timing.
+  //
+  // This function may be omitted if |mul_public_batch| is provided.
   void (*mul_public)(const EC_GROUP *group, EC_RAW_POINT *r,
                      const EC_SCALAR *g_scalar, const EC_RAW_POINT *p,
                      const EC_SCALAR *p_scalar);
+  // mul_public_batch implements |ec_point_mul_scalar_public_batch|.
+  int (*mul_public_batch)(const EC_GROUP *group, EC_RAW_POINT *r,
+                          const EC_SCALAR *g_scalar, const EC_RAW_POINT *points,
+                          const EC_SCALAR *scalars, size_t num);
 
   // init_precomp implements |ec_init_precomp|.
   int (*init_precomp)(const EC_GROUP *group, EC_PRECOMP *out,
@@ -632,9 +651,10 @@
 void ec_compute_wNAF(const EC_GROUP *group, int8_t *out,
                      const EC_SCALAR *scalar, size_t bits, int w);
 
-void ec_GFp_mont_mul_public(const EC_GROUP *group, EC_RAW_POINT *r,
-                            const EC_SCALAR *g_scalar, const EC_RAW_POINT *p,
-                            const EC_SCALAR *p_scalar);
+int ec_GFp_mont_mul_public_batch(const EC_GROUP *group, EC_RAW_POINT *r,
+                                 const EC_SCALAR *g_scalar,
+                                 const EC_RAW_POINT *points,
+                                 const EC_SCALAR *scalars, size_t num);
 
 // method functions in simple.c
 int ec_GFp_simple_group_init(EC_GROUP *);
diff --git a/crypto/fipsmodule/ec/wnaf.c b/crypto/fipsmodule/ec/wnaf.c
index fd1b480..ff90dcd 100644
--- a/crypto/fipsmodule/ec/wnaf.c
+++ b/crypto/fipsmodule/ec/wnaf.c
@@ -174,24 +174,57 @@
 // EC_WNAF_TABLE_SIZE is the table size to use for |ec_GFp_mont_mul_public|.
 #define EC_WNAF_TABLE_SIZE (1 << (EC_WNAF_WINDOW_BITS - 1))
 
-void ec_GFp_mont_mul_public(const EC_GROUP *group, EC_RAW_POINT *r,
-                            const EC_SCALAR *g_scalar, const EC_RAW_POINT *p,
-                            const EC_SCALAR *p_scalar) {
+// EC_WNAF_STACK is the number of points worth of data to stack-allocate and
+// avoid a malloc.
+#define EC_WNAF_STACK 3
+
+int ec_GFp_mont_mul_public_batch(const EC_GROUP *group, EC_RAW_POINT *r,
+                                 const EC_SCALAR *g_scalar,
+                                 const EC_RAW_POINT *points,
+                                 const EC_SCALAR *scalars, size_t num) {
   size_t bits = BN_num_bits(&group->order);
   size_t wNAF_len = bits + 1;
 
+  int ret = 0;
+  int8_t wNAF_stack[EC_WNAF_STACK][EC_MAX_BYTES * 8 + 1];
+  int8_t (*wNAF_alloc)[EC_MAX_BYTES * 8 + 1] = NULL;
+  int8_t (*wNAF)[EC_MAX_BYTES * 8 + 1];
+  EC_RAW_POINT precomp_stack[EC_WNAF_STACK][EC_WNAF_TABLE_SIZE];
+  EC_RAW_POINT (*precomp_alloc)[EC_WNAF_TABLE_SIZE] = NULL;
+  EC_RAW_POINT (*precomp)[EC_WNAF_TABLE_SIZE];
+  if (num <= EC_WNAF_STACK) {
+    wNAF = wNAF_stack;
+    precomp = precomp_stack;
+  } else {
+    if (num >= ((size_t)-1) / sizeof(wNAF_alloc[0]) ||
+        num >= ((size_t)-1) / sizeof(precomp_alloc[0])) {
+      OPENSSL_PUT_ERROR(EC, ERR_R_OVERFLOW);
+      goto err;
+    }
+    wNAF_alloc = OPENSSL_malloc(num * sizeof(wNAF_alloc[0]));
+    precomp_alloc = OPENSSL_malloc(num * sizeof(precomp_alloc[0]));
+    if (wNAF_alloc == NULL || precomp_alloc == NULL) {
+      OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
+      goto err;
+    }
+    wNAF = wNAF_alloc;
+    precomp = precomp_alloc;
+  }
+
   int8_t g_wNAF[EC_MAX_BYTES * 8 + 1];
   EC_RAW_POINT g_precomp[EC_WNAF_TABLE_SIZE];
   assert(wNAF_len <= OPENSSL_ARRAY_SIZE(g_wNAF));
   const EC_RAW_POINT *g = &group->generator->raw;
-  ec_compute_wNAF(group, g_wNAF, g_scalar, bits, EC_WNAF_WINDOW_BITS);
-  compute_precomp(group, g_precomp, g, EC_WNAF_TABLE_SIZE);
+  if (g_scalar != NULL) {
+    ec_compute_wNAF(group, g_wNAF, g_scalar, bits, EC_WNAF_WINDOW_BITS);
+    compute_precomp(group, g_precomp, g, EC_WNAF_TABLE_SIZE);
+  }
 
-  int8_t p_wNAF[EC_MAX_BYTES * 8 + 1];
-  EC_RAW_POINT p_precomp[EC_WNAF_TABLE_SIZE];
-  assert(wNAF_len <= OPENSSL_ARRAY_SIZE(p_wNAF));
-  ec_compute_wNAF(group, p_wNAF, p_scalar, bits, EC_WNAF_WINDOW_BITS);
-  compute_precomp(group, p_precomp, p, EC_WNAF_TABLE_SIZE);
+  for (size_t i = 0; i < num; i++) {
+    assert(wNAF_len <= OPENSSL_ARRAY_SIZE(wNAF[i]));
+    ec_compute_wNAF(group, wNAF[i], &scalars[i], bits, EC_WNAF_WINDOW_BITS);
+    compute_precomp(group, precomp[i], &points[i], EC_WNAF_TABLE_SIZE);
+  }
 
   EC_RAW_POINT tmp;
   int r_is_at_infinity = 1;
@@ -200,7 +233,7 @@
       ec_GFp_mont_dbl(group, r, r);
     }
 
-    if (g_wNAF[k] != 0) {
+    if (g_scalar != NULL && g_wNAF[k] != 0) {
       lookup_precomp(group, &tmp, g_precomp, g_wNAF[k]);
       if (r_is_at_infinity) {
         ec_GFp_simple_point_copy(r, &tmp);
@@ -210,13 +243,15 @@
       }
     }
 
-    if (p_wNAF[k] != 0) {
-      lookup_precomp(group, &tmp, p_precomp, p_wNAF[k]);
-      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);
+    for (size_t i = 0; i < num; i++) {
+      if (wNAF[i][k] != 0) {
+        lookup_precomp(group, &tmp, precomp[i], wNAF[i][k]);
+        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);
+        }
       }
     }
   }
@@ -224,4 +259,11 @@
   if (r_is_at_infinity) {
     ec_GFp_simple_point_set_to_infinity(group, r);
   }
+
+  ret = 1;
+
+err:
+  OPENSSL_free(wNAF_alloc);
+  OPENSSL_free(precomp_alloc);
+  return ret;
 }
diff --git a/crypto/trust_token/pmbtoken.c b/crypto/trust_token/pmbtoken.c
index 258cd40..291cb86 100644
--- a/crypto/trust_token/pmbtoken.c
+++ b/crypto/trust_token/pmbtoken.c
@@ -128,6 +128,16 @@
   return 1;
 }
 
+static int mul_public_3(const EC_GROUP *group, EC_RAW_POINT *out,
+                        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) {
+  EC_RAW_POINT points[3] = {*p0, *p1, *p2};
+  EC_SCALAR scalars[3] = {*scalar0, *scalar1, *scalar2};
+  return ec_point_mul_scalar_public_batch(group, out, /*g_scalar=*/NULL, points,
+                                          scalars, 3);
+}
+
 void PMBTOKEN_PRETOKEN_free(PMBTOKEN_PRETOKEN *pretoken) {
   OPENSSL_free(pretoken);
 }
@@ -594,7 +604,9 @@
 
   // We verify a DLEQ proof for the validity token and a DLEQOR2 proof for the
   // private metadata token. To allow amortizing Jacobian-to-affine conversions,
-  // we compute Ki for both proofs first.
+  // we compute Ki for both proofs first. Additionally, all inputs to this
+  // function are public, so we can use the faster variable-time
+  // multiplications.
   enum {
     idx_T,
     idx_S,
@@ -620,17 +632,14 @@
   }
 
   // Ks = us*(G;T) + vs*(H;S) - cs*(pubs;Ws)
-  //
-  // TODO(davidben): The multiplications in this function are public and can be
-  // switched to a public batch multiplication function if we add one.
   EC_RAW_POINT pubs;
   ec_affine_to_jacobian(group, &pubs, &pub->pubs);
   EC_SCALAR minus_cs;
   ec_scalar_neg(group, &minus_cs, &cs);
-  if (!ec_point_mul_scalar_batch(group, &jacobians[idx_Ks0], g, &us, &method->h,
-                                 &vs, &pubs, &minus_cs) ||
-      !ec_point_mul_scalar_batch(group, &jacobians[idx_Ks1], T, &us, S, &vs, Ws,
-                                 &minus_cs)) {
+  if (!mul_public_3(group, &jacobians[idx_Ks0], g, &us, &method->h, &vs, &pubs,
+                    &minus_cs) ||
+      !mul_public_3(group, &jacobians[idx_Ks1], T, &us, S, &vs, Ws,
+                    &minus_cs)) {
     return 0;
   }
 
@@ -653,15 +662,13 @@
   ec_scalar_neg(group, &minus_c0, &c0);
   ec_scalar_neg(group, &minus_c1, &c1);
   if (// K0 = u0*(G;T) + v0*(H;S) - c0*(pub0;W)
-      !ec_point_mul_scalar_batch(group, &jacobians[idx_K00], g, &u0, &method->h,
-                                 &v0, &pub0, &minus_c0) ||
-      !ec_point_mul_scalar_batch(group, &jacobians[idx_K01], T, &u0, S, &v0, W,
-                                 &minus_c0) ||
+      !mul_public_3(group, &jacobians[idx_K00], g, &u0, &method->h, &v0, &pub0,
+                    &minus_c0) ||
+      !mul_public_3(group, &jacobians[idx_K01], T, &u0, S, &v0, W, &minus_c0) ||
       // K1 = u1*(G;T) + v1*(H;S) - c1*(pub1;W)
-      !ec_point_mul_scalar_batch(group, &jacobians[idx_K10], g, &u1, &method->h,
-                                 &v1, &pub1, &minus_c1) ||
-      !ec_point_mul_scalar_batch(group, &jacobians[idx_K11], T, &u1, S, &v1, W,
-                                 &minus_c1)) {
+      !mul_public_3(group, &jacobians[idx_K10], g, &u1, &method->h, &v1, &pub1,
+                    &minus_c1) ||
+      !mul_public_3(group, &jacobians[idx_K11], T, &u1, S, &v1, W, &minus_c1)) {
     return 0;
   }
 
@@ -722,10 +729,12 @@
   EC_RAW_POINT *Sps = NULL;
   EC_RAW_POINT *Wps = NULL;
   EC_RAW_POINT *Wsps = NULL;
+  EC_SCALAR *es = NULL;
   CBB batch_cbb;
   CBB_zero(&batch_cbb);
   if (method->batched_proof) {
-    if (num_to_issue > ((size_t)-1) / sizeof(EC_RAW_POINT)) {
+    if (num_to_issue > ((size_t)-1) / sizeof(EC_RAW_POINT) ||
+        num_to_issue > ((size_t)-1) / sizeof(EC_SCALAR)) {
       OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_OVERFLOW);
       goto err;
     }
@@ -733,10 +742,12 @@
     Sps = OPENSSL_malloc(num_to_issue * sizeof(EC_RAW_POINT));
     Wps = OPENSSL_malloc(num_to_issue * sizeof(EC_RAW_POINT));
     Wsps = OPENSSL_malloc(num_to_issue * sizeof(EC_RAW_POINT));
+    es = OPENSSL_malloc(num_to_issue * sizeof(EC_SCALAR));
     if (!Tps ||
         !Sps ||
         !Wps ||
         !Wsps ||
+        !es ||
         !CBB_init(&batch_cbb, 0) ||
         !point_to_cbb(&batch_cbb, method->group, &key->pubs) ||
         !point_to_cbb(&batch_cbb, method->group, &key->pub0) ||
@@ -808,35 +819,29 @@
   }
 
   // The DLEQ batching construction is described in appendix B of
-  // https://eprint.iacr.org/2020/072/20200324:214215.
+  // https://eprint.iacr.org/2020/072/20200324:214215. Note the additional
+  // computations all act on public inputs.
   if (method->batched_proof) {
-    EC_RAW_POINT Tp_batch, Sp_batch, Wp_batch, Wsp_batch;
     for (size_t i = 0; i < num_to_issue; i++) {
-      EC_SCALAR e;
-      if (!hash_c_batch(method, &e, &batch_cbb, i)) {
+      if (!hash_c_batch(method, &es[i], &batch_cbb, i)) {
         goto err;
       }
+    }
 
-      EC_RAW_POINT Tp_e, Sp_e, Wp_e, Wsp_e;
-      if (!ec_point_mul_scalar(group, &Tp_e, &Tps[i], &e) ||
-          !ec_point_mul_scalar(group, &Sp_e, &Sps[i], &e) ||
-          !ec_point_mul_scalar(group, &Wp_e, &Wps[i], &e) ||
-          !ec_point_mul_scalar(group, &Wsp_e, &Wsps[i], &e)) {
-        goto err;
-      }
-
-      // TODO: Switch this to a multi-scalar multiplication.
-      if (i == 0) {
-        Tp_batch = Tp_e;
-        Sp_batch = Sp_e;
-        Wp_batch = Wp_e;
-        Wsp_batch = Wsp_e;
-      } else {
-        group->meth->add(group, &Tp_batch, &Tp_batch, &Tp_e);
-        group->meth->add(group, &Sp_batch, &Sp_batch, &Sp_e);
-        group->meth->add(group, &Wp_batch, &Wp_batch, &Wp_e);
-        group->meth->add(group, &Wsp_batch, &Wsp_batch, &Wsp_e);
-      }
+    EC_RAW_POINT Tp_batch, Sp_batch, Wp_batch, Wsp_batch;
+    if (!ec_point_mul_scalar_public_batch(group, &Tp_batch,
+                                          /*g_scalar=*/NULL, Tps, es,
+                                          num_to_issue) ||
+        !ec_point_mul_scalar_public_batch(group, &Sp_batch,
+                                          /*g_scalar=*/NULL, Sps, es,
+                                          num_to_issue) ||
+        !ec_point_mul_scalar_public_batch(group, &Wp_batch,
+                                          /*g_scalar=*/NULL, Wps, es,
+                                          num_to_issue) ||
+        !ec_point_mul_scalar_public_batch(group, &Wsp_batch,
+                                          /*g_scalar=*/NULL, Wsps, es,
+                                          num_to_issue)) {
+      goto err;
     }
 
     CBB proof;
@@ -862,6 +867,7 @@
   OPENSSL_free(Sps);
   OPENSSL_free(Wps);
   OPENSSL_free(Wsps);
+  OPENSSL_free(es);
   CBB_cleanup(&batch_cbb);
   return ret;
 }
@@ -888,10 +894,12 @@
   EC_RAW_POINT *Sps = NULL;
   EC_RAW_POINT *Wps = NULL;
   EC_RAW_POINT *Wsps = NULL;
+  EC_SCALAR *es = NULL;
   CBB batch_cbb;
   CBB_zero(&batch_cbb);
   if (method->batched_proof) {
-    if (count > ((size_t)-1) / sizeof(EC_RAW_POINT)) {
+    if (count > ((size_t)-1) / sizeof(EC_RAW_POINT) ||
+        count > ((size_t)-1) / sizeof(EC_SCALAR)) {
       OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_OVERFLOW);
       goto err;
     }
@@ -899,10 +907,12 @@
     Sps = OPENSSL_malloc(count * sizeof(EC_RAW_POINT));
     Wps = OPENSSL_malloc(count * sizeof(EC_RAW_POINT));
     Wsps = OPENSSL_malloc(count * sizeof(EC_RAW_POINT));
+    es = OPENSSL_malloc(count * sizeof(EC_SCALAR));
     if (!Tps ||
         !Sps ||
         !Wps ||
         !Wsps ||
+        !es ||
         !CBB_init(&batch_cbb, 0) ||
         !point_to_cbb(&batch_cbb, method->group, &key->pubs) ||
         !point_to_cbb(&batch_cbb, method->group, &key->pub0) ||
@@ -1006,35 +1016,25 @@
   }
 
   // The DLEQ batching construction is described in appendix B of
-  // https://eprint.iacr.org/2020/072/20200324:214215.
+  // https://eprint.iacr.org/2020/072/20200324:214215. Note the additional
+  // computations all act on public inputs.
   if (method->batched_proof) {
-    EC_RAW_POINT Tp_batch, Sp_batch, Wp_batch, Wsp_batch;
     for (size_t i = 0; i < count; i++) {
-      EC_SCALAR e;
-      if (!hash_c_batch(method, &e, &batch_cbb, i)) {
+      if (!hash_c_batch(method, &es[i], &batch_cbb, i)) {
         goto err;
       }
+    }
 
-      EC_RAW_POINT Tp_e, Sp_e, Wp_e, Wsp_e;
-      if (!ec_point_mul_scalar(group, &Tp_e, &Tps[i], &e) ||
-          !ec_point_mul_scalar(group, &Sp_e, &Sps[i], &e) ||
-          !ec_point_mul_scalar(group, &Wp_e, &Wps[i], &e) ||
-          !ec_point_mul_scalar(group, &Wsp_e, &Wsps[i], &e)) {
-        goto err;
-      }
-
-      // TODO: Switch this to a multi-scalar multiplication.
-      if (i == 0) {
-        Tp_batch = Tp_e;
-        Sp_batch = Sp_e;
-        Wp_batch = Wp_e;
-        Wsp_batch = Wsp_e;
-      } else {
-        group->meth->add(group, &Tp_batch, &Tp_batch, &Tp_e);
-        group->meth->add(group, &Sp_batch, &Sp_batch, &Sp_e);
-        group->meth->add(group, &Wp_batch, &Wp_batch, &Wp_e);
-        group->meth->add(group, &Wsp_batch, &Wsp_batch, &Wsp_e);
-      }
+    EC_RAW_POINT Tp_batch, Sp_batch, Wp_batch, Wsp_batch;
+    if (!ec_point_mul_scalar_public_batch(group, &Tp_batch,
+                                          /*g_scalar=*/NULL, Tps, es, count) ||
+        !ec_point_mul_scalar_public_batch(group, &Sp_batch,
+                                          /*g_scalar=*/NULL, Sps, es, count) ||
+        !ec_point_mul_scalar_public_batch(group, &Wp_batch,
+                                          /*g_scalar=*/NULL, Wps, es, count) ||
+        !ec_point_mul_scalar_public_batch(group, &Wsp_batch,
+                                          /*g_scalar=*/NULL, Wsps, es, count)) {
+      goto err;
     }
 
     CBS proof;
@@ -1053,6 +1053,7 @@
   OPENSSL_free(Sps);
   OPENSSL_free(Wps);
   OPENSSL_free(Wsps);
+  OPENSSL_free(es);
   CBB_cleanup(&batch_cbb);
   if (!ok) {
     sk_TRUST_TOKEN_pop_free(ret, TRUST_TOKEN_free);