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

#include <frodo_matrix.h>

Public Types

using Dimensions = std::tuple<size_t, size_t>

Public Member Functions

constexpr void _const_time_poison () const
constexpr void _const_time_unpoison () const
CT::Mask< uint8_t > constant_time_compare (const FrodoMatrix &other) const
FrodoPlaintext decode (const FrodoKEMConstants &constants) const
Dimensions dimensions () const
size_t element_count () const
uint16_t elements_at (size_t i) const
 FrodoMatrix (Dimensions dims)
FrodoPackedMatrix pack (const FrodoKEMConstants &constants) const
void pack (const FrodoKEMConstants &constants, StrongSpan< FrodoPackedMatrix > out) const
size_t packed_size (const FrodoKEMConstants &constants) const
void reduce (const FrodoKEMConstants &constants)
FrodoSerializedMatrix serialize () const

Static Public Member Functions

static FrodoMatrix add (const FrodoKEMConstants &constants, const FrodoMatrix &a, const FrodoMatrix &b)
static FrodoMatrix deserialize (const Dimensions &dimensions, StrongSpan< const FrodoSerializedMatrix > bytes)
static FrodoMatrix encode (const FrodoKEMConstants &constants, StrongSpan< const FrodoPlaintext > in)
static std::function< FrodoMatrix(const Dimensions &dimensions)> make_sample_generator (const FrodoKEMConstants &constants, Botan::XOF &shake)
static FrodoMatrix mul_add_as_plus_e (const FrodoKEMConstants &constants, const FrodoMatrix &s, const FrodoMatrix &e, StrongSpan< const FrodoSeedA > seed_a)
static FrodoMatrix mul_add_sa_plus_e (const FrodoKEMConstants &constants, const FrodoMatrix &s, const FrodoMatrix &e, StrongSpan< const FrodoSeedA > seed_a)
static FrodoMatrix mul_add_sb_plus_e (const FrodoKEMConstants &constants, const FrodoMatrix &b, const FrodoMatrix &s, const FrodoMatrix &e)
static FrodoMatrix mul_bs (const FrodoKEMConstants &constants, const FrodoMatrix &b_p, const FrodoMatrix &s)
static FrodoMatrix sample (const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoSampleR > r)
static FrodoMatrix sub (const FrodoKEMConstants &constants, const FrodoMatrix &a, const FrodoMatrix &b)
static FrodoMatrix unpack (const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoPackedMatrix > packed_bytes)

Detailed Description

Definition at line 26 of file frodo_matrix.h.

Member Typedef Documentation

◆ Dimensions

using Botan::FrodoMatrix::Dimensions = std::tuple<size_t, size_t>

Definition at line 28 of file frodo_matrix.h.

Constructor & Destructor Documentation

◆ FrodoMatrix()

Botan::FrodoMatrix::FrodoMatrix ( Dimensions dims)
explicit

Definition at line 121 of file frodo_matrix.cpp.

121 :
122 m_dim1(std::get<0>(dims)), m_dim2(std::get<1>(dims)), m_elements(make_elements_vector(dims)) {}

Referenced by add(), constant_time_compare(), deserialize(), encode(), make_sample_generator(), mul_add_as_plus_e(), mul_add_sa_plus_e(), mul_add_sb_plus_e(), mul_bs(), sample(), sub(), and unpack().

Member Function Documentation

◆ _const_time_poison()

void Botan::FrodoMatrix::_const_time_poison ( ) const
inlineconstexpr

Definition at line 129 of file frodo_matrix.h.

129{ CT::poison(m_elements); }
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56

References Botan::CT::poison().

◆ _const_time_unpoison()

void Botan::FrodoMatrix::_const_time_unpoison ( ) const
inlineconstexpr

Definition at line 131 of file frodo_matrix.h.

131{ CT::unpoison(m_elements); }
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67

References Botan::CT::unpoison().

◆ add()

FrodoMatrix Botan::FrodoMatrix::add ( const FrodoKEMConstants & constants,
const FrodoMatrix & a,
const FrodoMatrix & b )
static

Definition at line 301 of file frodo_matrix.cpp.

