Botan::Dilithium_Algos Namespace Reference

Functions
std::pair< DilithiumSeedRho, DilithiumPolyVec >	decode_public_key (StrongSpan< const DilithiumSerializedPublicKey > pk, const DilithiumConstants &mode)
std::optional< std::tuple< DilithiumCommitmentHash, DilithiumPolyVec, DilithiumPolyVec > >	decode_signature (StrongSpan< const DilithiumSerializedSignature > sig, const DilithiumConstants &mode)
std::pair< DilithiumPolyVec, DilithiumPolyVec >	decompose (const DilithiumPolyVec &vec, const DilithiumConstants &mode)
DilithiumSerializedCommitment	encode_commitment (const DilithiumPolyVec &w1, const DilithiumConstants &mode)
DilithiumSerializedPublicKey	encode_public_key (StrongSpan< const DilithiumSeedRho > rho, const DilithiumPolyVec &t1, const DilithiumConstants &mode)
DilithiumSerializedSignature	encode_signature (StrongSpan< const DilithiumCommitmentHash > c, const DilithiumPolyVec &response, const DilithiumPolyVec &hint, const DilithiumConstants &mode)
DilithiumPolyMatNTT	expand_A (StrongSpan< const DilithiumSeedRho > rho, const DilithiumConstants &mode)
DilithiumInternalKeypair	expand_keypair (DilithiumSeedRandomness xi, DilithiumConstants mode)
DilithiumPolyVec	expand_mask (StrongSpan< const DilithiumSeedRhoPrime > rhoprime, uint16_t nonce, const DilithiumConstants &mode)
std::pair< DilithiumPolyVec, DilithiumPolyVec >	expand_s (StrongSpan< const DilithiumSeedRhoPrime > rhoprime, const DilithiumConstants &mode)
bool	infinity_norm_within_bound (const DilithiumPolyVec &vec, size_t bound)
DilithiumPolyVec	make_hint (const DilithiumPolyVec &z, const DilithiumPolyVec &r, const DilithiumConstants &mode)
std::pair< DilithiumPolyVec, DilithiumPolyVec >	power2round (const DilithiumPolyVec &vec)
DilithiumPoly	sample_in_ball (StrongSpan< const DilithiumCommitmentHash > seed, const DilithiumConstants &mode)
void	use_hint (DilithiumPolyVec &vec, const DilithiumPolyVec &hints, const DilithiumConstants &mode)

Function Documentation

decode_public_key()

