diff --git a/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client.cc b/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client.cc
index 2ccd9c5..77e2e9e 100644
--- a/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client.cc
+++ b/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client.cc
@@ -120,20 +120,20 @@
 
   AnonymousTokensSignRequest request;
   for (const PlaintextMessageWithPublicMetadata& input : inputs) {
-    if (input.plaintext_message().empty()) {
-      return absl::InvalidArgumentError(
-          "Cannot send an empty message to sign.");
-    }
-
     // Generate nonce and masked message. For more details, see
     // https://datatracker.ietf.org/doc/draft-irtf-cfrg-rsa-blind-signatures/
     ANON_TOKENS_ASSIGN_OR_RETURN(std::string mask, GenerateMask(public_key_));
     std::string masked_message =
         MaskMessageConcat(mask, input.plaintext_message());
 
+    std::optional<std::string> public_metadata = std::nullopt;
+    if (public_key_.public_metadata_support()) {
+      // Empty public metadata is a valid value.
+      public_metadata = input.public_metadata();
+    }
     // Generate RSA blinder.
     ANON_TOKENS_ASSIGN_OR_RETURN(auto rsa_bssa_blinder,
-                                 RsaBlinder::New(public_key_));
+                                 RsaBlinder::New(public_key_, public_metadata));
     ANON_TOKENS_ASSIGN_OR_RETURN(const std::string blinded_message,
                                  rsa_bssa_blinder->Blind(masked_message));
 
@@ -217,7 +217,7 @@
     if (blinding_info.input.public_metadata() !=
         anonymous_token.public_metadata()) {
       return absl::InvalidArgumentError(
-          "Response metadata does not match input.");
+          "Response public metadata does not match input.");
     }
 
     // Unblind the blinded anonymous token to obtain the final anonymous token
@@ -246,8 +246,9 @@
 }
 
 absl::Status AnonymousTokensRsaBssaClient::Verify(
-    const RSABlindSignatureToken& /*token*/, absl::string_view /*message*/,
-    absl::optional<absl::string_view> /*public_metadata*/) {
+    const RSABlindSignaturePublicKey& /*public_key*/,
+    const RSABlindSignatureToken& /*token*/,
+    const PlaintextMessageWithPublicMetadata& /*input*/) {
   return absl::UnimplementedError("Verify not implemented yet.");
 }
 
diff --git a/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client.h b/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client.h
index 0f2cd5c..e760182 100644
--- a/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client.h
+++ b/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client.h
@@ -77,12 +77,12 @@
   absl::StatusOr<std::vector<RSABlindSignatureTokenWithInput>> ProcessResponse(
       const AnonymousTokensSignResponse& response);
 
-  // Method to verify whether a blind token is valid or not.
+  // Method to verify whether an anonymous token is valid or not.
   //
   // Returns OK on a valid token and non-OK otherwise.
