updates bb_oblivious_sig param combinations and dy_vrf params proof

10 files changed, 1041 insertions, 477 deletions

diff --git a/bazel/pjc_deps.bzl b/bazel/pjc_deps.bzl
index 3153c58..62a0e15 100644
--- a/bazel/pjc_deps.bzl
+++ b/bazel/pjc_deps.bzl
@@ -32,6 +32,7 @@ def pjc_deps():
     if "com_google_absl" not in native.existing_rules():
         http_archive(
             name = "com_google_absl",
+            sha256 = "f7c2cb2c5accdcbbbd5c0c59f241a988c0b1da2a3b7134b823c0bd613b1a6880",
             strip_prefix = "abseil-cpp-b971ac5250ea8de900eae9f95e06548d14cd95fe",
             urls = [
                 "https://github.com/abseil/abseil-cpp/archive/b971ac5250ea8de900eae9f95e06548d14cd95fe.zip",
@@ -42,6 +43,7 @@ def pjc_deps():
     if "com_github_google_googletest" not in native.existing_rules():
         http_archive(
             name = "com_github_google_googletest",
+            sha256 = "ad7fdba11ea011c1d925b3289cf4af2c66a352e18d4c7264392fead75e919363",
             strip_prefix = "googletest-1.13.0",
             urls = [
                 "https://github.com/google/googletest/archive/refs/tags/v1.13.0.tar.gz",
diff --git a/private_join_and_compute/crypto/dodis_yampolskiy_prf/BUILD b/private_join_and_compute/crypto/dodis_yampolskiy_prf/BUILD
index 90b1e0e..ebf5965 100644
--- a/private_join_and_compute/crypto/dodis_yampolskiy_prf/BUILD
+++ b/private_join_and_compute/crypto/dodis_yampolskiy_prf/BUILD
@@ -130,6 +130,7 @@ cc_test(
         "//private_join_and_compute/crypto:pedersen_over_zn",
         "//private_join_and_compute/crypto/proto:big_num_cc_proto",
         "//private_join_and_compute/crypto/proto:camenisch_shoup_cc_proto",
+        "//private_join_and_compute/crypto/proto:ec_point_cc_proto",
         "//private_join_and_compute/crypto/proto:pedersen_cc_proto",
         "//private_join_and_compute/crypto/proto:proto_util",
         "//private_join_and_compute/util:status_testing_includes",
diff --git a/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.cc b/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.cc
index d3bd6eb..4a85bef 100644
--- a/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.cc
+++ b/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.cc
@@ -17,6 +17,9 @@
 
 #include <stdint.h>
 
+#include <algorithm>
+#include <cstddef>
+#include <iterator>
 #include <memory>
 #include <string>
 #include <tuple>
@@ -37,6 +40,71 @@
 
 namespace private_join_and_compute {
 
+namespace {
+
+// Helper functions to compute batched encryptions of Enc(a*(k + m + yr) + bq)
+// given masked_messages (= am + bq), as, gammas (= ar), Enc(k), Enc(y), and the
+// public_camenisch_shoup. Assumes that all sizes have been checked beforehand.
+//
+// Can be used for the "real" encryptions, the dummy encryptions, and the masked
+// dummy encryptions.
+StatusOr<std::vector<CamenischShoupCiphertext>>
+GenerateHomomorphicCsCiphertexts(
+    const std::vector<BigNum>& masked_messages, const std::vector<BigNum>& as,
+    const std::vector<BigNum>& gammas,
+    const std::vector<BigNum>& encryption_randomness,
+    const std::vector<CamenischShoupCiphertext>& parsed_encrypted_k,
+    const std::vector<CamenischShoupCiphertext>& parsed_encrypted_y,
+    PublicCamenischShoup* public_camenisch_shoup) {
+  // The messages are encrypted in batches of vector_encryption_length. We
+  // compute the number of Camenisch Shoup ciphertexts needed to cover the
+  // messages.
+  size_t num_camenisch_shoup_ciphertexts =
+      (masked_messages.size() +
+       public_camenisch_shoup->vector_encryption_length() - 1) /
+      public_camenisch_shoup->vector_encryption_length();
+
+  std::vector<CamenischShoupCiphertext> encrypted_masked_messages;
+  encrypted_masked_messages.reserve(num_camenisch_shoup_ciphertexts);
+
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    size_t batch_start_index =
+        i * public_camenisch_shoup->vector_encryption_length();
+    size_t batch_size =
+        std::min(public_camenisch_shoup->vector_encryption_length(),
+                 masked_messages.size() - batch_start_index);
+    size_t batch_end_index = batch_start_index + batch_size;
+    // Determine the messages for the i'th batch.
+    std::vector<BigNum> masked_messages_for_batch_i(
+        masked_messages.begin() + batch_start_index,
+        masked_messages.begin() + batch_end_index);
+    ASSIGN_OR_RETURN(
+        CamenischShoupCiphertext encrypted_masked_message_at_i,
+        public_camenisch_shoup->EncryptWithRand(masked_messages_for_batch_i,
+                                                encryption_randomness[i]));
+
+    // Homomorphically add the appropriate a*k and a*r*y to the masked_message
+    // in the j'th slot, by using the encryption of k in the j'th slot and y in
+    // the j'th slot respectively (from the BbObliviousSignature public key).
+    for (uint64_t j = 0; j < batch_size; ++j) {
+      encrypted_masked_message_at_i = public_camenisch_shoup->Add(
+          encrypted_masked_message_at_i,
+          public_camenisch_shoup->Multiply(parsed_encrypted_k[j],
+                                           as[batch_start_index + j]));
+
+      encrypted_masked_message_at_i = public_camenisch_shoup->Add(
+          encrypted_masked_message_at_i,
+          public_camenisch_shoup->Multiply(parsed_encrypted_y[j],
+                                           gammas[batch_start_index + j]));
+    }
+    encrypted_masked_messages.push_back(
+        std::move(encrypted_masked_message_at_i));
+  }
+  return std::move(encrypted_masked_messages);
+}
+
+}  // namespace
+
 StatusOr<std::unique_ptr<BbObliviousSignature>> BbObliviousSignature::Create(
     proto::BbObliviousSignatureParameters parameters_proto, Context* ctx,
     ECGroup* ec_group, PublicCamenischShoup* public_camenisch_shoup,
@@ -68,14 +136,6 @@ StatusOr<std::unique_ptr<BbObliviousSignature>> BbObliviousSignature::Create(
         "positive.");
   }
 
-  if (pedersen->gs().size() <
-      public_camenisch_shoup->vector_encryption_length()) {
-    return absl::InvalidArgumentError(
-        "BbObliviousSignature::Create: The Pedersen object provided does not "
-        "support the "
-        "vector_commitment_length corresponding to the Camenisch Shoup "
-        "encryption scheme.");
-  }
   // dummy_masked_betas_bound is the largest value that should be encrypt-able
   // by the Camenisch-Shoup scheme.
   BigNum dummy_masked_betas_bound =
@@ -166,12 +226,13 @@ BbObliviousSignature::GenerateRequestAndProof(
   proto::BbObliviousSignatureRequestPrivateState private_state_proto;
 
   // Check that sizes are compatible
-  if (messages.size() > public_camenisch_shoup_->vector_encryption_length()) {
+  if (messages.size() > pedersen_->gs().size()) {
     return absl::InvalidArgumentError(absl::StrCat(
         "BbObliviousSignature::GenerateRequest: messages has size ",
         messages.size(),
-        " which is larger than vector_encryption_length in parameters_ (",
-        public_camenisch_shoup_->vector_encryption_length(), ")"));
+        " which is larger than the batch size supported by the Pedersen "
+        "commitment scheme (",
+        pedersen_->gs().size(), ")"));
   }
   if (rs.size() != messages.size()) {
     return absl::InvalidArgumentError(absl::StrCat(
@@ -205,16 +266,7 @@ BbObliviousSignature::GenerateRequestAndProof(
                               (bs.back() * ec_group_->GetOrder()));
   }
 
-  ASSIGN_OR_RETURN(
-      CamenischShoupCiphertextWithRand encrypted_masked_messages_and_rand,
-      public_camenisch_shoup_->EncryptAndGetRand(masked_messages));
-
-  CamenischShoupCiphertext encrypted_masked_messages =
-      std::move(encrypted_masked_messages_and_rand.ct);
-  // Used for request proof.
-  BigNum encryption_randomness =
-      std::move(encrypted_masked_messages_and_rand.r);
-
+  // Parse the needed components of the public key.
   std::vector<CamenischShoupCiphertext> parsed_encrypted_k;
   parsed_encrypted_k.reserve(
       public_camenisch_shoup_->vector_encryption_length());
@@ -222,31 +274,47 @@ BbObliviousSignature::GenerateRequestAndProof(
   parsed_encrypted_y.reserve(
       public_camenisch_shoup_->vector_encryption_length());
 
-  // Homomorphically add a[i]*k and as[i]*rs[i]*y to the masked_message in the
-  // i'th slot, by using the encryption of k in the i'th slot and y in the i'th
-  // slot respectively (from the BbObliviousSignature public key).
-  for (size_t i = 0; i < messages.size(); ++i) {
+  for (int i = 0; i < public_camenisch_shoup_->vector_encryption_length();
+       ++i) {
     ASSIGN_OR_RETURN(CamenischShoupCiphertext cs_encrypt_k_at_i,
                      public_camenisch_shoup_->ParseCiphertextProto(
                          public_key.encrypted_k(i)));
-    encrypted_masked_messages = public_camenisch_shoup_->Add(
-        encrypted_masked_messages,
-        public_camenisch_shoup_->Multiply(cs_encrypt_k_at_i, as[i]));
     parsed_encrypted_k.push_back(std::move(cs_encrypt_k_at_i));
 
     ASSIGN_OR_RETURN(CamenischShoupCiphertext cs_encrypt_y_at_i,
                      public_camenisch_shoup_->ParseCiphertextProto(
                          public_key.encrypted_y(i)));
-    encrypted_masked_messages = public_camenisch_shoup_->Add(
-        encrypted_masked_messages,
-        public_camenisch_shoup_->Multiply(cs_encrypt_y_at_i, gammas[i]));
     parsed_encrypted_y.push_back(std::move(cs_encrypt_y_at_i));
   }
 
+  // The messages are encrypted in batches of vector_encryption_length. We
+  // compute the number of Camenisch Shoup ciphertexts needed to cover the
+  // messages.
+  size_t num_camenisch_shoup_ciphertexts =
+      (messages.size() + public_camenisch_shoup_->vector_encryption_length() -
+       1) /
+      public_camenisch_shoup_->vector_encryption_length();
+
+  // Used for request proof.
+  std::vector<BigNum> encryption_randomness;
+  encryption_randomness.reserve(num_camenisch_shoup_ciphertexts);
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    encryption_randomness.push_back(
+        ctx_->GenerateRandLessThan(public_camenisch_shoup_->n()));
+  }
+
+  ASSIGN_OR_RETURN(
+      std::vector<CamenischShoupCiphertext> encrypted_masked_messages,
+      GenerateHomomorphicCsCiphertexts(
+          masked_messages, as, gammas, encryption_randomness,
+          parsed_encrypted_k, parsed_encrypted_y, public_camenisch_shoup_));
+
   request_proto.set_num_messages(messages.size());
-  *request_proto.mutable_encrypted_masked_messages() =
-      CamenischShoupCiphertextToProto(encrypted_masked_messages);
   *private_state_proto.mutable_private_as() = BigNumVectorToProto(as);
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    *request_proto.add_repeated_encrypted_masked_messages() =
+        CamenischShoupCiphertextToProto(encrypted_masked_messages[i]);
+  }
 
   // Commit to as, bs.
   // as must be committed separately in order to be able to homomorphically
@@ -269,26 +337,28 @@ BbObliviousSignature::GenerateRequestAndProof(
   ASSIGN_OR_RETURN(PedersenOverZn::CommitmentAndOpening commit_and_open_bs,
                    pedersen_->Commit(bs));
 
-  // Homomorphically generate commitment to alphas, gammas. This homomorphically
-  // generated commitment will be used in 2 parts of the proof.
+  // Homomorphically generate commitment to alphas, gammas. This
+  // homomorphically generated commitment will be used in 2 parts of the
+  // proof.
   //
-  // Taking the example of alphas, recall that alphas[i] = as[i] * messages[i].
-  // We want to show that alphas[i] was (1) properly used in computing
-  // encrypted_masked_messages, and (2) was properly generated as
-  // as[i]*messages[i]. For property (1), we need to show knowledge of alphas[i]
-  // and the randomness used to commit to alphas, and for property (2), we need
-  // to show that the commitment to alphas was homomorphically generated from
-  // Com(as[i]).
-
-  // To support these proofs, we homomorphically generate Com(alpha) as (Prod_i
-  // Com(as[i])^messages[i]) * Com(0), where Com(0) is a fresh commitment to 0.
-  // Since we generated Com(as[i]) with as[i] each in a different Pedersen
-  // vector slot, this will correctly come out to a commitment of alpha, with
-  // overall commitment randomness (Sum_i open_as[i] * messages[i]) +
-  // open_alphas_2, where open_alphas_2 is the randomness used in the second
-  // commitment of 0. We will refer to the overall commitment randomness as
-  // open_alphas_1, and the randomness used to commit to 0 as open_alphas_2.
-  // These will be used in order to prove properties (1) and (2) respectively.
+  // Taking the example of alphas, recall that alphas[i] = as[i] *
+  // messages[i]. We want to show that alphas[i] was (1) properly used in
+  // computing encrypted_masked_messages, and (2) was properly generated as
+  // as[i]*messages[i]. For property (1), we need to show knowledge of
+  // alphas[i] and the randomness used to commit to alphas, and for property
+  // (2), we need to show that the commitment to alphas was homomorphically
+  // generated from Com(as[i]).
+
+  // To support these proofs, we homomorphically generate Com(alpha) as
+  // (Prod_i Com(as[i])^messages[i]) * Com(0), where Com(0) is a fresh
+  // commitment to 0. Since we generated Com(as[i]) with as[i] each in a
+  // different Pedersen vector slot, this will correctly come out to a
+  // commitment of alpha, with overall commitment randomness (Sum_i open_as[i]
+  // * messages[i]) + open_alphas_2, where open_alphas_2 is the randomness
+  // used in the second commitment of 0. We will refer to the overall
+  // commitment randomness as open_alphas_1, and the randomness used to commit
+  // to 0 as open_alphas_2. These will be used in order to prove properties
+  // (1) and (2) respectively.
   //
   // We proceed similarly for gammas, where gammas[i] = as[i] * rs[i].
   std::vector<BigNum> zero_vector(pedersen_->gs().size(), ctx_->Zero());
@@ -300,8 +370,8 @@ BbObliviousSignature::GenerateRequestAndProof(
       pedersen_->Commit(zero_vector));
 
   // commit_alphas and commit_gammas serve as accumulators for the homomorphic
-  // computation. open_alphas_1 and open_gammas_1 will serve as accumulators for
-  // the randomness in these homomorphically generated commitments.
+  // computation. open_alphas_1 and open_gammas_1 will serve as accumulators
+  // for the randomness in these homomorphically generated commitments.
   // open_alphas_2 and open_gammas_2 will serve to record the randomness used
   // in the commitments to 0.
   PedersenOverZn::Commitment commit_alphas =
@@ -339,8 +409,8 @@ BbObliviousSignature::GenerateRequestAndProof(
       pedersen_->n().Lshift(parameters_proto_.challenge_length_bits() +
                             parameters_proto_.security_parameter());
 
-  // The homomorphically computed openings for Com(alphas) and Com(gammas) need
-  // larger dummy values.
+  // The homomorphically computed openings for Com(alphas) and Com(gammas)
+  // need larger dummy values.
   BigNum dummy_homomorphically_computed_openings_bound =
       dummy_openings_bound * ec_group_->GetOrder() *
       ctx_->CreateBigNum(messages.size() + 1);
@@ -390,8 +460,12 @@ BbObliviousSignature::GenerateRequestAndProof(
       ctx_->GenerateRandLessThan(dummy_homomorphically_computed_openings_bound);
   BigNum dummy_gammas_opening_2 =
       ctx_->GenerateRandLessThan(dummy_openings_bound);
-  BigNum dummy_encryption_randomness =
-      ctx_->GenerateRandLessThan(dummy_encryption_randomness_bound);
+  std::vector<BigNum> dummy_encryption_randomness;
+  dummy_encryption_randomness.reserve(num_camenisch_shoup_ciphertexts);
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    dummy_encryption_randomness.push_back(
+        ctx_->GenerateRandLessThan(dummy_encryption_randomness_bound));
+  }
 
   // Create dummy composites for all values
   ASSIGN_OR_RETURN(
@@ -431,22 +505,13 @@ BbObliviousSignature::GenerateRequestAndProof(
         dummy_commit_gammas_2, pedersen_->Multiply(commit_as[i], dummy_rs[i]));
   }
 
-  ASSIGN_OR_RETURN(CamenischShoupCiphertext dummy_encrypted_masked_messages,
-                   public_camenisch_shoup_->EncryptWithRand(
-                       dummy_masked_messages, dummy_encryption_randomness));
-
-  // Homomorphically add a[i]*k + gammas[i]*y to the masked_message in the i'th
-  // slot, by using the encryption of k and y in the i'th slot (from the BB
-  // Oblivious Signature public key).
-  for (size_t i = 0; i < messages.size(); ++i) {
-    dummy_encrypted_masked_messages = public_camenisch_shoup_->Add(
-        dummy_encrypted_masked_messages,
-        public_camenisch_shoup_->Multiply(parsed_encrypted_k[i], dummy_as[i]));
-    dummy_encrypted_masked_messages = public_camenisch_shoup_->Add(
-        dummy_encrypted_masked_messages,
-        public_camenisch_shoup_->Multiply(parsed_encrypted_y[i],
-                                          dummy_gammas[i]));
-  }
+  // Generate the dummy Camenisch Shoup encryptions.
+  ASSIGN_OR_RETURN(
+      std::vector<CamenischShoupCiphertext> dummy_encrypted_masked_messages,
+      GenerateHomomorphicCsCiphertexts(
+          dummy_masked_messages, dummy_as, dummy_gammas,
+          dummy_encryption_randomness, parsed_encrypted_k, parsed_encrypted_y,
+          public_camenisch_shoup_));
 
   // Serialize the statement and first message into protos, and generate the
   // challenge
@@ -472,8 +537,10 @@ BbObliviousSignature::GenerateRequestAndProof(
   proof_message_1.set_dummy_commit_alphas_2(dummy_commit_alphas_2.ToBytes());
   proof_message_1.set_dummy_commit_gammas_1(dummy_commit_gammas_1.ToBytes());
   proof_message_1.set_dummy_commit_gammas_2(dummy_commit_gammas_2.ToBytes());
-  *proof_message_1.mutable_dummy_encrypted_masked_messages() =
-      CamenischShoupCiphertextToProto(dummy_encrypted_masked_messages);
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    *proof_message_1.add_repeated_dummy_encrypted_masked_messages() =
+        CamenischShoupCiphertextToProto(dummy_encrypted_masked_messages[i]);
+  }
 
   ASSIGN_OR_RETURN(BigNum challenge, GenerateRequestProofChallenge(
                                          proof_statement, proof_message_1));
@@ -519,8 +586,12 @@ BbObliviousSignature::GenerateRequestAndProof(
       dummy_gammas_opening_1 + challenge * open_gammas_1;
   BigNum masked_dummy_gammas_opening_2 =
       dummy_gammas_opening_2 + challenge * open_gammas_2;
-  BigNum masked_dummy_encryption_randomness =
-      dummy_encryption_randomness + challenge * encryption_randomness;
+  std::vector<BigNum> masked_dummy_encryption_randomness;
+  masked_dummy_encryption_randomness.reserve(num_camenisch_shoup_ciphertexts);
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    masked_dummy_encryption_randomness.push_back(
+        dummy_encryption_randomness[i] + challenge * encryption_randomness[i]);
+  }
 
   // Generate proof proto.
 
@@ -560,8 +631,9 @@ BbObliviousSignature::GenerateRequestAndProof(
       masked_dummy_gammas_opening_1.ToBytes());
   proof_proto_message_2->set_masked_dummy_gammas_opening_2(
       masked_dummy_gammas_opening_2.ToBytes());
-  proof_proto_message_2->set_masked_dummy_encryption_randomness(
-      masked_dummy_encryption_randomness.ToBytes());
+  *proof_proto_message_2
+       ->mutable_masked_dummy_encryption_randomness_per_ciphertext() =
+      BigNumVectorToProto(masked_dummy_encryption_randomness);
 
   return std::make_tuple(std::move(request_proto), std::move(proof_proto),
                          std::move(private_state_proto));
@@ -574,6 +646,114 @@ Status BbObliviousSignature::VerifyRequest(
     const proto::BbObliviousSignatureRequestProof& request_proof,
     const PedersenOverZn::Commitment& commit_messages,
     const PedersenOverZn::Commitment& commit_rs) {
+  if (request.num_messages() > pedersen_->gs().size()) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "BbObliviousSignature::VerifyRequest: messages has size ",
+        request.num_messages(),
+        " which is larger than the pedersen batch size in parameters (",
+        pedersen_->gs().size(), ")"));
+  }
+  // Check that all vectors have the correct size.
+  if (request_proof.commit_as().serialized_big_nums_size() !=
+      request.num_messages()) {
+    return absl::InvalidArgumentError(
+        absl::StrCat("BbObliviousSignatures::VerifyRequest: request proof "
+                     "has wrong number of commit_as: expected ",
+                     request.num_messages(), ", actual ",
+                     request_proof.commit_as().serialized_big_nums_size()));
+  }
+  if (request_proof.message_2()
+          .masked_dummy_messages()
+          .serialized_big_nums_size() != request.num_messages()) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "BbObliviousSignatures::VerifyRequest: request proof has wrong "
+        "number of masked_dummy_messages: expected ",
+        request.num_messages(), ", actual ",
+        request_proof.message_2()
+            .masked_dummy_messages()
+            .serialized_big_nums_size()));
+  }
+  if (request_proof.message_2().masked_dummy_rs().serialized_big_nums_size() !=
+      request.num_messages()) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "BbObliviousSignatures::VerifyRequest: request proof has wrong "
+        "number of masked_dummy_rs: expected ",
+        request.num_messages(), ", actual ",
+        request_proof.message_2()
+            .masked_dummy_rs()
+            .serialized_big_nums_size()));
+  }
+  if (request_proof.message_2().masked_dummy_as().serialized_big_nums_size() !=
+      request.num_messages()) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "BbObliviousSignatures::VerifyRequest: request proof has wrong "
+        "number of masked_dummy_as: expected ",
+        request.num_messages(), ", actual ",
+        request_proof.message_2()
+            .masked_dummy_as()
+            .serialized_big_nums_size()));
+  }
+  if (request_proof.message_2().masked_dummy_bs().serialized_big_nums_size() !=
+      request.num_messages()) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "BbObliviousSignatures::VerifyRequest: request proof has wrong "
+        "number of masked_dummy_bs: expected ",
+        request.num_messages(), ", actual ",
+        request_proof.message_2()
+            .masked_dummy_bs()
+            .serialized_big_nums_size()));
+  }
+  if (request_proof.message_2()
+          .masked_dummy_alphas()
+          .serialized_big_nums_size() != request.num_messages()) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "BbObliviousSignatures::VerifyRequest: request proof has wrong "
+        "number of masked_dummy_alphas: expected ",
+        request.num_messages(), ", actual ",
+        request_proof.message_2()
+            .masked_dummy_alphas()
+            .serialized_big_nums_size()));
+  }
+  if (request_proof.message_2()
+          .masked_dummy_gammas()
+          .serialized_big_nums_size() != request.num_messages()) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "BbObliviousSignatures::VerifyRequest: request proof has wrong "
+        "number of masked_dummy_gammas: expected ",
+        request.num_messages(), ", actual ",
+        request_proof.message_2()
+            .masked_dummy_gammas()
+            .serialized_big_nums_size()));
+  }
+
+  // The messages are encrypted in batches of vector_encryption_length. We
+  // compute the number of Camenisch Shoup ciphertexts needed to cover the
+  // messages.
+  size_t num_camenisch_shoup_ciphertexts =
+      (request.num_messages() +
+       public_camenisch_shoup_->vector_encryption_length() - 1) /
+      public_camenisch_shoup_->vector_encryption_length();
+
+  if (request.repeated_encrypted_masked_messages_size() !=
+      num_camenisch_shoup_ciphertexts) {
+    return absl::InvalidArgumentError(
+        absl::StrCat("BbObliviousSignatures::VerifyRequest: request has wrong "
+                     "number of ciphertexts: expected ",
+                     num_camenisch_shoup_ciphertexts, ", actual ",
+                     request.repeated_encrypted_masked_messages_size()));
+  }
+  if (request_proof.message_2()
+          .masked_dummy_encryption_randomness_per_ciphertext()
+          .serialized_big_nums_size() != num_camenisch_shoup_ciphertexts) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "BbObliviousSignatures::VerifyRequest: request proof has wrong "
+        "number of masked_dummy_encryption_randomness: expected ",
+        num_camenisch_shoup_ciphertexts, ", actual ",
+        request_proof.message_2()
+            .masked_dummy_encryption_randomness_per_ciphertext()
+            .serialized_big_nums_size()));
+  }
+
   // Create the proof statement
   proto::BbObliviousSignatureRequestProof::Statement proof_statement;
   *proof_statement.mutable_parameters() = parameters_proto_;