301 {
302 // Addition is defined for n_bar x n_bar matrices only
303 BOTAN_ASSERT_NOMSG(a.dimensions() == b.dimensions());
304 BOTAN_ASSERT_NOMSG(std::get<0>(a.dimensions()) == constants.n_bar() &&
305 std::get<1>(a.dimensions()) == constants.n_bar());
306
307 auto elements = make_elements_vector(a.dimensions());
308
309 for(size_t i = 0; i < constants.n_bar() * constants.n_bar(); ++i) {
310 elements.at(i) = a.elements_at(i) + b.elements_at(i);
311 }
312
313 return FrodoMatrix(a.dimensions(), std::move(elements));
314}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
FrodoMatrix(Dimensions dims)

References BOTAN_ASSERT_NOMSG, dimensions(), elements_at(), FrodoMatrix(), and Botan::FrodoKEMConstants::n_bar().

◆ constant_time_compare()

CT::Mask< uint8_t > Botan::FrodoMatrix::constant_time_compare ( const FrodoMatrix & other) const

Definition at line 331 of file frodo_matrix.cpp.

331 {
332 BOTAN_ASSERT_NOMSG(dimensions() == other.dimensions());
333 // TODO: Possibly use range-based comparison after #3715 is merged
334 return CT::is_equal(reinterpret_cast<const uint8_t*>(m_elements.data()),
335 reinterpret_cast<const uint8_t*>(other.m_elements.data()),
336 sizeof(decltype(m_elements)::value_type) * m_elements.size());
337}
Dimensions dimensions() const
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:803

References BOTAN_ASSERT_NOMSG, dimensions(), FrodoMatrix(), and Botan::CT::is_equal().

◆ decode()

FrodoPlaintext Botan::FrodoMatrix::decode ( const FrodoKEMConstants & constants) const

Definition at line 421 of file frodo_matrix.cpp.

421 {
422 const size_t nwords = (constants.n_bar() * constants.n_bar()) / 8;
423 const uint16_t maskex = static_cast<uint16_t>(1 << constants.b()) - 1;
424 const uint16_t maskq = static_cast<uint16_t>(1 << constants.d()) - 1;
425
426 FrodoPlaintext out(nwords * constants.b());
427
428 size_t index = 0;
429 for(size_t i = 0; i < nwords; i++) {
430 uint64_t templong = 0;
431 for(size_t j = 0; j < 8; j++) {
432 const auto temp =
433 static_cast<uint16_t>(((m_elements.at(index) & maskq) + (1 << (constants.d() - constants.b() - 1))) >>
434 (constants.d() - constants.b()));
435 templong |= static_cast<uint64_t>(temp & maskex) << (constants.b() * j);
436 index++;
437 }
438 for(size_t j = 0; j < constants.b(); j++) {
439 out[i * constants.b() + j] = (templong >> (8 * j)) & 0xFF;
440 }
441 }
442
443 return out;
444}
Strong< secure_vector< uint8_t >, struct FrodoPlaintext_ > FrodoPlaintext
Definition frodo_types.h:50

References Botan::FrodoKEMConstants::b(), Botan::FrodoKEMConstants::d(), and Botan::FrodoKEMConstants::n_bar().

◆ deserialize()

FrodoMatrix Botan::FrodoMatrix::deserialize ( const Dimensions & dimensions,
StrongSpan< const FrodoSerializedMatrix > bytes )
static

Definition at line 503 of file frodo_matrix.cpp.

503 {
504 auto elements = make_elements_vector(dimensions);
505 BOTAN_ASSERT_NOMSG(elements.size() * 2 == bytes.size());
506 load_le<uint16_t>(elements.data(), bytes.data(), elements.size());
507 return FrodoMatrix(dimensions, std::move(elements));
508}
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495

References BOTAN_ASSERT_NOMSG, Botan::StrongSpan< T >::data(), dimensions(), FrodoMatrix(), Botan::load_le(), and Botan::StrongSpan< T >::size().

Referenced by Botan::FrodoKEM_PrivateKey::FrodoKEM_PrivateKey().

◆ dimensions()

Dimensions Botan::FrodoMatrix::dimensions ( ) const
inline

◆ element_count()

size_t Botan::FrodoMatrix::element_count ( ) const
inline

Definition at line 125 of file frodo_matrix.h.

125{ return m_elements.size(); }

Referenced by pack(), and packed_size().

