#include <kyber_polynomial.h>

Inheritance diagram for Botan::KyberPolyTraits:

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 > p)
static constexpr void	ntt (std::span< T, N > p)
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< KyberConstants, KyberPolyTraits >

Detailed Description

Definition at line 25 of file kyber_polynomial.h.

Member Typedef Documentation

◆ T

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

inherited

Definition at line 51 of file pqcrystals.h.

◆ T2

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

protectedinherited

Definition at line 56 of file pqcrystals.h.

Member Function Documentation

◆ barrett_reduce()

constexpr void Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::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);
         }
      }

Referenced by Botan::KyberPolyTraits::ntt().

◆ fqmul()

constexpr T Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::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::KyberPolyTraits::inverse_ntt(), Botan::KyberPolyTraits::ntt(), and Botan::KyberPolyTraits::poly_pointwise_montgomery().

◆ inverse_ntt()

constexpr void Botan::KyberPolyTraits::inverse_ntt ( std::span< T, N > p )

inlinestaticconstexpr

NIST FIPS 203, Algorithm 10 (NTT^-1)

The output is effectively multiplied by the montgomery parameter 2^16 mod q so that the input factors 2^(-16) mod q are eliminated. Note that factors 2^(-16) 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^16 mod q) added (!). See above.

Definition at line 77 of file kyber_polynomial.h.

                                                         {
         for(size_t len = 2, i = 127; len <= N / 2; len *= 2) {
            for(size_t start = 0, j = 0; start < N; start = j + len) {
               const auto zeta = zetas[i--];
               for(j = start; j < start + len; ++j) {
                  const auto t = p[j];
                  p[j] = barrett_reduce_coefficient(static_cast<T>(t + p[j + len]));
                  p[j + len] = fqmul(zeta, static_cast<T>(p[j + len] - t));
               }
            }
         }
 
         for(auto& c : p) {
            c = fqmul(c, F_WITH_MONTY_SQUARED);
         }
      }

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

◆ ntt()

constexpr void Botan::KyberPolyTraits::ntt ( std::span< T, N > p )

inlinestaticconstexpr

NIST FIPS 203, Algorithm 9 (NTT)

Produces the result of the NTT transformation without any montgomery factors in the coefficients. Zetas are pre-computed and stored in the zetas array. The zeta values contain the montgomery factor 2^16 mod q.

Definition at line 51 of file kyber_polynomial.h.

                                                 {
         for(size_t len = N / 2, i = 0; len >= 2; len /= 2) {
            for(size_t start = 0, j = 0; start < N; start = j + len) {
               const auto zeta = zetas[++i];
               for(j = start; j < start + len; ++j) {
                  const auto t = fqmul(zeta, p[j + len]);
                  p[j + len] = static_cast<T>(p[j] - t);
                  p[j] = static_cast<T>(p[j] + t);
               }
            }
         }
 
         barrett_reduce(p);
      }

References Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::barrett_reduce(), Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::fqmul(), Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::N, and Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::zetas.

◆ poly_add()

constexpr void Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::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, KyberPolyTraits >::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, KyberPolyTraits >::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::KyberPolyTraits::poly_pointwise_montgomery	(	std::span< T, N >	result,
		std::span< const T, N >	lhs,
		std::span< const T, N >	rhs )

inlinestaticconstexpr

NIST FIPS 203, Algorithms 11 (MultiplyNTTs) and 12 (BaseCaseMultiply)

The result contains factors of 2^(-16) mod q (i.e. the inverse montgomery factor). This factor is eliminated by the inverse NTT transformation, see above.

NIST FIPS 203, Algorithm 12 (BaseCaseMultiply)

Definition at line 100 of file kyber_polynomial.h.

                                                                               {
         /**
          * NIST FIPS 203, Algorithm 12 (BaseCaseMultiply)
          */
         auto basemul = [](const auto a, const auto b, const T zeta) -> std::tuple<T, T> {
            return {static_cast<T>(fqmul(a[0], b[0]) + fqmul(fqmul(a[1], b[1]), zeta)),
                    static_cast<T>(fqmul(a[0], b[1]) + fqmul(a[1], b[0]))};
         };
 
         auto Tq_elem_count = [](auto p) { return p.size() / 2; };
 
         auto Tq_elem = [](auto p, size_t i) {
            if constexpr(std::is_const_v<typename decltype(p)::element_type>) {
               return std::array<T, 2>{p[2 * i], p[2 * i + 1]};
            } else {
               return std::tuple<T&, T&>{p[2 * i], p[2 * i + 1]};
            }
         };
 
         for(size_t i = 0; i < Tq_elem_count(result) / 2; ++i) {
            const T zeta = zetas[64 + i];
            const T nzeta = static_cast<T>(-zeta);
            Tq_elem(result, 2 * i) = basemul(Tq_elem(lhs, 2 * i), Tq_elem(rhs, 2 * i), zeta);
            Tq_elem(result, 2 * i + 1) = basemul(Tq_elem(lhs, 2 * i + 1), Tq_elem(rhs, 2 * i + 1), nzeta);
         }
      }

References Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::fqmul(), and Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::zetas.

◆ poly_sub()

constexpr void Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::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, KyberPolyTraits >::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, KyberPolyTraits >::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);
      }