Botan::CRYSTALS Namespace Reference

Namespaces
namespace	detail

Classes
struct	BitPackingTrait
class	Polynomial
class	PolynomialMatrix
class	PolynomialVector
class	Trait_Base

Concepts
concept	crystals_constants
concept	crystals_trait
concept	byte_source
concept	coeff_map_fn
concept	coeff_unmap_fn

Enumerations
enum class	Domain { Normal , NTT }

Functions
template<crystals_trait Trait>
Polynomial< Trait, Domain::Normal >	inverse_ntt (Polynomial< Trait, Domain::NTT > p_ntt)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::Normal >	inverse_ntt (PolynomialVector< Trait, Domain::NTT > polyvec_ntt)
template<crystals_trait Trait, Domain D>
Polynomial< Trait, D >	montgomery (Polynomial< Trait, D > p)
template<crystals_trait Trait, Domain D>
PolynomialVector< Trait, D >	montgomery (PolynomialVector< Trait, D > polyvec)
template<crystals_trait Trait>
Polynomial< Trait, Domain::NTT >	ntt (Polynomial< Trait, Domain::Normal > p)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::NTT >	ntt (PolynomialVector< Trait, Domain::Normal > polyvec)
template<crystals_trait Trait>
Polynomial< Trait, Domain::NTT >	operator* (const Polynomial< Trait, Domain::NTT > &a, const Polynomial< Trait, Domain::NTT > &b)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::NTT >	operator* (const Polynomial< Trait, Domain::NTT > &p, const PolynomialVector< Trait, Domain::NTT > &pv)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::NTT >	operator* (const PolynomialMatrix< Trait > &mat, const PolynomialVector< Trait, Domain::NTT > &vec)
template<crystals_trait Trait>
Polynomial< Trait, Domain::NTT >	operator* (const PolynomialVector< Trait, Domain::NTT > &a, const PolynomialVector< Trait, Domain::NTT > &b)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::Normal >	operator+ (const PolynomialVector< Trait, Domain::Normal > &a, const PolynomialVector< Trait, Domain::Normal > &b)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::Normal >	operator<< (const PolynomialVector< Trait, Domain::Normal > &pv, size_t shift)
template<int32_t range, crystals_trait PolyTrait, Domain D>
constexpr void	pack (const Polynomial< PolyTrait, D > &p, BufferStuffer &stuffer)
	Overload for packing polynomials with a NOOP map function.
template<int32_t range, crystals_trait PolyTrait, Domain D, coeff_map_fn< typename PolyTrait::T > MapFnT>
constexpr void	pack (const Polynomial< PolyTrait, D > &p, BufferStuffer &stuffer, MapFnT map)
template<int32_t range, byte_source ByteSourceT, crystals_trait PolyTrait, Domain D>
constexpr void	unpack (Polynomial< PolyTrait, D > &p, ByteSourceT &byte_source)
	Overload for unpacking polynomials with a NOOP unmap function.
template<int32_t range, byte_source ByteSourceT, crystals_trait PolyTrait, Domain D, coeff_unmap_fn< typename PolyTrait::T > UnmapFnT>
constexpr void	unpack (Polynomial< PolyTrait, D > &p, ByteSourceT &byte_source, UnmapFnT unmap)

Enumeration Type Documentation

Domain

enum class Botan::CRYSTALS::Domain

strong

Enumerator
Normal
NTT

Definition at line 28 of file pqcrystals.h.

{ Normal, NTT };

Function Documentation

inverse_ntt() [1/2]

template<crystals_trait Trait>

Polynomial< Trait, Domain::Normal > Botan::CRYSTALS::inverse_ntt

(

Polynomial< Trait, Domain::NTT >

p_ntt

)

Definition at line 564 of file pqcrystals.h.

                                                                                {
   auto p = detail::domain_cast<Domain::Normal>(std::move(p_ntt));
   Trait::inverse_ntt(p.coefficients());
   return p;
}

References Botan::CRYSTALS::detail::domain_cast().

inverse_ntt() [2/2]

template<crystals_trait Trait>

PolynomialVector< Trait, Domain::Normal > Botan::CRYSTALS::inverse_ntt

(

PolynomialVector< Trait, Domain::NTT >

polyvec_ntt

)

Definition at line 580 of file pqcrystals.h.

                                                                                                  {
   auto polyvec = detail::domain_cast<Domain::Normal>(std::move(polyvec_ntt));
   for(auto& poly : polyvec) {
      Trait::inverse_ntt(poly.coefficients());
   }
   return polyvec;
}

References Botan::CRYSTALS::detail::domain_cast().

montgomery() [1/2]

template<crystals_trait Trait, Domain D>

Polynomial< Trait, D > Botan::CRYSTALS::montgomery