@@ -595,9 +775,15 @@ Status BbObliviousSignature::VerifyRequest(
       ctx_->CreateBigNum(request_proof.commit_alphas());
   PedersenOverZn::Commitment commit_gammas =
       ctx_->CreateBigNum(request_proof.commit_gammas());
-  ASSIGN_OR_RETURN(CamenischShoupCiphertext encrypted_masked_messages,
-                   public_camenisch_shoup_->ParseCiphertextProto(
-                       request.encrypted_masked_messages()));
+  std::vector<CamenischShoupCiphertext> encrypted_masked_messages;
+  encrypted_masked_messages.reserve(num_camenisch_shoup_ciphertexts);
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    ASSIGN_OR_RETURN(CamenischShoupCiphertext encrypted_masked_messages_at_i,
+                     public_camenisch_shoup_->ParseCiphertextProto(
+                         request.repeated_encrypted_masked_messages(i)));
+    encrypted_masked_messages.push_back(
+        std::move(encrypted_masked_messages_at_i));
+  }
 
   // Parse challenge from the proof.
   BigNum challenge_from_proof = ctx_->CreateBigNum(request_proof.challenge());
@@ -631,61 +817,10 @@ Status BbObliviousSignature::VerifyRequest(
       request_proof.message_2().masked_dummy_gammas_opening_1());
   BigNum masked_dummy_gammas_opening_2 = ctx_->CreateBigNum(
       request_proof.message_2().masked_dummy_gammas_opening_2());
