Botan 3.14.1
Crypto and TLS for C&
Botan::KyberPolyTraits Class Referencefinal

#include <kyber_polynomial.h>

Inheritance diagram for Botan::KyberPolyTraits:
Botan::CRYSTALS::Trait_Base< KyberConstants, 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 T inverse_ntt_scale ()
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 q_inverse ()
static constexpr T to_montgomery (T a)
static constexpr const std::array< T, N/2 > & zeta_table ()
 Constants shared with the SIMD kernels.

Static Public Attributes

static constexpr T BARRETT_V
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 29 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 58 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 124 of file pqcrystals.h.

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

◆ fqmul()

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

◆ 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 93 of file kyber_polynomial.h.

93 {
94#if defined(BOTAN_HAS_KYBER_AVX2)
95 if(!std::is_constant_evaluated() && CPUID::has(CPUID::Feature::AVX2)) {
97 }
98#endif
99
100 for(size_t len = 2, i = 127; len <= N / 2; len *= 2) {
101 for(size_t start = 0, j = 0; start < N; start = j + len) {
102 const auto zeta = zetas[i--];
103 for(j = start; j < start + len; ++j) {
104 const auto t = p[j];
105 p[j] = barrett_reduce_coefficient(static_cast<T>(t + p[j + len]));
106 p[j + len] = fqmul(zeta, static_cast<T>(p[j + len] - t));
107 }
108 }
109 }
110
111 for(auto& c : p) {
113 }
114 }
static bool has(CPUID::Feature feat)
Definition cpuid.h:93
BOTAN_FN_ISA_AVX2 void inverse_ntt(std::span< int16_t, 256 > p)

References Botan::CPUFeature::AVX2, Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::F_WITH_MONTY_SQUARED, Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::fqmul(), Botan::CPUID::has(), Botan::Kyber_AVX2::inverse_ntt(), Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::N, and Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::zetas.

◆ inverse_ntt_scale()

constexpr T Botan::KyberPolyTraits::inverse_ntt_scale ( )
inlinestaticconstexpr

◆ 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 61 of file kyber_polynomial.h.

61 {
62#if defined(BOTAN_HAS_KYBER_AVX2)
63 if(!std::is_constant_evaluated() && CPUID::has(CPUID::Feature::AVX2)) {
64 return Kyber_AVX2::ntt(p);
65 }
66#endif
67
68 for(size_t len = N / 2, i = 0; len >= 2; len /= 2) {
69 for(size_t start = 0, j = 0; start < N; start = j + len) {
70 const auto zeta = zetas[++i];
71 for(j = start; j < start + len; ++j) {
72 const auto t = fqmul(zeta, p[j + len]);
73 p[j + len] = static_cast<T>(p[j] - t);
74 p[j] = static_cast<T>(p[j] + t);
75 }
76 }
77 }
78
80 }
static constexpr void barrett_reduce(std::span< T, N > poly)
Definition pqcrystals.h:124
BOTAN_FN_ISA_AVX2 void ntt(std::span< int16_t, 256 > p)

References Botan::CPUFeature::AVX2, Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::barrett_reduce(), Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::fqmul(), Botan::CPUID::has(), Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::N, Botan::Kyber_AVX2::ntt(), 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 101 of file pqcrystals.h.

101 {
102 for(size_t i = 0; i < N; ++i) {
103 result[i] = lhs[i] + rhs[i];
104 }
105 }

◆ 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 114 of file pqcrystals.h.

114 {
115 for(auto& coeff : coeffs) {
118 coeff += is_negative.if_set_return(Q);
119 }
120 }
static constexpr Mask< T > expand_top_bit(T v)
Definition ct_utils.h:420

◆ 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 91 of file pqcrystals.h.

91 {
92 BOTAN_DEBUG_ASSERT(polyvec.size() % N == 0);
94 const auto polyspan = polyvec.subspan(index * N, N);
95 return std::span<U, N>{polyspan.data(), polyspan.size()};
96 }
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136

◆ 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 122 of file kyber_polynomial.h.

