#include <dilithium_polynomial.h>

Inheritance diagram for Botan::DilithiumPolyTraits:

Public Types
using	T

Static Public Member Functions
static constexpr void	barrett_reduce (std::span< T, N > poly)
static constexpr void	inverse_ntt (std::span< T, N > coeffs)
static constexpr void	ntt (std::span< T, N > coeffs)
static constexpr void	poly_add (std::span< T, N > result, std::span< const T, N > lhs, std::span< const T, N > rhs)
static constexpr void	poly_cadd_q (std::span< T, N > coeffs)
	Adds Q if the coefficient is negative.
static constexpr void	poly_pointwise_montgomery (std::span< T, N > result, std::span< const T, N > lhs, std::span< const T, N > rhs)
static constexpr void	poly_sub (std::span< T, N > result, std::span< const T, N > lhs, std::span< const T, N > rhs)
static constexpr void	polyvec_pointwise_acc_montgomery (std::span< T, N > w, std::span< const T > u, std::span< const T > v)
	Multiplication and accumulation of 2 polynomial vectors `u` and `v`.
static constexpr T	to_montgomery (T a)

Static Public Attributes
static constexpr T	N
static constexpr T	Q

Protected Types
using	T2

Static Protected Member Functions
static constexpr T	fqmul (T a, T b)
static constexpr std::span< U, N >	poly_in_polyvec (std::span< U > polyvec, size_t index)
static constexpr size_t	polys_in_polyvec (std::span< const T > polyvec)

Static Protected Attributes
Pre-computed algorithm constants
static constexpr T	Q_inverse
static constexpr T	MONTY
static constexpr T	MONTY_SQUARED
static constexpr T	F_WITH_MONTY_SQUARED
static constexpr auto	zetas

Friends
class	CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >

Detailed Description

Definition at line 22 of file dilithium_polynomial.h.

Member Typedef Documentation

◆ T

using Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::T

inherited

Definition at line 51 of file pqcrystals.h.

◆ T2

using Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::T2

protectedinherited

Definition at line 56 of file pqcrystals.h.

Member Function Documentation

◆ barrett_reduce()

constexpr void Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::barrett_reduce ( std::span< T, N > poly )

inlinestaticconstexprinherited

Definition at line 122 of file pqcrystals.h.

                                                               {
         for(auto& coeff : poly) {
            coeff = DerivedT::barrett_reduce_coefficient(coeff);
         }
      }

◆ fqmul()

constexpr T Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::fqmul	(	T	a,
		T	b )

inlinestaticconstexprprotectedinherited

Definition at line 96 of file pqcrystals.h.

96{ return DerivedT::montgomery_reduce_coefficient(static_cast<T2>(a) * b); }

Referenced by Botan::DilithiumPolyTraits::inverse_ntt(), Botan::DilithiumPolyTraits::ntt(), and Botan::DilithiumPolyTraits::poly_pointwise_montgomery().

◆ inverse_ntt()

constexpr void Botan::DilithiumPolyTraits::inverse_ntt ( std::span< T, N > coeffs )

inlinestaticconstexpr

NIST FIPS 204, Algorithm 42 (NTT^-1).

The output is effectively multiplied by the montgomery parameter 2^32 mod q so that the input factors 2^(-32) mod q are eliminated. Note that factors 2^(-32) mod q are introduced by multiplication and reduction of values not in montgomery domain.

Produces the result of the inverse NTT transformation with a montgomery factor of (2^32 mod q) added (!). See above.

Definition at line 78 of file dilithium_polynomial.h.

                                                              {
         size_t j = 0;
         size_t k = N;
         for(size_t len = 1; len < N; len <<= 1) {
            for(size_t start = 0; start < N; start = j + len) {
               const T zeta = -zetas[--k];
               for(j = start; j < start + len; ++j) {
                  T t = coeffs[j];
                  coeffs[j] = t + coeffs[j + len];
                  coeffs[j + len] = t - coeffs[j + len];
                  // Zetas contain the montgomery parameter 2^32 mod q
                  coeffs[j + len] = fqmul(zeta, coeffs[j + len]);
               }
            }
         }
 
         for(auto& coeff : coeffs) {
            coeff = fqmul(coeff, F_WITH_MONTY_SQUARED);
         }
      }

References Botan::CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >::F_WITH_MONTY_SQUARED, Botan::CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >::fqmul(), Botan::CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >::N, and Botan::CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >::zetas.

◆ ntt()

constexpr void Botan::DilithiumPolyTraits::ntt ( std::span< T, N > coeffs )

inlinestaticconstexpr

NIST FIPS 204, Algorithm 41 (NTT)

Note: ntt(), inverse_ntt() and operator* have side effects on the montgomery factor of the involved coefficients! It is assumed that EXACTLY ONE vector or matrix multiplication is performed between transforming in and out of NTT domain.