-  BigNum masked_dummy_encryption_randomness = ctx_->CreateBigNum(
-      request_proof.message_2().masked_dummy_encryption_randomness());
-
-  if (request.num_messages() >
-      public_camenisch_shoup_->vector_encryption_length()) {
-    return absl::InvalidArgumentError(absl::StrCat(
-        "BbObliviousSignature::VerifyRequest: messages has size ",
-        request.num_messages(),
-        " which is larger than vector_encryption_length in parameters (",
-        public_camenisch_shoup_->vector_encryption_length(), ")"));
-  }
-
-  // Check that all vectors have the correct size.
-  if (commit_as.size() != request.num_messages()) {
-    return absl::InvalidArgumentError(absl::StrCat(
-        "BbObliviousSignatures::VerifyRequest: request proof has wrong number "
-        "of commit_as: expected ",
-        request.num_messages(), ", actual ", commit_as.size()));
-  }
-  if (masked_dummy_messages.size() != request.num_messages()) {
-    return absl::InvalidArgumentError(absl::StrCat(
-        "BbObliviousSignatures::VerifyRequest: request proof has wrong number "
-        "of masked_dummy_messages: expected ",
-        request.num_messages(), ", actual ", masked_dummy_messages.size()));
-  }
-  if (masked_dummy_rs.size() != request.num_messages()) {
-    return absl::InvalidArgumentError(absl::StrCat(
-        "BbObliviousSignatures::VerifyRequest: request proof has wrong number "
-        "of masked_dummy_rs: expected ",
-        request.num_messages(), ", actual ", masked_dummy_rs.size()));
-  }
-  if (masked_dummy_as.size() != request.num_messages()) {
-    return absl::InvalidArgumentError(absl::StrCat(
-        "BbObliviousSignatures::VerifyRequest: request proof has wrong number "
-        "of masked_dummy_as: expected ",
-        request.num_messages(), ", actual ", masked_dummy_as.size()));
-  }
-  if (masked_dummy_bs.size() != request.num_messages()) {
-    return absl::InvalidArgumentError(absl::StrCat(
-        "BbObliviousSignatures::VerifyRequest: request proof has wrong number "
-        "of masked_dummy_bs: expected ",
-        request.num_messages(), ", actual ", masked_dummy_bs.size()));
-  }
-  if (masked_dummy_alphas.size() != request.num_messages()) {
-    return absl::InvalidArgumentError(absl::StrCat(
-        "BbObliviousSignatures::VerifyRequest: request proof has wrong number "
-        "of masked_dummy_alphas: expected ",
-        request.num_messages(), ", actual ", masked_dummy_alphas.size()));
-  }
-  if (masked_dummy_gammas.size() != request.num_messages()) {
-    return absl::InvalidArgumentError(absl::StrCat(
-        "BbObliviousSignatures::VerifyRequest: request proof has wrong number "
-        "of masked_dummy_gammas: expected ",
-        request.num_messages(), ", actual ", masked_dummy_gammas.size()));
-  }
+  std::vector<BigNum> masked_dummy_encryption_randomness =
+      ParseBigNumVectorProto(
+          ctx_, request_proof.message_2()
+                    .masked_dummy_encryption_randomness_per_ciphertext());
 
   // Verify bounds.
   BigNum masked_dummy_messages_bound =
@@ -807,33 +942,35 @@ Status BbObliviousSignature::VerifyRequest(
         masked_dummy_alphas[i] + masked_dummy_bs[i] * ec_group_->GetOrder());
   }
 
