Botan 3.14.1
Crypto and TLS for C&
kyber_polynomial.h
Go to the documentation of this file.
1/*
2 * Crystals Kyber Polynomial Adapter
3 *
4 * (C) 2021-2024 Jack Lloyd
5 * (C) 2021-2022 Manuel Glaser and Michael Boric, Rohde & Schwarz Cybersecurity
6 * (C) 2021-2022 René Meusel and Hannes Rantzsch, neXenio GmbH
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_KYBER_POLYNOMIAL_H_
13#define BOTAN_KYBER_POLYNOMIAL_H_
14
15#include <botan/internal/kyber_constants.h>
16#include <botan/internal/pqcrystals.h>
17
18#if defined(BOTAN_HAS_KYBER_AVX2)
19 #include <botan/internal/cpuid.h>
20 #include <botan/internal/kyber_avx2.h>
21#endif
22
23#include <type_traits>
24
25namespace Botan {
26
28
29class KyberPolyTraits final : public CRYSTALS::Trait_Base<KyberConstants, KyberPolyTraits> {
30 private:
32
33 constexpr static T montgomery_reduce_coefficient(T2 a) {
34 const T u = static_cast<T>(static_cast<T>(a) * Q_inverse);
35 auto t = static_cast<T2>(u) * Q;
36 t = a - t;
37 t >>= sizeof(T) * 8;
38 return static_cast<T>(t);
39 }
40
41 constexpr static T barrett_reduce_coefficient(T a) {
42 const T t = static_cast<T>(((BARRETT_V * a) >> 26) * Q);
43 return static_cast<T>(a - t);
44 }
45
46 public:
47 /// Constants shared with the SIMD kernels
48 static constexpr const std::array<T, N / 2>& zeta_table() { return zetas; }
49
50 static constexpr T q_inverse() { return Q_inverse; }
51
52 static constexpr T inverse_ntt_scale() { return F_WITH_MONTY_SQUARED; }
53
54 /**
55 * NIST FIPS 203, Algorithm 9 (NTT)
56 *
57 * Produces the result of the NTT transformation without any montgomery
58 * factors in the coefficients. Zetas are pre-computed and stored in the
59 * zetas array. The zeta values contain the montgomery factor 2^16 mod q.
60 */
61 constexpr static void ntt(std::span<T, N> p) {
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 }
81
82 /**
83 * NIST FIPS 203, Algorithm 10 (NTT^-1)
84 *
85 * The output is effectively multiplied by the montgomery parameter 2^16
86 * mod q so that the input factors 2^(-16) mod q are eliminated. Note
87 * that factors 2^(-16) mod q are introduced by multiplication and
88 * reduction of values not in montgomery domain.
89 *
90 * Produces the result of the inverse NTT transformation with a montgomery
91 * factor of (2^16 mod q) added (!). See above.
92 */
93 static constexpr void inverse_ntt(std::span<T, N> p) {
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 }
115
116 /**
117 * NIST FIPS 203, Algorithms 11 (MultiplyNTTs) and 12 (BaseCaseMultiply)
118 *
119 * The result contains factors of 2^(-16) mod q (i.e. the inverse montgomery factor).
120 * This factor is eliminated by the inverse NTT transformation, see above.
121 */
122 static constexpr void poly_pointwise_montgomery(std::span<T, N> result,
123 std::span<const T, N> lhs,
124 std::span<const T, N> rhs) {
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 }
156};
157
158} // namespace Botan
159
160#endif
static bool has(CPUID::Feature feat)
Definition cpuid.h:93
static constexpr void barrett_reduce(std::span< T, N > poly)
Definition pqcrystals.h:124
static constexpr T inverse_ntt_scale()
static constexpr const std::array< T, N/2 > & zeta_table()
Constants shared with the SIMD kernels.
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 inverse_ntt(std::span< T, N > p)
static constexpr T q_inverse()
static constexpr void ntt(std::span< T, N > p)
BOTAN_FN_ISA_AVX2 void inverse_ntt(std::span< int16_t, 256 > p)
BOTAN_FN_ISA_AVX2 void ntt(std::span< int16_t, 256 > p)
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)