(

Polynomial< Trait, D >

p

)

Definition at line 589 of file pqcrystals.h.

                                                        {
   detail::montgomery(p);
   return p;
}

References Botan::CRYSTALS::detail::montgomery().

montgomery() [2/2]

template<crystals_trait Trait, Domain D>

PolynomialVector< Trait, D > Botan::CRYSTALS::montgomery

(

PolynomialVector< Trait, D >

polyvec

)

Definition at line 595 of file pqcrystals.h.

                                                                          {
   for(auto& p : polyvec) {
      detail::montgomery(p);
   }
   return polyvec;
}

References Botan::CRYSTALS::detail::montgomery().

ntt() [1/2]

template<crystals_trait Trait>

Polynomial< Trait, Domain::NTT > Botan::CRYSTALS::ntt

(

Polynomial< Trait, Domain::Normal >

p

)

Definition at line 557 of file pqcrystals.h.

                                                                    {
   auto p_ntt = detail::domain_cast<Domain::NTT>(std::move(p));
   Trait::ntt(p_ntt.coefficients());
   return p_ntt;
}

References Botan::CRYSTALS::detail::domain_cast().

ntt() [2/2]

template<crystals_trait Trait>

PolynomialVector< Trait, Domain::NTT > Botan::CRYSTALS::ntt

(

PolynomialVector< Trait, Domain::Normal >

polyvec

)

Definition at line 571 of file pqcrystals.h.

                                                                                      {
   auto polyvec_ntt = detail::domain_cast<Domain::NTT>(std::move(polyvec));
   for(auto& poly : polyvec_ntt) {
      Trait::ntt(poly.coefficients());
   }
   return polyvec_ntt;
}

References Botan::CRYSTALS::detail::domain_cast().

operator*() [1/4]

template<crystals_trait Trait>

Polynomial< Trait, Domain::NTT > Botan::CRYSTALS::operator*	(	const Polynomial< Trait, Domain::NTT > &	a,
		const Polynomial< Trait, Domain::NTT > &	b )

Definition at line 642 of file pqcrystals.h.

                                                                                {
   Polynomial<Trait, Domain::NTT> result;
   Trait::poly_pointwise_montgomery(result.coefficients(), a.coefficients(), b.coefficients());
   return result;
}

References Botan::b, and Botan::CRYSTALS::Polynomial< Trait, D >::coefficients().

operator*() [2/4]

template<crystals_trait Trait>

PolynomialVector< Trait, Domain::NTT > Botan::CRYSTALS::operator*	(	const Polynomial< Trait, Domain::NTT > &	p,
		const PolynomialVector< Trait, Domain::NTT > &	pv )

Definition at line 632 of file pqcrystals.h.

                                                                                             {
   PolynomialVector<Trait, Domain::NTT> result(pv.size());
   for(size_t i = 0; i < pv.size(); ++i) {
      Trait::poly_pointwise_montgomery(result[i].coefficients(), p.coefficients(), pv[i].coefficients());
   }
   return result;
}

References Botan::CRYSTALS::Polynomial< Trait, D >::coefficients(), Botan::CRYSTALS::PolynomialVector< Trait, D >::coefficients(), and Botan::CRYSTALS::PolynomialVector< Trait, D >::size().

operator*() [3/4]

template<crystals_trait Trait>

PolynomialVector< Trait, Domain::NTT > Botan::CRYSTALS::operator*	(	const PolynomialMatrix< Trait > &	mat,
		const PolynomialVector< Trait, Domain::NTT > &	vec )

Definition at line 614 of file pqcrystals.h.

                                                                                              {
   PolynomialVector<Trait, Domain::NTT> result(mat.size());
   for(size_t i = 0; i < mat.size(); ++i) {
      Trait::polyvec_pointwise_acc_montgomery(result[i].coefficients(), mat[i].coefficients(), vec.coefficients());
   }
   return result;
}

References Botan::CRYSTALS::PolynomialVector< Trait, D >::coefficients(), and Botan::CRYSTALS::PolynomialMatrix< Trait >::size().

operator*() [4/4]

template<crystals_trait Trait>

Polynomial< Trait, Domain::NTT > Botan::CRYSTALS::operator*	(	const PolynomialVector< Trait, Domain::NTT > &	a,
		const PolynomialVector< Trait, Domain::NTT > &	b )

Definition at line 624 of file pqcrystals.h.

                                                                                      {
   Polynomial<Trait, Domain::NTT> result;
   detail::dot_product(result, a, b);
   return result;
}

References Botan::b, and Botan::CRYSTALS::detail::dot_product().

operator+()

template<crystals_trait Trait>

PolynomialVector< Trait, Domain::Normal > Botan::CRYSTALS::operator+	(	const PolynomialVector< Trait, Domain::Normal > &	a,
		const PolynomialVector< Trait, Domain::Normal > &	b )