-  ASSIGN_OR_RETURN(
-      CamenischShoupCiphertext masked_dummy_encrypted_masked_messages,
-      public_camenisch_shoup_->EncryptWithRand(
-          dummy_masked_encrypted_masked_messages,
-          masked_dummy_encryption_randomness));
-
-  // Homomorphically add a[i]*k and as[i]*rs[i]*y to the masked_message in the
-  // i'th slot, by using the encryption of k in the i'th slot and y in the i'th
-  // slot respectively (from the BbObliviousSignature public key).
-  for (size_t i = 0; i < dummy_masked_encrypted_masked_messages.size(); ++i) {
+  std::vector<CamenischShoupCiphertext> parsed_encrypted_k;
+  parsed_encrypted_k.reserve(
+      public_camenisch_shoup_->vector_encryption_length());
+  std::vector<CamenischShoupCiphertext> parsed_encrypted_y;
+  parsed_encrypted_y.reserve(
+      public_camenisch_shoup_->vector_encryption_length());
+
+  for (size_t i = 0; i < public_camenisch_shoup_->vector_encryption_length();
+       ++i) {
     ASSIGN_OR_RETURN(CamenischShoupCiphertext cs_encrypt_k_at_i,
                      public_camenisch_shoup_->ParseCiphertextProto(
                          public_key.encrypted_k(i)));
-    masked_dummy_encrypted_masked_messages = public_camenisch_shoup_->Add(
-        masked_dummy_encrypted_masked_messages,
-        public_camenisch_shoup_->Multiply(cs_encrypt_k_at_i,
-                                          masked_dummy_as[i]));
+    parsed_encrypted_k.push_back(std::move(cs_encrypt_k_at_i));
 
     ASSIGN_OR_RETURN(CamenischShoupCiphertext cs_encrypt_y_at_i,
                      public_camenisch_shoup_->ParseCiphertextProto(
                          public_key.encrypted_y(i)));
-    masked_dummy_encrypted_masked_messages = public_camenisch_shoup_->Add(
-        masked_dummy_encrypted_masked_messages,
-        public_camenisch_shoup_->Multiply(cs_encrypt_y_at_i,
-                                          masked_dummy_gammas[i]));
+    parsed_encrypted_y.push_back(std::move(cs_encrypt_y_at_i));
   }
 
+  // Generate the dummy Camenisch Shoup encryptions.
+  ASSIGN_OR_RETURN(
+      std::vector<CamenischShoupCiphertext>
+          masked_dummy_encrypted_masked_messages,
+      GenerateHomomorphicCsCiphertexts(
+          dummy_masked_encrypted_masked_messages, masked_dummy_as,
+          masked_dummy_gammas, masked_dummy_encryption_randomness,
+          parsed_encrypted_k, parsed_encrypted_y, public_camenisch_shoup_));
+
   //  Recreate dummy composites from masked dummy composites (in order to
   //  regenerate Proof Message 1). Each dummy_composite is computed as
   //  masked_dummy_composite / original_value^challenge_in_proof.
@@ -882,33 +1019,6 @@ Status BbObliviousSignature::VerifyRequest(
   PedersenOverZn::Commitment dummy_commit_gammas_2 = pedersen_->Add(
       masked_dummy_commit_gammas_2, commit_gammas_to_challenge_inverse);
 
-  // Some extra work is needed for the Camenisch Shoup ciphertext since it
-  // doesn't natively support inverse.
-  CamenischShoupCiphertext encrypted_masked_messages_to_challenge =
-      public_camenisch_shoup_->Multiply(encrypted_masked_messages,
-                                        challenge_from_proof);
-  ASSIGN_OR_RETURN(BigNum encrypted_masked_messages_to_challenge_u_inverse,
-                   encrypted_masked_messages_to_challenge.u.ModInverse(
-                       public_camenisch_shoup_->modulus()));
-  std::vector<BigNum> encrypted_masked_messages_to_challenge_es_inverse;
-  encrypted_masked_messages_to_challenge_es_inverse.reserve(
-      encrypted_masked_messages_to_challenge.es.size());
-  for (size_t i = 0; i < encrypted_masked_messages_to_challenge.es.size();
-       ++i) {
-    ASSIGN_OR_RETURN(BigNum encrypted_masked_messages_to_challenge_e_inverse,
-                     encrypted_masked_messages_to_challenge.es[i].ModInverse(
-                         public_camenisch_shoup_->modulus()));
-    encrypted_masked_messages_to_challenge_es_inverse.push_back(
-        std::move(encrypted_masked_messages_to_challenge_e_inverse));
-  }
-  CamenischShoupCiphertext encrypted_masked_messages_to_challenge_inverse{
-      std::move(encrypted_masked_messages_to_challenge_u_inverse),
-      std::move(encrypted_masked_messages_to_challenge_es_inverse)};
-  CamenischShoupCiphertext dummy_encrypted_masked_messages =
-      public_camenisch_shoup_->Add(
-          masked_dummy_encrypted_masked_messages,
-          encrypted_masked_messages_to_challenge_inverse);
-
   // Package dummy_composites into Proof message_1.
   proto::BbObliviousSignatureRequestProof::Message1 message_1;
   message_1.set_dummy_commit_messages(dummy_commit_messages.ToBytes());
@@ -919,11 +1029,42 @@ Status BbObliviousSignature::VerifyRequest(
   message_1.set_dummy_commit_alphas_2(dummy_commit_alphas_2.ToBytes());
   message_1.set_dummy_commit_gammas_1(dummy_commit_gammas_1.ToBytes());
   message_1.set_dummy_commit_gammas_2(dummy_commit_gammas_2.ToBytes());
-  *message_1.mutable_dummy_encrypted_masked_messages() =
-      CamenischShoupCiphertextToProto(dummy_encrypted_masked_messages);
+  // dummy_encrypted_masked_messages are computed below.
 
-  // Reconstruct the challenge and check that it matches the one supplied in the
-  // proof.
+  // Some extra work is needed for the Camenisch Shoup ciphertext since it
+  // doesn't natively support inverse.
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    CamenischShoupCiphertext encrypted_masked_messages_to_challenge =
+        public_camenisch_shoup_->Multiply(encrypted_masked_messages[i],
+                                          challenge_from_proof);
+    ASSIGN_OR_RETURN(BigNum encrypted_masked_messages_to_challenge_u_inverse,
+                     encrypted_masked_messages_to_challenge.u.ModInverse(
+                         public_camenisch_shoup_->modulus()));
+    std::vector<BigNum> encrypted_masked_messages_to_challenge_es_inverse;
+    encrypted_masked_messages_to_challenge_es_inverse.reserve(
+        encrypted_masked_messages_to_challenge.es.size());
+    for (size_t i = 0; i < encrypted_masked_messages_to_challenge.es.size();
+         ++i) {
+      ASSIGN_OR_RETURN(BigNum encrypted_masked_messages_to_challenge_e_inverse,
+                       encrypted_masked_messages_to_challenge.es[i].ModInverse(
+                           public_camenisch_shoup_->modulus()));
+      encrypted_masked_messages_to_challenge_es_inverse.push_back(
+          std::move(encrypted_masked_messages_to_challenge_e_inverse));
+    }
+    CamenischShoupCiphertext encrypted_masked_messages_to_challenge_inverse{
+        std::move(encrypted_masked_messages_to_challenge_u_inverse),
+        std::move(encrypted_masked_messages_to_challenge_es_inverse)};
+    CamenischShoupCiphertext dummy_encrypted_masked_messages =
+        public_camenisch_shoup_->Add(
+            masked_dummy_encrypted_masked_messages[i],
+            encrypted_masked_messages_to_challenge_inverse);
+
+    *message_1.add_repeated_dummy_encrypted_masked_messages() =
+        CamenischShoupCiphertextToProto(dummy_encrypted_masked_messages);
+  }
+
+  // Reconstruct the challenge and check that it matches the one supplied in
+  // the proof.
   ASSIGN_OR_RETURN(BigNum reconstructed_challenge,
                    GenerateRequestProofChallenge(proof_statement, message_1));
 
@@ -951,25 +1092,38 @@ BbObliviousSignature::GenerateResponseAndProof(
   proto::BbObliviousSignatureResponse response_proto;
   proto::BbObliviousSignatureResponseProof response_proof_proto;
 
-  if (request.num_messages() >
-          public_camenisch_shoup_->vector_encryption_length() ||
+  if (request.num_messages() > pedersen_->gs().size() ||
       request.num_messages() < 0) {
     return absl::InvalidArgumentError(
         "BbObliviousSignature::GenerateResponse: invalid num_messages in "
         "request.");
   }
 
+  size_t num_camenisch_shoup_ciphertexts =
+      request.repeated_encrypted_masked_messages_size();
+
   // We will refer to the values decrypted from the CS ciphertexts as betas.
   // These betas are implicitly bounded as long as the request proof was
   // verified (and the sender generated its parameters correctly).
-  ASSIGN_OR_RETURN(CamenischShoupCiphertext encrypted_masked_messages,
-                   public_camenisch_shoup_->ParseCiphertextProto(
-                       request.encrypted_masked_messages()));
-  ASSIGN_OR_RETURN(std::vector<BigNum> betas,
-                   private_camenisch_shoup->Decrypt(encrypted_masked_messages));
-
-  // Truncate the last few elements of betas, if it's larger than num_messages.
-  // (These should be all zeros.)
+  std::vector<BigNum> betas;
+  betas.reserve(request.num_messages());
+  std::vector<CamenischShoupCiphertext> encrypted_masked_messages;
+  encrypted_masked_messages.reserve(num_camenisch_shoup_ciphertexts);
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    ASSIGN_OR_RETURN(CamenischShoupCiphertext encrypted_masked_messages_at_i,
+                     public_camenisch_shoup_->ParseCiphertextProto(
+                         request.repeated_encrypted_masked_messages(i)));
+    ASSIGN_OR_RETURN(
+        std::vector<BigNum> betas_at_i,
+        private_camenisch_shoup->Decrypt(encrypted_masked_messages_at_i));
+
+    encrypted_masked_messages.push_back(
+        std::move(encrypted_masked_messages_at_i));
+    betas.insert(betas.end(), std::make_move_iterator(betas_at_i.begin()),
+                 std::make_move_iterator(betas_at_i.end()));
+  }
+  // Truncate the last few elements of betas, if it's larger than
+  // num_messages. (These should be all zeros.)
   betas.erase(betas.begin() + request.num_messages(), betas.end());
 
   std::vector<ECPoint> masked_prf_values;
@@ -1023,8 +1177,8 @@ BbObliviousSignature::GenerateResponseAndProof(
   ASSIGN_OR_RETURN(PedersenOverZn::Commitment dummy_commit_betas,
                    pedersen_->CommitWithRand(dummy_betas, dummy_beta_opening));
 
-  // (1.2) Use the dummy values above to create dummy_cs_ys, dummy_commit_betas,
-  // dummy_enc_mask_messages_es and dummy_base_gs.
+  // (1.2) Use the dummy values above to create dummy_cs_ys,
+  // dummy_commit_betas, and dummy_base_gs and add them to proof message 1.
   std::vector<BigNum> dummy_cs_ys;
   dummy_cs_ys.reserve(public_camenisch_shoup_->vector_encryption_length());
   for (uint64_t i = 0; i < public_camenisch_shoup_->vector_encryption_length();
@@ -1033,25 +1187,6 @@ BbObliviousSignature::GenerateResponseAndProof(
         dummy_xs[i], private_camenisch_shoup->modulus()));
   }
 
-  // intermediate_es contains (1+n)^dummy_betas[i] mod n^(s+1) in the "es"
-  // component. This is achieved by encrypting dummy_betas with randomness 0.
-  ASSIGN_OR_RETURN(
-      CamenischShoupCiphertext intermediate_ciphertext,
-      private_camenisch_shoup->EncryptWithRand(dummy_betas, ctx_->Zero()));
-  // dummy_enc_mask_messages_es contains u^dummy_xs[i] * (1+n)^dummy_betas[i]
-  // mod n^(s+1) in the "es" component.
-  std::vector<BigNum> dummy_enc_mask_messages_es;
-  dummy_enc_mask_messages_es.reserve(
-      public_camenisch_shoup_->vector_encryption_length());
-  for (uint64_t i = 0; i < request.num_messages(); ++i) {
-    BigNum dummy_e =
-        encrypted_masked_messages.u
-            .ModExp(dummy_xs[i], private_camenisch_shoup->modulus())
-            .ModMul(intermediate_ciphertext.es[i],
-                    private_camenisch_shoup->modulus());
-    dummy_enc_mask_messages_es.push_back(std::move(dummy_e));
-  }
-
   std::vector<ECPoint> dummy_base_gs;
   dummy_base_gs.reserve(request.num_messages());
   for (uint64_t i = 0; i < request.num_messages(); ++i) {
@@ -1064,11 +1199,48 @@ BbObliviousSignature::GenerateResponseAndProof(
   *proof_message_1.mutable_dummy_camenisch_shoup_ys() =
       BigNumVectorToProto(dummy_cs_ys);
   proof_message_1.set_dummy_commit_betas(dummy_commit_betas.ToBytes());
-  *proof_message_1.mutable_dummy_encrypted_masked_messages_es() =
-      BigNumVectorToProto(dummy_enc_mask_messages_es);
   ASSIGN_OR_RETURN(*proof_message_1.mutable_dummy_base_gs(),
                    ECPointVectorToProto(dummy_base_gs));
 
+  // (1.3) dummy_enc_mask_messages_es is more complicated: we need to create one
+  // entry for each CS ciphertext in the request.
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    size_t batch_start_index =
+        i * public_camenisch_shoup_->vector_encryption_length();
+    size_t batch_size =
+        std::min(public_camenisch_shoup_->vector_encryption_length(),
+                 request.num_messages() - batch_start_index);
+    size_t batch_end_index = batch_start_index + batch_size;
+
+    // determine the dummy_betas that are to be used for this ciphertext.
+    std::vector<BigNum> dummy_betas_for_batch(
+        dummy_betas.begin() + batch_start_index,
+        dummy_betas.begin() + batch_end_index);
+
+    //  intermediate_es contains
+    // (1+n)^dummy_betas[i] mod n^(s+1) in the "es" component. This is achieved
+    // by encrypting dummy_betas with randomness 0.
+    ASSIGN_OR_RETURN(CamenischShoupCiphertext intermediate_ciphertext,
+                     private_camenisch_shoup->EncryptWithRand(
+                         dummy_betas_for_batch, ctx_->Zero()));
+    // dummy_enc_mask_messages_es contains u^dummy_xs[j] * (1+n)^dummy_betas[j]
+    // mod n^(s+1) in the "es" component.
+    std::vector<BigNum> dummy_enc_mask_messages_es;
+    dummy_enc_mask_messages_es.reserve(
+        public_camenisch_shoup_->vector_encryption_length());
+    for (size_t j = 0; j < batch_size; ++j) {
+      BigNum dummy_e =
+          encrypted_masked_messages[i]
+              .u.ModExp(dummy_xs[j], private_camenisch_shoup->modulus())
+              .ModMul(intermediate_ciphertext.es[j],
+                      private_camenisch_shoup->modulus());
+      dummy_enc_mask_messages_es.push_back(std::move(dummy_e));
+    }
+
+    *proof_message_1.add_repeated_dummy_encrypted_masked_messages_es() =
+        BigNumVectorToProto(dummy_enc_mask_messages_es);
+  }
+
   // (2) Generate challenge
   ASSIGN_OR_RETURN(
       BigNum challenge,
@@ -1117,7 +1289,8 @@ Status BbObliviousSignature::VerifyResponse(
   if (response.masked_signature_values().serialized_ec_points_size() !=
       request.num_messages()) {
     return absl::InvalidArgumentError(
-        "BbObliviousSignature::VerifyResponse: response has a different number "
+        "BbObliviousSignature::VerifyResponse: response has a different "
+        "number "
         "of masked_signature_values values than the request");
   }
 
@@ -1126,21 +1299,32 @@ Status BbObliviousSignature::VerifyResponse(
           .serialized_big_nums_size() !=
       public_camenisch_shoup_->vector_encryption_length()) {
     return absl::InvalidArgumentError(
-        "BbObliviousSignature::VerifyResponse: response proof has wrong number "
+        "BbObliviousSignature::VerifyResponse: response proof has wrong "
+        "number "
         "of masked_dummy_camenisch_shoup_xs in message 2.");
   }
   if (response_proof.message_2()
           .masked_dummy_betas()
           .serialized_big_nums_size() != request.num_messages()) {
     return absl::InvalidArgumentError(
-        "BbObliviousSignature::VerifyResponse: response proof has wrong number "
+        "BbObliviousSignature::VerifyResponse: response proof has wrong "
+        "number "
         "of masked_dummy_betas in message 2.");
   }
 
+  size_t num_camenisch_shoup_ciphertexts =
+      request.repeated_encrypted_masked_messages_size();
+
+  std::vector<CamenischShoupCiphertext> encrypted_masked_messages;
+  encrypted_masked_messages.reserve(num_camenisch_shoup_ciphertexts);
   // Parse the needed request, response and response proof elements.
-  ASSIGN_OR_RETURN(CamenischShoupCiphertext encrypted_masked_messages,
-                   public_camenisch_shoup_->ParseCiphertextProto(
-                       request.encrypted_masked_messages()));
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    ASSIGN_OR_RETURN(CamenischShoupCiphertext encrypted_masked_messages_at_i,
+                     public_camenisch_shoup_->ParseCiphertextProto(
+                         request.repeated_encrypted_masked_messages(i)));
+    encrypted_masked_messages.push_back(
+        std::move(encrypted_masked_messages_at_i));
+  }
   ASSIGN_OR_RETURN(std::vector<ECPoint> masked_signature_values,
                    ParseECPointVectorProto(ctx_, ec_group_,
                                            response.masked_signature_values()));
@@ -1193,32 +1377,46 @@ Status BbObliviousSignature::VerifyResponse(
   ASSIGN_OR_RETURN(*reconstructed_message_1.mutable_dummy_base_gs(),
                    ECPointVectorToProto(dummy_base_gs));
 
-  // Reconstruct dummy_es
-  // es[i] of intermediate_ciphertext is (1+n)^masked_dummy_betas[i].
-  ASSIGN_OR_RETURN(CamenischShoupCiphertext intermediate_ciphertext,
-                   public_camenisch_shoup_->EncryptWithRand(masked_dummy_betas,
-                                                            ctx_->Zero()));
-  std::vector<BigNum> dummy_es;
-  dummy_es.reserve(request.num_messages());
-  for (uint64_t i = 0; i < request.num_messages(); ++i) {
-    // masked_dummy_e = (1+n)^masked_dummy_betas[i] * u^masked_dummy_xs[i]
-    BigNum masked_dummy_e = intermediate_ciphertext.es[i].ModMul(
-        encrypted_masked_messages.u.ModExp(masked_dummy_camenisch_shoup_xs[i],
-                                           public_camenisch_shoup_->modulus()),
-        public_camenisch_shoup_->modulus());
-
-    ASSIGN_OR_RETURN(
-        BigNum e_to_challenge_inverse,
-        encrypted_masked_messages.es[i]
-            .ModExp(challenge_from_proof, public_camenisch_shoup_->modulus())
-            .ModInverse(public_camenisch_shoup_->modulus()));
-
-    BigNum dummy_e = masked_dummy_e.ModMul(e_to_challenge_inverse,
-                                           public_camenisch_shoup_->modulus());
-    dummy_es.push_back(std::move(dummy_e));
+  for (size_t i = 0; i < num_camenisch_shoup_ciphertexts; ++i) {
+    size_t batch_start_index =
+        i * public_camenisch_shoup_->vector_encryption_length();
+    size_t batch_size =
+        std::min(public_camenisch_shoup_->vector_encryption_length(),
+                 request.num_messages() - batch_start_index);
+    size_t batch_end_index = batch_start_index + batch_size;
+    std::vector<BigNum> masked_dummy_betas_for_batch(
+        masked_dummy_betas.begin() + batch_start_index,
+        masked_dummy_betas.begin() + batch_end_index);
+    // Reconstruct dummy_es
+    // es[i] of intermediate_ciphertext is (1+n)^masked_dummy_betas[i].
+    ASSIGN_OR_RETURN(CamenischShoupCiphertext intermediate_ciphertext,
+                     public_camenisch_shoup_->EncryptWithRand(
+                         masked_dummy_betas_for_batch, ctx_->Zero()));
+    std::vector<BigNum> dummy_es;
+    dummy_es.reserve(batch_size);
+    for (size_t j = 0; j < batch_size; ++j) {
+      // masked_dummy_e = (1+n)^masked_dummy_betas_for_batch[j] *
+      // u^masked_dummy_xs[j]
+      BigNum masked_dummy_e = intermediate_ciphertext.es[j].ModMul(
+          encrypted_masked_messages[i].u.ModExp(
+              masked_dummy_camenisch_shoup_xs[j],
+              public_camenisch_shoup_->modulus()),
+          public_camenisch_shoup_->modulus());
+
+      ASSIGN_OR_RETURN(
+          BigNum e_to_challenge_inverse,
+          encrypted_masked_messages[i]
+              .es[j]
+              .ModExp(challenge_from_proof, public_camenisch_shoup_->modulus())
+              .ModInverse(public_camenisch_shoup_->modulus()));
+
+      BigNum dummy_e = masked_dummy_e.ModMul(
+          e_to_challenge_inverse, public_camenisch_shoup_->modulus());
+      dummy_es.push_back(std::move(dummy_e));
+    }
+    *reconstructed_message_1.add_repeated_dummy_encrypted_masked_messages_es() =
+        BigNumVectorToProto(dummy_es);
   }
-  *reconstructed_message_1.mutable_dummy_encrypted_masked_messages_es() =
-      BigNumVectorToProto(dummy_es);
 
   // Reconstruct dummy_commit_betas.
   ASSIGN_OR_RETURN(
@@ -1251,8 +1449,8 @@ Status BbObliviousSignature::VerifyResponse(
   *reconstructed_message_1.mutable_dummy_camenisch_shoup_ys() =
       BigNumVectorToProto(dummy_camenisch_shoup_ys);
 
-  // Reconstruct the challenge by applying FiatShamir to the reconstructed first
-  // message, and ensure it exactly matches the challenge in the proof.
+  // Reconstruct the challenge by applying FiatShamir to the reconstructed
+  // first message, and ensure it exactly matches the challenge in the proof.
   ASSIGN_OR_RETURN(BigNum reconstructed_challenge,
                    GenerateResponseProofChallenge(
                        public_key, commit_messages, commit_rs, request,
diff --git a/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.h b/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.h
index 110f22c..605379d 100644
--- a/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.h
+++ b/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.h
@@ -71,7 +71,8 @@ class BbObliviousSignature {
  public:
   // Creates an object for producing Boneh-Boyen signatures. Fails if the
   // provided pointers are nullptr, or if the Pedersen commitment scheme is
-  // inconsistent with the Camenisch-Shoup encryption scheme.
+  // inconsistent with the Camenisch-Shoup encryption scheme. The max number
+  // of messages in a batch will be the Pedersen Batch size.
   static StatusOr<std::unique_ptr<BbObliviousSignature>> Create(
       proto::BbObliviousSignatureParameters parameters_proto, Context* ctx,
       ECGroup* ec_group, PublicCamenischShoup* public_camenisch_shoup,
diff --git a/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.proto b/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.proto
index 3facfc1..94f4f7f 100644
--- a/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.proto
+++ b/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature.proto
@@ -37,7 +37,10 @@ message BbObliviousSignatureParameters {
   bytes base_g = 4;
   // Public key for the associated CamenischShoup keypair.
   CamenischShoupPublicKey camenisch_shoup_public_key = 5;
-  // PedersenParameters for the associated commitment scheme.
+  // PedersenParameters for the associated commitment scheme. The batch size
+  // for the Pedersen parameters is effectively the max number of messages that
+  // can be simultaneously requested. The vector_encryption_length of
+  // camenisch_shoup_public_key must divide the pedersen batch size.
   PedersenParameters pedersen_parameters = 6;
 }
 
@@ -62,8 +65,11 @@ message BbObliviousSignaturePrivateKey {
 }
 
 message BbObliviousSignatureRequest {
+  reserved 2;
   uint64 num_messages = 1;
-  CamenischShoupCiphertext encrypted_masked_messages = 2;
+  // There will be as many Camenisch-Shoup ciphertexts as needed to fit the
+  // messages.
+  repeated CamenischShoupCiphertext repeated_encrypted_masked_messages = 3;
 }
 
 message BbObliviousSignatureRequestProof {
@@ -91,6 +97,7 @@ message BbObliviousSignatureRequestProof {
   }
 
   message Message1 {
+    reserved 9;
     bytes dummy_commit_messages = 1;
     bytes dummy_commit_rs = 2;
     // Serialized BigNum corresponding to a Pedersen Commitment.
@@ -109,10 +116,13 @@ message BbObliviousSignatureRequestProof {
     // Serialized BigNum corresponding to a Pedersen Commitment. Computed as
     // Prod_i commit_as[i]^dummy_rs[i] * Com(0, dummy_gamma_opening_2).
     bytes dummy_commit_gammas_2 = 8;
-    CamenischShoupCiphertext dummy_encrypted_masked_messages = 9;
+    // One dummy ciphertext per ciphertext in the request.
+    repeated CamenischShoupCiphertext repeated_dummy_encrypted_masked_messages =
+        10;
   }
 
   message Message2 {
+    reserved 15;
     BigNumVector masked_dummy_messages = 1;
     // Serialized BigNum corresponding to a Pedersen Commitment Opening.
     bytes masked_dummy_messages_opening = 2;
@@ -135,7 +145,8 @@ message BbObliviousSignatureRequestProof {
     bytes masked_dummy_gammas_opening_1 = 13;
     // The Pedersen Commitment opening corresponding to dummy_commit_gammas_2.
     bytes masked_dummy_gammas_opening_2 = 14;
-    bytes masked_dummy_encryption_randomness = 15;
+    // One dummy encryption randomness for each ciphertext in the request.
+    BigNumVector masked_dummy_encryption_randomness_per_ciphertext = 16;
   }
 
   BigNumVector commit_as = 1;
@@ -172,14 +183,17 @@ message BbObliviousSignatureResponseProof {
   }
 
   message Message1 {
+    reserved 3;
     // Dummy version of the Camenisch Shoup public key ys.
     BigNumVector dummy_camenisch_shoup_ys = 1;
     // Serialized BigNum corresponding to a dummy Pedersen Commitment.
     bytes dummy_commit_betas = 2;
-    BigNumVector dummy_encrypted_masked_messages_es = 3;
     // For each masked_signature_value, we show that
     // masked_signature_value^beta = base_g. Serialized ECPoints.
     ECPointVector dummy_base_gs = 4;
+    // One dummy_encrypted_masked_messages_es for each ciphertext in the
+    // request.
+    repeated BigNumVector repeated_dummy_encrypted_masked_messages_es = 5;
   }
 
   message Message2 {
diff --git a/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature_test.cc b/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature_test.cc
index f192eff..66f05e3 100644
--- a/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature_test.cc
+++ b/private_join_and_compute/crypto/dodis_yampolskiy_prf/bb_oblivious_signature_test.cc
@@ -32,6 +32,7 @@
 #include "private_join_and_compute/crypto/pedersen_over_zn.h"
 #include "private_join_and_compute/crypto/proto/big_num.pb.h"
 #include "private_join_and_compute/crypto/proto/camenisch_shoup.pb.h"
+#include "private_join_and_compute/crypto/proto/ec_point.pb.h"
 #include "private_join_and_compute/crypto/proto/pedersen.pb.h"
 #include "private_join_and_compute/crypto/proto/proto_util.h"
 #include "private_join_and_compute/util/status_testing.inc"
@@ -46,9 +47,18 @@ const int kSafePrimeLengthBits = 768;
 const int kChallengeLengthBits = 128;
 const int kSecurityParameter = 128;
 const int kCamenischShoupS = 1;
-const int kCamenischShoupVectorEncryptionLength = 3;
 
-class BbObliviousSignatureTest : public ::testing::Test {
+// Different test cases for combinations of parameters.
+struct BbObliviousSignatureTestCase {
+  std::string name;
+  int num_messages;
+  // should be >= num_messages.
+  int num_pedersen_bases;
+  int camenisch_shoup_vector_encryption_length;
+};
+
+class BbObliviousSignatureTest
+    : public ::testing::TestWithParam<BbObliviousSignatureTestCase> {
  protected:
   static void SetUpTestSuite() {
     Context ctx;
@@ -64,6 +74,12 @@ class BbObliviousSignatureTest : public ::testing::Test {
   }
 
   void SetUp() override {
+    const BbObliviousSignatureTestCase& test_case = GetParam();
+    num_messages_ = test_case.num_messages;
+    num_pedersen_bases_ = test_case.num_pedersen_bases;
+    camenisch_shoup_vector_encryption_length_ =
+        test_case.camenisch_shoup_vector_encryption_length;
+
     ASSERT_OK_AND_ASSIGN(auto ec_group_do_not_use_later,
                          ECGroup::Create(kTestCurveId, &ctx_));
     ec_group_ = std::make_unique<ECGroup>(std::move(ec_group_do_not_use_later));
@@ -79,20 +95,20 @@ class BbObliviousSignatureTest : public ::testing::Test {
         std::make_unique<ECPoint>(ec_group_->GetRandomGenerator().value());
     params_proto_.set_base_g(base_g_->ToBytesCompressed().value());
 
-    // We generate a Pedersen with fixed bases 2^2, 3^2, 5^2 and h=7^2.
-    std::vector<BigNum> bases = {ctx_.CreateBigNum(4), ctx_.CreateBigNum(9),
-                                 ctx_.CreateBigNum(25)};
-    proto::PedersenParameters pedersen_params;
-    pedersen_params.set_n(n.ToBytes());
-    *pedersen_params.mutable_gs() = BigNumVectorToProto(bases);
-    pedersen_params.set_h(ctx_.CreateBigNum(49).ToBytes());
+    // Generate Pedersen Parameters
+    PedersenOverZn::Parameters pedersen_parameters_struct =
+        PedersenOverZn::GenerateParameters(&ctx_, n,
+                                           test_case.num_pedersen_bases);
+    proto::PedersenParameters pedersen_params =
+        PedersenOverZn::ParametersToProto(pedersen_parameters_struct);
 
     *params_proto_.mutable_pedersen_parameters() = pedersen_params;
     ASSERT_OK_AND_ASSIGN(pedersen_,
                          PedersenOverZn::FromProto(&ctx_, pedersen_params));
 
     std::tie(cs_public_key_, cs_private_key_) = GenerateCamenischShoupKeyPair(
-        &ctx_, n, kCamenischShoupS, kCamenischShoupVectorEncryptionLength);
+        &ctx_, n, kCamenischShoupS,
+        test_case.camenisch_shoup_vector_encryption_length);
 
     *params_proto_.mutable_camenisch_shoup_public_key() =
         CamenischShoupPublicKeyToProto(*cs_public_key_);
@@ -116,6 +132,16 @@ class BbObliviousSignatureTest : public ::testing::Test {
     y_ = std::make_unique<BigNum>(ctx_.CreateBigNum(private_key_proto_.y()));
   }
 
+  // Generates random messages appropriate for a signature request.
+  std::vector<BigNum> GenerateRandomMessages(int num_messages) {
+    std::vector<BigNum> messages;
+    messages.reserve(num_messages);
+    for (int i = 0; i < num_messages; ++i) {
+      messages.push_back(ec_group_->GeneratePrivateKey());
+    }
+    return messages;
+  }
+
   // Holds a transcript for a Oblivious Signature request.
   struct Transcript {
     std::unique_ptr<PedersenOverZn::CommitmentAndOpening>
@@ -185,6 +211,10 @@ class BbObliviousSignatureTest : public ::testing::Test {
   static std::string* serialized_safe_prime_p_;
   static std::string* serialized_safe_prime_q_;
 
+  int num_messages_;
+  int num_pedersen_bases_;
+  int camenisch_shoup_vector_encryption_length_;
+
   proto::BbObliviousSignatureParameters params_proto_;
 
   Context ctx_;
@@ -210,7 +240,7 @@ class BbObliviousSignatureTest : public ::testing::Test {
 std::string* BbObliviousSignatureTest::serialized_safe_prime_p_ = nullptr;
 std::string* BbObliviousSignatureTest::serialized_safe_prime_q_ = nullptr;
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        CreateFailsWhenPublicCamenischShoupNotLargeEnough) {
   // Create an "n" with a smaller modulus.
   int small_prime_length_bits = 256;
@@ -226,7 +256,7 @@ TEST_F(BbObliviousSignatureTest,
   std::unique_ptr<PublicCamenischShoup> small_public_camenisch_shoup;
   std::tie(small_cs_public_key, small_cs_private_key) =
       GenerateCamenischShoupKeyPair(&ctx_, small_n, kCamenischShoupS,
-                                    kCamenischShoupVectorEncryptionLength);
+                                    camenisch_shoup_vector_encryption_length_);
 
   *small_params.mutable_camenisch_shoup_public_key() =
       CamenischShoupPublicKeyToProto(*small_cs_public_key);
@@ -242,16 +272,17 @@ TEST_F(BbObliviousSignatureTest,
                        HasSubstr("not large enough")));
 }
 
-TEST_F(BbObliviousSignatureTest, CreateFailsWhenPedersenNotLargeEnough) {
+TEST_P(BbObliviousSignatureTest, CreateFailsWhenPedersenNotLargeEnough) {
   // Create an "n" with a smaller modulus.
   int small_prime_length_bits = 256;
   BigNum p = ctx_.GenerateSafePrime(small_prime_length_bits);
   BigNum q = ctx_.GenerateSafePrime(small_prime_length_bits);
   BigNum small_n = p * q;
 
-  // Change the pedersen params to use the smaller modulus (all other params can
-  // stay the same).
-  params_proto_.mutable_pedersen_parameters()->set_n(small_n.ToBytes());
+  // Change the pedersen params to use the smaller modulus.
+  *params_proto_.mutable_pedersen_parameters() =
+      PedersenOverZn::ParametersToProto(PedersenOverZn::GenerateParameters(
+          &ctx_, small_n, num_pedersen_bases_));
   // Reset the pedersen object with the updated params.
   ASSERT_OK_AND_ASSIGN(
       pedersen_,
@@ -264,9 +295,8 @@ TEST_F(BbObliviousSignatureTest, CreateFailsWhenPedersenNotLargeEnough) {
                        HasSubstr("not large enough")));
 }
 
-TEST_F(BbObliviousSignatureTest, EvaluatesCorrectlyNoProofs) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, EvaluatesCorrectlyNoProofs) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   // Validate results.
@@ -281,8 +311,8 @@ TEST_F(BbObliviousSignatureTest, EvaluatesCorrectlyNoProofs) {
   }
 }
 
-TEST_F(BbObliviousSignatureTest, EvaluatesCorrectlyWithFewerMessagesNoProofs) {
-  std::vector<BigNum> fewer_messages = {ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, EvaluatesCorrectlyWithFewerMessagesNoProofs) {
+  std::vector<BigNum> fewer_messages = GenerateRandomMessages(1);
   ASSERT_OK_AND_ASSIGN(Transcript transcript,
                        GenerateTranscript(fewer_messages));
 
@@ -298,13 +328,13 @@ TEST_F(BbObliviousSignatureTest, EvaluatesCorrectlyWithFewerMessagesNoProofs) {
   }
 }
 
-TEST_F(BbObliviousSignatureTest, KeysEncryptsVectorOfSecret) {
-  EXPECT_EQ(kCamenischShoupVectorEncryptionLength,
+TEST_P(BbObliviousSignatureTest, KeysEncryptsVectorOfSecret) {
+  EXPECT_EQ(camenisch_shoup_vector_encryption_length_,
             public_key_proto_.encrypted_k_size());
-  EXPECT_EQ(kCamenischShoupVectorEncryptionLength,
+  EXPECT_EQ(camenisch_shoup_vector_encryption_length_,
             public_key_proto_.encrypted_y_size());
 
-  for (int i = 0; i < kCamenischShoupVectorEncryptionLength; ++i) {
+  for (int i = 0; i < camenisch_shoup_vector_encryption_length_; ++i) {
     ASSERT_OK_AND_ASSIGN(CamenischShoupCiphertext encrypted_k_at_i,
                          public_camenisch_shoup_->ParseCiphertextProto(
                              public_key_proto_.encrypted_k(i)));
@@ -316,10 +346,12 @@ TEST_F(BbObliviousSignatureTest, KeysEncryptsVectorOfSecret) {
     ASSERT_OK_AND_ASSIGN(std::vector<BigNum> decrypted_y_at_i,
                          private_camenisch_shoup_->Decrypt(encrypted_y_at_i));
 
-    EXPECT_EQ(decrypted_k_at_i.size(), kCamenischShoupVectorEncryptionLength);
-    EXPECT_EQ(decrypted_y_at_i.size(), kCamenischShoupVectorEncryptionLength);
+    EXPECT_EQ(decrypted_k_at_i.size(),
+              camenisch_shoup_vector_encryption_length_);
+    EXPECT_EQ(decrypted_y_at_i.size(),
+              camenisch_shoup_vector_encryption_length_);
 
-    for (int j = 0; j < kCamenischShoupVectorEncryptionLength; ++j) {
+    for (int j = 0; j < camenisch_shoup_vector_encryption_length_; ++j) {
       // Each should be equal to the secret key at the i'th position, and 0
       // elsewhere.
       if (j != i) {
@@ -333,11 +365,11 @@ TEST_F(BbObliviousSignatureTest, KeysEncryptsVectorOfSecret) {
   }
 }
 
-TEST_F(BbObliviousSignatureTest, GeneratesDistinctYAndK) {
+TEST_P(BbObliviousSignatureTest, GeneratesDistinctYAndK) {
   EXPECT_NE(*k_, *y_);
 }
 
-TEST_F(BbObliviousSignatureTest, GeneratesDifferentKeys) {
+TEST_P(BbObliviousSignatureTest, GeneratesDifferentKeys) {
   proto::BbObliviousSignaturePublicKey other_public_key_proto;
   proto::BbObliviousSignaturePrivateKey other_private_key_proto;
   ASSERT_OK_AND_ASSIGN(
@@ -348,13 +380,27 @@ TEST_F(BbObliviousSignatureTest, GeneratesDifferentKeys) {
   EXPECT_NE(private_key_proto_.y(), other_private_key_proto.y());
 }
 
-// Test for too many messages as input to request is skipped because Pedersen
-// fails when computing the commitment on too many messages.
+TEST_P(BbObliviousSignatureTest, RequestFailsWhenNumMessagesTooLarge) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+  ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
+
+  // Change messages to have one extra message (note that the messages vector is
+  // inconsistent with the commitment, which is just for the purposes of this
+  // test).
+  messages.push_back(ctx_.Three());
+
+  // Generating the request should fail.
+  EXPECT_THAT(
+      bb_ob_sig_->GenerateRequestAndProof(
+          messages, transcript.rs, public_key_proto_,
+          *transcript.commit_and_open_messages, *transcript.commit_and_open_rs),
+      StatusIs(absl::StatusCode::kInvalidArgument,
+               HasSubstr("messages has size")));
+}
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestFailsWhenRsHasDifferentLengthFromMessages) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   // Change rs to have one less message, and recommit.
@@ -374,19 +420,18 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("rs has size")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestsAreDifferent) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestsAreDifferent) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript_1, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
-  EXPECT_NE(transcript_1.request_proto.encrypted_masked_messages().u(),
-            transcript_2.request_proto.encrypted_masked_messages().u());
+  EXPECT_NE(
+      transcript_1.request_proto.repeated_encrypted_masked_messages(0).u(),
+      transcript_2.request_proto.repeated_encrypted_masked_messages(0).u());
 }
 
-TEST_F(BbObliviousSignatureTest, ResponseFailsWhenNumMessagesIsTooLarge) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, ResponseFailsWhenNumMessagesIsTooLarge) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   transcript.request_proto.set_num_messages(messages.size() + 1);
@@ -401,11 +446,10 @@ TEST_F(BbObliviousSignatureTest, ResponseFailsWhenNumMessagesIsTooLarge) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("num_messages")));
 }
 
-TEST_F(BbObliviousSignatureTest, ResponsesFromDifferentRequestsAreDifferent) {
+TEST_P(BbObliviousSignatureTest, ResponsesFromDifferentRequestsAreDifferent) {
   // Responses are actually generated deterministically from requests, so this
   // test is implicitly testing that the requests used different randomness.
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript_1, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -419,9 +463,43 @@ TEST_F(BbObliviousSignatureTest, ResponsesFromDifferentRequestsAreDifferent) {
 // Verify Request tests
 ////////////////////////////////////////////////////////////////////////////////
 
-TEST_F(BbObliviousSignatureTest, RequestProofSucceeds) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest,
+       VerifyRequestFailsWhenNumMessagesTooLargeForPedersen) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+  ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
+
+  // Modify num_messages to be too large.
+  transcript.request_proto.set_num_messages(num_messages_ + 1);
+
+  EXPECT_THAT(
+      bb_ob_sig_->VerifyRequest(public_key_proto_, transcript.request_proto,
+                                transcript.request_proof_proto,
+                                transcript.commit_and_open_messages->commitment,
+                                transcript.commit_and_open_rs->commitment),
+      StatusIs(absl::StatusCode::kInvalidArgument,
+               HasSubstr("messages has size")));
+}
+
+TEST_P(BbObliviousSignatureTest,
+       VerifyRequestFailsWithEncryptedMaskedMessagesOfWrongSize) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+  ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
+
+  // Remove one of the encrypted_masked_messages.
+  transcript.request_proto.mutable_repeated_encrypted_masked_messages()
+      ->RemoveLast();
+
+  EXPECT_THAT(
+      bb_ob_sig_->VerifyRequest(public_key_proto_, transcript.request_proto,
+                                transcript.request_proof_proto,
+                                transcript.commit_and_open_messages->commitment,
+                                transcript.commit_and_open_rs->commitment),
+      StatusIs(absl::StatusCode::kInvalidArgument,
+               HasSubstr("number of ciphertexts")));
+}
+
+TEST_P(BbObliviousSignatureTest, RequestProofSucceeds) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   EXPECT_OK(
@@ -431,9 +509,8 @@ TEST_F(BbObliviousSignatureTest, RequestProofSucceeds) {
                                 transcript.commit_and_open_rs->commitment));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestChallengeIsBounded) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestChallengeIsBounded) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
 
   ASSERT_OK_AND_ASSIGN(auto transcript, GenerateTranscript(messages));
 
@@ -441,9 +518,8 @@ TEST_F(BbObliviousSignatureTest, RequestChallengeIsBounded) {
             ctx_.One().Lshift(kChallengeLengthBits));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestChallengeChangesIfRoPrefixIsChanged) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestChallengeChangesIfRoPrefixIsChanged) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
 
   ASSERT_OK_AND_ASSIGN(auto transcript, GenerateTranscript(messages));
 
@@ -464,34 +540,24 @@ TEST_F(BbObliviousSignatureTest, RequestChallengeChangesIfRoPrefixIsChanged) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("challenge")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFromDifferentRequestHasDifferentChallenge) {
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_1,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1), ctx_.CreateBigNum(5)}));
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+  ASSERT_OK_AND_ASSIGN(auto transcript_1, GenerateTranscript(messages));
 
   // Generate a second transcript
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_2,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(3), ctx_.CreateBigNum(7), ctx_.CreateBigNum(9)}));
+  ASSERT_OK_AND_ASSIGN(auto transcript_2, GenerateTranscript(messages));
 
   EXPECT_NE(transcript_1.request_proof_proto.challenge(),
             transcript_2.request_proof_proto.challenge());
 }
 
-TEST_F(BbObliviousSignatureTest, RquestProofFromDifferentRequestFails) {
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_1,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1), ctx_.CreateBigNum(5)}));
+TEST_P(BbObliviousSignatureTest, RquestProofFromDifferentRequestFails) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+  ASSERT_OK_AND_ASSIGN(auto transcript_1, GenerateTranscript(messages));
 
   // Generate a second transcript
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_2,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(3), ctx_.CreateBigNum(7), ctx_.CreateBigNum(9)}));
+  ASSERT_OK_AND_ASSIGN(auto transcript_2, GenerateTranscript(messages));
 
   // Use the request proof from the first request to validate the second.
   // Expect the verification to fail.
@@ -504,9 +570,8 @@ TEST_F(BbObliviousSignatureTest, RquestProofFromDifferentRequestFails) {
                        HasSubstr("VerifyRequest: Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithCommitAsOfWrongSize) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithCommitAsOfWrongSize) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   // Remove one of the commit_as.
@@ -522,10 +587,9 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithCommitAsOfWrongSize) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("commit_as")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithMaskedDummyMessagesOfWrongSize) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   // Remove one of the masked_dummy_messages.
@@ -543,10 +607,9 @@ TEST_F(BbObliviousSignatureTest,
                HasSubstr("masked_dummy_messages")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithMaskedDummyRsOfWrongSize) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   // Remove one of the masked_dummy_rs.
@@ -564,10 +627,9 @@ TEST_F(BbObliviousSignatureTest,
                HasSubstr("masked_dummy_rs")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithMaskedDummyAsOfWrongSize) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   // Remove one of the masked_dummy_as.
@@ -585,10 +647,9 @@ TEST_F(BbObliviousSignatureTest,
                HasSubstr("masked_dummy_as")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithMaskedDummyBsOfWrongSize) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   // Remove one of the masked_dummy_bs.
@@ -606,10 +667,9 @@ TEST_F(BbObliviousSignatureTest,
                HasSubstr("masked_dummy_bs")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithMaskedDummyAlphasOfWrongSize) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   // Remove one of the masked_dummy_alphas.
@@ -627,10 +687,9 @@ TEST_F(BbObliviousSignatureTest,
                HasSubstr("masked_dummy_alphas")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithMaskedDummyGammasOfWrongSize) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   // Remove one of the masked_dummy_gammas.
@@ -648,9 +707,28 @@ TEST_F(BbObliviousSignatureTest,
                HasSubstr("masked_dummy_gammas")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongCommitBs) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest,
+       RequestProofFailsWithMaskedDummyEncryptionRandomnessOfWrongSize) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+  ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
+
+  // Remove one of the encrypted_masked_messages.
+  transcript.request_proof_proto.mutable_message_2()
+      ->mutable_masked_dummy_encryption_randomness_per_ciphertext()
+      ->mutable_serialized_big_nums()
+      ->RemoveLast();
+
+  EXPECT_THAT(
+      bb_ob_sig_->VerifyRequest(public_key_proto_, transcript.request_proto,
+                                transcript.request_proof_proto,
+                                transcript.commit_and_open_messages->commitment,
+                                transcript.commit_and_open_rs->commitment),
+      StatusIs(absl::StatusCode::kInvalidArgument,
+               HasSubstr("masked_dummy_encryption_randomness")));
+}
+
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithWrongCommitBs) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -666,9 +744,8 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongCommitBs) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongCommitAlphas) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithWrongCommitAlphas) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -684,9 +761,8 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongCommitAlphas) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongCommitGammas) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithWrongCommitGammas) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -702,9 +778,8 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongCommitGammas) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongChallenge) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithWrongChallenge) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -720,10 +795,9 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongChallenge) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyMessages) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -741,9 +815,8 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyRs) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyRs) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -761,9 +834,8 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyRs) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyAs) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyAs) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -781,9 +853,8 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyAs) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyBs) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyBs) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -801,9 +872,8 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyBs) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyAlphas) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyAlphas) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -821,9 +891,8 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyAlphas) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyGammas) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyGammas) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -841,10 +910,9 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithWrongMaskedDummyGammas) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyMessagesOpening) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -863,10 +931,9 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyRsOpening) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -884,10 +951,9 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyAsOpening) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -905,10 +971,9 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyBsOpening) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -926,10 +991,9 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyAlphasOpening1) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -948,10 +1012,9 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyAlphasOpening2) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -970,10 +1033,9 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyGammasOpening1) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -992,10 +1054,9 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyGammasOpening2) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
@@ -1014,19 +1075,18 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        RequestProofFailsWithWrongMaskedDummyEncryptionRandomness) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
   ASSERT_OK_AND_ASSIGN(Transcript transcript_2, GenerateTranscript(messages));
 
   // Replace masked_dummy_encryption_randomness in the first transcript with
   // that from the second.