◆ elements_at()

uint16_t Botan::FrodoMatrix::elements_at ( size_t i) const
inline

Definition at line 32 of file frodo_matrix.h.

32{ return m_elements.at(i); }

Referenced by add(), mul_add_as_plus_e(), mul_add_sa_plus_e(), mul_add_sb_plus_e(), mul_bs(), and sub().

◆ encode()

FrodoMatrix Botan::FrodoMatrix::encode ( const FrodoKEMConstants & constants,
StrongSpan< const FrodoPlaintext > in )
static

Definition at line 278 of file frodo_matrix.cpp.

278 {
279 const uint64_t mask = (uint64_t(1) << constants.b()) - 1;
280
281 const auto dimensions = std::make_tuple<size_t, size_t>(constants.n_bar(), constants.n_bar());
282 auto elements = make_elements_vector(dimensions);
283
284 BOTAN_ASSERT_NOMSG(in.size() * 8 == constants.n_bar() * constants.n_bar() * constants.b());
285
286 size_t pos = 0;
287 for(size_t i = 0; i < (constants.n_bar() * constants.n_bar()) / 8; ++i) {
288 uint64_t temp = 0;
289 for(size_t j = 0; j < constants.b(); ++j) {
290 temp |= static_cast<uint64_t /* avoiding integral promotion */>(in[i * constants.b() + j]) << (8 * j);
291 }
292 for(size_t j = 0; j < 8; ++j) {
293 elements.at(pos++) = static_cast<uint16_t>((temp & mask) << (constants.d() - constants.b())); // k*2^(D-B)
294 temp >>= constants.b();
295 }
296 }
297
298 return FrodoMatrix(dimensions, std::move(elements));
299}

References Botan::FrodoKEMConstants::b(), BOTAN_ASSERT_NOMSG, Botan::FrodoKEMConstants::d(), dimensions(), FrodoMatrix(), Botan::FrodoKEMConstants::n_bar(), and Botan::StrongSpan< T >::size().

◆ make_sample_generator()

std::function< FrodoMatrix(const FrodoMatrix::Dimensions &dimensions)> Botan::FrodoMatrix::make_sample_generator ( const FrodoKEMConstants & constants,
Botan::XOF & shake )
static

Definition at line 112 of file frodo_matrix.cpp.

113 {
114 return [&constants, &shake](const FrodoMatrix::Dimensions& dimensions) mutable {
115 return sample(constants,
117 shake.output<FrodoSampleR>(sizeof(uint16_t) * std::get<0>(dimensions) * std::get<1>(dimensions)));
118 };
119}
std::tuple< size_t, size_t > Dimensions
static FrodoMatrix sample(const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoSampleR > r)
T output(size_t bytes)
Definition xof.h:161
Strong< secure_vector< uint8_t >, struct FrodoSampleR_ > FrodoSampleR
Definition frodo_types.h:35

References dimensions(), FrodoMatrix(), Botan::XOF::output(), and sample().

Referenced by Botan::FrodoKEM_PrivateKey::FrodoKEM_PrivateKey().

◆ mul_add_as_plus_e()

FrodoMatrix Botan::FrodoMatrix::mul_add_as_plus_e ( const FrodoKEMConstants & constants,
const FrodoMatrix & s,
const FrodoMatrix & e,
StrongSpan< const FrodoSeedA > seed_a )
static

Definition at line 124 of file frodo_matrix.cpp.