std::pair< DilithiumSeedRho, DilithiumPolyVec > Botan::Dilithium_Algos::decode_public_key	(	StrongSpan< const DilithiumSerializedPublicKey >	pk,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 23 (pkDecode)

Definition at line 344 of file dilithium_algos.cpp.

                                                                                                {
   if(pk.size() != mode.public_key_bytes()) {
      throw Decoding_Error("Dilithium: Invalid public key length");
   }
 
   BufferSlicer slicer(pk);
   auto rho = slicer.copy<DilithiumSeedRho>(DilithiumConstants::SEED_RHO_BYTES);
 
   DilithiumPolyVec t1(mode.k());
   for(auto& p : t1) {
      poly_unpack_t1(p, slicer);
   }
   BOTAN_ASSERT_NOMSG(slicer.empty());
 
   return {std::move(rho), std::move(t1)};
}

References BOTAN_ASSERT_NOMSG, Botan::BufferSlicer::copy(), Botan::BufferSlicer::empty(), Botan::DilithiumConstants::k(), Botan::DilithiumConstants::public_key_bytes(), Botan::rho(), Botan::DilithiumConstants::SEED_RHO_BYTES, and Botan::StrongSpan< T >::size().

Referenced by Botan::Dilithium_PublicKeyInternal::decode().

decode_signature()

std::optional< std::tuple< DilithiumCommitmentHash, DilithiumPolyVec, DilithiumPolyVec > > Botan::Dilithium_Algos::decode_signature	(	StrongSpan< const DilithiumSerializedSignature >	sig,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 27 (sigDecode)

Definition at line 492 of file dilithium_algos.cpp.

                                                                                       {
   BufferSlicer slicer(sig);
   BOTAN_ASSERT_NOMSG(slicer.remaining() == mode.signature_bytes());
 
   auto commitment_hash = slicer.copy<DilithiumCommitmentHash>(mode.commitment_hash_full_bytes());
 
   DilithiumPolyVec response(mode.l());
   for(auto& p : response) {
      poly_unpack_gamma1(p, slicer, mode);
   }
   BOTAN_ASSERT_NOMSG(slicer.remaining() == size_t(mode.omega()) + mode.k());
 
   auto hint = hint_unpack(slicer, mode);
   BOTAN_ASSERT_NOMSG(slicer.empty());
   if(!hint.has_value()) {
      return std::nullopt;
   }
 
   return std::make_tuple(std::move(commitment_hash), std::move(response), std::move(hint.value()));
}

References BOTAN_ASSERT_NOMSG, Botan::DilithiumConstants::commitment_hash_full_bytes(), Botan::BufferSlicer::copy(), Botan::BufferSlicer::empty(), Botan::DilithiumConstants::k(), Botan::DilithiumConstants::l(), Botan::DilithiumConstants::omega(), Botan::BufferSlicer::remaining(), and Botan::DilithiumConstants::signature_bytes().

decompose()

std::pair< DilithiumPolyVec, DilithiumPolyVec > Botan::Dilithium_Algos::decompose	(	const DilithiumPolyVec &	vec,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 36 (Decompose) on a polynomial vector

Algorithms 37 (HighBits) and 38 (LowBits) are not implemented explicitly, simply use the first (HighBits) and second (LowBits) element of the result.

Definition at line 818 of file dilithium_algos.cpp.

                                                                                                                   {
   using Gamma2 = DilithiumConstants::DilithiumGamma2;
   switch(mode.gamma2()) {
      case Gamma2::Qminus1DividedBy32:
         return decompose_all_coefficients<Gamma2::Qminus1DividedBy32>(vec);
         break;
      case Gamma2::Qminus1DividedBy88:
         return decompose_all_coefficients<Gamma2::Qminus1DividedBy88>(vec);
         break;
   }
 
   BOTAN_ASSERT_UNREACHABLE();
}

References BOTAN_ASSERT_UNREACHABLE, and Botan::DilithiumConstants::gamma2().

encode_commitment()

DilithiumSerializedCommitment Botan::Dilithium_Algos::encode_commitment	(	const DilithiumPolyVec &	w1,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 28 (w1Encode)

Definition at line 517 of file dilithium_algos.cpp.

                                                                                                            {
   DilithiumSerializedCommitment commitment(mode.serialized_commitment_bytes());
   BufferStuffer stuffer(commitment);
 
   for(const auto& p : w1) {
      poly_pack_w1(p, stuffer, mode);
   }
 
   return commitment;
}

References Botan::DilithiumConstants::serialized_commitment_bytes().

encode_public_key()

DilithiumSerializedPublicKey Botan::Dilithium_Algos::encode_public_key	(	StrongSpan< const DilithiumSeedRho >	rho,
		const DilithiumPolyVec &	t1,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 22 (pkEncode)

Definition at line 326 of file dilithium_algos.cpp.

                                                                               {
   DilithiumSerializedPublicKey pk(mode.public_key_bytes());
   BufferStuffer stuffer(pk);
 
   stuffer.append(rho);
   for(const auto& p : t1) {
      poly_pack_t1(p, stuffer);
   }
 
   BOTAN_ASSERT_NOMSG(stuffer.full());
   return pk;
}

References Botan::BufferStuffer::append(), BOTAN_ASSERT_NOMSG, Botan::BufferStuffer::full(), Botan::DilithiumConstants::public_key_bytes(), and Botan::rho().

Referenced by Botan::Dilithium_PublicKeyInternal::raw_pk().

encode_signature()

DilithiumSerializedSignature Botan::Dilithium_Algos::encode_signature	(	StrongSpan< const DilithiumCommitmentHash >	c,
		const DilithiumPolyVec &	response,
		const DilithiumPolyVec &	hint,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 26 (sigEncode)

Definition at line 473 of file dilithium_algos.cpp.

                                                                              {
   DilithiumSerializedSignature sig(mode.signature_bytes());
   BufferStuffer stuffer(sig);
 
   stuffer.append(c);
   for(const auto& p : response) {
      poly_pack_gamma1(p, stuffer, mode);
   }
   hint_pack(hint, stuffer, mode);
 
   return sig;
}

References Botan::BufferStuffer::append(), and Botan::DilithiumConstants::signature_bytes().

expand_A()

DilithiumPolyMatNTT Botan::Dilithium_Algos::expand_A	(	StrongSpan< const DilithiumSeedRho >	rho,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 32 (ExpandA)

Note that the actual concatenation of rho, s and r is done downstream in the sampling function.

Definition at line 694 of file dilithium_algos.cpp.

                                                                                                     {
   DilithiumPolyMatNTT A(mode.k(), mode.l());
   for(uint8_t r = 0; r < mode.k(); ++r) {
      for(uint8_t s = 0; s < mode.l(); ++s) {
         sample_ntt_uniform(rho, A[r][s], load_le(std::array{s, r}), mode);
      }
   }
   return A;
}

References Botan::DilithiumConstants::k(), Botan::DilithiumConstants::l(), Botan::load_le(), and Botan::rho().

Referenced by expand_keypair().

expand_keypair()

DilithiumInternalKeypair Botan::Dilithium_Algos::expand_keypair	(	DilithiumSeedRandomness	xi,
		DilithiumConstants	mode )

NIST FIPS 204, Algorithm 6 (ML-DSA.KeyGen_internal)

Lines 5-7 are extracted into a separate function, see above. The key encoding is deferred until the user explicitly invokes the encoding.

Definition at line 664 of file dilithium_algos.cpp.

                                                                                             {
   const auto& sympriv = mode.symmetric_primitives();
   CT::poison(xi);
 
   auto [rho, rhoprime, K] = sympriv.H(xi);
   CT::unpoison(rho);  // rho is public (seed for the public matrix A)
 
   const auto A = Dilithium_Algos::expand_A(rho, mode);
   auto [s1, s2] = Dilithium_Algos::expand_s(rhoprime, mode);
   auto [t1, t0] = Dilithium_Algos::compute_t1_and_t0(A, s1, s2);
 
   CT::unpoison(t1);  // part of the public key
 
   DilithiumInternalKeypair keypair{
      std::make_shared<Dilithium_PublicKeyInternal>(mode, std::move(rho), std::move(t1)),
      std::make_shared<Dilithium_PrivateKeyInternal>(
         std::move(mode), std::move(xi), std::move(K), std::move(s1), std::move(s2), std::move(t0)),
   };
 
   CT::unpoison(*keypair.second);
 
   return keypair;
}

References expand_A(), expand_s(), Botan::CT::poison(), Botan::rho(), Botan::DilithiumConstants::symmetric_primitives(), and Botan::CT::unpoison().

Referenced by Botan::ML_DSA_Expanding_Keypair_Codec::decode_keypair(), and Botan::Dilithium_PrivateKey::Dilithium_PrivateKey().

expand_mask()

DilithiumPolyVec Botan::Dilithium_Algos::expand_mask	(	StrongSpan< const DilithiumSeedRhoPrime >	rhoprime,
		uint16_t	nonce,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 34 (ExpandMask)

Definition at line 727 of file dilithium_algos.cpp.

                                                             {
   DilithiumPolyVec s(mode.l());
   for(auto& p : s) {
      auto& xof = mode.symmetric_primitives().H(rhoprime, nonce++);
      poly_unpack_gamma1(p, xof, mode);
   }
   return s;
}

References Botan::Dilithium_Symmetric_Primitives_Base::H(), Botan::DilithiumConstants::l(), and Botan::DilithiumConstants::symmetric_primitives().

expand_s()

std::pair< DilithiumPolyVec, DilithiumPolyVec > Botan::Dilithium_Algos::expand_s	(	StrongSpan< const DilithiumSeedRhoPrime >	rhoprime,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 33 (ExpandS)

Definition at line 707 of file dilithium_algos.cpp.

                                                                                       {
   auto result = std::make_pair(DilithiumPolyVec(mode.l()), DilithiumPolyVec(mode.k()));
   auto& [s1, s2] = result;
 
   uint16_t nonce = 0;
   for(auto& p : s1) {
      sample_uniform_eta(rhoprime, p, nonce++, mode);
   }
 
   for(auto& p : s2) {
      sample_uniform_eta(rhoprime, p, nonce++, mode);
   }
 
   return result;
}

References Botan::DilithiumConstants::k(), and Botan::DilithiumConstants::l().

Referenced by expand_keypair().

infinity_norm_within_bound()

bool Botan::Dilithium_Algos::infinity_norm_within_bound	(	const DilithiumPolyVec &	vec,
		size_t	bound )

Definition at line 935 of file dilithium_algos.cpp.

                                                                           {
   BOTAN_DEBUG_ASSERT(bound <= (DilithiumConstants::Q - 1) / 8);
 
   // It is ok to leak which coefficient violates the bound as the probability
   // for each coefficient is independent of secret data but we must not leak
   // the sign of the centralized representative.
   for(const auto& p : vec) {
      for(auto c : p) {
         const auto abs_c = c - is_negative_mask(c).if_set_return(2 * c);
         if(CT::driveby_unpoison(abs_c >= bound)) {
            return false;
         }
      }
   }
 
   return true;
}

References BOTAN_DEBUG_ASSERT, Botan::CT::driveby_unpoison(), and Botan::DilithiumConstants::Q.

make_hint()

DilithiumPolyVec Botan::Dilithium_Algos::make_hint	(	const DilithiumPolyVec &	z,
		const DilithiumPolyVec &	r,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 39 (MakeHint)

MakeHint is specified per value in FIPS 204. This implements the algorithm for the entire polynomial vector. The specified algorithm is equivalent to the inner lambda.

TODO: This is taken from the reference implementation. We should implement it as specified in the spec, and see if that has any performance impact.

Definition at line 842 of file dilithium_algos.cpp.

                                                                                                                 {
   BOTAN_DEBUG_ASSERT(z.size() == r.size());
 
   auto make_hint = [gamma2 = uint32_t(mode.gamma2()),
                     q_gamma2 = static_cast<uint32_t>(DilithiumConstants::Q) - uint32_t(mode.gamma2())](
                       int32_t c0, int32_t c1) -> CT::Choice {
      BOTAN_DEBUG_ASSERT(c0 >= 0);
      BOTAN_DEBUG_ASSERT(c1 >= 0);
 
      const uint32_t pc0 = static_cast<uint32_t>(c0);
      const uint32_t pc1 = static_cast<uint32_t>(c1);
 
      return (CT::Mask<uint32_t>::is_gt(pc0, gamma2) & CT::Mask<uint32_t>::is_lte(pc0, q_gamma2) &
              ~(CT::Mask<uint32_t>::is_equal(pc0, q_gamma2) & CT::Mask<uint32_t>::is_zero(pc1)))
         .as_choice();
   };
 
   DilithiumPolyVec hint(r.size());
 
   for(size_t i = 0; i < r.size(); ++i) {
      for(size_t j = 0; j < r[i].size(); ++j) {
         hint[i][j] = static_cast<int>(make_hint(z[i][j], r[i][j]).as_bool());
      }
   }
 
   BOTAN_DEBUG_ASSERT(hint.ct_validate_value_range(0, 1));
 
   return hint;
}

References BOTAN_DEBUG_ASSERT, Botan::CRYSTALS::PolynomialVector< Trait, D >::ct_validate_value_range(), Botan::DilithiumConstants::gamma2(), Botan::CT::Mask< T >::is_equal(), Botan::CT::Mask< T >::is_gt(), Botan::CT::Mask< T >::is_lte(), Botan::CT::Mask< T >::is_zero(), make_hint(), Botan::DilithiumConstants::Q, and Botan::CRYSTALS::PolynomialVector< Trait, D >::size().

Referenced by make_hint().

power2round()

std::pair< DilithiumPolyVec, DilithiumPolyVec > Botan::Dilithium_Algos::power2round

(

const DilithiumPolyVec &

vec

)

NIST FIPS 204, Algorithm 35 (Power2Round)

In contrast to the spec, this function takes a polynomial vector and performs the power2round operation on each coefficient in the vector. The actual Algorithm 35 as specified is actually just the inner lambda.

Definition at line 745 of file dilithium_algos.cpp.

                                                                                     {
   // This procedure is taken verbatim from Dilithium's reference implementation.
   auto power2round = [d = DilithiumConstants::D](int32_t r) -> std::pair<int32_t, int32_t> {
      const int32_t r1 = (r + (1 << (d - 1)) - 1) >> d;
      const int32_t r0 = r - (r1 << d);
      return {r1, r0};
   };
 
   auto result = std::make_pair(DilithiumPolyVec(vec.size()), DilithiumPolyVec(vec.size()));
 
   for(size_t i = 0; i < vec.size(); ++i) {
      for(size_t j = 0; j < vec[i].size(); ++j) {
         std::tie(result.first[i][j], result.second[i][j]) = power2round(vec[i][j]);
      }
   }
 
   return result;
}

References Botan::DilithiumConstants::D, power2round(), and Botan::CRYSTALS::PolynomialVector< Trait, D >::size().

Referenced by power2round().

sample_in_ball()

DilithiumPoly Botan::Dilithium_Algos::sample_in_ball	(	StrongSpan< const DilithiumCommitmentHash >	seed,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 29 (SampleInBall)

Definition at line 531 of file dilithium_algos.cpp.

                                                                                                             {
   // This generator resembles the while loop in the spec.
   auto& xof = mode.symmetric_primitives().H(seed);
   auto bounded_xof = Bounded_XOF<DilithiumConstants::SAMPLE_IN_BALL_XOF_BOUND + 8>(xof);
 
   DilithiumPoly c;
   uint64_t signs = load_le(bounded_xof.next<8>());
   for(size_t i = c.size() - mode.tau(); i < c.size(); ++i) {
      const auto j = bounded_xof.next_byte([i](uint8_t byte) { return byte <= i; });
      c[i] = c[j];
      c[j] = 1 - 2 * (signs & 1);
      signs >>= 1;
   }
 
   BOTAN_DEBUG_ASSERT(c.ct_validate_value_range(-1, 1));
   BOTAN_DEBUG_ASSERT(c.hamming_weight() == mode.tau());
 
   return c;
}

References BOTAN_DEBUG_ASSERT, Botan::CRYSTALS::Polynomial< Trait, D >::ct_validate_value_range(), Botan::Dilithium_Symmetric_Primitives_Base::H(), Botan::CRYSTALS::Polynomial< Trait, D >::hamming_weight(), Botan::load_le(), Botan::CRYSTALS::Polynomial< Trait, D >::size(), Botan::DilithiumConstants::symmetric_primitives(), and Botan::DilithiumConstants::tau().

use_hint()

void Botan::Dilithium_Algos::use_hint	(	DilithiumPolyVec &	vec,
		const DilithiumPolyVec &	hints,
		const DilithiumConstants &	mode )

NIST FIPS 204, Algorithm 40 (UseHint)

UseHint is specified per value in FIPS 204. This implements the algorithm for the entire polynomial vector. The specified algorithm is equivalent to the inner lambdas of 'use_hint_with_coefficients'.

Definition at line 917 of file dilithium_algos.cpp.

                                                                                                    {
   BOTAN_DEBUG_ASSERT(hints.size() == vec.size());
   BOTAN_DEBUG_ASSERT(hints.ct_validate_value_range(0, 1));
   BOTAN_DEBUG_ASSERT(vec.ct_validate_value_range(0, DilithiumConstants::Q - 1));
 
   using Gamma2 = DilithiumConstants::DilithiumGamma2;
   switch(mode.gamma2()) {
      case Gamma2::Qminus1DividedBy32:
         use_hint_on_coefficients<Gamma2::Qminus1DividedBy32>(hints, vec);
         break;
      case Gamma2::Qminus1DividedBy88:
         use_hint_on_coefficients<Gamma2::Qminus1DividedBy88>(hints, vec);
         break;
   }
 
   BOTAN_DEBUG_ASSERT(vec.ct_validate_value_range(0, (DilithiumConstants::Q - 1) / (2 * mode.gamma2())));
}

References BOTAN_DEBUG_ASSERT, Botan::CRYSTALS::PolynomialVector< Trait, D >::ct_validate_value_range(), Botan::DilithiumConstants::gamma2(), Botan::DilithiumConstants::Q, and Botan::CRYSTALS::PolynomialVector< Trait, D >::size().