-  transcript.request_proof_proto.mutable_message_2()
-      ->set_masked_dummy_encryption_randomness(
-          transcript_2.request_proof_proto.message_2()
-              .masked_dummy_encryption_randomness());
+  *transcript.request_proof_proto.mutable_message_2()
+       ->mutable_masked_dummy_encryption_randomness_per_ciphertext() =
+      transcript_2.request_proof_proto.message_2()
+          .masked_dummy_encryption_randomness_per_ciphertext();
 
   EXPECT_THAT(
       bb_ob_sig_->VerifyRequest(public_key_proto_, transcript.request_proto,
@@ -1036,7 +1096,7 @@ TEST_F(BbObliviousSignatureTest,
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, RequestProofFailsWithEnormousMessages) {
+TEST_P(BbObliviousSignatureTest, RequestProofFailsWithEnormousMessages) {
   BigNum large_message =
       ec_group_->GetOrder() *
       ec_group_->GetOrder().Lshift(
@@ -1056,9 +1116,8 @@ TEST_F(BbObliviousSignatureTest, RequestProofFailsWithEnormousMessages) {
 // Verify Response tests
 ////////////////////////////////////////////////////////////////////////////////
 
-TEST_F(BbObliviousSignatureTest, ResponseProofSucceeds) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, ResponseProofSucceeds) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
   ASSERT_OK_AND_ASSIGN(Transcript transcript, GenerateTranscript(messages));
 
   EXPECT_OK(bb_ob_sig_->VerifyResponse(
@@ -1068,9 +1127,8 @@ TEST_F(BbObliviousSignatureTest, ResponseProofSucceeds) {
       transcript.commit_and_open_rs->commitment));
 }
 
-TEST_F(BbObliviousSignatureTest, ResponseChallengeIsBounded) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, ResponseChallengeIsBounded) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
 
   ASSERT_OK_AND_ASSIGN(auto transcript, GenerateTranscript(messages));
 
@@ -1078,9 +1136,8 @@ TEST_F(BbObliviousSignatureTest, ResponseChallengeIsBounded) {
             ctx_.One().Lshift(kChallengeLengthBits));
 }
 
-TEST_F(BbObliviousSignatureTest, ResponseChallengeChangesIfRoPrefixIsChanged) {
-  std::vector<BigNum> messages = {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1),
-                                  ctx_.CreateBigNum(5)};
+TEST_P(BbObliviousSignatureTest, ResponseChallengeChangesIfRoPrefixIsChanged) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
 
   ASSERT_OK_AND_ASSIGN(auto transcript, GenerateTranscript(messages));
 
@@ -1101,34 +1158,26 @@ TEST_F(BbObliviousSignatureTest, ResponseChallengeChangesIfRoPrefixIsChanged) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("challenge")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        ResponseProofFromDifferentRequestHasDifferentChallenge) {
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_1,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1), ctx_.CreateBigNum(5)}));
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+
+  ASSERT_OK_AND_ASSIGN(auto transcript_1, GenerateTranscript(messages));
 
   // Generate a second transcript
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_2,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(3), ctx_.CreateBigNum(7), ctx_.CreateBigNum(9)}));
+  ASSERT_OK_AND_ASSIGN(auto transcript_2, GenerateTranscript(messages));
 
   EXPECT_NE(transcript_1.response_proof_proto.challenge(),
             transcript_2.response_proof_proto.challenge());
 }
 