127 {
128 BOTAN_ASSERT(std::get<0>(e.dimensions()) == std::get<1>(s.dimensions()) &&
129 std::get<1>(e.dimensions()) == std::get<0>(s.dimensions()),
130 "FrodoMatrix dimension mismatch of E and S");
131 BOTAN_ASSERT(std::get<0>(e.dimensions()) == constants.n() && std::get<1>(e.dimensions()) == constants.n_bar(),
132 "FrodoMatrix dimension mismatch of new matrix dimensions and E");
133
134 auto elements = make_elements_vector(e.dimensions());
135 const auto row_generator = make_row_generator(constants, seed_a);
136
137 /*
138 We generate the rows of A in batched chunks, each row containing n 16-bit values.
139 a_row_data contains the 16-bit values of the current chunk of rows.
140 a_row_data_bytes represents the corresponding bytes.
141 */
142 const size_t row_chunk = frodo_row_chunk(constants);
143 std::vector<uint16_t> a_row_data(row_chunk * constants.n(), 0);
144 // TODO: maybe use std::as_bytes() instead
145 // (take extra care, as it produces a std::span<std::byte>)
146 const std::span<uint8_t> a_row_data_bytes(reinterpret_cast<uint8_t*>(a_row_data.data()),
147 sizeof(uint16_t) * a_row_data.size());
148
149 for(size_t i = 0; i < constants.n(); i += row_chunk) {
150 const size_t rows = std::min(row_chunk, constants.n() - i);
151
152 row_generator(a_row_data_bytes.first(rows * constants.n() * sizeof(uint16_t)), static_cast<uint16_t>(i), rows);
153
154 // On little-endian the generated bytes already have the in-memory
155 // layout of the 16-bit elements
156 if constexpr(std::endian::native == std::endian::big) {
157 load_le<uint16_t>(a_row_data.data(), a_row_data_bytes.data(), rows * constants.n());
158 }
159
160 // Process 4 rows of the chunk per pass
161 for(size_t r = 0; r < rows; r += 4) {
162 for(size_t k = 0; k < constants.n_bar(); ++k) {
163 std::array<uint16_t, 4> sum = {0};
164 for(size_t j = 0; j < constants.n(); ++j) { // Matrix-vector multiplication
165 // Note: we use uint32_t for `sp` to avoid an integral promotion to `int`
166 // when multiplying `sp` with other row values. Otherwise we might
167 // suffer from undefined behaviour due to a signed integer overflow.
168 // See: https://learn.microsoft.com/en-us/cpp/cpp/standard-conversions#integral-promotions
169 const uint32_t sp = s.elements_at(k * constants.n() + j);
170
171 // Go through four lines with same sp
172 sum[0] += static_cast<uint16_t>(a_row_data[(r + 0) * constants.n() + j] * sp);
173 sum[1] += static_cast<uint16_t>(a_row_data[(r + 1) * constants.n() + j] * sp);
174 sum[2] += static_cast<uint16_t>(a_row_data[(r + 2) * constants.n() + j] * sp);
175 sum[3] += static_cast<uint16_t>(a_row_data[(r + 3) * constants.n() + j] * sp);
176 }
177 elements.at((i + r + 0) * constants.n_bar() + k) =
178 e.elements_at((i + r + 0) * constants.n_bar() + k) + sum.at(0);
179 elements.at((i + r + 3) * constants.n_bar() + k) =
180 e.elements_at((i + r + 3) * constants.n_bar() + k) + sum.at(3);
181 elements.at((i + r + 2) * constants.n_bar() + k) =
182 e.elements_at((i + r + 2) * constants.n_bar() + k) + sum.at(2);
183 elements.at((i + r + 1) * constants.n_bar() + k) =
184 e.elements_at((i + r + 1) * constants.n_bar() + k) + sum.at(1);
185 }
186 }
187 }
188
189 return FrodoMatrix(e.dimensions(), std::move(elements));
190}
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69

References BOTAN_ASSERT, dimensions(), elements_at(), FrodoMatrix(), Botan::load_le(), Botan::FrodoKEMConstants::n(), and Botan::FrodoKEMConstants::n_bar().

Referenced by Botan::FrodoKEM_PrivateKey::FrodoKEM_PrivateKey().

◆ mul_add_sa_plus_e()

FrodoMatrix Botan::FrodoMatrix::mul_add_sa_plus_e ( const FrodoKEMConstants & constants,
const FrodoMatrix & s,
const FrodoMatrix & e,
StrongSpan< const FrodoSeedA > seed_a )
static

Definition at line 192 of file frodo_matrix.cpp.

