Botan 3.14.1
Crypto and TLS for C&
dilithium_polynomial.h
Go to the documentation of this file.
1/*
2 * Crystals Dilithium Polynomial Adapter
3 *
4 * (C) 2022-2023 Jack Lloyd
5 * (C) 2022 Manuel Glaser - Rohde & Schwarz Cybersecurity
6 * (C) 2022-2023 Michael Boric, René Meusel - Rohde & Schwarz Cybersecurity
7 * (C) 2024 René Meusel, Rohde & Schwarz Cybersecurity
8 *
9 * Botan is released under the Simplified BSD License (see license.txt)
10 */
11
12#ifndef BOTAN_DILITHIUM_POLYNOMIAL_H_
13#define BOTAN_DILITHIUM_POLYNOMIAL_H_
14
15#include <botan/internal/dilithium_constants.h>
16#include <botan/internal/pqcrystals.h>
17
18namespace Botan {
19
20class DilithiumPolyTraits final : public CRYSTALS::Trait_Base<DilithiumConstants, DilithiumPolyTraits> {
21 private:
23
24 static constexpr T montgomery_reduce_coefficient(T2 a) {
25 const T2 t = static_cast<T>(static_cast<T2>(static_cast<T>(a)) * Q_inverse);
26 return static_cast<T>((a - static_cast<T2>(t) * Q) >> (sizeof(T) * 8));
27 }
28
29 static constexpr T barrett_reduce_coefficient(T a) {
30 // 2**22 is roughly Q/2 and 2**23 is roughly Q
31 const T t = (a + (1 << 22)) >> 23;
32 a = a - t * Q;
33 return a;
34 }
35
36 public:
37 /**
38 * NIST FIPS 204, Algorithm 41 (NTT)
39 *
40 * Note: ntt(), inverse_ntt() and operator* have side effects on the
41 * montgomery factor of the involved coefficients!
42 * It is assumed that EXACTLY ONE vector or matrix multiplication
43 * is performed between transforming in and out of NTT domain.
44 *
45 * Produces the result of the NTT transformation without any montgomery
46 * factors in the coefficients.
47 */
48 static constexpr void ntt(std::span<T, N> coeffs) {
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 }
64
65 /**
66 * NIST FIPS 204, Algorithm 42 (NTT^-1).
67 *
68 * The output is effectively multiplied by the montgomery parameter 2^32
69 * mod q so that the input factors 2^(-32) mod q are eliminated. Note
70 * that factors 2^(-32) mod q are introduced by multiplication and
71 * reduction of values not in montgomery domain.
72 *
73 * Produces the result of the inverse NTT transformation with a montgomery
74 * factor of (2^32 mod q) added (!). See above.
75 */
76 static constexpr void inverse_ntt(std::span<T, N> coeffs) {
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 }
96
97 /**
98 * Multiplication of two polynomials @p lhs and @p rhs in NTT domain.
99 *
100 * Produces the result of the multiplication in NTT domain, with a factor
101 * of (2^-32 mod q) in each element due to montgomery reduction.
102 */
103 static constexpr void poly_pointwise_montgomery(std::span<T, N> result,
104 std::span<const T, N> lhs,
105 std::span<const T, N> rhs) {
106 for(size_t i = 0; i < N; ++i) {
107 result[i] = fqmul(lhs[i], rhs[i]);
108 }
109 }
110};
111
112} // namespace Botan
113
114#endif
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 ntt(std::span< T, N > coeffs)
static constexpr void inverse_ntt(std::span< T, N > coeffs)