-TEST_F(BbObliviousSignatureTest, ResponseProofFromDifferentRequestFails) {
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_1,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1), ctx_.CreateBigNum(5)}));
+TEST_P(BbObliviousSignatureTest, ResponseProofFromDifferentRequestFails) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+
+  ASSERT_OK_AND_ASSIGN(auto transcript_1, GenerateTranscript(messages));
 
   // Generate a second transcript
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_2,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(3), ctx_.CreateBigNum(7), ctx_.CreateBigNum(9)}));
+  ASSERT_OK_AND_ASSIGN(auto transcript_2, GenerateTranscript(messages));
 
   // Use the response proof from the first request to validate the second.
   // Expect the verification to fail.
@@ -1141,12 +1190,10 @@ TEST_F(BbObliviousSignatureTest, ResponseProofFromDifferentRequestFails) {
                        HasSubstr("VerifyResponse: Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest,
+TEST_P(BbObliviousSignatureTest,
        ResponseProofFailsWithTooFewMaskedSignatureValues) {
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1), ctx_.CreateBigNum(5)}));
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+  ASSERT_OK_AND_ASSIGN(auto transcript, GenerateTranscript(messages));
   // Remove one of the masked_signature_values.
   transcript.response_proto.mutable_masked_signature_values()
       ->mutable_serialized_ec_points()