-  absl::Status Verify(
-      const RSABlindSignatureToken& token, absl::string_view message,
-      absl::optional<absl::string_view> public_metadata = absl::nullopt);
+  absl::Status Verify(const RSABlindSignaturePublicKey& public_key,
+                      const RSABlindSignatureToken& token,
+                      const PlaintextMessageWithPublicMetadata& input);
 
  private:
   struct BlindingInfo {
diff --git a/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client_test.cc b/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client_test.cc
index 84a297f..37d3a01 100644
--- a/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client_test.cc
+++ b/quiche/blind_sign_auth/anonymous_tokens/cpp/client/anonymous_tokens_rsa_bssa_client_test.cc
@@ -35,6 +35,7 @@
 namespace anonymous_tokens {
 namespace {
 
+using ::testing::SizeIs;
 using quiche::test::StatusIs;
 
 // Returns a fixed public private key pair by calling GetStrongRsaKeys4096().
@@ -159,9 +160,8 @@
 class AnonymousTokensRsaBssaClientTest : public testing::Test {
  protected:
   void SetUp() override {
-    ANON_TOKENS_ASSERT_OK_AND_ASSIGN(auto key_pair, CreateClientTestKey());
-    public_key_ = std::move(key_pair.first);
-    private_key_ = std::move(key_pair.second);
+    ANON_TOKENS_ASSERT_OK_AND_ASSIGN(std::tie(public_key_, private_key_),
+                                     CreateClientTestKey());
     ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
         client_, AnonymousTokensRsaBssaClient::Create(public_key_));
   }
@@ -179,8 +179,8 @@
                                    client_->CreateRequest(input_messages));
   ANON_TOKENS_ASSERT_OK_AND_ASSIGN(AnonymousTokensSignResponse response,
                                    CreateResponse(request, private_key_));
+  EXPECT_THAT(response.anonymous_tokens(), SizeIs(1));
   QUICHE_EXPECT_OK(client_->ProcessResponse(response));
-  EXPECT_EQ(response.anonymous_tokens_size(), 1);
 }
 
 TEST_F(AnonymousTokensRsaBssaClientTest, SuccessMultipleMessages) {
@@ -191,7 +191,7 @@
                                    client_->CreateRequest(input_messages));
   ANON_TOKENS_ASSERT_OK_AND_ASSIGN(AnonymousTokensSignResponse response,
                                    CreateResponse(request, private_key_));
-  EXPECT_EQ(response.anonymous_tokens_size(), 4);
+  EXPECT_THAT(response.anonymous_tokens(), SizeIs(4));
   QUICHE_EXPECT_OK(client_->ProcessResponse(response));
 }
 
@@ -327,6 +327,144 @@
               StatusIs(absl::StatusCode::kInvalidArgument));
 }
 