124 {
125#if defined(BOTAN_HAS_KYBER_AVX2)
126 if(!std::is_constant_evaluated() && CPUID::has(CPUID::Feature::AVX2)) {
127 return Kyber_AVX2::poly_pointwise_montgomery(result, lhs, rhs);
128 }
129#endif
130
131 /**
132 * NIST FIPS 203, Algorithm 12 (BaseCaseMultiply)
133 */
134 const auto basemul = [](const auto a, const auto b, const T zeta) -> std::tuple<T, T> {
135 return {static_cast<T>(fqmul(a[0], b[0]) + fqmul(fqmul(a[1], b[1]), zeta)),
136 static_cast<T>(fqmul(a[0], b[1]) + fqmul(a[1], b[0]))};
137 };
138
139 const auto Tq_elem_count = [](auto p) { return p.size() / 2; };
140
141 const auto Tq_elem = [](auto p, size_t i) {
142 if constexpr(std::is_const_v<typename decltype(p)::element_type>) {
143 return std::array<T, 2>{p[2 * i], p[2 * i + 1]};
144 } else {
145 return std::tuple<T&, T&>{p[2 * i], p[2 * i + 1]};
146 }
147 };
148
149 for(size_t i = 0; i < Tq_elem_count(result) / 2; ++i) {
150 const T zeta = zetas[64 + i];
151 const T nzeta = static_cast<T>(-zeta);
152 Tq_elem(result, 2 * i) = basemul(Tq_elem(lhs, 2 * i), Tq_elem(rhs, 2 * i), zeta);
153 Tq_elem(result, 2 * i + 1) = basemul(Tq_elem(lhs, 2 * i + 1), Tq_elem(rhs, 2 * i + 1), nzeta);
154 }
155 }
BOTAN_FN_ISA_AVX2 void poly_pointwise_montgomery(std::span< int16_t, 256 > result, std::span< const int16_t, 256 > lhs, std::span< const int16_t, 256 > rhs)

References Botan::CPUFeature::AVX2, Botan::CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >::fqmul(), Botan::CPUID::has(), Botan::Kyber_AVX2::poly_pointwise_montgomery(), 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 107 of file pqcrystals.h.

107 {
108 for(size_t i = 0; i < N; ++i) {
109 result[i] = lhs[i] - rhs[i];
110 }
111 }

◆ 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 83 of file pqcrystals.h.

83 {
84 BOTAN_DEBUG_ASSERT(polyvec.size() % N == 0);
85 return polyvec.size() / N;
86 }

◆ 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 131 of file pqcrystals.h.

133 {
134 clear_mem(w);
136 for(size_t i = 0; i < polys_in_polyvec(u); ++i) {
138 poly_add(w, w, t);
139 }
141 }
static constexpr void poly_add(std::span< T, N > result, std::span< const T, N > lhs, std::span< const T, N > rhs)
Definition pqcrystals.h:101
static constexpr std::span< U, N > poly_in_polyvec(std::span< U > polyvec, size_t index)
Definition pqcrystals.h:91
static constexpr size_t polys_in_polyvec(std::span< const T > polyvec)
Definition pqcrystals.h:83
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118

◆ q_inverse()

constexpr T Botan::KyberPolyTraits::q_inverse ( )
inlinestaticconstexpr

◆ to_montgomery()

constexpr T Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::to_montgomery ( T a)
inlinestaticconstexprinherited

Definition at line 122 of file pqcrystals.h.

122{ return fqmul(a, MONTY_SQUARED); }

◆ zeta_table()

constexpr const std::array< T, N/2 > & Botan::KyberPolyTraits::zeta_table ( )
inlinestaticconstexpr

◆ CRYSTALS::Trait_Base< KyberConstants, KyberPolyTraits >

Member Data Documentation

◆ BARRETT_V

◆ F_WITH_MONTY_SQUARED

T Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::F_WITH_MONTY_SQUARED
staticconstexprprotectedinherited

◆ MONTY

T Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::MONTY
staticconstexprprotectedinherited

Definition at line 64 of file pqcrystals.h.

◆ MONTY_SQUARED

T Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::MONTY_SQUARED
staticconstexprprotectedinherited

Definition at line 65 of file pqcrystals.h.

◆ N

◆ Q

T Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::Q
staticconstexprinherited

◆ Q_inverse

T Botan::CRYSTALS::Trait_Base< ConstantsT, KyberPolyTraits >::Q_inverse
staticconstexprprotectedinherited

◆ zetas


The documentation for this class was generated from the following file: