Botan 3.5.0
Crypto and TLS for C&
frodo_matrix.h
Go to the documentation of this file.
1/*
2 * FrodoKEM matrix logic
3 * Based on the MIT licensed reference implementation by the designers
4 * (https://github.com/microsoft/PQCrypto-LWEKE/tree/master/src)
5 *
6 * The Fellowship of the FrodoKEM:
7 * (C) 2023 Jack Lloyd
8 * 2023 René Meusel, Amos Treiber - Rohde & Schwarz Cybersecurity
9 *
10 * Botan is released under the Simplified BSD License (see license.txt)
11 */
12
13#ifndef BOTAN_FRODOKEM_MATRIX_H_
14#define BOTAN_FRODOKEM_MATRIX_H_
15
16#include <botan/internal/ct_utils.h>
17#include <botan/internal/frodo_constants.h>
18#include <botan/internal/frodo_types.h>
19
20#include <functional>
21#include <tuple>
22#include <utility>
23#include <vector>
24
25namespace Botan {
26
28 public:
29 using Dimensions = std::tuple<size_t, size_t>;
30
31 explicit FrodoMatrix(Dimensions dims);
32
33 uint16_t elements_at(size_t i) const { return m_elements.at(i); }
34
35 size_t packed_size(const FrodoKEMConstants& constants) const {
36 const size_t lsb = constants.d();
37 const size_t inlen = element_count();
38 BOTAN_ASSERT_NOMSG((lsb * inlen) % 8 == 0);
39 return lsb * inlen / 8; // in bytes
40 }
41
42 FrodoPackedMatrix pack(const FrodoKEMConstants& constants) const {
43 FrodoPackedMatrix out(packed_size(constants));
44 pack(constants, out);
45 return out;
46 }
47
48 // Pack m_elements into a output buffer, copying lsb = D = log2 q bits from each input element.
49 // Section 7.3 of spec
50 void pack(const FrodoKEMConstants& constants, StrongSpan<FrodoPackedMatrix> out) const;
51
53
54 FrodoPlaintext decode(const FrodoKEMConstants& constants) const;
55
56 // Unpack the input FrodoPackedMatrix into the 16 bit m_elements vector, copying d bits
57 // for each output element from input. outlen must be at least ceil(inlen * 8 / d).
58 // m_elements is allocated here.
59 static FrodoMatrix unpack(const FrodoKEMConstants& constants,
62
64
65 static FrodoMatrix encode(const FrodoKEMConstants& constants,
66 StrongSpan<const FrodoPlaintext> in); // Section 7.2 of spec
67
68 // Creates a matrix with n samples from the noise distribution which requires 16 bits to sample.
69 // The distribution is specified by its CDF.
70 // Input: pseudo-random values (2*n bytes) passed in r.
71 // Section 7.5 of spec
72 static FrodoMatrix sample(const FrodoKEMConstants& constants,
75
76 // Helper function that calls FrodoMatrix::sample on initially provided consts and shake XOF.
77 // The output function calls shake.output at each invocation.
78 static std::function<FrodoMatrix(const Dimensions& dimensions)> make_sample_generator(
79 const FrodoKEMConstants& constants, Botan::XOF& shake);
80
81 // Generate-and-multiply: generate matrix A (N x N) row-wise, multiply by s on the right.
82 // Inputs: s^T (N_BAR x N), e (N x N_BAR), seed for matrix A
83 // Output: The elements of the FrodoMatrix will correspond to A*s + e (N x N_BAR).
84 static FrodoMatrix mul_add_as_plus_e(const FrodoKEMConstants& constants,
85 const FrodoMatrix& s,
86 const FrodoMatrix& e,
88
89 // Generate-and-multiply: generate matrix A (N x N) column-wise, multiply by s' on the left.
90 // Inputs: s', e' (N_BAR x N)
91 // Output: out = s'*A + e' (N_BAR x N)
92 // The matrix multiplication uses the row-wise blocking and packing (RWCF) approach described in: J.W. Bos, M. Ofner, J. Renes,
93 // T. Schneider, C. van Vredendaal, "The Matrix Reloaded: Multiplication Strategies in FrodoKEM". https://eprint.iacr.org/2021/711
94 static FrodoMatrix mul_add_sa_plus_e(const FrodoKEMConstants& constants,
95 const FrodoMatrix& s,
96 const FrodoMatrix& e,
98
99 // Multiply by s on the left
100 // Inputs: b (N x N_BAR), s (N_BAR x N), e (N_BAR x N_BAR)
101 // Output: out = s*b + e (N_BAR x N_BAR). The existing elements are overwritten and a self reference is returned.
102 static FrodoMatrix mul_add_sb_plus_e(const FrodoKEMConstants& constants,
103 const FrodoMatrix& b,
104 const FrodoMatrix& s,
105 const FrodoMatrix& e);
106
107 // Multiply by s on the right
108 // Inputs: b (N_BAR x N), s^T (N_BAR x N)
109 // Output: out = b*s (N_BAR x N_BAR)
110 static FrodoMatrix mul_bs(const FrodoKEMConstants& constants, const FrodoMatrix& b_p, const FrodoMatrix& s);
111
112 // Add a and b
113 // Inputs: a, b (N_BAR x N_BAR)
114 // Output: c = a + b
115 static FrodoMatrix add(const FrodoKEMConstants& constants, const FrodoMatrix& a, const FrodoMatrix& b);
116
117 // Subtract a and b
118 // Inputs: a, b (N_BAR x N_BAR)
119 // Output: c = a - b
120 static FrodoMatrix sub(const FrodoKEMConstants& constants, const FrodoMatrix& a, const FrodoMatrix& b);
121
122 Dimensions dimensions() const { return {m_dim1, m_dim2}; }
123
125
126 size_t element_count() const { return m_elements.size(); }
127
128 void reduce(const FrodoKEMConstants& constants);
129
130 private:
132 m_dim1(std::get<0>(dimensions)), m_dim2(std::get<1>(dimensions)), m_elements(std::move(elements)) {}
133
134 private:
135 size_t m_dim1;
136 size_t m_dim2;
137
138 secure_vector<uint16_t> m_elements;
139};
140
141} // namespace Botan
142
143#endif
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
static FrodoMatrix mul_add_sa_plus_e(const FrodoKEMConstants &constants, const FrodoMatrix &s, const FrodoMatrix &e, StrongSpan< const FrodoSeedA > seed_a)
static std::function< FrodoMatrix(const Dimensions &dimensions)> make_sample_generator(const FrodoKEMConstants &constants, Botan::XOF &shake)
static FrodoMatrix mul_add_sb_plus_e(const FrodoKEMConstants &constants, const FrodoMatrix &b, const FrodoMatrix &s, const FrodoMatrix &e)
void reduce(const FrodoKEMConstants &constants)
static FrodoMatrix mul_add_as_plus_e(const FrodoKEMConstants &constants, const FrodoMatrix &s, const FrodoMatrix &e, StrongSpan< const FrodoSeedA > seed_a)
static FrodoMatrix sub(const FrodoKEMConstants &constants, const FrodoMatrix &a, const FrodoMatrix &b)
FrodoPlaintext decode(const FrodoKEMConstants &constants) const
static FrodoMatrix add(const FrodoKEMConstants &constants, const FrodoMatrix &a, const FrodoMatrix &b)
std::tuple< size_t, size_t > Dimensions
static FrodoMatrix sample(const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoSampleR > r)
CT::Mask< uint8_t > constant_time_compare(const FrodoMatrix &other) const
FrodoPackedMatrix pack(const FrodoKEMConstants &constants) const
static FrodoMatrix encode(const FrodoKEMConstants &constants, StrongSpan< const FrodoPlaintext > in)
Dimensions dimensions() const
FrodoMatrix(Dimensions dims)
static FrodoMatrix unpack(const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoPackedMatrix > packed_bytes)
uint16_t elements_at(size_t i) const
size_t element_count() const
static FrodoMatrix mul_bs(const FrodoKEMConstants &constants, const FrodoMatrix &b_p, const FrodoMatrix &s)
static FrodoMatrix deserialize(const Dimensions &dimensions, StrongSpan< const FrodoSerializedMatrix > bytes)
size_t packed_size(const FrodoKEMConstants &constants) const
FrodoSerializedMatrix serialize() const
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61