Produces the result of the NTT transformation without any montgomery factors in the coefficients.

Definition at line 50 of file dilithium_polynomial.h.

                                                      {
         size_t j = 0;
         size_t k = 0;
 
         for(size_t len = N / 2; len > 0; len >>= 1) {
            for(size_t start = 0; start < N; start = j + len) {
               const T zeta = zetas[++k];
               for(j = start; j < start + len; ++j) {
                  // Zetas contain the montgomery parameter 2^32 mod q
                  T t = fqmul(zeta, coeffs[j + len]);
                  coeffs[j + len] = coeffs[j] - t;
                  coeffs[j] = coeffs[j] + t;
               }
            }
         }
      }

References Botan::CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >::fqmul(), Botan::CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >::N, and Botan::CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >::zetas.

◆ poly_add()

constexpr void Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::poly_add	(	std::span< T, N >	result,
		std::span< const T, N >	lhs,
		std::span< const T, N >	rhs )

inlinestaticconstexprinherited

Definition at line 99 of file pqcrystals.h.

                                                                                                             {
         for(size_t i = 0; i < N; ++i) {
            result[i] = lhs[i] + rhs[i];
         }
      }

◆ poly_cadd_q()

constexpr void Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::poly_cadd_q ( std::span< T, N > coeffs )

inlinestaticconstexprinherited

Adds Q if the coefficient is negative.

Definition at line 112 of file pqcrystals.h.

                                                              {
         for(auto& coeff : coeffs) {
            using unsigned_T = std::make_unsigned_t<T>;
            const auto is_negative = CT::Mask<unsigned_T>::expand_top_bit(static_cast<unsigned_T>(coeff));
            coeff += is_negative.if_set_return(Q);
         }
      }

◆ poly_in_polyvec()

constexpr std::span< U, N > Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::poly_in_polyvec	(	std::span< U >	polyvec,
		size_t	index )

inlinestaticconstexprprotectedinherited

Returns: the index-th polynomial in the polynomial vector polyvec.

Definition at line 89 of file pqcrystals.h.

                                                                                       {
         BOTAN_DEBUG_ASSERT(polyvec.size() % N == 0);
         BOTAN_DEBUG_ASSERT(polyvec.size() / N > index);
         auto polyspan = polyvec.subspan(index * N, N);
         return std::span<U, N>{polyspan.data(), polyspan.size()};
      }

◆ poly_pointwise_montgomery()

constexpr void Botan::DilithiumPolyTraits::poly_pointwise_montgomery	(	std::span< T, N >	result,
		std::span< const T, N >	lhs,
		std::span< const T, N >	rhs )

inlinestaticconstexpr

Multiplication of two polynomials lhs and rhs in NTT domain.

Produces the result of the multiplication in NTT domain, with a factor of (2^-32 mod q) in each element due to montgomery reduction.

Definition at line 105 of file dilithium_polynomial.h.

                                                                               {
         for(size_t i = 0; i < N; ++i) {
            result[i] = fqmul(lhs[i], rhs[i]);
         }
      }

References Botan::CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >::fqmul(), and Botan::CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >::N.

◆ poly_sub()

constexpr void Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::poly_sub	(	std::span< T, N >	result,
		std::span< const T, N >	lhs,
		std::span< const T, N >	rhs )

inlinestaticconstexprinherited

Definition at line 105 of file pqcrystals.h.

                                                                                                             {
         for(size_t i = 0; i < N; ++i) {
            result[i] = lhs[i] - rhs[i];
         }
      }

◆ polys_in_polyvec()

constexpr size_t Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::polys_in_polyvec ( std::span< const T > polyvec )

inlinestaticconstexprprotectedinherited

Returns: the number of polynomials in the polynomial vector polyvec.

Definition at line 81 of file pqcrystals.h.

                                                                         {
         BOTAN_DEBUG_ASSERT(polyvec.size() % N == 0);
         return polyvec.size() / N;
      }

◆ polyvec_pointwise_acc_montgomery()

constexpr void Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::polyvec_pointwise_acc_montgomery	(	std::span< T, N >	w,
		std::span< const T >	u,
		std::span< const T >	v )

inlinestaticconstexprinherited

Multiplication and accumulation of 2 polynomial vectors u and v.

Definition at line 129 of file pqcrystals.h.

                                                                                 {
         clear_mem(w);
         std::array<T, N> t{};
         for(size_t i = 0; i < polys_in_polyvec(u); ++i) {
            DerivedT::poly_pointwise_montgomery(t, poly_in_polyvec(u, i), poly_in_polyvec(v, i));
            poly_add(w, w, t);
         }
         barrett_reduce(w);
      }