Botan 3.14.1
Crypto and TLS for C&
pqcrystals.h
Go to the documentation of this file.
1/*
2 * PQ CRYSTALS Common Structures
3 *
4 * Further changes
5 * (C) 2021-2024 Jack Lloyd
6 * (C) 2021-2022 Manuel Glaser and Michael Boric, Rohde & Schwarz Cybersecurity
7 * (C) 2021-2022 René Meusel and Hannes Rantzsch, neXenio GmbH
8 * (C) 2024 René Meusel, Fabian Albert, Rohde & Schwarz Cybersecurity
9 *
10 * Botan is released under the Simplified BSD License (see license.txt)
11 */
12
13#ifndef BOTAN_PQ_CRYSTALS_H_
14#define BOTAN_PQ_CRYSTALS_H_
15
16#include <concepts>
17#include <limits>
18#include <span>
19#include <vector>
20
21#include <botan/assert.h>
22#include <botan/mem_ops.h>
23#include <botan/internal/ct_utils.h>
24#include <botan/internal/pqcrystals_helpers.h>
25
26namespace Botan::CRYSTALS {
27
28enum class Domain : uint8_t { Normal, NTT };
29
30template <typename T>
32 std::signed_integral<typename T::T> && std::integral<decltype(T::N)> && std::integral<decltype(T::Q)> &&
33 std::integral<decltype(T::F)> && std::unsigned_integral<decltype(T::NTT_Degree)> &&
34 std::integral<decltype(T::ROOT_OF_UNITY)>;
35
36/**
37 * This implements basic polynomial operations for Kyber and Dilithium
38 * based on the given algorithm constants (@p ConstantsT) and back-
39 * references some of the operations to the actual implementation
40 * into the derived class (CRTP @p DerivedT).
41 *
42 * Polynomial parameters are passed as spans of coefficients for maximum
43 * flexibility.
44 *
45 * It is assumed that this is subclassed with the actual implementation
46 * with establishing a CRTP back-reference.
47 */
48template <crystals_constants ConstantsT, typename DerivedT>
50 public:
51 using T = typename ConstantsT::T;
52 static constexpr T N = ConstantsT::N;
53 static constexpr T Q = ConstantsT::Q;
54
55 static constexpr T BARRETT_V = ((1U << 26) + Q / 2) / Q;
56
57 protected:
59
60 /// \name Pre-computed algorithm constants
61 /// @{
62
63 static constexpr T Q_inverse = modular_inverse(Q);
64 static constexpr T MONTY = montgomery_R(Q);
65 static constexpr T MONTY_SQUARED = montgomery_R2(Q);
66
67 // Contains the constant f from Algorithm 36 multiplied two times by
68 // the montgomery parameter, i.e. 2^(2*32) mod q. The first montgomery
69 // factor is then removed by the reduction in the loop. The second one
70 // is required to eliminate factors 2^(-32) mod q in coeffs introduced
71 // by previous montgomery multiplications in a single vector/matrix
72 // multiplication operation.
73 static constexpr T F_WITH_MONTY_SQUARED = (static_cast<T2>(ConstantsT::F) * MONTY_SQUARED) % Q;
74
75 static constexpr auto zetas = precompute_zetas<ConstantsT::NTT_Degree>(Q, MONTY, ConstantsT::ROOT_OF_UNITY);
76
77 /// @}
78
79 protected:
80 Trait_Base() = default; // NOLINT(*crtp-constructor-accessibility)
81
82 /// @returns the number of polynomials in the polynomial vector @p polyvec.
83 static constexpr size_t polys_in_polyvec(std::span<const T> polyvec) {
84 BOTAN_DEBUG_ASSERT(polyvec.size() % N == 0);
85 return polyvec.size() / N;
86 }
87
88 /// @returns the @p index-th polynomial in the polynomial vector @p polyvec.
89 template <typename U>
90 requires(std::same_as<T, U> || std::same_as<const T, U>)
91 static constexpr std::span<U, N> poly_in_polyvec(std::span<U> polyvec, size_t index) {
92 BOTAN_DEBUG_ASSERT(polyvec.size() % N == 0);
93 BOTAN_DEBUG_ASSERT(polyvec.size() / N > index);
94 const auto polyspan = polyvec.subspan(index * N, N);
95 return std::span<U, N>{polyspan.data(), polyspan.size()};
96 }
97
98 static constexpr T fqmul(T a, T b) { return DerivedT::montgomery_reduce_coefficient(static_cast<T2>(a) * b); }
99
100 public:
101 static constexpr void poly_add(std::span<T, N> result, std::span<const T, N> lhs, std::span<const T, N> rhs) {
102 for(size_t i = 0; i < N; ++i) {
103 result[i] = lhs[i] + rhs[i];
104 }
105 }
106
107 static constexpr void poly_sub(std::span<T, N> result, std::span<const T, N> lhs, std::span<const T, N> rhs) {
108 for(size_t i = 0; i < N; ++i) {
109 result[i] = lhs[i] - rhs[i];
110 }
111 }
112
113 /// Adds Q if the coefficient is negative.
114 static constexpr void poly_cadd_q(std::span<T, N> coeffs) {
115 for(auto& coeff : coeffs) {
116 using unsigned_T = std::make_unsigned_t<T>;
117 const auto is_negative = CT::Mask<unsigned_T>::expand_top_bit(static_cast<unsigned_T>(coeff));
118 coeff += is_negative.if_set_return(Q);
119 }
120 }
121
122 static constexpr T to_montgomery(T a) { return fqmul(a, MONTY_SQUARED); }
123
124 constexpr static void barrett_reduce(std::span<T, N> poly) {
125 for(auto& coeff : poly) {
126 coeff = DerivedT::barrett_reduce_coefficient(coeff);
127 }
128 }
129
130 /// Multiplication and accumulation of 2 polynomial vectors @p u and @p v.
131 static constexpr void polyvec_pointwise_acc_montgomery(std::span<T, N> w,
132 std::span<const T> u,
133 std::span<const T> v) {
134 clear_mem(w);
135 std::array<T, N> t{};
136 for(size_t i = 0; i < polys_in_polyvec(u); ++i) {
137 DerivedT::poly_pointwise_montgomery(t, poly_in_polyvec(u, i), poly_in_polyvec(v, i));
138 poly_add(w, w, t);
139 }
141 }
142};
143
144template <typename T>
146 std::signed_integral<typename T::T> && sizeof(typename T::T) <= 4 && std::integral<decltype(T::N)> &&
147 T::N % 2 == 0 &&
148 requires(std::span<typename T::T, T::N> polyspan, std::span<typename T::T> polyvecspan, typename T::T coeff) {
149 { T::to_montgomery(coeff) };
150 { T::barrett_reduce(polyspan) };
151 { T::poly_cadd_q(polyspan) };
152 { T::ntt(polyspan) };
153 { T::inverse_ntt(polyspan) };
154 { T::poly_pointwise_montgomery(polyspan, polyspan, polyspan) };
155 { T::polyvec_pointwise_acc_montgomery(polyspan, polyvecspan, polyvecspan) };
156 };
157
158namespace detail {
159
160/**
161 * Converts polynomials or polynomial vectors from one domain to another.
162 */
163template <Domain To, template <typename, Domain> class StructureT, crystals_trait Trait, Domain From>
164 requires(To != From)
165StructureT<Trait, To> domain_cast(StructureT<Trait, From>&& p) {
166 // The public factory method `from_domain_cast` is just a workaround for
167 // Xcode and NDK not understanding the friend declaration to allow this
168 // to directly call the private constructor.
169 return StructureT<Trait, To>::from_domain_cast(std::move(p));
170}
171
172/**
173 * Ensures that all values in the @p range are within the range [min, max]
174 * using constant-time operations.
175 *
176 * @returns true if all values are within the range, false otherwise.
177 */
178template <std::integral T, size_t N = std::dynamic_extent>
179constexpr static bool ct_all_within_range(std::span<const T, N> range, T min, T max)
180 requires(sizeof(T) <= 4)
181{
182 BOTAN_DEBUG_ASSERT(min < max);
183
184 using unsigned_T = std::make_unsigned_t<T>;
185 const auto map = [](T v) -> unsigned_T {
186 if constexpr(std::signed_integral<T>) {
187 constexpr int64_t offset = -static_cast<int64_t>(std::numeric_limits<T>::min());
188 return static_cast<unsigned_T>(static_cast<int64_t>(v) + offset);
189 } else {
190 return v;
191 }
192 };
193
194 const auto umin = map(min);
195 const auto umax = map(max);
196
197 auto mask = CT::Mask<unsigned_T>::set();
198 for(const T c : range) {
199 mask &= CT::Mask<unsigned_T>::is_within_range(map(c), umin, umax);
200 }
201 return mask.as_bool();
202}
203
204} // namespace detail
205
206/**
207 * Represents a polynomial with Trait::N coefficients of type Trait::T.
208 * The domain of the polynomial can be either Domain::Normal or Domain::NTT and
209 * this information is represented in the C++ type system.
210 *
211 * Polynomials may either own their storage of piggy-back on external storage
212 * when they are part of a PolynomialVector.
213 */
214template <crystals_trait Trait, Domain D = Domain::Normal>
216 private:
217 using ThisPolynomial = Polynomial<Trait, D>;
218 using T = typename Trait::T;
219
220 private:
221 // TODO: perhaps secure vector
222 std::vector<T> m_coeffs_storage;
223 std::span<T, Trait::N> m_coeffs;
224
225 private:
226 template <crystals_trait OtherTrait, Domain OtherD>
227 friend class Polynomial;
228
229 template <Domain To, template <typename, Domain> class StructureT, crystals_trait C, Domain From>
230 requires(To != From)
231 friend StructureT<C, To> detail::domain_cast(StructureT<C, From>&&);
232
233 /**
234 * This constructor is used to convert a Polynomial from one domain to another.
235 * The friend declarations above facilitate this.
236 */
237 template <Domain OtherD>
238 requires(D != OtherD)
239 explicit Polynomial(Polynomial<Trait, OtherD>&& other) noexcept : // NOLINT(*-rvalue-reference-param-not-moved)
240 m_coeffs_storage(std::move(other.m_coeffs_storage)),
241 m_coeffs(owns_storage() ? std::span<T, Trait::N>(m_coeffs_storage) : other.m_coeffs) {}
242
243 public:
244 // Workaround, because Xcode and NDK don't understand the
245 // `detail::domain_cast` friend declaration.
246 //
247 // TODO: Try to remove this and use the c'tor directly in
248 // `detail::domain_cast` after updating the compilers.
249 template <Domain OtherD>
250 requires(D != OtherD)
254
255 public:
256 Polynomial() : m_coeffs_storage(Trait::N), m_coeffs(m_coeffs_storage) { BOTAN_DEBUG_ASSERT(owns_storage()); }
257
258 explicit Polynomial(std::span<T, Trait::N> coeffs) : m_coeffs(coeffs) { BOTAN_DEBUG_ASSERT(!owns_storage()); }
259
260 Polynomial(const ThisPolynomial& other) = delete;
261
262 Polynomial(ThisPolynomial&& other) noexcept :
263 m_coeffs_storage(std::move(other.m_coeffs_storage)), m_coeffs(other.m_coeffs) {}
264
265 ThisPolynomial& operator=(const ThisPolynomial& other) = delete;
266
267 ThisPolynomial& operator=(ThisPolynomial&& other) noexcept {
268 if(this != &other) {
270 m_coeffs_storage = std::move(other.m_coeffs_storage);
271 m_coeffs = std::span<T, Trait::N>(m_coeffs_storage);
272 }
273 return *this;
274 }
275
276 ~Polynomial() = default;
277
278 constexpr size_t size() const { return m_coeffs.size(); }
279
280 constexpr Domain domain() const noexcept { return D; }
281
282 ThisPolynomial clone() const {
283 ThisPolynomial res;
284 copy_mem(res.m_coeffs_storage, m_coeffs);
285 res.m_coeffs = std::span<T, Trait::N>(res.m_coeffs_storage);
287 return res;
288 }
289
290 /// @returns true if all coefficients are within the range [min, max]
291 constexpr bool ct_validate_value_range(T min, T max) const noexcept {
292 return detail::ct_all_within_range(coefficients(), min, max);
293 }
294
295 /// @returns the number of non-zero coefficients in the polynomial
296 constexpr size_t hamming_weight() const noexcept {
297 size_t weight = 0;
298 for(const auto c : m_coeffs) {
299 weight += (c != 0);
300 }
301 return weight;
302 }
303
304 std::span<T, Trait::N> coefficients() { return m_coeffs; }
305
306 std::span<const T, Trait::N> coefficients() const { return m_coeffs; }
307
308 T& operator[](size_t i) { return m_coeffs[i]; }
309
310 T operator[](size_t i) const { return m_coeffs[i]; }
311
312 decltype(auto) begin() { return m_coeffs.begin(); }
313
314 decltype(auto) begin() const { return m_coeffs.begin(); }
315
316 decltype(auto) end() { return m_coeffs.end(); }
317
318 decltype(auto) end() const { return m_coeffs.end(); }
319
320 constexpr bool owns_storage() const { return !m_coeffs_storage.empty(); }
321
322 ThisPolynomial& reduce() {
323 Trait::barrett_reduce(m_coeffs);
324 return *this;
325 }
326
327 ThisPolynomial& conditional_add_q() {
328 Trait::poly_cadd_q(m_coeffs);
329 return *this;
330 }
331
332 void _const_time_poison() const { CT::poison(m_coeffs); }
333
334 void _const_time_unpoison() const { CT::unpoison(m_coeffs); }
335
336 /**
337 * Adds two polynomials element-wise. Does not perform a reduction after the addition.
338 * Therefore this operation might cause an integer overflow.
339 */
340 decltype(auto) operator+=(const ThisPolynomial& other) {
341 Trait::poly_add(m_coeffs, m_coeffs, other.m_coeffs);
342 return *this;
343 }
344
345 /**
346 * Subtracts two polynomials element-wise. Does not perform a reduction after the subtraction.
347 * Therefore this operation might cause an integer underflow.
348 */
349 decltype(auto) operator-=(const ThisPolynomial& other) {
350 Trait::poly_sub(m_coeffs, m_coeffs, other.m_coeffs);
351 return *this;
352 }
353};
354
355template <crystals_trait Trait, Domain D = Domain::Normal>
357 private:
358 using ThisPolynomialVector = PolynomialVector<Trait, D>;
359 using T = typename Trait::T;
360
361 private:
362 std::vector<T> m_polys_storage;
363 std::vector<Polynomial<Trait, D>> m_vec;
364
365 private:
366 template <crystals_trait OtherTrait, Domain OtherD>
367 friend class PolynomialVector;
368
369 template <Domain To, template <typename, Domain> class StructureT, crystals_trait C, Domain From>
370 requires(To != From)
371 friend StructureT<C, To> detail::domain_cast(StructureT<C, From>&&);
372
373 /**
374 * This constructor is used to convert a PolynomialVector from one domain to another.
375 * The friend declarations above facilitate this.
376 */
377 template <Domain OtherD>
378 requires(D != OtherD)
379 /* NOLINTNEXTLINE(*rvalue-reference-param-not-moved) */ explicit PolynomialVector(
381 m_polys_storage(std::move(other.m_polys_storage)) {
382 BOTAN_DEBUG_ASSERT(m_polys_storage.size() % Trait::N == 0);
383 const size_t vecsize = m_polys_storage.size() / Trait::N;
384 for(size_t i = 0; i < vecsize; ++i) {
385 m_vec.emplace_back(
386 Polynomial<Trait, D>(std::span{m_polys_storage}.subspan(i * Trait::N).template first<Trait::N>()));
387 }
388 }
389
390 public:
391 // Workaround, because Xcode and NDK don't understand the
392 // `detail::domain_cast` friend declaration above.
393 //
394 // TODO: Try to remove this and use the c'tor directly in
395 // `detail::domain_cast` after updating the compilers.
396 template <Domain OtherD>
397 requires(D != OtherD)
401
402 public:
403 explicit PolynomialVector(size_t vecsize) : m_polys_storage(vecsize * Trait::N) {
404 for(size_t i = 0; i < vecsize; ++i) {
405 m_vec.emplace_back(
406 Polynomial<Trait, D>(std::span{m_polys_storage}.subspan(i * Trait::N).template first<Trait::N>()));
407 }
408 }
409
410 PolynomialVector(const ThisPolynomialVector& other) = delete;
411 PolynomialVector(ThisPolynomialVector&& other) noexcept = default;
412 ThisPolynomialVector& operator=(const ThisPolynomialVector& other) = delete;
413 ThisPolynomialVector& operator=(ThisPolynomialVector&& other) noexcept = default;
414 ~PolynomialVector() = default;
415
416 size_t size() const { return m_vec.size(); }
417
418 constexpr Domain domain() const noexcept { return D; }
419
420 ThisPolynomialVector clone() const {
421 ThisPolynomialVector res(size());
422
423 // The default-constructed PolynomialVector has set up res.m_vec to
424 // point to res.m_polys_storage. Therefore we can just copy the data
425 // into res.m_polys_storage to fill the non-owning polynomials.
426 copy_mem(res.m_polys_storage, m_polys_storage);
427
428 return res;
429 }
430
431 /// @returns the number of non-zero coefficients in the polynomial vector
432 size_t hamming_weight() const noexcept {
433 size_t weight = 0;
434 for(const auto c : m_polys_storage) {
435 weight += (c != 0);
436 }
437 return weight;
438 }
439
440 /// @returns true if all coefficients are within the range [min, max]
441 constexpr bool ct_validate_value_range(T min, T max) const noexcept {
442 return detail::ct_all_within_range(coefficients(), min, max);
443 }
444
445 std::span<T> coefficients() { return m_polys_storage; }
446
447 std::span<const T> coefficients() const { return m_polys_storage; }
448
449 ThisPolynomialVector& operator+=(const ThisPolynomialVector& other) {
450 BOTAN_ASSERT(m_vec.size() == other.m_vec.size(), "cannot add polynomial vectors of differing lengths");
451 for(size_t i = 0; i < m_vec.size(); ++i) {
452 Trait::poly_add(m_vec[i].coefficients(), m_vec[i].coefficients(), other.m_vec[i].coefficients());
453 }
454 return *this;
455 }
456
457 ThisPolynomialVector& operator-=(const ThisPolynomialVector& other) {
458 BOTAN_ASSERT(m_vec.size() == other.m_vec.size(), "cannot subtract polynomial vectors of differing lengths");
459 for(size_t i = 0; i < m_vec.size(); ++i) {
460 Trait::poly_sub(m_vec[i].coefficients(), m_vec[i].coefficients(), other.m_vec[i].coefficients());
461 }
462 return *this;
463 }
464
465 ThisPolynomialVector& reduce() {
466 for(auto& p : m_vec) {
467 Trait::barrett_reduce(p.coefficients());
468 }
469 return *this;
470 }
471
472 ThisPolynomialVector& conditional_add_q() {
473 for(auto& v : m_vec) {
474 Trait::poly_cadd_q(v.coefficients());
475 }
476 return *this;
477 }
478
479 Polynomial<Trait, D>& operator[](size_t i) { return m_vec[i]; }
480
481 const Polynomial<Trait, D>& operator[](size_t i) const { return m_vec[i]; }
482
483 /// @returns pointers to the polynomials in this vector, in order
484 std::vector<Polynomial<Trait, D>*> polynomials() {
485 std::vector<Polynomial<Trait, D>*> result;
486 result.reserve(m_vec.size());
487 for(auto& p : m_vec) {
488 result.push_back(&p);
489 }
490 return result;
491 }
492
493 decltype(auto) begin() { return m_vec.begin(); }
494
495 decltype(auto) begin() const { return m_vec.begin(); }
496
497 decltype(auto) end() { return m_vec.end(); }
498
499 decltype(auto) end() const { return m_vec.end(); }
500
501 void _const_time_poison() const { CT::poison_range(m_vec); }
502
504};
505
506template <crystals_trait Trait>
508 private:
509 using ThisPolynomialMatrix = PolynomialMatrix<Trait>;
510
511 private:
512 std::vector<PolynomialVector<Trait, Domain::NTT>> m_mat;
513
514 public:
515 explicit PolynomialMatrix(std::vector<PolynomialVector<Trait>> mat) : m_mat(std::move(mat)) {}
516
517 PolynomialMatrix(const ThisPolynomialMatrix& other) = delete;
518 PolynomialMatrix(ThisPolynomialMatrix&& other) noexcept = default;
519 ThisPolynomialMatrix& operator=(const ThisPolynomialMatrix& other) = delete;
520 ThisPolynomialMatrix& operator=(ThisPolynomialMatrix&& other) noexcept = default;
521 ~PolynomialMatrix() = default;
522
523 size_t size() const { return m_mat.size(); }
524
525 PolynomialMatrix(size_t rows, size_t cols) {
526 m_mat.reserve(rows);
527 for(size_t i = 0; i < rows; ++i) {
528 m_mat.emplace_back(cols);
529 }
530 }
531
532 PolynomialVector<Trait, Domain::NTT>& operator[](size_t i) { return m_mat[i]; }
533
534 const PolynomialVector<Trait, Domain::NTT>& operator[](size_t i) const { return m_mat[i]; }
535
536 decltype(auto) begin() { return m_mat.begin(); }
537
538 decltype(auto) begin() const { return m_mat.begin(); }
539
540 decltype(auto) end() { return m_mat.end(); }
541
542 decltype(auto) end() const { return m_mat.end(); }
543
544 void _const_time_poison() const { CT::poison_range(m_mat); }
545
547};
548
549namespace detail {
550
551template <crystals_trait Trait, Domain D>
553 for(auto& c : p) {
554 c = Trait::to_montgomery(c);
555 }
556}
557
558template <crystals_trait Trait>
562 BOTAN_ASSERT(a.size() == b.size(), "Dot product requires equally sized PolynomialVectors");
563 for(size_t i = 0; i < a.size(); ++i) {
564 out += a[i] * b[i];
565 }
566 out.reduce();
567}
568
569} // namespace detail
570
571template <crystals_trait Trait>
573 auto p_ntt = detail::domain_cast<Domain::NTT>(std::move(p));
574 Trait::ntt(p_ntt.coefficients());
575 return p_ntt;
576}
577
578template <crystals_trait Trait>
580 auto p = detail::domain_cast<Domain::Normal>(std::move(p_ntt));
581 Trait::inverse_ntt(p.coefficients());
582 return p;
583}
584
585template <crystals_trait Trait>
587 auto polyvec_ntt = detail::domain_cast<Domain::NTT>(std::move(polyvec));
588 for(auto& poly : polyvec_ntt) {
589 Trait::ntt(poly.coefficients());
590 }
591 return polyvec_ntt;
592}
593
594template <crystals_trait Trait>
596 auto polyvec = detail::domain_cast<Domain::Normal>(std::move(polyvec_ntt));
597 for(auto& poly : polyvec) {
598 Trait::inverse_ntt(poly.coefficients());
599 }
600 return polyvec;
601}
602
603template <crystals_trait Trait, Domain D>
608
609template <crystals_trait Trait, Domain D>
611 for(auto& p : polyvec) {
613 }
614 return polyvec;
615}
616
617template <crystals_trait Trait>
620 BOTAN_DEBUG_ASSERT(a.size() == b.size());
622 for(size_t i = 0; i < a.size(); ++i) {
623 Trait::poly_add(result[i].coefficients(), a[i].coefficients(), b[i].coefficients());
624 }
625 return result;
626}
627
628template <crystals_trait Trait>
632 for(size_t i = 0; i < mat.size(); ++i) {
633 Trait::polyvec_pointwise_acc_montgomery(result[i].coefficients(), mat[i].coefficients(), vec.coefficients());
634 }
635 return result;
636}
637
638template <crystals_trait Trait>
645
646template <crystals_trait Trait>
650 for(size_t i = 0; i < pv.size(); ++i) {
651 Trait::poly_pointwise_montgomery(result[i].coefficients(), p.coefficients(), pv[i].coefficients());
652 }
653 return result;
654}
655
656template <crystals_trait Trait>
660 Trait::poly_pointwise_montgomery(result.coefficients(), a.coefficients(), b.coefficients());
661 return result;
662}
663
664template <crystals_trait Trait>
665PolynomialVector<Trait, Domain::Normal> operator<<(const PolynomialVector<Trait, Domain::Normal>& pv, size_t shift) {
666 BOTAN_ASSERT_NOMSG(shift < sizeof(typename Trait::T) * 8);
667 PolynomialVector<Trait, Domain::Normal> result(pv.size());
668 for(size_t i = 0; i < pv.size(); ++i) {
669 for(size_t j = 0; j < Trait::N; ++j) {
670 result[i][j] = pv[i][j] << shift;
671 }
672 }
673 return result;
674}
675
676} // namespace Botan::CRYSTALS
677
678#endif
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
PolynomialMatrix(size_t rows, size_t cols)
Definition pqcrystals.h:525
PolynomialVector< Trait, Domain::NTT > & operator[](size_t i)
Definition pqcrystals.h:532
PolynomialMatrix(ThisPolynomialMatrix &&other) noexcept=default
ThisPolynomialMatrix & operator=(const ThisPolynomialMatrix &other)=delete
decltype(auto) end() const
Definition pqcrystals.h:542
PolynomialMatrix(const ThisPolynomialMatrix &other)=delete
const PolynomialVector< Trait, Domain::NTT > & operator[](size_t i) const
Definition pqcrystals.h:534
ThisPolynomialMatrix & operator=(ThisPolynomialMatrix &&other) noexcept=default
PolynomialMatrix(std::vector< PolynomialVector< Trait > > mat)
Definition pqcrystals.h:515
decltype(auto) begin() const
Definition pqcrystals.h:538
ThisPolynomialVector & operator=(const ThisPolynomialVector &other)=delete
Polynomial< Trait, D > & operator[](size_t i)
Definition pqcrystals.h:479
std::span< const T > coefficients() const
Definition pqcrystals.h:447
ThisPolynomialVector & reduce()
Definition pqcrystals.h:465
constexpr Domain domain() const noexcept
Definition pqcrystals.h:418
ThisPolynomialVector & operator-=(const ThisPolynomialVector &other)
Definition pqcrystals.h:457
size_t hamming_weight() const noexcept
Definition pqcrystals.h:432
PolynomialVector(const ThisPolynomialVector &other)=delete
ThisPolynomialVector & operator=(ThisPolynomialVector &&other) noexcept=default
decltype(auto) begin() const
Definition pqcrystals.h:495
const Polynomial< Trait, D > & operator[](size_t i) const
Definition pqcrystals.h:481
ThisPolynomialVector clone() const
Definition pqcrystals.h:420
PolynomialVector(ThisPolynomialVector &&other) noexcept=default
std::vector< Polynomial< Trait, D > * > polynomials()
Definition pqcrystals.h:484
constexpr bool ct_validate_value_range(T min, T max) const noexcept
Definition pqcrystals.h:441
ThisPolynomialVector & conditional_add_q()
Definition pqcrystals.h:472
decltype(auto) end() const
Definition pqcrystals.h:499
ThisPolynomialVector & operator+=(const ThisPolynomialVector &other)
Definition pqcrystals.h:449
static PolynomialVector< Trait, D > from_domain_cast(PolynomialVector< Trait, OtherD > &&other)
Definition pqcrystals.h:398
Polynomial(const ThisPolynomial &other)=delete
constexpr bool owns_storage() const
Definition pqcrystals.h:320
void _const_time_unpoison() const
Definition pqcrystals.h:334
ThisPolynomial & operator=(ThisPolynomial &&other) noexcept
Definition pqcrystals.h:267
T operator[](size_t i) const
Definition pqcrystals.h:310
Polynomial(std::span< T, Trait::N > coeffs)
Definition pqcrystals.h:258
Polynomial(ThisPolynomial &&other) noexcept
Definition pqcrystals.h:262
ThisPolynomial & conditional_add_q()
Definition pqcrystals.h:327
std::span< const T, Trait::N > coefficients() const
Definition pqcrystals.h:306
ThisPolynomial & operator=(const ThisPolynomial &other)=delete
static Polynomial< Trait, D > from_domain_cast(Polynomial< Trait, OtherD > &&p)
Definition pqcrystals.h:251
constexpr size_t hamming_weight() const noexcept
Definition pqcrystals.h:296
decltype(auto) end() const
Definition pqcrystals.h:318
std::span< T, Trait::N > coefficients()
Definition pqcrystals.h:304
constexpr size_t size() const
Definition pqcrystals.h:278
void _const_time_poison() const
Definition pqcrystals.h:332
constexpr Domain domain() const noexcept
Definition pqcrystals.h:280
ThisPolynomial & reduce()
Definition pqcrystals.h:322
ThisPolynomial clone() const
Definition pqcrystals.h:282
decltype(auto) begin() const
Definition pqcrystals.h:314
constexpr bool ct_validate_value_range(T min, T max) const noexcept
Definition pqcrystals.h:291
static constexpr void barrett_reduce(std::span< T, N > poly)
Definition pqcrystals.h:124
static constexpr T Q
Definition pqcrystals.h:53
static constexpr T to_montgomery(T a)
Definition pqcrystals.h:122
static constexpr T F_WITH_MONTY_SQUARED
Definition pqcrystals.h:73
static constexpr void poly_sub(std::span< T, N > result, std::span< const T, N > lhs, std::span< const T, N > rhs)
Definition pqcrystals.h:107
next_longer_int_t< T > T2
Definition pqcrystals.h:58
static constexpr T N
Definition pqcrystals.h:52
static constexpr T MONTY
Definition pqcrystals.h:64
static constexpr T Q_inverse
Definition pqcrystals.h:63
static constexpr T MONTY_SQUARED
Definition pqcrystals.h:65
static constexpr void poly_cadd_q(std::span< T, N > coeffs)
Adds Q if the coefficient is negative.
Definition pqcrystals.h:114
static constexpr T fqmul(T a, T b)
Definition pqcrystals.h:98
static constexpr auto zetas
Definition pqcrystals.h:75
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 T BARRETT_V
Definition pqcrystals.h:55
static constexpr std::span< U, N > poly_in_polyvec(std::span< U > polyvec, size_t index)
Definition pqcrystals.h:91
typename ConstantsT::T T
Definition pqcrystals.h:51
static constexpr size_t polys_in_polyvec(std::span< const T > polyvec)
Definition pqcrystals.h:83
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.
Definition pqcrystals.h:131
static constexpr Mask< T > set()
Definition ct_utils.h:387
static constexpr Mask< T > expand_top_bit(T v)
Definition ct_utils.h:420
static constexpr Mask< T > is_within_range(T v, T l, T u)
Definition ct_utils.h:475
StructureT< Trait, To > domain_cast(StructureT< Trait, From > &&p)
Definition pqcrystals.h:165
void dot_product(Polynomial< Trait, Domain::NTT > &out, const PolynomialVector< Trait, Domain::NTT > &a, const PolynomialVector< Trait, Domain::NTT > &b)
Definition pqcrystals.h:559
void montgomery(Polynomial< Trait, D > &p)
Definition pqcrystals.h:552
Polynomial< Trait, D > montgomery(Polynomial< Trait, D > p)
Definition pqcrystals.h:604
PolynomialVector< Trait, Domain::NTT > operator*(const PolynomialMatrix< Trait > &mat, const PolynomialVector< Trait, Domain::NTT > &vec)
Definition pqcrystals.h:629
PolynomialVector< Trait, Domain::Normal > operator+(const PolynomialVector< Trait, Domain::Normal > &a, const PolynomialVector< Trait, Domain::Normal > &b)
Definition pqcrystals.h:618
Polynomial< Trait, Domain::NTT > ntt(Polynomial< Trait, Domain::Normal > p)
Definition pqcrystals.h:572
PolynomialVector< Trait, Domain::Normal > operator<<(const PolynomialVector< Trait, Domain::Normal > &pv, size_t shift)
Definition pqcrystals.h:665
Polynomial< Trait, Domain::Normal > inverse_ntt(Polynomial< Trait, Domain::NTT > p_ntt)
Definition pqcrystals.h:579
constexpr void unpoison_range(const R &r)
Definition ct_utils.h:189
constexpr void poison_range(const R &r)
Definition ct_utils.h:181
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
consteval T montgomery_R2(T q)
consteval T montgomery_R(T q)
consteval T modular_inverse(T q, T2 m=T2(1)<< sizeof(T) *8)
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
std::conditional_t< sizeof(T)==1, int16_t, std::conditional_t< sizeof(T)==2, int32_t, std::conditional_t< sizeof(T)==4, int64_t, void > > > next_longer_int_t
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118