195 {
196 BOTAN_ASSERT(std::get<0>(e.dimensions()) == std::get<0>(s.dimensions()) &&
197 std::get<1>(e.dimensions()) == std::get<1>(s.dimensions()),
198 "FrodoMatrix dimension mismatch of E and S");
199 BOTAN_ASSERT(std::get<0>(e.dimensions()) == constants.n_bar() && std::get<1>(e.dimensions()) == constants.n(),
200 "FrodoMatrix dimension mismatch of new matrix dimensions and E");
201
202 auto elements = e.m_elements;
203 const auto row_generator = make_row_generator(constants, seed_a);
204
205 /*
206 We generate the rows of A in batched chunks, each row containing n 16-bit values.
207 a_row_data contains the 16-bit values of the current chunk of rows.
208 a_row_data_bytes represents the corresponding bytes.
209 */
210 const size_t row_chunk = frodo_row_chunk(constants);
211 std::vector<uint16_t> a_row_data(row_chunk * constants.n(), 0);
212 // TODO: maybe use std::as_bytes()
213 const std::span<uint8_t> a_row_data_bytes(reinterpret_cast<uint8_t*>(a_row_data.data()),
214 sizeof(uint16_t) * a_row_data.size());
215
216 // Start matrix multiplication
217 for(size_t i = 0; i < constants.n(); i += row_chunk) {
218 const size_t rows = std::min(row_chunk, constants.n() - i);
219
220 row_generator(a_row_data_bytes.first(rows * constants.n() * sizeof(uint16_t)), static_cast<uint16_t>(i), rows);
221
222 // On little-endian the generated bytes already have the in-memory
223 // layout of the 16-bit elements
224 if constexpr(std::endian::native == std::endian::big) {
225 load_le<uint16_t>(a_row_data.data(), a_row_data_bytes.data(), rows * constants.n());
226 }
227
228 // Process 8 rows of the chunk per pass
229 for(size_t r = 0; r < rows; r += 8) {
230 for(size_t j = 0; j < constants.n_bar(); ++j) {
231 uint16_t sum = 0;
232 std::array<uint32_t /* to avoid integral promotion */, 8> sp{};
233 for(size_t p = 0; p < 8; ++p) {
234 sp[p] = s.elements_at(j * constants.n() + i + r + p);
235 }
236 for(size_t q = 0; q < constants.n(); ++q) {
237 sum = elements[j * constants.n() + q];
238 for(size_t p = 0; p < 8; ++p) {
239 sum += static_cast<uint16_t>(sp[p] * a_row_data[(r + p) * constants.n() + q]);
240 }
241 elements[j * constants.n() + q] = sum;
242 }
243 }
244 }
245 }
246
247 return FrodoMatrix(e.dimensions(), std::move(elements));
248}

References BOTAN_ASSERT, dimensions(), elements_at(), FrodoMatrix(), Botan::load_le(), Botan::FrodoKEMConstants::n(), and Botan::FrodoKEMConstants::n_bar().

◆ mul_add_sb_plus_e()

FrodoMatrix Botan::FrodoMatrix::mul_add_sb_plus_e ( const FrodoKEMConstants & constants,
const FrodoMatrix & b,
const FrodoMatrix & s,
const FrodoMatrix & e )
static

Definition at line 250 of file frodo_matrix.cpp.

253 {
254 BOTAN_ASSERT(std::get<0>(b.dimensions()) == std::get<1>(s.dimensions()) &&
255 std::get<1>(b.dimensions()) == std::get<0>(s.dimensions()),
256 "FrodoMatrix dimension mismatch of B and S");
257 BOTAN_ASSERT(std::get<0>(b.dimensions()) == constants.n() && std::get<1>(b.dimensions()) == constants.n_bar(),
258 "FrodoMatrix dimension mismatch of B");
259 BOTAN_ASSERT(std::get<0>(e.dimensions()) == constants.n_bar() && std::get<1>(e.dimensions()) == constants.n_bar(),
260 "FrodoMatrix dimension mismatch of E");
261
262 auto elements = make_elements_vector(e.dimensions());
263
264 for(size_t k = 0; k < constants.n_bar(); ++k) {
265 for(size_t i = 0; i < constants.n_bar(); ++i) {
266 elements.at(k * constants.n_bar() + i) = e.elements_at(k * constants.n_bar() + i);
267 for(size_t j = 0; j < constants.n(); ++j) {
268 elements.at(k * constants.n_bar() + i) += static_cast<uint16_t>(
269 static_cast<uint32_t /* to avoid integral promotion */>(s.elements_at(k * constants.n() + j)) *
270 b.elements_at(j * constants.n_bar() + i));
271 }
272 }
273 }
274
275 return FrodoMatrix(e.dimensions(), std::move(elements));
276}

