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

#include <dilithium_polynomial.h>

Inheritance diagram for Botan::DilithiumPolyTraits:
Botan::CRYSTALS::Trait_Base< DilithiumConstants, 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 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< DilithiumConstants, DilithiumPolyTraits >

Detailed Description

Definition at line 20 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 58 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 124 of file pqcrystals.h.

◆ fqmul()

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

◆ 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 76 of file dilithium_polynomial.h.

76 {
77 size_t j = 0;
78 size_t k = N;
79 for(size_t len = 1; len < N; len <<= 1) {
80 for(size_t start = 0; start < N; start = j + len) {
81 const T zeta = -zetas[--k];
82 for(j = start; j < start + len; ++j) {
83 const T t = coeffs[j];
84 coeffs[j] = t + coeffs[j + len];
85 coeffs[j + len] = t - coeffs[j + len];
86 // Zetas contain the montgomery parameter 2^32 mod q
87 coeffs[j + len] = fqmul(zeta, coeffs[j + len]);
88 }
89 }
90 }
91
92 for(auto& coeff : coeffs) {
93 coeff = fqmul(coeff, F_WITH_MONTY_SQUARED);
94 }
95 }

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 48 of file dilithium_polynomial.h.

48 {
49 size_t j = 0;
50 size_t k = 0;
51
52 for(size_t len = N / 2; len > 0; len >>= 1) {
53 for(size_t start = 0; start < N; start = j + len) {
54 const T zeta = zetas[++k];
55 for(j = start; j < start + len; ++j) {
56 // Zetas contain the montgomery parameter 2^32 mod q
57 const T t = fqmul(zeta, coeffs[j + len]);
58 coeffs[j + len] = coeffs[j] - t;
59 coeffs[j] = coeffs[j] + t;
60 }
61 }
62 }
63 }

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 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, DilithiumPolyTraits >::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, 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 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::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 103 of file dilithium_polynomial.h.

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

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 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, DilithiumPolyTraits >::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, 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 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 barrett_reduce(std::span< T, N > poly)
Definition pqcrystals.h:124
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

◆ to_montgomery()

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

Definition at line 122 of file pqcrystals.h.

122{ return fqmul(a, MONTY_SQUARED); }

◆ CRYSTALS::Trait_Base< DilithiumConstants, DilithiumPolyTraits >

Member Data Documentation

◆ BARRETT_V

T Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::BARRETT_V
staticconstexprinherited

Definition at line 55 of file pqcrystals.h.

◆ F_WITH_MONTY_SQUARED

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

Definition at line 73 of file pqcrystals.h.

Referenced by Botan::DilithiumPolyTraits::inverse_ntt().

◆ MONTY

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

Definition at line 64 of file pqcrystals.h.

◆ MONTY_SQUARED

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

Definition at line 65 of file pqcrystals.h.

◆ N

◆ Q

◆ Q_inverse

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

◆ zetas

auto Botan::CRYSTALS::Trait_Base< ConstantsT, DilithiumPolyTraits >::zetas
staticconstexprprotectedinherited

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