+class AnonymousTokensRsaBssaClientWithPublicMetadataTest
+    : public testing::Test {
+ protected:
+  void SetUp() override {
+    ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+        std::tie(public_key_, private_key_),
+        CreateClientTestKey("TEST_USE_CASE", /*key_version=*/1,
+                            AT_MESSAGE_MASK_CONCAT,
+                            kRsaMessageMaskSizeInBytes32,
+                            /*enable_public_metadata=*/true));
+    ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+        public_metadata_client_,
+        AnonymousTokensRsaBssaClient::Create(public_key_));
+  }
+
+  RSAPrivateKey private_key_;
+  RSABlindSignaturePublicKey public_key_;
+  std::unique_ptr<AnonymousTokensRsaBssaClient> public_metadata_client_;
+};
+
+TEST_F(AnonymousTokensRsaBssaClientWithPublicMetadataTest,
+       SuccessOneMessageWithPublicMetadata) {
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      std::vector<PlaintextMessageWithPublicMetadata> input_messages,
+      CreateInput({"message"}, {"md1"}));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignRequest request,
+      public_metadata_client_->CreateRequest(input_messages));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignResponse response,
+      CreateResponse(request, private_key_, /*enable_public_metadata=*/true));
+  EXPECT_THAT(response.anonymous_tokens(), SizeIs(1));
+  QUICHE_EXPECT_OK(public_metadata_client_->ProcessResponse(response));
+}
+
+TEST_F(AnonymousTokensRsaBssaClientWithPublicMetadataTest,
+       FailureWithEmptyPublicMetadata) {
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      std::vector<PlaintextMessageWithPublicMetadata> input_messages,
+      CreateInput({"message"}, {"md1"}));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignRequest request,
+      public_metadata_client_->CreateRequest(input_messages));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignResponse response,
+      CreateResponse(request, private_key_, /*enable_public_metadata=*/false));
+  EXPECT_THAT(public_metadata_client_->ProcessResponse(response),
+              StatusIs(absl::StatusCode::kInvalidArgument));
+}
+
+TEST_F(AnonymousTokensRsaBssaClientWithPublicMetadataTest,
+       FailureWithWrongPublicMetadata) {
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      std::vector<PlaintextMessageWithPublicMetadata> input_messages,
+      CreateInput({"message"}, {"md1"}));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignRequest request,
+      public_metadata_client_->CreateRequest(input_messages));
+  request.mutable_blinded_tokens(0)->set_public_metadata(
+      "wrong_public_metadata");
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignResponse response,
+      CreateResponse(request, private_key_, /*enable_public_metadata=*/true));
+  EXPECT_THAT(public_metadata_client_->ProcessResponse(response),
+              StatusIs(absl::StatusCode::kInvalidArgument));
+}
+
+TEST_F(AnonymousTokensRsaBssaClientWithPublicMetadataTest,
+       FailureWithPublicMetadataSupportOff) {
+  // Create a client with public metadata support disabled.
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(auto key_pair, CreateClientTestKey());
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      std::unique_ptr<AnonymousTokensRsaBssaClient> non_public_metadata_client,
+      AnonymousTokensRsaBssaClient::Create(key_pair.first));
+
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      std::vector<PlaintextMessageWithPublicMetadata> input_messages,
+      CreateInput({"message"}, {"md1"}));
+  // Use client_ that does not support public metadata.
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignRequest request,
+      non_public_metadata_client->CreateRequest(input_messages));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignResponse response,
+      CreateResponse(request, private_key_, /*enable_public_metadata=*/true));
+  EXPECT_THAT(non_public_metadata_client->ProcessResponse(response),
+              StatusIs(absl::StatusCode::kInvalidArgument));
+}
+
+TEST_F(AnonymousTokensRsaBssaClientWithPublicMetadataTest,
+       SuccessMultipleMessagesWithDistinctPublicMetadata) {
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      std::vector<PlaintextMessageWithPublicMetadata> input_messages,
+      CreateInput({"message1", "msg2", "anotherMessage", "one_more_message"},
+                  {"md1", "md2", "md3", "md4"}));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignRequest request,
+      public_metadata_client_->CreateRequest(input_messages));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignResponse response,
+      CreateResponse(request, private_key_, /*enable_public_metadata=*/true));
+  EXPECT_THAT(response.anonymous_tokens(), SizeIs(4));
+  QUICHE_EXPECT_OK(public_metadata_client_->ProcessResponse(response));
+}
+
+TEST_F(AnonymousTokensRsaBssaClientWithPublicMetadataTest,
+       SuccessMultipleMessagesWithRepeatedPublicMetadata) {
+  // Create input with repeated public metadata
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      std::vector<PlaintextMessageWithPublicMetadata> input_messages,
+      CreateInput({"message1", "msg2", "anotherMessage", "one_more_message"},
+                  {"md1", "md2", "md2", "md1"}));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignRequest request,
+      public_metadata_client_->CreateRequest(input_messages));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignResponse response,
+      CreateResponse(request, private_key_, /*enable_public_metadata=*/true));
+  EXPECT_THAT(response.anonymous_tokens(), SizeIs(4));
+  QUICHE_EXPECT_OK(public_metadata_client_->ProcessResponse(response));
+}
+
+TEST_F(AnonymousTokensRsaBssaClientWithPublicMetadataTest,
+       SuccessMultipleMessagesWithEmptyStringPublicMetadata) {
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      std::vector<PlaintextMessageWithPublicMetadata> input_messages,
+      CreateInput({"message1", "msg2", "anotherMessage", "one_more_message"},
+                  {"md1", "", "", "md4"}));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignRequest request,
+      public_metadata_client_->CreateRequest(input_messages));
+  ANON_TOKENS_ASSERT_OK_AND_ASSIGN(
+      AnonymousTokensSignResponse response,
+      CreateResponse(request, private_key_, /*enable_public_metadata=*/true));
+  EXPECT_THAT(response.anonymous_tokens(), SizeIs(4));
+  QUICHE_EXPECT_OK(public_metadata_client_->ProcessResponse(response));
+}
+
 }  // namespace
 }  // namespace anonymous_tokens
 }  // namespace private_membership