References BOTAN_ASSERT, dimensions(), elements_at(), FrodoMatrix(), Botan::FrodoKEMConstants::n(), and Botan::FrodoKEMConstants::n_bar().

◆ mul_bs()

FrodoMatrix Botan::FrodoMatrix::mul_bs ( const FrodoKEMConstants & constants,
const FrodoMatrix & b_p,
const FrodoMatrix & s )
static

Definition at line 339 of file frodo_matrix.cpp.

339 {
340 const Dimensions dimensions = {constants.n_bar(), constants.n_bar()};
341 auto elements = make_elements_vector(dimensions);
342
343 for(size_t i = 0; i < constants.n_bar(); ++i) {
344 for(size_t j = 0; j < constants.n_bar(); ++j) {
345 auto& current = elements.at(i * constants.n_bar() + j);
346 current = 0;
347 for(size_t k = 0; k < constants.n(); ++k) {
348 // Explicitly store the values in 32-bit variables to avoid integral promotion
349 const uint32_t b_ink = b.elements_at(i * constants.n() + k);
350
351 // Since the input is s^T, we multiply the i-th row of b with the j-th row of s^t
352 const uint32_t s_ink = s.elements_at(j * constants.n() + k);
353
354 current += static_cast<uint16_t>(b_ink * s_ink);
355 }
356 }
357 }
358
359 return FrodoMatrix(dimensions, std::move(elements));
360}

References dimensions(), elements_at(), FrodoMatrix(), Botan::FrodoKEMConstants::n(), and Botan::FrodoKEMConstants::n_bar().

◆ pack() [1/2]

FrodoPackedMatrix Botan::FrodoMatrix::pack ( const FrodoKEMConstants & constants) const
inline

Definition at line 41 of file frodo_matrix.h.

41 {
42 FrodoPackedMatrix out(packed_size(constants));
43 pack(constants, out);
44 return out;
45 }
FrodoPackedMatrix pack(const FrodoKEMConstants &constants) const
size_t packed_size(const FrodoKEMConstants &constants) const
Strong< std::vector< uint8_t >, struct FrodoPackedMatrix_ > FrodoPackedMatrix
Definition frodo_types.h:41

References pack(), and packed_size().

Referenced by pack().

◆ pack() [2/2]

void Botan::FrodoMatrix::pack ( const FrodoKEMConstants & constants,
StrongSpan< FrodoPackedMatrix > out ) const

Definition at line 362 of file frodo_matrix.cpp.

362 {
363 const size_t outlen = packed_size(constants);
364 BOTAN_ASSERT_NOMSG(out.size() == outlen);
365
366 // The bit assembly below accumulates into out, so it requires a zeroed destination
367 clear_mem(out);
368
369 size_t i = 0; // whole bytes already filled in
370 size_t j = 0; // whole uint16_t already copied
371 uint16_t w = 0; // the leftover, not yet copied
372 uint8_t bits = 0; // the number of lsb in w
373
374 while(i < outlen && (j < element_count() || ((j == element_count()) && (bits > 0)))) {
375 /*
376 in: | | |********|********|
377 ^
378 j
379 w : | ****|
380 ^
381 bits
382 out:|**|**|**|**|**|**|**|**|* |
383 ^^
384 ib
385 */
386 uint8_t b = 0; // bits in out[i] already filled in
387 while(b < 8) {
388 const uint8_t nbits = std::min(static_cast<uint8_t>(8 - b), bits);
389 const uint16_t mask = static_cast<uint16_t>(1 << nbits) - 1;
390 const auto t = static_cast<uint8_t>((w >> (bits - nbits)) & mask); // the bits to copy from w to out
391 out[i] = out[i] + static_cast<uint8_t>(t << (8 - b - nbits));
392 b += nbits;
393 bits -= nbits;
394
395 if(bits == 0) {
396 if(j < element_count()) {
397 w = m_elements.at(j);
398 bits = static_cast<uint8_t>(constants.d());
399 j++;
400 } else {
401 break; // the input vector is exhausted
402 }
403 }
404 }
405 if(b == 8) { // out[i] is filled in
406 i++;
407 }
408 }
409}
size_t element_count() const
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118