@@ -1160,11 +1207,9 @@ TEST_F(BbObliviousSignatureTest,
                        HasSubstr("masked_signature_values")));
 }
 
-TEST_F(BbObliviousSignatureTest, ResponseProofFailsWithTooFewMaskedXs) {
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1), ctx_.CreateBigNum(5)}));
+TEST_P(BbObliviousSignatureTest, ResponseProofFailsWithTooFewMaskedXs) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+  ASSERT_OK_AND_ASSIGN(auto transcript, GenerateTranscript(messages));
   // Remove one of the masked_xs.
   transcript.response_proof_proto.mutable_message_2()
       ->mutable_masked_dummy_camenisch_shoup_xs()
@@ -1179,11 +1224,9 @@ TEST_F(BbObliviousSignatureTest, ResponseProofFailsWithTooFewMaskedXs) {
                        HasSubstr("masked_dummy_camenisch_shoup_xs")));
 }
 
-TEST_F(BbObliviousSignatureTest, ResponseProofFailsWithTooFewMaskedBetas) {
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1), ctx_.CreateBigNum(5)}));
+TEST_P(BbObliviousSignatureTest, ResponseProofFailsWithTooFewMaskedBetas) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+  ASSERT_OK_AND_ASSIGN(auto transcript, GenerateTranscript(messages));
   // Remove one of the masked_betas.
   transcript.response_proof_proto.mutable_message_2()
       ->mutable_masked_dummy_betas()
@@ -1198,17 +1241,13 @@ TEST_F(BbObliviousSignatureTest, ResponseProofFailsWithTooFewMaskedBetas) {
                        HasSubstr("masked_dummy_betas")));
 }
 
-TEST_F(BbObliviousSignatureTest, FailsWithWrongResponseProofCommitBetas) {
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_1,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(0), ctx_.CreateBigNum(1), ctx_.CreateBigNum(5)}));
+TEST_P(BbObliviousSignatureTest, FailsWithWrongResponseProofCommitBetas) {
+  std::vector<BigNum> messages = GenerateRandomMessages(num_messages_);
+
+  ASSERT_OK_AND_ASSIGN(auto transcript_1, GenerateTranscript(messages));
 
   // Generate a second transcript
-  ASSERT_OK_AND_ASSIGN(
-      auto transcript_2,
-      GenerateTranscript(
-          {ctx_.CreateBigNum(3), ctx_.CreateBigNum(7), ctx_.CreateBigNum(9)}));
+  ASSERT_OK_AND_ASSIGN(auto transcript_2, GenerateTranscript(messages));
 
   // Use the commit_betas in response proof from the first request to
   // validate the second. Expect the verification to fail.
@@ -1224,7 +1263,7 @@ TEST_F(BbObliviousSignatureTest, FailsWithWrongResponseProofCommitBetas) {
                        HasSubstr("VerifyResponse: Failed")));
 }
 
-TEST_F(BbObliviousSignatureTest, ResponseProofFailsWithEnormousBeta) {
+TEST_P(BbObliviousSignatureTest, ResponseProofFailsWithEnormousBeta) {
   BigNum large_message =
       ec_group_->GetOrder() *
       ec_group_->GetOrder().Lshift(
@@ -1245,5 +1284,18 @@ TEST_F(BbObliviousSignatureTest, ResponseProofFailsWithEnormousBeta) {
       StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("larger")));
 }
 
+INSTANTIATE_TEST_SUITE_P(
+    BbObliviousSignatureTests, BbObliviousSignatureTest,
+    ::testing::ValuesIn<BbObliviousSignatureTestCase>({
+        {"pedersen_4_cs_4", /*num_messages=*/4, /*num_pedersen_bases=*/4,
+         /*camenisch_shoup_vector_encryption_length=*/4},
+        {"pedersen_4_cs_2", /*num_messages=*/4, /*num_pedersen_bases=*/4,
+         /*camenisch_shoup_vector_encryption_length=*/2},
+        {"pedersen_4_cs_3", /*num_messages=*/4, /*num_pedersen_bases=*/4,
+         /*camenisch_shoup_vector_encryption_length=*/3},
+    }),
+    [](const ::testing::TestParamInfo<BbObliviousSignatureTest::ParamType>&
+           info) { return info.param.name; });
+
 }  // namespace
 }  // namespace private_join_and_compute
diff --git a/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.cc b/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.cc
index bcb8374..bab9ea3 100644
--- a/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.cc
+++ b/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.cc
@@ -54,9 +54,8 @@ DyVerifiableRandomFunction::Create(proto::DyVrfParameters parameters_proto,
       pedersen));
 }
 
-StatusOr<
-    std::tuple<proto::DyVrfPublicKey, proto::DyVrfPrivateKey,
-               std::unique_ptr<DyVerifiableRandomFunction::GenerateKeysProof>>>
+StatusOr<std::tuple<proto::DyVrfPublicKey, proto::DyVrfPrivateKey,
+                    proto::DyVrfGenerateKeysProof>>
 DyVerifiableRandomFunction::GenerateKeyPair() {
   // Generate a fresh key, and commit to it with respect to each Pedersen
   // generator.
@@ -67,22 +66,184 @@ DyVerifiableRandomFunction::GenerateKeyPair() {
                    pedersen_->Commit(std::vector<BigNum>(num_copies, key)));
 
   DyVerifiableRandomFunction::PublicKey public_key{
-      std::move(commit_and_open_key.commitment)  // commit_key
+      commit_and_open_key.commitment  // commit_key
   };
   DyVerifiableRandomFunction::PrivateKey private_key{
-      std::move(key),                         // key
-      std::move(commit_and_open_key.opening)  // open_key
+      key,                         // key
+      commit_and_open_key.opening  // open_key
   };
 
-  std::unique_ptr<GenerateKeysProof> empty_proof = nullptr;
-
   proto::DyVrfPublicKey public_key_proto = DyVrfPublicKeyToProto(public_key);
   proto::DyVrfPrivateKey private_key_proto =
       DyVrfPrivateKeyToProto(private_key);
 
+  // Generate the keys proof. This proof is a sigma protocol that proves
+  // knowledge of the key, and also that the same key has been committed in each
+  // component of the batched Pedersen commitment scheme. Furthermore, this
+  // proof shows that the key is bounded-with-slack, using the range proof
+  // feature of sigma protocols (i.e. checking the size of the masked dummy
+  // opening to the key). The proven bound on the key is ec_group_order *
+  // 2^(challenge_length + security_parameter).
+  //
+  // These properties are sufficient for the key to be safe for use downstream.
+  //
+  // As in all sigma protocols, this proof proceeds by the prover generating
+  // dummy values for all the secret exponents (here, these are the key and the
+  // commitment randomness), and then creating a dummy commitment to the key
+  // using the dummy values. The sigma protocol then hashes this dummy
+  // commitment together with the proof statement (i.e. the original commitment)
+  // to produce a challenge using the Fiat-Shamir heuristic. Given this
+  // challenge, the prover then sends the receiver "masked_dummy_values" as
+  // dummy_value + (challenge * real_value) for each of the secret exponents.
+  // The verifier can then use these masked_dummy_values to verify the proof.
+
+  // Generate dummy key and opening.
+  BigNum dummy_key_bound =
+      ec_group_->GetOrder().Lshift(parameters_proto_.challenge_length_bits() +
+                                   parameters_proto_.security_parameter());
+  BigNum dummy_opening_bound =
+      pedersen_->n().Lshift(parameters_proto_.challenge_length_bits() +
+                            parameters_proto_.security_parameter());
+  BigNum dummy_key = context_->GenerateRandLessThan(dummy_key_bound);
+  BigNum dummy_opening = context_->GenerateRandLessThan(dummy_opening_bound);
+  std::vector<BigNum> dummy_key_vector =
+      std::vector<BigNum>(num_copies, dummy_key);
+  ASSIGN_OR_RETURN(PedersenOverZn::Commitment dummy_commit_prf_key,
+                   pedersen_->CommitWithRand(dummy_key_vector, dummy_opening));
+
+  // Create Statement and first message, and generate the challenge.
+  proto::DyVrfGenerateKeysProof::Statement statement;
+  *statement.mutable_parameters() = parameters_proto_;
+  *statement.mutable_public_key() = public_key_proto;
+
+  proto::DyVrfGenerateKeysProof::Message1 message_1;
+  *message_1.mutable_dummy_commit_prf_key() = dummy_commit_prf_key.ToBytes();
+
+  ASSIGN_OR_RETURN(BigNum challenge,
+                   GenerateChallengeForGenerateKeysProof(statement, message_1));
+
+  // Create the masked_dummy_opening values.
+  BigNum masked_dummy_prf_key = dummy_key + (key.Mul(challenge));
+  BigNum masked_dummy_opening =
+      dummy_opening + (commit_and_open_key.opening.Mul(challenge));
+
+  // Package the values into the proof proto.
+  proto::DyVrfGenerateKeysProof generate_keys_proof;
+
+  generate_keys_proof.set_challenge(challenge.ToBytes());
+  generate_keys_proof.mutable_message_2()->set_masked_dummy_prf_key(
+      masked_dummy_prf_key.ToBytes());
+  generate_keys_proof.mutable_message_2()->set_masked_dummy_opening(
+      masked_dummy_opening.ToBytes());
+
   return {std::make_tuple(std::move(public_key_proto),
                           std::move(private_key_proto),
-                          std::move(empty_proof))};
+                          std::move(generate_keys_proof))};
+}
+
+// Verifies that the public key has a bounded key, and commits to the same key
+// in each component of the Pedersen batch commitment.
+Status DyVerifiableRandomFunction::VerifyGenerateKeysProof(
+    const proto::DyVrfPublicKey& public_key,
+    const proto::DyVrfGenerateKeysProof& proof) {
+  // Deserialize components of the public key and proof
+  BigNum commit_prf_key = context_->CreateBigNum(public_key.commit_prf_key());
+  BigNum challenge_from_proof = context_->CreateBigNum(proof.challenge());
+  BigNum masked_dummy_prf_key =
+      context_->CreateBigNum(proof.message_2().masked_dummy_prf_key());
+  BigNum masked_dummy_opening =
+      context_->CreateBigNum(proof.message_2().masked_dummy_opening());
+
+  // Verify the bounds on masked_dummy values
+  BigNum masked_dummy_prf_key_bound =
+      ec_group_->GetOrder().Lshift(parameters_proto_.challenge_length_bits() +
+                                   parameters_proto_.security_parameter() + 1);
+  if (masked_dummy_prf_key > masked_dummy_prf_key_bound) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "DyVerifiableRandomFunction::VerifyGenerateKeysProof: "
+        "masked_dummy_prf_key is larger than the bound. Supplied value: ",
+        masked_dummy_prf_key.ToDecimalString(),
+        ". bound: ", masked_dummy_prf_key_bound.ToDecimalString()));
+  }
+
+  // Regenerate dummy values from the masked_dummy values and the challenge in
+  // the proof.
+  std::vector<BigNum> masked_dummy_prf_key_vector =
+      std::vector<BigNum>(pedersen_->gs().size(), masked_dummy_prf_key);
+  ASSIGN_OR_RETURN(PedersenOverZn::Commitment masked_dummy_prf_key_commitment,
+                   pedersen_->CommitWithRand(masked_dummy_prf_key_vector,
+                                             masked_dummy_opening));
+
+  ASSIGN_OR_RETURN(PedersenOverZn::Commitment commit_keys_to_challenge_inverse,
+                   pedersen_->Multiply(commit_prf_key, challenge_from_proof)
+                       .ModInverse(pedersen_->n()));
+  PedersenOverZn::Commitment dummy_commit_prf_key = pedersen_->Add(
+      commit_keys_to_challenge_inverse, masked_dummy_prf_key_commitment);
+
+  // Regenerate the challenge and verify that it matches the challenge in the
+  // proof.
+  proto::DyVrfGenerateKeysProof::Statement statement;
+  proto::DyVrfGenerateKeysProof::Message1 message_1;
+
+  *statement.mutable_parameters() = parameters_proto_;
+  *statement.mutable_public_key() = public_key;
+
+  message_1.set_dummy_commit_prf_key(dummy_commit_prf_key.ToBytes());
+
+  ASSIGN_OR_RETURN(BigNum reconstructed_challenge,
+                   GenerateChallengeForGenerateKeysProof(statement, message_1));
+
+  if (reconstructed_challenge != challenge_from_proof) {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "DyVerifiableRandomFunction::VerifyGenerateKeysProof: Failed to verify "
+        " proof. Challenge in proof (",
+        challenge_from_proof.ToDecimalString(),
+        ") does not match reconstructed challenge (",
+        reconstructed_challenge.ToDecimalString(), ")."));
+  }
+
+  return absl::OkStatus();
+}
+
+// Generates the challenge for the GenerateKeysProof using the Fiat-Shamir
+// heuristic.
+StatusOr<BigNum>
+DyVerifiableRandomFunction::GenerateChallengeForGenerateKeysProof(
+    const proto::DyVrfGenerateKeysProof::Statement& statement,
+    const proto::DyVrfGenerateKeysProof::Message1& message_1) {
+  // Note that the random oracle prefix is implicitly included as part of the
+  // parameters being serialized in the statement proto. We skip including it
+  // again here to avoid unnecessary duplication.
+  std::string challenge_string =
+      "DyVerifiableRandomFunction::GenerateChallengeForGenerateKeysProof";
+  auto challenge_sos =
+      std::make_unique<google::protobuf::io::StringOutputStream>(
+          &challenge_string);
+  auto challenge_cos =
+      std::make_unique<google::protobuf::io::CodedOutputStream>(
+          challenge_sos.get());
+  challenge_cos->SetSerializationDeterministic(true);
+  challenge_cos->WriteVarint64(statement.ByteSizeLong());
+  if (!statement.SerializeToCodedStream(challenge_cos.get())) {
+    return absl::InternalError(
+        "DyVerifiableRandomFunction::GenerateChallengeForGenerateKeysProof: "
+        "Failed to serialize statement.");
+  }
+  challenge_cos->WriteVarint64(message_1.ByteSizeLong());
+  if (!message_1.SerializeToCodedStream(challenge_cos.get())) {
+    return absl::InternalError(
+        "DyVerifiableRandomFunction::GenerateChallengeForGenerateKeysProof: "
+        "Failed to serialize message_1.");
+  }
+
+  BigNum challenge_bound =
+      context_->One().Lshift(parameters_proto_.challenge_length_bits());
+
+  // Delete the serialization objects to make sure they clean up and write.
+  challenge_cos.reset();
+  challenge_sos.reset();
+
+  return context_->RandomOracleSha512(challenge_string, challenge_bound);
 }
 
 // Applies the DY VRF to a given batch of messages.
