Add sign/verify subtle wrappers and utility functions for Falcon signature schemes.

PiperOrigin-RevId: 397266875

10 files changed, 1046 insertions, 2 deletions

diff --git a/cc/experimental/pqcrypto/signature/subtle/dilithium_key.h b/cc/experimental/pqcrypto/signature/subtle/dilithium_key.h
index cab6f0ef9..ee06afd20 100644
--- a/cc/experimental/pqcrypto/signature/subtle/dilithium_key.h
+++ b/cc/experimental/pqcrypto/signature/subtle/dilithium_key.h
@@ -35,7 +35,6 @@ enum class DilithiumSeedExpansion {
   SEED_EXPANSION_AES = 2,
 };
 
-
 // Dilithium public key representation.
 class DilithiumPublicKeyPqclean {
  public:
@@ -54,7 +53,7 @@ class DilithiumPublicKeyPqclean {
  private:
   DilithiumPublicKeyPqclean(absl::string_view key_data,
                             DilithiumSeedExpansion seed_expansion)
-      : key_data_(std::move(key_data)), seed_expansion_(seed_expansion) {}
+      : key_data_(key_data), seed_expansion_(seed_expansion) {}
 
   const std::string key_data_;
   const DilithiumSeedExpansion seed_expansion_;
diff --git a/cc/experimental/pqcrypto/signature/subtle/falcon_sign.cc b/cc/experimental/pqcrypto/signature/subtle/falcon_sign.cc
new file mode 100644
index 000000000..d873946e2
--- /dev/null
+++ b/cc/experimental/pqcrypto/signature/subtle/falcon_sign.cc
@@ -0,0 +1,89 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_sign.h"
+
+#include <string>
+#include <utility>
+
+#include "absl/memory/memory.h"
+#include "absl/strings/str_format.h"
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h"
+#include "tink/util/secret_data.h"
+#include "tink/util/statusor.h"
+
+extern "C" {
+#include "third_party/pqclean/crypto_sign/falcon-1024/avx2/api.h"
+#include "third_party/pqclean/crypto_sign/falcon-512/avx2/api.h"
+}
+
+namespace crypto {
+namespace tink {
+namespace subtle {
+
+// static
+util::StatusOr<std::unique_ptr<PublicKeySign>> FalconSign::New(
+    const FalconPrivateKeyPqclean& key) {
+  auto status = internal::CheckFipsCompatibility<FalconSign>();
+  if (!status.ok()) return status;
+
+  return {absl::WrapUnique(new FalconSign(key))};
+}
+
+util::StatusOr<std::string> FalconSign::Sign(absl::string_view data) const {
+  size_t sig_length;
+  int32_t key_size = private_key_.GetKey().size();
+  std::string signature;
+  int result = 1;
+
+  switch (key_size) {
+    case kFalcon512PrivateKeySize: {
+      signature.resize(PQCLEAN_FALCON512_AVX2_CRYPTO_BYTES, '0');
+      result = PQCLEAN_FALCON512_AVX2_crypto_sign_signature(
+          reinterpret_cast<uint8_t *>(signature.data()), &sig_length,
+          reinterpret_cast<const uint8_t *>(data.data()), data.size(),
+          reinterpret_cast<const uint8_t *>(private_key_.GetKey().data()));
+      if (sig_length > PQCLEAN_FALCON512_AVX2_CRYPTO_BYTES) {
+        result = -1;
+      }
+      break;
+    }
+    case kFalcon1024PrivateKeySize: {
+      signature.resize(PQCLEAN_FALCON1024_AVX2_CRYPTO_BYTES, '0');
+      result = PQCLEAN_FALCON1024_AVX2_crypto_sign_signature(
+          reinterpret_cast<uint8_t *>(signature.data()), &sig_length,
+          reinterpret_cast<const uint8_t *>(data.data()), data.size(),
+          reinterpret_cast<const uint8_t *>(private_key_.GetKey().data()));
+      if (sig_length > PQCLEAN_FALCON1024_AVX2_CRYPTO_BYTES) {
+        result = -1;
+      }
+      break;
+    }
+    default:
+      return util::Status(util::error::INVALID_ARGUMENT, "Invalid keysize.");
+  }
+
+  if (result != 0) {
+    return util::Status(util::error::INTERNAL, "Signing failed.");
+  }
+
+  signature.resize(sig_length);
+  return signature;
+}
+
+}  // namespace subtle
+}  // namespace tink
+}  // namespace crypto
diff --git a/cc/experimental/pqcrypto/signature/subtle/falcon_sign.h b/cc/experimental/pqcrypto/signature/subtle/falcon_sign.h
new file mode 100644
index 000000000..d2e970264
--- /dev/null
+++ b/cc/experimental/pqcrypto/signature/subtle/falcon_sign.h
@@ -0,0 +1,61 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef TINK_EXPERIMENTAL_PQCRYPTO_SIGNATURE_SUBTLE_FALCON_SIGN_H_
+#define TINK_EXPERIMENTAL_PQCRYPTO_SIGNATURE_SUBTLE_FALCON_SIGN_H_
+
+#include <memory>
+#include <string>
+#include <utility>
+
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h"
+#include "tink/internal/fips_utils.h"
+#include "tink/public_key_sign.h"
+#include "tink/util/secret_data.h"
+#include "tink/util/statusor.h"
+
+namespace crypto {
+namespace tink {
+namespace subtle {
+
+// Post-Quantum Signing using Falcon - Fast-Fourier Lattice-based
+// Compact Signature over NTRU
+class FalconSign : public PublicKeySign {
+ public:
+  static constexpr crypto::tink::internal::FipsCompatibility kFipsStatus =
+      crypto::tink::internal::FipsCompatibility::kNotFips;
+
+  static crypto::tink::util::StatusOr<std::unique_ptr<PublicKeySign>> New(
+      const FalconPrivateKeyPqclean& private_key);
+
+  ~FalconSign() override = default;
+
+  // Computes the signature for 'data'.
+  crypto::tink::util::StatusOr<std::string> Sign(
+      absl::string_view data) const override;
+
+ private:
+  explicit FalconSign(const FalconPrivateKeyPqclean& private_key)
+      : private_key_(private_key) {}
+
+  const FalconPrivateKeyPqclean private_key_;
+};
+
+}  // namespace subtle
+}  // namespace tink
+}  // namespace crypto
+
+#endif  // TINK_EXPERIMENTAL_PQCRYPTO_SIGNATURE_SUBTLE_FALCON_SIGN_H_
diff --git a/cc/experimental/pqcrypto/signature/subtle/falcon_sign_test.cc b/cc/experimental/pqcrypto/signature/subtle/falcon_sign_test.cc
new file mode 100644
index 000000000..d120a745a
--- /dev/null
+++ b/cc/experimental/pqcrypto/signature/subtle/falcon_sign_test.cc
@@ -0,0 +1,143 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_sign.h"
+
+#include <string>
+#include <utility>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/strings/str_cat.h"
+#include "tink/config/tink_fips.h"
+#include "tink/util/status.h"
+#include "tink/util/statusor.h"
+#include "tink/util/test_matchers.h"
+
+extern "C" {
+#include "third_party/pqclean/crypto_sign/falcon-1024/avx2/api.h"
+#include "third_party/pqclean/crypto_sign/falcon-512/avx2/api.h"
+}
+
+namespace crypto {
+namespace tink {
+namespace subtle {
+namespace {
+
+using ::crypto::tink::test::IsOk;
+
+struct FalconTestCase {
+  std::string test_name;
+  int32_t private_key_size;
+  int32_t signature_length;
+};
+
+using FalconSignTest = testing::TestWithParam<FalconTestCase>;
+
+TEST_P(FalconSignTest, ValidSignatureLength) {
+  if (IsFipsModeEnabled()) {
+    GTEST_SKIP() << "Test assumes kOnlyUseFips is false.";
+  }
+
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Create a new signer.
+  util::StatusOr<std::unique_ptr<PublicKeySign>> signer =
+      FalconSign::New(key_pair->GetPrivateKey());
+  ASSERT_THAT(signer.status(), IsOk());
+
+  // Sign a message.
+  std::string message = "message to be signed";
+  util::StatusOr<std::string> signature = ((*signer)->Sign(message));
+  ASSERT_THAT(signature.status(), IsOk());
+
+  // Check signature size.
+  EXPECT_NE(*signature, message);
+  EXPECT_LE((*signature).size(), test_case.signature_length);
+}
+
+TEST_P(FalconSignTest, NonDeterminism) {
+  if (IsFipsModeEnabled()) {
+    GTEST_SKIP() << "Test assumes kOnlyUseFips is false.";
+  }
+
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Create two signers based on same private key.
+  util::StatusOr<std::unique_ptr<PublicKeySign>> signer =
+      FalconSign::New(key_pair->GetPrivateKey());
+  ASSERT_THAT(signer.status(), IsOk());
+
+  // Sign the same message twice, using the same private key.
+  std::string message = "message to be signed";
+  util::StatusOr<std::string> first_signature = ((*signer))->Sign(message);
+  ASSERT_THAT(first_signature.status(), IsOk());
+
+  util::StatusOr<std::string> second_signature = ((*signer))->Sign(message);
+  ASSERT_THAT(second_signature.status(), IsOk());
+
+  // Check signatures size.
+  EXPECT_NE(*first_signature, message);
+  EXPECT_LE((*first_signature).size(), test_case.signature_length);
+
+  EXPECT_NE(*second_signature, message);
+  EXPECT_LE((*second_signature).size(), test_case.signature_length);
+
+  // Check if signatures are equal.
+  EXPECT_NE(*first_signature, *second_signature);
+}
+
+TEST_P(FalconSignTest, FipsMode) {
+  if (!IsFipsModeEnabled()) {
+    GTEST_SKIP() << "Test assumes kOnlyUseFips.";
+  }
+
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Create a new signer.
+  EXPECT_THAT(FalconSign::New(key_pair->GetPrivateKey()).status(),
+              test::StatusIs(util::error::INTERNAL));
+}
+
+INSTANTIATE_TEST_SUITE_P(
+    FalconSignTests, FalconSignTest,
+    testing::ValuesIn<FalconTestCase>({{"Falcon512", kFalcon512PrivateKeySize,
+                                        PQCLEAN_FALCON512_AVX2_CRYPTO_BYTES},
+                                       {"Falcon1024", kFalcon1024PrivateKeySize,
+                                        PQCLEAN_FALCON1024_AVX2_CRYPTO_BYTES}}),
+    [](const testing::TestParamInfo<FalconSignTest::ParamType>& info) {
+      return info.param.test_name;
+    });
+
+}  // namespace
+}  // namespace subtle
+}  // namespace tink
+}  // namespace crypto
diff --git a/cc/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.cc b/cc/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.cc
new file mode 100644
index 000000000..24555ef11
--- /dev/null
+++ b/cc/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.cc
@@ -0,0 +1,142 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h"
+
+#include <string>
+#include <utility>
+
+#include "absl/memory/memory.h"
+#include "absl/strings/str_format.h"
+#include "tink/experimental/pqcrypto/signature/subtle/sphincs_helper_pqclean.h"
+#include "tink/util/secret_data.h"
+#include "tink/util/status.h"
+#include "tink/util/statusor.h"
+
+extern "C" {
+#include "third_party/pqclean/crypto_sign/falcon-1024/avx2/api.h"
+#include "third_party/pqclean/crypto_sign/falcon-512/avx2/api.h"
+}
+
+namespace crypto {
+namespace tink {
+namespace subtle {
+
+// static
+util::StatusOr<FalconPrivateKeyPqclean> FalconPrivateKeyPqclean::NewPrivateKey(
+    const util::SecretData& key_data) {
+  util::Status status = ValidateFalconPrivateKeySize(key_data.size());
+  if (!status.ok()) {
+    return status;
+  }
+
+  return FalconPrivateKeyPqclean(key_data);
+}
+
+// static
+util::StatusOr<FalconPublicKeyPqclean> FalconPublicKeyPqclean::NewPublicKey(
+    absl::string_view key_data) {
+  util::Status status = ValidateFalconPublicKeySize(key_data.size());
+  if (!status.ok()) {
+    return status;
+  }
+
+  return FalconPublicKeyPqclean(key_data);
+}
+
+crypto::tink::util::StatusOr<FalconKeyPair> GenerateFalconKeyPair(
+    int32_t private_key_size) {
+  std::string public_key;
+  std::string private_key;
+
+  switch (private_key_size) {
+    // Falcon512.
+    case kFalcon512PrivateKeySize: {
+      private_key.resize(private_key_size);
+      public_key.resize(kFalcon512PublicKeySize);
+      PQCLEAN_FALCON512_AVX2_crypto_sign_keypair(
+          reinterpret_cast<uint8_t*>(public_key.data()),
+          reinterpret_cast<uint8_t*>(private_key.data()));
+      break;
+    }
+    // Falcon1024.
+    case kFalcon1024PrivateKeySize: {
+      private_key.resize(private_key_size);
+      public_key.resize(kFalcon1024PublicKeySize);
+      PQCLEAN_FALCON1024_AVX2_crypto_sign_keypair(
+          reinterpret_cast<uint8_t*>(public_key.data()),
+          reinterpret_cast<uint8_t*>(private_key.data()));
+      break;
+    }
+    // Invalid key size.
+    default: {
+      return util::Status(
+          util::error::INVALID_ARGUMENT,
+          absl::StrFormat("Invalid private key size (%d). "
+                          "The only valid sizes are %d, %d",
+                          private_key_size, kFalcon512PrivateKeySize,
+                          kFalcon1024PrivateKeySize));
+    }
+  }
+
+  util::SecretData private_key_data =
+      util::SecretDataFromStringView(private_key);
+
+  util::StatusOr<FalconPrivateKeyPqclean> falcon_private_key =
+      FalconPrivateKeyPqclean::NewPrivateKey(private_key_data);
+  util::StatusOr<FalconPublicKeyPqclean> falcon_public_key =
+      FalconPublicKeyPqclean::NewPublicKey(public_key);
+
+  if (!falcon_private_key.ok() || !falcon_public_key.ok()) {
+    return util::Status(util::error::INTERNAL, "Key generation failed.");
+  }
+
+  FalconKeyPair key_pair(*falcon_private_key, *falcon_public_key);
+
+  return key_pair;
+}
+
+crypto::tink::util::Status ValidateFalconPrivateKeySize(int32_t key_size) {
+  switch (key_size) {
+    case kFalcon512PrivateKeySize:
+    case kFalcon1024PrivateKeySize:
+      return util::Status::OK;
+    default:
+      return util::Status(util::error::INVALID_ARGUMENT,
+                          absl::StrFormat("Invalid private key size (%d). "
+                                          "The only valid sizes are %d, %d",
+                                          key_size, kFalcon512PrivateKeySize,
+                                          kFalcon1024PrivateKeySize));
+  }
+}
+
+crypto::tink::util::Status ValidateFalconPublicKeySize(int32_t key_size) {
+  switch (key_size) {
+    case kFalcon512PublicKeySize:
+    case kFalcon1024PublicKeySize:
+      return util::Status::OK;
+    default:
+      return util::Status(util::error::INVALID_ARGUMENT,
+                          absl::StrFormat("Invalid public key size (%d). "
+                                          "The only valid sizes are %d, %d",
+                                          key_size, kFalcon512PublicKeySize,
+                                          kFalcon1024PublicKeySize));
+  }
+}
+
+}  // namespace subtle
+}  // namespace tink
+}  // namespace crypto
diff --git a/cc/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h b/cc/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h
new file mode 100644
index 000000000..302803aea
--- /dev/null
+++ b/cc/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h
@@ -0,0 +1,117 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef TINK_EXPERIMENTAL_PQCRYPTO_SIGNATURE_SUBTLE_FALCON_SUBTLE_UTILS_H_
+#define TINK_EXPERIMENTAL_PQCRYPTO_SIGNATURE_SUBTLE_FALCON_SUBTLE_UTILS_H_
+
+#include <string>
+#include <utility>
+
+#include "absl/memory/memory.h"
+#include "absl/strings/str_format.h"
+#include "absl/strings/string_view.h"
+#include "tink/util/secret_data.h"
+#include "tink/util/statusor.h"
+
+namespace crypto {
+namespace tink {
+namespace subtle {
+
+// The two possible falcon private key sizes, as defined at
+// https://falcon-sign.info/.
+
+const int kFalcon512PrivateKeySize = 1281;
+const int kFalcon1024PrivateKeySize = 2305;
+
+// The two possible falcon public key sizes as defined at
+// https://falcon-sign.info/.
+const int kFalcon512PublicKeySize = 897;
+const int kFalcon1024PublicKeySize = 1793;
+
+// Representation of the Falcon private key.
+class FalconPrivateKeyPqclean {
+ public:
+  // Creates a new FalconPrivateKeyPqclean from key_data.
+  static util::StatusOr<FalconPrivateKeyPqclean> NewPrivateKey(
+      const util::SecretData& key_data);
+
+  FalconPrivateKeyPqclean(const FalconPrivateKeyPqclean& other) = default;
+  FalconPrivateKeyPqclean& operator=(const FalconPrivateKeyPqclean& other) =
+      default;
+
+  const util::SecretData& GetKey() const { return key_data_; }
+
+ private:
+  explicit FalconPrivateKeyPqclean(const util::SecretData& key_data)
+      : key_data_(key_data) {}
+
+  const util::SecretData key_data_;
+};
+
+// Representation of the Falcon public key.
+class FalconPublicKeyPqclean {
+ public:
+  // Creates a new FalconPublicKeyPqclean from key_data.
+  static util::StatusOr<FalconPublicKeyPqclean> NewPublicKey(
+      absl::string_view key_data);
+
+  FalconPublicKeyPqclean(const FalconPublicKeyPqclean& other) = default;
+  FalconPublicKeyPqclean& operator=(const FalconPublicKeyPqclean& other) =
+      default;
+
+  const std::string& GetKey() const { return key_data_; }
+
+ private:
+  explicit FalconPublicKeyPqclean(absl::string_view key_data)
+      : key_data_(std::move(key_data)) {}
+
+  const std::string key_data_;
+};
+
+class FalconKeyPair {
+ public:
+  FalconKeyPair(FalconPrivateKeyPqclean private_key,
+                FalconPublicKeyPqclean public_key)
+      : private_key_(std::move(private_key)),
+        public_key_(std::move(public_key)) {}
+
+  FalconKeyPair(const FalconKeyPair& other) = default;
+  FalconKeyPair& operator=(const FalconKeyPair& other) = default;
+
+  const FalconPrivateKeyPqclean& GetPrivateKey() const { return private_key_; }
+  const FalconPublicKeyPqclean& GetPublicKey() const { return public_key_; }
+
+ private:
+  const FalconPrivateKeyPqclean private_key_;
+  const FalconPublicKeyPqclean public_key_;
+};
+
+// This is an utility function that generates a new Falcon key pair.
+// This function is expected to be called from a key manager class.
+crypto::tink::util::StatusOr<FalconKeyPair> GenerateFalconKeyPair(
+    int32 private_key_size);
+
+// Validates whether the private key size is safe to use for falcon signature.
+crypto::tink::util::Status ValidateFalconPrivateKeySize(int32_t key_size);
+
+// Validates whether the public key size is safe to use for falcon signature.
+crypto::tink::util::Status ValidateFalconPublicKeySize(int32_t key_size);
+
+}  // namespace subtle
+}  // namespace tink
+}  // namespace crypto
+
+#endif  // TINK_EXPERIMENTAL_PQCRYPTO_SIGNATURE_SUBTLE_FALCON_SUBTLE_UTILS_H_
diff --git a/cc/experimental/pqcrypto/signature/subtle/falcon_subtle_utils_test.cc b/cc/experimental/pqcrypto/signature/subtle/falcon_subtle_utils_test.cc
new file mode 100644
index 000000000..4ac7782d8
--- /dev/null
+++ b/cc/experimental/pqcrypto/signature/subtle/falcon_subtle_utils_test.cc
@@ -0,0 +1,137 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h"
+
+#include <climits>
+#include <string>
+#include <utility>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/strings/str_cat.h"
+#include "tink/util/status.h"
+#include "tink/util/statusor.h"
+#include "tink/util/test_matchers.h"
+
+namespace crypto {
+namespace tink {
+namespace subtle {
+namespace {
+
+using ::crypto::tink::test::IsOk;
+using ::testing::Not;
+
+struct FalconTestCase {
+  std::string test_name;
+  int32_t private_key_size;
+  int32_t public_key_size;
+};
+
+using FalconUtilsTest = testing::TestWithParam<FalconTestCase>;
+
+TEST_P(FalconUtilsTest, FalconKeyGeneration) {
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Check keys size.
+  EXPECT_EQ(key_pair->GetPrivateKey().GetKey().size(),
+            test_case.private_key_size);
+  EXPECT_EQ(key_pair->GetPublicKey().GetKey().size(),
+            test_case.public_key_size);
+}
+
+TEST_P(FalconUtilsTest, DifferentContent) {
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Check keys content is different.
+  EXPECT_NE(util::SecretDataAsStringView(key_pair->GetPrivateKey().GetKey()),
+            key_pair->GetPublicKey().GetKey());
+}
+
+TEST(FalconUtilsTest, ValidPrivateKeySize) {
+  EXPECT_THAT(ValidateFalconPrivateKeySize(kFalcon1024PrivateKeySize), IsOk());
+  EXPECT_THAT(ValidateFalconPrivateKeySize(kFalcon512PrivateKeySize), IsOk());
+}
+
+TEST(FalconUtilsTest, InvalidPrivateKeySize) {
+  std::vector<int32_t> invalid_keysizes{0,
+                                        -1,
+                                        kFalcon1024PrivateKeySize - 1,
+                                        kFalcon1024PrivateKeySize + 1,
+                                        INT_MAX,
+                                        INT_MIN};
+  for (int i = 0; i < invalid_keysizes.size(); i++) {
+    EXPECT_FALSE(ValidateFalconPrivateKeySize(invalid_keysizes[i]).ok());
+  }
+}
+
+TEST(FalconUtilsTest, ValidPublicKeySize) {
+  EXPECT_THAT(ValidateFalconPublicKeySize(kFalcon1024PublicKeySize), IsOk());
+  EXPECT_THAT(ValidateFalconPublicKeySize(kFalcon512PublicKeySize), IsOk());
+}
+
+TEST(FalconUtilsTest, InvalidPublicKeySize) {
+  std::vector<int32_t> invalid_keysizes{0,
+                                        -1,
+                                        kFalcon1024PublicKeySize - 1,
+                                        kFalcon1024PublicKeySize + 1,
+                                        INT_MAX,
+                                        INT_MIN};
+  for (int i = 0; i < invalid_keysizes.size(); i++) {
+    EXPECT_FALSE(ValidateFalconPublicKeySize(invalid_keysizes[i]).ok());
+  }
+}
+
+TEST(FalconUtilsTest, InvalidPrivateKey) {
+  std::string bad_private_key_data = "bad private key";
+  util::StatusOr<FalconPrivateKeyPqclean> private_key =
+      FalconPrivateKeyPqclean::NewPrivateKey(
+          util::SecretDataFromStringView(bad_private_key_data));
+
+  EXPECT_THAT(private_key.status(), testing::Not(IsOk()));
+}
+
+TEST(FalconUtilsTest, InvalidPubliceKey) {
+  std::string bad_public_key_data = "bad public key";
+  util::StatusOr<FalconPublicKeyPqclean> public_key =
+      FalconPublicKeyPqclean::NewPublicKey(bad_public_key_data);
+
+  EXPECT_THAT(public_key.status(), Not(IsOk()));
+}
+
+INSTANTIATE_TEST_SUITE_P(
+    FalconUtilsTests, FalconUtilsTest,
+    testing::ValuesIn<FalconTestCase>(
+        {{"Falcon512", kFalcon512PrivateKeySize, kFalcon512PublicKeySize},
+         {"Falcon1024", kFalcon1024PrivateKeySize, kFalcon1024PublicKeySize}}),
+    [](const testing::TestParamInfo<FalconUtilsTest::ParamType>& info) {
+      return info.param.test_name;
+    });
+
+}  // namespace
+}  // namespace subtle
+}  // namespace tink
+}  // namespace crypto
diff --git a/cc/experimental/pqcrypto/signature/subtle/falcon_verify.cc b/cc/experimental/pqcrypto/signature/subtle/falcon_verify.cc
new file mode 100644
index 000000000..f50aeb6bc
--- /dev/null
+++ b/cc/experimental/pqcrypto/signature/subtle/falcon_verify.cc
@@ -0,0 +1,80 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_verify.h"
+
+#include <string>
+#include <utility>
+
+#include "absl/memory/memory.h"
+#include "absl/strings/str_format.h"
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h"
+#include "tink/util/secret_data.h"
+#include "tink/util/statusor.h"
+
+extern "C" {
+#include "third_party/pqclean/crypto_sign/falcon-1024/avx2/api.h"
+#include "third_party/pqclean/crypto_sign/falcon-512/avx2/api.h"
+}
+
+namespace crypto {
+namespace tink {
+namespace subtle {
+
+// static
+util::StatusOr<std::unique_ptr<PublicKeyVerify>> FalconVerify::New(
+    const FalconPublicKeyPqclean& public_key) {
+  auto status = internal::CheckFipsCompatibility<FalconVerify>();
+  if (!status.ok()) return status;
+
+  return {
+      absl::WrapUnique<FalconVerify>(new FalconVerify(public_key))};
+}
+
+util::Status FalconVerify::Verify(absl::string_view signature,
+                                  absl::string_view data) const {
+  int32_t key_size = public_key_.GetKey().size();
+  int result = 1;
+
+  switch (key_size) {
+    case kFalcon512PublicKeySize: {
+      result = PQCLEAN_FALCON512_AVX2_crypto_sign_verify(
+          reinterpret_cast<const uint8_t *>(signature.data()), signature.size(),
+          reinterpret_cast<const uint8_t *>(data.data()), data.size(),
+          reinterpret_cast<const uint8_t *>(public_key_.GetKey().data()));
+      break;
+    }
+    case kFalcon1024PublicKeySize: {
+      result = PQCLEAN_FALCON1024_AVX2_crypto_sign_verify(
+          reinterpret_cast<const uint8_t *>(signature.data()), signature.size(),
+          reinterpret_cast<const uint8_t *>(data.data()), data.size(),
+          reinterpret_cast<const uint8_t *>(public_key_.GetKey().data()));
+      break;
+    }
+    default:
+      return util::Status(util::error::INVALID_ARGUMENT, "Invalid keysize.");
+  }
+
+  if (result != 0) {
+    return util::Status(util::error::INTERNAL, "Signature is not valid.");
+  }
+
+  return util::Status::OK;
+}
+
+}  // namespace subtle
+}  // namespace tink
+}  // namespace crypto
diff --git a/cc/experimental/pqcrypto/signature/subtle/falcon_verify.h b/cc/experimental/pqcrypto/signature/subtle/falcon_verify.h
new file mode 100644
index 000000000..9131901ce
--- /dev/null
+++ b/cc/experimental/pqcrypto/signature/subtle/falcon_verify.h
@@ -0,0 +1,57 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef TINK_EXPERIMENTAL_PQCRYPTO_SIGNATURE_SUBTLE_FALCON_VERIFY_H_
+#define TINK_EXPERIMENTAL_PQCRYPTO_SIGNATURE_SUBTLE_FALCON_VERIFY_H_
+
+#include <memory>
+#include <string>
+#include <utility>
+
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h"
+#include "tink/internal/fips_utils.h"
+#include "tink/public_key_verify.h"
+#include "tink/util/secret_data.h"
+#include "tink/util/statusor.h"
+
+namespace crypto {
+namespace tink {
+namespace subtle {
+
+class FalconVerify : public PublicKeyVerify {
+ public:
+  static constexpr crypto::tink::internal::FipsCompatibility kFipsStatus =
+      crypto::tink::internal::FipsCompatibility::kNotFips;
+
+  static crypto::tink::util::StatusOr<std::unique_ptr<PublicKeyVerify>> New(
+      const FalconPublicKeyPqclean& public_key);
+
+  // Verifies that 'signature' is a digital signature for 'data'.
+  crypto::tink::util::Status Verify(absl::string_view signature,
+                                    absl::string_view data) const override;
+
+ private:
+  explicit FalconVerify(const FalconPublicKeyPqclean& public_key)
+      : public_key_(public_key) {}
+
+  const FalconPublicKeyPqclean public_key_;
+};
+
+}  // namespace subtle
+}  // namespace tink
+}  // namespace crypto
+
+#endif  // TINK_EXPERIMENTAL_PQCRYPTO_SIGNATURE_SUBTLE_FALCON_VERIFY_H_
diff --git a/cc/experimental/pqcrypto/signature/subtle/falcon_verify_test.cc b/cc/experimental/pqcrypto/signature/subtle/falcon_verify_test.cc
new file mode 100644
index 000000000..ddf1d5794
--- /dev/null
+++ b/cc/experimental/pqcrypto/signature/subtle/falcon_verify_test.cc
@@ -0,0 +1,219 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_verify.h"
+
+#include <string>
+#include <utility>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/strings/escaping.h"
+#include "absl/strings/str_cat.h"
+#include "tink/config/tink_fips.h"
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_sign.h"
+#include "tink/experimental/pqcrypto/signature/subtle/falcon_subtle_utils.h"
+#include "tink/public_key_sign.h"
+#include "tink/public_key_verify.h"
+#include "tink/util/status.h"
+#include "tink/util/statusor.h"
+#include "tink/util/test_matchers.h"
+
+extern "C" {
+#include "third_party/pqclean/crypto_sign/falcon-1024/avx2/api.h"
+#include "third_party/pqclean/crypto_sign/falcon-512/avx2/api.h"
+}
+
+namespace crypto {
+namespace tink {
+namespace subtle {
+namespace {
+
+using ::crypto::tink::test::IsOk;
+using ::crypto::tink::test::StatusIs;
+using crypto::tink::util::Status;
+
+struct FalconTestCase {
+  std::string test_name;
+  int32_t private_key_size;
+  int32_t signature_length;
+};
+
+using FalconVerifyTest = testing::TestWithParam<FalconTestCase>;
+
+TEST_P(FalconVerifyTest, BasicSignVerify) {
+  if (IsFipsModeEnabled()) {
+    GTEST_SKIP() << "Test assumes kOnlyUseFips is false.";
+  }
+
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Create a new signer.
+  util::StatusOr<std::unique_ptr<PublicKeySign>> signer =
+      FalconSign::New(key_pair->GetPrivateKey());
+  ASSERT_THAT(signer.status(), IsOk());
+
+  // Sign a message.
+  std::string message = "message to be signed";
+  util::StatusOr<std::string> signature = (*signer)->Sign(message);
+  ASSERT_THAT(signature.status(), IsOk());
+
+  // Create a new verifier.
+  absl::StatusOr<std::unique_ptr<PublicKeyVerify>> verifier =
+      FalconVerify::New(key_pair->GetPublicKey());
+  ASSERT_THAT(verifier.status(), IsOk());
+
+  // Verify signature.
+  Status status = (*verifier)->Verify(*signature, message);
+  EXPECT_THAT(status, IsOk());
+}
+
+TEST_P(FalconVerifyTest, FailsWithWrongSignature) {
+  if (IsFipsModeEnabled()) {
+    GTEST_SKIP() << "Test assumes kOnlyUseFips is false.";
+  }
+
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Create a new signer.
+  util::StatusOr<std::unique_ptr<PublicKeySign>> signer =
+      FalconSign::New(key_pair->GetPrivateKey());
+  ASSERT_THAT(signer.status(), IsOk());
+
+  // Sign a message.
+  std::string message = "message to be signed";
+  util::StatusOr<std::string> signature = (*signer)->Sign(message);
+  ASSERT_THAT(signature.status(), IsOk());
+
+  // Create a new verifier.
+  absl::StatusOr<std::unique_ptr<PublicKeyVerify>> verifier =
+      FalconVerify::New(key_pair->GetPublicKey());
+  ASSERT_THAT(verifier.status(), IsOk());
+
+  // Verify signature.
+  Status status =
+      (*verifier)->Verify(*signature + "some trailing data", message);
+  EXPECT_FALSE(status.ok());
+}
+
+TEST_P(FalconVerifyTest, FailsWithWrongMessage) {
+  if (IsFipsModeEnabled()) {
+    GTEST_SKIP() << "Test assumes kOnlyUseFips is false.";
+  }
+
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Create a new signer.
+  util::StatusOr<std::unique_ptr<PublicKeySign>> signer =
+      FalconSign::New(key_pair->GetPrivateKey());
+  ASSERT_THAT(signer.status(), IsOk());
+
+  // Sign a message.
+  std::string message = "message to be signed";
+  util::StatusOr<std::string> signature = (*signer)->Sign(message);
+  ASSERT_THAT(signature.status(), IsOk());
+
+  // Create a new verifier.
+  absl::StatusOr<std::unique_ptr<PublicKeyVerify>> verifier =
+      FalconVerify::New(key_pair->GetPublicKey());
+  ASSERT_THAT(verifier.status(), IsOk());
+
+  // Verify signature.
+  Status status = (*verifier)->Verify(*signature, "some bad message");
+  EXPECT_FALSE(status.ok());
+}
+
+TEST_P(FalconVerifyTest, FailsWithBytesFlipped) {
+  if (IsFipsModeEnabled()) {
+    GTEST_SKIP() << "Test assumes kOnlyUseFips is false.";
+  }
+
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Create a new signer.
+  util::StatusOr<std::unique_ptr<PublicKeySign>> signer =
+      FalconSign::New(key_pair->GetPrivateKey());
+  ASSERT_THAT(signer.status(), IsOk());
+
+  // Sign a message.
+  std::string message = "message to be signed";
+  util::StatusOr<std::string> signature = (*signer)->Sign(message);
+  ASSERT_THAT(signature.status(), IsOk());
+
+  // Create a new verifier.
+  absl::StatusOr<std::unique_ptr<PublicKeyVerify>> verifier =
+      FalconVerify::New(key_pair->GetPublicKey());
+  ASSERT_THAT(verifier.status(), IsOk());
+
+  // Invalidate one signature byte.
+  (*signature)[0] ^= 1;
+
+  // Verify signature.
+  Status status = (*verifier)->Verify(*signature, message);
+  EXPECT_FALSE(status.ok());
+}
+
+TEST_P(FalconVerifyTest, FipsMode) {
+  if (!IsFipsModeEnabled()) {
+    GTEST_SKIP() << "Test assumes kOnlyUseFips.";
+  }
+
+  const FalconTestCase& test_case = GetParam();
+
+  // Generate falcon key pair.
+  util::StatusOr<FalconKeyPair> key_pair =
+      GenerateFalconKeyPair(test_case.private_key_size);
+  ASSERT_THAT(key_pair.status(), IsOk());
+
+  // Create a new signer.
+  EXPECT_THAT(FalconVerify::New(key_pair->GetPublicKey()).status(),
+              StatusIs(util::error::INTERNAL));
+}
+
+INSTANTIATE_TEST_SUITE_P(
+    FalconVerifyTests, FalconVerifyTest,
+    testing::ValuesIn<FalconTestCase>({{"Falcon512", kFalcon512PrivateKeySize,
+                                        PQCLEAN_FALCON512_AVX2_CRYPTO_BYTES},
+                                       {"Falcon1024", kFalcon1024PrivateKeySize,
+                                        PQCLEAN_FALCON1024_AVX2_CRYPTO_BYTES}}),
+    [](const testing::TestParamInfo<FalconVerifyTest::ParamType>& info) {
+      return info.param.test_name;
+    });
+
+}  // namespace
+}  // namespace subtle
+}  // namespace tink
+}  // namespace crypto