Definition at line 603 of file pqcrystals.h.

                                                                                                  {
   BOTAN_DEBUG_ASSERT(a.size() == b.size());
   PolynomialVector<Trait, Domain::Normal> result(a.size());
   for(size_t i = 0; i < a.size(); ++i) {
      Trait::poly_add(result[i].coefficients(), a[i].coefficients(), b[i].coefficients());
   }
   return result;
}

References Botan::b, BOTAN_DEBUG_ASSERT, and Botan::CRYSTALS::PolynomialVector< Trait, D >::size().

operator<<()

template<crystals_trait Trait>

PolynomialVector< Trait, Domain::Normal > Botan::CRYSTALS::operator<<	(	const PolynomialVector< Trait, Domain::Normal > &	pv,
		size_t	shift )

Definition at line 642 of file pqcrystals.h.

                                                                                                                {
   BOTAN_ASSERT_NOMSG(shift < sizeof(typename Trait::T) * 8);
   PolynomialVector<Trait, Domain::Normal> result(pv.size());
   for(size_t i = 0; i < pv.size(); ++i) {
      for(size_t j = 0; j < Trait::N; ++j) {
         result[i][j] = pv[i][j] << shift;
      }
   }
   return result;
}

pack() [1/2]

template<int32_t range, crystals_trait PolyTrait, Domain D>

void Botan::CRYSTALS::pack ( const Polynomial< PolyTrait, D > & p, BufferStuffer & stuffer )

constexpr

Overload for packing polynomials with a NOOP map function.

Definition at line 222 of file pqcrystals_encoding.h.

                                                                               {
   using unsigned_T = std::make_unsigned_t<typename PolyTrait::T>;
   pack<range>(p, stuffer, [](typename PolyTrait::T x) { return static_cast<unsigned_T>(x); });
}

References pack().

pack() [2/2]

template<int32_t range, crystals_trait PolyTrait, Domain D, coeff_map_fn< typename PolyTrait::T > MapFnT>

void Botan::CRYSTALS::pack ( const Polynomial< PolyTrait, D > & p, BufferStuffer & stuffer, MapFnT map )

constexpr

Base implementation of NIST FIPS 203 Algorithm 5 (ByteEncode) and NIST FIPS 204 Algorithms 16 (SimpleBitPack) and 17 (BitPack).

This takes a polynomial p and packs its coefficients into the buffer represented by stuffer. Optionally, the coefficients can be transformed using the map function before packing them. Kyber uses map to compress the coefficients as needed, Dilithium to transform coefficients to unsigned.

The implementation assumes that the values returned from the custom map transformation are in the range [0, range]. No assumption is made about the value range of the coefficients in the polynomial p.

Note that this bit-packing algorithm is inefficient if the bit-length of the coefficients is a multiple of 8. In that case, a byte-level encoding (that might need to take endianess into account) would be more efficient. However, neither Kyber nor Dilithium instantiate bit-packings with such a value range.

Template Parameters

range

the upper bound of the coefficient range.

Definition at line 116 of file pqcrystals_encoding.h.

                                                                                           {
   using trait = BitPackingTrait<range, PolyTrait>;
 
   BOTAN_DEBUG_ASSERT(stuffer.remaining_capacity() >= p.size() * trait::bits_per_coeff / 8);
 
   // Bit-packing example that shows a coefficients' bit-pack that spills across
   // more than one 64-bit collectors. This illustrates the algorithm below.
   //
   //                         0                                       64                                       128
   // Collectors   (64 bits): |               collectors[0]            |               collectors[1]            |
   //                         |                                        |                                        |
   // Coefficients (11 bits): | c[0] | c[1] | c[2] | c[3] | c[4] | c[5] | c[6] | c[7] |      |      |      |      | ...
   //                         |                                                       |                         |
   //                         |         < byte-aligned coefficient pack >             |  < byte-aligned pad. >  |
   //                         |             (one inner loop iteration)                |
   //                         0                                                      88 (divisible by 8)
 
   for(size_t i = 0; i < p.size(); i += trait::coeffs_per_pack) {
      // The collectors array is filled with bit-packed coefficients to produce
      // a byte-aligned pack of coefficients. When coefficients fall onto the
      // boundary of two collectors, their bits must be split.
      typename trait::collector_array collectors = {0};
      for(size_t j = 0, bit_offset = 0, c = 0; j < trait::coeffs_per_pack; ++j) {
         // Transform p[i] via a custom map function (that may be a NOOP).
         const typename trait::unsigned_T mapped_coeff = map(p[i + j]);
         const auto coeff_value = static_cast<typename trait::sink_t>(mapped_coeff);
 
         // pack() is called only on data produced by us. If the values returned
         // by the map function are not in the range [0, range] we have a bug.
         BOTAN_DEBUG_ASSERT(coeff_value <= range);
 
         // Bit-pack the coefficient into the collectors array and keep track of
         // the bit-offset within the current collector. Note that this might
         // shift some high-bits of the coefficient out of the current collector.
         collectors[c] |= coeff_value << bit_offset;
         bit_offset += trait::bits_per_coeff;
 
         // If the bit-offset now exceeds the collector's bit-width, we fill the
         // next collector with the high-bits that didn't fit into the previous.
         // The bit-offset is adjusted to now point into the new collector.
         if(bit_offset > trait::bits_in_collector) {
            bit_offset = bit_offset - trait::bits_in_collector;
            collectors[++c] = coeff_value >> (trait::bits_per_coeff - bit_offset);
         }
      }
 
      // One byte-aligned pack of bit-packed coefficients is now stored in the
      // collectors and can be written to an output buffer. Note that we might
      // have to remove some padding bytes of unused collector space.
      const auto bytes = store_le(collectors);
      stuffer.append(std::span{bytes}.template first<trait::bytes_per_pack>());
   }
}

References Botan::BufferStuffer::append(), BOTAN_DEBUG_ASSERT, Botan::BufferStuffer::remaining_capacity(), Botan::CRYSTALS::Polynomial< Trait, D >::size(), and Botan::store_le().

Referenced by pack().

unpack() [1/2]

template<int32_t range, byte_source ByteSourceT, crystals_trait PolyTrait, Domain D>

void Botan::CRYSTALS::unpack ( Polynomial< PolyTrait, D > & p, ByteSourceT & byte_source )

constexpr

Overload for unpacking polynomials with a NOOP unmap function.

Definition at line 229 of file pqcrystals_encoding.h.

                                                                             {
   using unsigned_T = std::make_unsigned_t<typename PolyTrait::T>;
   unpack<range>(p, byte_source, [](unsigned_T x) { return static_cast<typename PolyTrait::T>(x); });
}

References unpack().

unpack() [2/2]

template<int32_t range, byte_source ByteSourceT, crystals_trait PolyTrait, Domain D, coeff_unmap_fn< typename PolyTrait::T > UnmapFnT>

void Botan::CRYSTALS::unpack ( Polynomial< PolyTrait, D > & p, ByteSourceT & byte_source, UnmapFnT unmap )

constexpr

Base implementation of NIST FIPS 203 Algorithm 6 (ByteDecode) and NIST FIPS 204 Algorithms 18 (SimpleBitUnpack) and 19 (BitUnpack).

This takes a byte sequence represented by byte_source and unpacks its coefficients into the polynomial p. Optionally, the coefficients can be transformed using the unmap function after unpacking them. Note that the unmap function must be able to deal with out-of-range values, as the input to unpack() may be untrusted data.

Kyber uses unmap to decompress the coefficients as needed, Dilithium uses it to convert the coefficients back to signed integers.

Template Parameters

range

the upper bound of the coefficient range.

Definition at line 190 of file pqcrystals_encoding.h.

                                                                                             {
   using trait = BitPackingTrait<range, PolyTrait>;
 
   auto get_bytes = detail::as_byte_source(byte_source);
   typename trait::collector_bytearray bytes = {0};
 
   // This is the inverse operation of the bit-packing algorithm above. Please
   // refer to the comments there for a detailed explanation of the algorithm.
   for(size_t i = 0; i < p.size(); i += trait::coeffs_per_pack) {
      get_bytes(std::span{bytes}.template first<trait::bytes_per_pack>());
      const auto collectors = load_le<typename trait::collector_array>(bytes);
 
      for(size_t j = 0, bit_offset = 0, c = 0; j < trait::coeffs_per_pack; ++j) {
         typename trait::sink_t coeff_value = collectors[c] >> bit_offset;
         bit_offset += trait::bits_per_coeff;
         if(bit_offset > trait::bits_in_collector) {
            bit_offset = bit_offset - trait::bits_in_collector;
            coeff_value |= collectors[++c] << (trait::bits_per_coeff - bit_offset);
         }
 
         // unpack() may be called on data produced by an untrusted party.
         // The values passed into the unmap function may be out of range, hence
         // it is acceptable for unmap to return an out-of-range value then.
         //
         // For that reason we cannot use BOTAN_ASSERT[_DEBUG] on the values.
         p[i + j] = unmap(static_cast<typename trait::unsigned_T>(coeff_value & trait::value_mask));
      }
   }
}

References Botan::CRYSTALS::detail::as_byte_source(), Botan::load_le(), and Botan::CRYSTALS::Polynomial< Trait, D >::size().

Referenced by unpack().