diff --git a/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.h b/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.h
index af0e100..ea7f761 100644
--- a/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.h
+++ b/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.h
@@ -61,9 +61,14 @@ class DyVerifiableRandomFunction {
   // Generates a new public/private keypair for the DY VRF together with a proof
   // that each entry of the commitment is the same key.
   StatusOr<std::tuple<proto::DyVrfPublicKey, proto::DyVrfPrivateKey,
-                      std::unique_ptr<GenerateKeysProof>>>
+                      proto::DyVrfGenerateKeysProof>>
   GenerateKeyPair();
 
+  // Verifies that the public key has a bounded key, and commits to the same key
+  // in each component of the Pedersen batch commitment.
+  Status VerifyGenerateKeysProof(const proto::DyVrfPublicKey& public_key,
+                                 const proto::DyVrfGenerateKeysProof& proof);
+
   // Applies the DY VRF to a given batch of messages.
   StatusOr<std::vector<ECPoint>> Apply(
       absl::Span<const BigNum> messages,
@@ -186,6 +191,12 @@ class DyVerifiableRandomFunction {
   ParseDyVrfApplyProofMessage2Proto(
       Context* ctx, const proto::DyVrfApplyProof::Message2& message_2_proto);
 
+  // Generates the challenge for the GenerateKeysProof using the Fiat-Shamir
+  // heuristic.
+  StatusOr<BigNum> GenerateChallengeForGenerateKeysProof(
+      const proto::DyVrfGenerateKeysProof::Statement& statement,
+      const proto::DyVrfGenerateKeysProof::Message1& message_1);
+
   proto::DyVrfParameters parameters_proto_;
   Context* context_;
   ECGroup* ec_group_;
diff --git a/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.proto b/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.proto
index 530b3db..14dfaf9 100644
--- a/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.proto
+++ b/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function.proto
@@ -40,6 +40,31 @@ message DyVrfParameters {
   PedersenParameters pedersen_parameters = 5;
 }
 
+// Proof that the parameters were generated correctly.
+message DyVrfGenerateKeysProof {
+  message Statement {
+    DyVrfParameters parameters = 1;
+    DyVrfPublicKey public_key = 2;
+  }
+  message Message1 {
+    // Dummy commitment to the key in each slot of the Pedersen Commitment.
+    bytes dummy_commit_prf_key = 1;
+  }
+
+  message Message2 {
+    // Masked dummy PRF key underlying the masked dummy commitment in each slot.
+    // Serialized BigNum.
+    bytes masked_dummy_prf_key = 1;
+    // Opening to the masked dummy commitment to the PRF key.
+    bytes masked_dummy_opening = 2;
+  }
+
+  // Message 1 and Statement are used to create the challenge via FiatShamir.
+  // Serialized BigNum
+  bytes challenge = 1;
+  Message2 message_2 = 2;
+}
+
 // A public key for the Dodis-Yampolskiy Verifiable Random Function. Implicitly
 // linked to parameters for a Pedersen batch-commitment scheme.
 message DyVrfPublicKey {
diff --git a/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function_test.cc b/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function_test.cc
index ae16efa..096c23b 100644
--- a/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function_test.cc
+++ b/private_join_and_compute/crypto/dodis_yampolskiy_prf/dy_verifiable_random_function_test.cc
@@ -163,6 +163,105 @@ TEST_F(DyVerifiableRandomFunctionTest, GenerateKeyPairProducesDifferentValues) {
             std::get<1>(key_pair_2).open_commit_prf_key());
 }
 
+TEST_F(DyVerifiableRandomFunctionTest, GenerateKeyProofSucceeds) {
+  proto::DyVrfPublicKey public_key_proto;
+  proto::DyVrfPrivateKey private_key_proto;
+  proto::DyVrfGenerateKeysProof generate_keys_proof_proto;
+  ASSERT_OK_AND_ASSIGN(
+      std::tie(public_key_proto, private_key_proto, generate_keys_proof_proto),
+      dy_vrf_->GenerateKeyPair());
+
+  EXPECT_OK(dy_vrf_->VerifyGenerateKeysProof(public_key_proto,
+                                             generate_keys_proof_proto));
+}
+
+TEST_F(DyVerifiableRandomFunctionTest, EmptyGenerateKeyProofFails) {
+  proto::DyVrfPublicKey public_key_proto;
+  proto::DyVrfPrivateKey private_key_proto;
+  proto::DyVrfGenerateKeysProof generate_keys_proof_proto;
+  ASSERT_OK_AND_ASSIGN(
+      std::tie(public_key_proto, private_key_proto, generate_keys_proof_proto),
+      dy_vrf_->GenerateKeyPair());
+
+  // Empty proof should fail.
+  EXPECT_THAT(
+      dy_vrf_->VerifyGenerateKeysProof(public_key_proto,
+                                       proto::DyVrfGenerateKeysProof()),
+      StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
+}
+
+TEST_F(DyVerifiableRandomFunctionTest, GenerateKeyProofFailsForDifferentKeys) {
+  proto::DyVrfPublicKey public_key_proto;
+  proto::DyVrfPrivateKey private_key_proto;
+  proto::DyVrfGenerateKeysProof generate_keys_proof_proto;
+  ASSERT_OK_AND_ASSIGN(
+      std::tie(public_key_proto, private_key_proto, generate_keys_proof_proto),
+      dy_vrf_->GenerateKeyPair());
+
+  // Using this proof with the keys generated by the test fixture should fail.
+  EXPECT_THAT(
+      dy_vrf_->VerifyGenerateKeysProof(public_key_, generate_keys_proof_proto),
+      StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
+}
+
+TEST_F(DyVerifiableRandomFunctionTest,
+       GenerateKeyProofFailsWhenPrfCommitmentIsMissing) {
+  proto::DyVrfPublicKey public_key_proto;
+  proto::DyVrfPrivateKey private_key_proto;
+  proto::DyVrfGenerateKeysProof generate_keys_proof_proto;
+  ASSERT_OK_AND_ASSIGN(
+      std::tie(public_key_proto, private_key_proto, generate_keys_proof_proto),
+      dy_vrf_->GenerateKeyPair());
+
+  public_key_proto.clear_commit_prf_key();
+  // Technically this proof fails because the verification method fails to
+  // compute a modular inverse.
+  EXPECT_THAT(
+      dy_vrf_->VerifyGenerateKeysProof(public_key_proto,
+                                       generate_keys_proof_proto),
+      StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Inverse")));
+}
+
+TEST_F(DyVerifiableRandomFunctionTest,
+       GenerateKeyProofFailsWhenMaskedDummyPrfKeyIsTooLarge) {
+  proto::DyVrfPublicKey public_key_proto;
+  proto::DyVrfPrivateKey private_key_proto;
+  proto::DyVrfGenerateKeysProof generate_keys_proof_proto;
+  ASSERT_OK_AND_ASSIGN(
+      std::tie(public_key_proto, private_key_proto, generate_keys_proof_proto),
+      dy_vrf_->GenerateKeyPair());
+
+  BigNum too_large =
+      ctx_.CreateBigNum(
+              generate_keys_proof_proto.message_2().masked_dummy_prf_key())
+          .Lshift(20);
+
+  generate_keys_proof_proto.mutable_message_2()->set_masked_dummy_prf_key(
+      too_large.ToBytes());
+
+  EXPECT_THAT(dy_vrf_->VerifyGenerateKeysProof(public_key_proto,
+                                               generate_keys_proof_proto),
+              StatusIs(absl::StatusCode::kInvalidArgument,
+                       HasSubstr("masked_dummy_prf_key")));
+}
+
+TEST_F(DyVerifiableRandomFunctionTest,
+       GenerateKeyProofFailsWhenMaskedDummyPrfKeyOpeningIsMissing) {
+  proto::DyVrfPublicKey public_key_proto;
+  proto::DyVrfPrivateKey private_key_proto;
+  proto::DyVrfGenerateKeysProof generate_keys_proof_proto;
+  ASSERT_OK_AND_ASSIGN(
+      std::tie(public_key_proto, private_key_proto, generate_keys_proof_proto),
+      dy_vrf_->GenerateKeyPair());
+
+  generate_keys_proof_proto.mutable_message_2()->clear_masked_dummy_prf_key();
+
+  EXPECT_THAT(
+      dy_vrf_->VerifyGenerateKeysProof(public_key_proto,
+                                       generate_keys_proof_proto),
+      StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("Failed")));
+}
+
 TEST_F(DyVerifiableRandomFunctionTest, ApplySucceeds) {
   std::vector<BigNum> messages = {ctx_.CreateBigNum(0),
                                   ctx_.CreateBigNum(5),