References BOTAN_ASSERT_NOMSG, Botan::clear_mem(), Botan::FrodoKEMConstants::d(), element_count(), packed_size(), and Botan::StrongSpan< T >::size().

◆ packed_size()

size_t Botan::FrodoMatrix::packed_size ( const FrodoKEMConstants & constants) const
inline

Definition at line 34 of file frodo_matrix.h.

34 {
35 const size_t lsb = constants.d();
36 const size_t inlen = element_count();
37 BOTAN_ASSERT_NOMSG((lsb * inlen) % 8 == 0);
38 return lsb * inlen / 8; // in bytes
39 }

References BOTAN_ASSERT_NOMSG, Botan::FrodoKEMConstants::d(), and element_count().

Referenced by pack(), and pack().

◆ reduce()

void Botan::FrodoMatrix::reduce ( const FrodoKEMConstants & constants)

Definition at line 510 of file frodo_matrix.cpp.

510 {
511 // Reduction is inherent if D is 16, because we use uint16_t in m_elements
512 if(constants.d() < sizeof(decltype(m_elements)::value_type) * 8) {
513 const uint16_t mask = static_cast<uint16_t>(1 << constants.d()) - 1;
514 for(auto& elem : m_elements) {
515 elem = elem & mask; // mod q
516 }
517 }
518}

References Botan::FrodoKEMConstants::d().

◆ sample()

FrodoMatrix Botan::FrodoMatrix::sample ( const FrodoKEMConstants & constants,
const Dimensions & dimensions,
StrongSpan< const FrodoSampleR > r )
static

Definition at line 74 of file frodo_matrix.cpp.

76 {
77 BOTAN_ASSERT_NOMSG(r.size() % 2 == 0);
78 const auto n = r.size() / 2;
79
80 auto elements = make_elements_vector(dimensions);
81 BOTAN_ASSERT_NOMSG(n == elements.size());
82
83 load_le<uint16_t>(elements.data(), r.data(), n);
84
85 std::array<uint16_t, 16> cdf{};
86 const size_t cdf_len = constants.cdf_table_len();
87 BOTAN_ASSERT_NOMSG(cdf_len <= cdf.size());
88 for(size_t j = 0; j != cdf_len; ++j) {
89 cdf[j] = constants.cdf_table_at(j);
90 }
91
92 for(auto& elem : elements) {
93 const auto prnd = CT::value_barrier(static_cast<uint16_t>(elem >> 1)); // Drop the least significant bit
94 const auto sign = CT::Mask<uint16_t>::expand_bit(elem, 0); // Pick the least significant bit
95
96 uint32_t sample = 0; // Avoid integral promotion
97
98 // No need to compare with the last value.
99 for(size_t j = 0; j < cdf_len - 1; ++j) {
100 // Constant time comparison: 1 if CDF_TABLE[j] < s, 0 otherwise.
101 sample += CT::Mask<uint16_t>::is_lt(cdf[j], prnd).if_set_return(1);
102 }
103 // Assuming that sign is either 0 or 1, flips sample iff sign = 1
104 const uint16_t sample_u16 = static_cast<uint16_t>(sample);
105
106 elem = sign.select(~sample_u16 + 1, sample_u16);
107 }
108
109 return FrodoMatrix(dimensions, std::move(elements));
110}
static constexpr Mask< T > expand_bit(T v, size_t bit)
Definition ct_utils.h:426
static constexpr Mask< T > is_lt(T x, T y)
Definition ct_utils.h:455
constexpr T value_barrier(T x)

References BOTAN_ASSERT_NOMSG, Botan::FrodoKEMConstants::cdf_table_at(), Botan::FrodoKEMConstants::cdf_table_len(), Botan::StrongSpan< T >::data(), dimensions(), Botan::CT::Mask< T >::expand_bit(), FrodoMatrix(), Botan::CT::Mask< T >::is_lt(), Botan::load_le(), sample(), Botan::StrongSpan< T >::size(), and Botan::CT::value_barrier().

Referenced by make_sample_generator(), and sample().

◆ serialize()

FrodoSerializedMatrix Botan::FrodoMatrix::serialize ( ) const

Definition at line 411 of file frodo_matrix.cpp.

411 {
412 FrodoSerializedMatrix out(2 * m_elements.size());
413
414 for(unsigned int i = 0; i < m_elements.size(); ++i) {
415 store_le(m_elements.at(i), out.data() + 2 * i);
416 }
417
418 return out;
419}
Strong< secure_vector< uint8_t >, struct FrodoSerializedMatrix_ > FrodoSerializedMatrix
Definition frodo_types.h:44
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736

References Botan::detail::Strong_Adapter< T >::data(), and Botan::store_le().

◆ sub()

FrodoMatrix Botan::FrodoMatrix::sub ( const FrodoKEMConstants & constants,
const FrodoMatrix & a,
const FrodoMatrix & b )
static

Definition at line 316 of file frodo_matrix.cpp.

316 {
317 // Subtraction is defined for n_bar x n_bar matrices only
318 BOTAN_ASSERT_NOMSG(a.dimensions() == b.dimensions());
319 BOTAN_ASSERT_NOMSG(std::get<0>(a.dimensions()) == constants.n_bar() &&
320 std::get<1>(a.dimensions()) == constants.n_bar());
321
322 auto elements = make_elements_vector(a.dimensions());
323
324 for(size_t i = 0; i < constants.n_bar() * constants.n_bar(); ++i) {
325 elements.at(i) = a.elements_at(i) - b.elements_at(i);
326 }
327
328 return FrodoMatrix(a.dimensions(), std::move(elements));
329}

References BOTAN_ASSERT_NOMSG, dimensions(), elements_at(), FrodoMatrix(), and Botan::FrodoKEMConstants::n_bar().

◆ unpack()

FrodoMatrix Botan::FrodoMatrix::unpack ( const FrodoKEMConstants & constants,
const Dimensions & dimensions,
StrongSpan< const FrodoPackedMatrix > packed_bytes )
static

Definition at line 446 of file frodo_matrix.cpp.

448 {
449 const uint8_t lsb = static_cast<uint8_t>(constants.d());
450 const size_t inlen = packed_bytes.size();
451 const size_t outlen = static_cast<size_t>(std::get<0>(dimensions)) * std::get<1>(dimensions);
452
453 BOTAN_ASSERT_NOMSG(inlen == ceil_tobytes(outlen * lsb));
454
455 auto elements = make_elements_vector(dimensions);
456
457 size_t i = 0; // whole uint16_t already filled in
458 size_t j = 0; // whole bytes already copied
459 uint8_t w = 0; // the leftover, not yet copied
460 uint8_t bits = 0; // the number of lsb bits of w
461
462 while(i < outlen && (j < inlen || ((j == inlen) && (bits > 0)))) {
463 /*
464 in: | | | | | | |**|**|...
465 ^
466 j
467 w : | *|
468 ^
469 bits
470 out:| *****| *****| *** | |...
471 ^ ^
472 i b
473 */
474 uint8_t b = 0; // bits in out[i] already filled in
475 while(b < lsb) {
476 const uint8_t nbits = std::min(static_cast<uint8_t>(lsb - b), bits);
477 const uint16_t mask = static_cast<uint16_t>(1 << nbits) - 1;
478 const uint8_t t = (w >> (bits - nbits)) & mask; // the bits to copy from w to out
479
480 elements.at(i) = elements.at(i) + static_cast<uint16_t>(t << (lsb - b - nbits));
481 b += nbits;
482 bits -= nbits;
483 w &= static_cast<uint8_t>(~(mask << bits)); // not strictly necessary; mostly for debugging
484
485 if(bits == 0) {
486 if(j < inlen) {
487 w = packed_bytes[j];
488 bits = 8;
489 j++;
490 } else {
491 break; // the input vector is exhausted
492 }
493 }
494 }
495 if(b == lsb) { // out[i] is filled in
496 i++;
497 }
498 }
499
500 return FrodoMatrix(dimensions, std::move(elements));
501}
BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits)
Definition bit_ops.h:176

References BOTAN_ASSERT_NOMSG, Botan::ceil_tobytes(), Botan::FrodoKEMConstants::d(), dimensions(), FrodoMatrix(), and Botan::StrongSpan< T >::size().

Referenced by Botan::FrodoKEM_PrivateKey::FrodoKEM_PrivateKey(), and Botan::FrodoKEM_PublicKey::FrodoKEM_PublicKey().


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