Botan 3.4.0
Crypto and TLS for C&
Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | List of all members
Botan::FrodoMatrix Class Reference

#include <frodo_matrix.h>

Public Types

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

Public Member Functions

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 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)
 

Static Public Attributes

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

Detailed Description

Definition at line 27 of file frodo_matrix.h.

Member Typedef Documentation

◆ Dimensions

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

Definition at line 29 of file frodo_matrix.h.

Constructor & Destructor Documentation

◆ FrodoMatrix()

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

Definition at line 107 of file frodo_matrix.cpp.

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

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

Member Function Documentation

◆ add()

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

Definition at line 279 of file frodo_matrix.cpp.

279 {
280 // Addition is defined for n_bar x n_bar matrices only
281 BOTAN_ASSERT_NOMSG(a.dimensions() == b.dimensions());
282 BOTAN_ASSERT_NOMSG(std::get<0>(a.dimensions()) == constants.n_bar() &&
283 std::get<1>(a.dimensions()) == constants.n_bar());
284
285 auto elements = make_elements_vector(a.dimensions());
286
287 for(size_t i = 0; i < constants.n_bar() * constants.n_bar(); ++i) {
288 elements.at(i) = a.elements_at(i) + b.elements_at(i);
289 }
290
291 return FrodoMatrix(a.dimensions(), std::move(elements));
292}
BOTAN_ASSERT_NOMSG
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
Botan::FrodoMatrix::FrodoMatrix
FrodoMatrix(Dimensions dims)
Definition frodo_matrix.cpp:107

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 309 of file frodo_matrix.cpp.

309 {
310 BOTAN_ASSERT_NOMSG(dimensions() == other.dimensions());
311 // TODO: Possibly use range-based comparison after #3715 is merged
312 return CT::is_equal(reinterpret_cast<const uint8_t*>(m_elements.data()),
313 reinterpret_cast<const uint8_t*>(other.m_elements.data()),
314 sizeof(decltype(m_elements)::value_type) * m_elements.size());
315}
Botan::FrodoMatrix::dimensions
Dimensions dimensions() const
Definition frodo_matrix.h:122
Botan::CT::is_equal
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:345

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

◆ decode()

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

Definition at line 396 of file frodo_matrix.cpp.

396 {
397 const size_t nwords = (constants.n_bar() * constants.n_bar()) / 8;
398 const uint16_t maskex = static_cast<uint16_t>(1 << constants.b()) - 1;
399 const uint16_t maskq = static_cast<uint16_t>(1 << constants.d()) - 1;
400
401 FrodoPlaintext out(nwords * constants.b());
402
403 size_t index = 0;
404 for(size_t i = 0; i < nwords; i++) {
405 uint64_t templong = 0;
406 for(size_t j = 0; j < 8; j++) {
407 const auto temp =
408 static_cast<uint16_t>(((m_elements.at(index) & maskq) + (1 << (constants.d() - constants.b() - 1))) >>
409 (constants.d() - constants.b()));
410 templong |= static_cast<uint64_t>(temp & maskex) << (constants.b() * j);
411 index++;
412 }
413 for(size_t j = 0; j < constants.b(); j++) {
414 out[i * constants.b() + j] = (templong >> (8 * j)) & 0xFF;
415 }
416 }
417
418 return out;
419}
Botan::FrodoPlaintext
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 478 of file frodo_matrix.cpp.

478 {
479 auto elements = make_elements_vector(dimensions);
480 BOTAN_ASSERT_NOMSG(elements.size() * 2 == bytes.size());
481 load_le<uint16_t>(elements.data(), bytes.data(), elements.size());
482 return FrodoMatrix(dimensions, std::move(elements));
483}

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

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

◆ dimensions()

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

Definition at line 122 of file frodo_matrix.h.

122{ return {m_dim1, m_dim2}; }

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

◆ element_count()

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

Definition at line 126 of file frodo_matrix.h.

126{ 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 33 of file frodo_matrix.h.

33{ 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 256 of file frodo_matrix.cpp.

256 {
257 const uint64_t mask = (uint64_t(1) << constants.b()) - 1;
258
259 const auto dimensions = std::make_tuple<size_t, size_t>(constants.n_bar(), constants.n_bar());
260 auto elements = make_elements_vector(dimensions);
261
262 BOTAN_ASSERT_NOMSG(in.size() * 8 == constants.n_bar() * constants.n_bar() * constants.b());
263
264 size_t pos = 0;
265 for(size_t i = 0; i < (constants.n_bar() * constants.n_bar()) / 8; ++i) {
266 uint64_t temp = 0;
267 for(size_t j = 0; j < constants.b(); ++j) {
268 temp |= static_cast<uint64_t /* avoiding integral promotion */>(in[i * constants.b() + j]) << (8 * j);
269 }
270 for(size_t j = 0; j < 8; ++j) {
271 elements.at(pos++) = static_cast<uint16_t>((temp & mask) << (constants.d() - constants.b())); // k*2^(D-B)
272 temp >>= constants.b();
273 }
274 }
275
276 return FrodoMatrix(dimensions, std::move(elements));
277}

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

◆ 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 110 of file frodo_matrix.cpp.

113 {
114 BOTAN_ASSERT(std::get<0>(e.dimensions()) == std::get<1>(s.dimensions()) &&
115 std::get<1>(e.dimensions()) == std::get<0>(s.dimensions()),
116 "FrodoMatrix dimension mismatch of E and S");
117 BOTAN_ASSERT(std::get<0>(e.dimensions()) == constants.n() && std::get<1>(e.dimensions()) == constants.n_bar(),
118 "FrodoMatrix dimension mismatch of new matrix dimensions and E");
119
120 auto elements = make_elements_vector(e.dimensions());
121 auto row_generator = make_row_generator(constants, seed_a);
122
123 /*
124 We perform 4 invocations of SHAKE128 per iteration to obtain n 16-bit values per invocation.
125 a_row_data contains the 16-bit values of the current 4 rows. a_row_data_bytes represents the corresponding bytes.
126 */
127 std::vector<uint16_t> a_row_data(4 * constants.n(), 0);
128 // TODO: maybe use std::as_bytes() instead
129 // (take extra care, as it produces a std::span<std::byte>)
130 std::span<uint8_t> a_row_data_bytes(reinterpret_cast<uint8_t*>(a_row_data.data()),
131 sizeof(uint16_t) * a_row_data.size());
132
133 for(size_t i = 0; i < constants.n(); i += 4) {
134 auto a_row = BufferStuffer(a_row_data_bytes);
135
136 // Do 4 invocations to fill 4 rows
137 row_generator(a_row.next(constants.n() * sizeof(uint16_t)), static_cast<uint16_t>(i + 0));
138 row_generator(a_row.next(constants.n() * sizeof(uint16_t)), static_cast<uint16_t>(i + 1));
139 row_generator(a_row.next(constants.n() * sizeof(uint16_t)), static_cast<uint16_t>(i + 2));
140 row_generator(a_row.next(constants.n() * sizeof(uint16_t)), static_cast<uint16_t>(i + 3));
141
142 // Use generated bytes to fill 16-bit data
143 load_le<uint16_t>(a_row_data.data(), a_row_data_bytes.data(), 4 * constants.n());
144
145 for(size_t k = 0; k < constants.n_bar(); ++k) {
146 std::array<uint16_t, 4> sum = {0};
147 for(size_t j = 0; j < constants.n(); ++j) { // Matrix-vector multiplication
148 // Note: we use uint32_t for `sp` to avoid an integral promotion to `int`
149 // when multiplying `sp` with other row values. Otherwise we might
150 // suffer from undefined behaviour due to a signed integer overflow.
151 // See: https://learn.microsoft.com/en-us/cpp/cpp/standard-conversions#integral-promotions
152 const uint32_t sp = s.elements_at(k * constants.n() + j);
153
154 // Go through four lines with same sp
155 sum.at(0) += static_cast<uint16_t>(a_row_data.at(0 * constants.n() + j) * sp);
156 sum.at(1) += static_cast<uint16_t>(a_row_data.at(1 * constants.n() + j) * sp);
157 sum.at(2) += static_cast<uint16_t>(a_row_data.at(2 * constants.n() + j) * sp);
158 sum.at(3) += static_cast<uint16_t>(a_row_data.at(3 * constants.n() + j) * sp);
159 }
160 elements.at((i + 0) * constants.n_bar() + k) = e.elements_at((i + 0) * constants.n_bar() + k) + sum.at(0);
161 elements.at((i + 3) * constants.n_bar() + k) = e.elements_at((i + 3) * constants.n_bar() + k) + sum.at(3);
162 elements.at((i + 2) * constants.n_bar() + k) = e.elements_at((i + 2) * constants.n_bar() + k) + sum.at(2);
163 elements.at((i + 1) * constants.n_bar() + k) = e.elements_at((i + 1) * constants.n_bar() + k) + sum.at(1);
164 }
165 }
166
167 return FrodoMatrix(e.dimensions(), std::move(elements));
168}
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:50

References BOTAN_ASSERT, dimensions(), elements_at(), FrodoMatrix(), 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 170 of file frodo_matrix.cpp.

173 {
174 BOTAN_ASSERT(std::get<0>(e.dimensions()) == std::get<0>(s.dimensions()) &&
175 std::get<1>(e.dimensions()) == std::get<1>(s.dimensions()),
176 "FrodoMatrix dimension mismatch of E and S");
177 BOTAN_ASSERT(std::get<0>(e.dimensions()) == constants.n_bar() && std::get<1>(e.dimensions()) == constants.n(),
178 "FrodoMatrix dimension mismatch of new matrix dimensions and E");
179
180 auto elements = e.m_elements;
181 auto row_generator = make_row_generator(constants, seed_a);
182
183 /*
184 We perform 8 invocations of SHAKE128 per iteration to obtain n 16-bit values per invocation.
185 a_row_data contains the 16-bit values of the current 8 rows. a_row_data_bytes represents the corresponding bytes.
186 */
187 std::vector<uint16_t> a_row_data(8 * constants.n(), 0);
188 // TODO: maybe use std::as_bytes()
189 std::span<uint8_t> a_row_data_bytes(reinterpret_cast<uint8_t*>(a_row_data.data()),
190 sizeof(uint16_t) * a_row_data.size());
191
192 // Start matrix multiplication
193 for(size_t i = 0; i < constants.n(); i += 8) {
194 auto a_row = BufferStuffer(a_row_data_bytes);
195
196 // Do 8 invocations to fill 8 rows
197 row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast<uint16_t>(i + 0));
198 row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast<uint16_t>(i + 1));
199 row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast<uint16_t>(i + 2));
200 row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast<uint16_t>(i + 3));
201 row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast<uint16_t>(i + 4));
202 row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast<uint16_t>(i + 5));
203 row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast<uint16_t>(i + 6));
204 row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast<uint16_t>(i + 7));
205
206 // Use generated bytes to fill 16-bit data
207 load_le<uint16_t>(a_row_data.data(), a_row_data_bytes.data(), 8 * constants.n());
208
209 for(size_t j = 0; j < constants.n_bar(); ++j) {
210 uint16_t sum = 0;
211 std::array<uint32_t /* to avoid integral promotion */, 8> sp;
212 for(size_t p = 0; p < 8; ++p) {
213 sp[p] = s.elements_at(j * constants.n() + i + p);
214 }
215 for(size_t q = 0; q < constants.n(); ++q) {
216 sum = elements.at(j * constants.n() + q);
217 for(size_t p = 0; p < 8; ++p) {
218 sum += static_cast<uint16_t>(sp[p] * a_row_data.at(p * constants.n() + q));
219 }
220 elements.at(j * constants.n() + q) = sum;
221 }
222 }
223 }
224
225 return FrodoMatrix(e.dimensions(), std::move(elements));
226}

References BOTAN_ASSERT, dimensions(), elements_at(), FrodoMatrix(), 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 228 of file frodo_matrix.cpp.

231 {
232 BOTAN_ASSERT(std::get<0>(b.dimensions()) == std::get<1>(s.dimensions()) &&
233 std::get<1>(b.dimensions()) == std::get<0>(s.dimensions()),
234 "FrodoMatrix dimension mismatch of B and S");
235 BOTAN_ASSERT(std::get<0>(b.dimensions()) == constants.n() && std::get<1>(b.dimensions()) == constants.n_bar(),
236 "FrodoMatrix dimension mismatch of B");
237 BOTAN_ASSERT(std::get<0>(e.dimensions()) == constants.n_bar() && std::get<1>(e.dimensions()) == constants.n_bar(),
238 "FrodoMatrix dimension mismatch of E");
239
240 auto elements = make_elements_vector(e.dimensions());
241
242 for(size_t k = 0; k < constants.n_bar(); ++k) {
243 for(size_t i = 0; i < constants.n_bar(); ++i) {
244 elements.at(k * constants.n_bar() + i) = e.elements_at(k * constants.n_bar() + i);
245 for(size_t j = 0; j < constants.n(); ++j) {
246 elements.at(k * constants.n_bar() + i) += static_cast<uint16_t>(
247 static_cast<uint32_t /* to avoid integral promotion */>(s.elements_at(k * constants.n() + j)) *
248 b.elements_at(j * constants.n_bar() + i));
249 }
250 }
251 }
252
253 return FrodoMatrix(e.dimensions(), std::move(elements));
254}

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 317 of file frodo_matrix.cpp.

317 {
318 Dimensions dimensions = {constants.n_bar(), constants.n_bar()};
319 auto elements = make_elements_vector(dimensions);
320
321 for(size_t i = 0; i < constants.n_bar(); ++i) {
322 for(size_t j = 0; j < constants.n_bar(); ++j) {
323 auto& current = elements.at(i * constants.n_bar() + j);
324 current = 0;
325 for(size_t k = 0; k < constants.n(); ++k) {
326 // Explicitly store the values in 32-bit variables to avoid integral promotion
327 const uint32_t b_ink = b.elements_at(i * constants.n() + k);
328
329 // Since the input is s^T, we multiply the i-th row of b with the j-th row of s^t
330 const uint32_t s_ink = s.elements_at(j * constants.n() + k);
331
332 current += static_cast<uint16_t>(b_ink * s_ink);
333 }
334 }
335 }
336
337 return FrodoMatrix(dimensions, std::move(elements));
338}
Botan::FrodoMatrix::Dimensions
std::tuple< size_t, size_t > Dimensions
Definition frodo_matrix.h:29

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 42 of file frodo_matrix.h.

42 {
43 FrodoPackedMatrix out(packed_size(constants));
44 pack(constants, out);
45 return out;
46 }
Botan::FrodoMatrix::pack
FrodoPackedMatrix pack(const FrodoKEMConstants &constants) const
Definition frodo_matrix.h:42
Botan::FrodoMatrix::packed_size
size_t packed_size(const FrodoKEMConstants &constants) const
Definition frodo_matrix.h:35
Botan::FrodoPackedMatrix
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 340 of file frodo_matrix.cpp.

340 {
341 const size_t outlen = packed_size(constants);
342 BOTAN_ASSERT_NOMSG(out.size() == outlen);
343
344 size_t i = 0; // whole bytes already filled in
345 size_t j = 0; // whole uint16_t already copied
346 uint16_t w = 0; // the leftover, not yet copied
347 uint8_t bits = 0; // the number of lsb in w
348
349 while(i < outlen && (j < element_count() || ((j == element_count()) && (bits > 0)))) {
350 /*
351 in: | | |********|********|
352 ^
353 j
354 w : | ****|
355 ^
356 bits
357 out:|**|**|**|**|**|**|**|**|* |
358 ^^
359 ib
360 */
361 uint8_t b = 0; // bits in out[i] already filled in
362 while(b < 8) {
363 const uint8_t nbits = std::min(static_cast<uint8_t>(8 - b), bits);
364 const uint16_t mask = static_cast<uint16_t>(1 << nbits) - 1;
365 const auto t = static_cast<uint8_t>((w >> (bits - nbits)) & mask); // the bits to copy from w to out
366 out[i] = out[i] + static_cast<uint8_t>(t << (8 - b - nbits));
367 b += nbits;
368 bits -= nbits;
369
370 if(bits == 0) {
371 if(j < element_count()) {
372 w = m_elements.at(j);
373 bits = static_cast<uint8_t>(constants.d());
374 j++;
375 } else {
376 break; // the input vector is exhausted
377 }
378 }
379 }
380 if(b == 8) { // out[i] is filled in
381 i++;
382 }
383 }
384}
Botan::FrodoMatrix::element_count
size_t element_count() const
Definition frodo_matrix.h:126

References BOTAN_ASSERT_NOMSG, 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 35 of file frodo_matrix.h.

35 {
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 }

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 485 of file frodo_matrix.cpp.

485 {
486 // Reduction is inherent if D is 16, because we use uint16_t in m_elements
487 if(constants.d() < sizeof(decltype(m_elements)::value_type) * 8) {
488 const uint16_t mask = static_cast<uint16_t>(1 << constants.d()) - 1;
489 for(auto& elem : m_elements) {
490 elem = elem & mask; // mod q
491 }
492 }
493}

References Botan::FrodoKEMConstants::d().

◆ sample()

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

Definition at line 70 of file frodo_matrix.cpp.

72 {
73 BOTAN_ASSERT_NOMSG(r.size() % 2 == 0);
74 const auto n = r.size() / 2;
75
76 auto elements = make_elements_vector(dimensions);
77 BOTAN_ASSERT_NOMSG(n == elements.size());
78
79 load_le<uint16_t>(elements.data(), r.data(), n);
80
81 for(size_t i = 0; i < n; ++i) {
82 uint32_t sample = 0; // Avoid integral promotion
83 const uint16_t prnd = elements.at(i) >> 1; // Drop the least significant bit
84 const uint16_t sign = elements.at(i) & 0x1; // Pick the least significant bit
85
86 // No need to compare with the last value.
87 for(size_t j = 0; j < constants.cdf_table_len() - 1; ++j) {
88 // Constant time comparison: 1 if CDF_TABLE[j] < s, 0 otherwise.
89 sample += CT::Mask<uint16_t>::is_lt(constants.cdf_table_at(j), prnd).if_set_return(1);
90 }
91 // Assuming that sign is either 0 or 1, flips sample iff sign = 1
92 elements.at(i) = static_cast<uint16_t>((-sign) ^ sample) + sign;
93 }
94
95 return FrodoMatrix(dimensions, std::move(elements));
96}
Botan::CT::Mask::is_lt
static constexpr Mask< T > is_lt(T x, T y)
Definition ct_utils.h:139
Botan::FrodoMatrix::sample
static FrodoMatrix sample(const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoSampleR > r)
Definition frodo_matrix.cpp:70

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

Referenced by sample().

◆ serialize()

FrodoSerializedMatrix Botan::FrodoMatrix::serialize ( ) const

Definition at line 386 of file frodo_matrix.cpp.

386 {
387 FrodoSerializedMatrix out(2 * m_elements.size());
388
389 for(unsigned int i = 0; i < m_elements.size(); ++i) {
390 store_le(m_elements.at(i), out.data() + 2 * i);
391 }
392
393 return out;
394}
Botan::FrodoSerializedMatrix
Strong< secure_vector< uint8_t >, struct FrodoSerializedMatrix_ > FrodoSerializedMatrix
Definition frodo_types.h:44
Botan::store_le
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:702

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 294 of file frodo_matrix.cpp.

294 {
295 // Subtraction is defined for n_bar x n_bar matrices only
296 BOTAN_ASSERT_NOMSG(a.dimensions() == b.dimensions());
297 BOTAN_ASSERT_NOMSG(std::get<0>(a.dimensions()) == constants.n_bar() &&
298 std::get<1>(a.dimensions()) == constants.n_bar());
299
300 auto elements = make_elements_vector(a.dimensions());
301
302 for(size_t i = 0; i < constants.n_bar() * constants.n_bar(); ++i) {
303 elements.at(i) = a.elements_at(i) - b.elements_at(i);
304 }
305
306 return FrodoMatrix(a.dimensions(), std::move(elements));
307}

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 421 of file frodo_matrix.cpp.

423 {
424 const uint8_t lsb = static_cast<uint8_t>(constants.d());
425 const size_t inlen = packed_bytes.size();
426 const size_t outlen = static_cast<size_t>(std::get<0>(dimensions)) * std::get<1>(dimensions);
427
428 BOTAN_ASSERT_NOMSG(inlen == ceil_tobytes(outlen * lsb));
429
430 auto elements = make_elements_vector(dimensions);
431
432 size_t i = 0; // whole uint16_t already filled in
433 size_t j = 0; // whole bytes already copied
434 uint8_t w = 0; // the leftover, not yet copied
435 uint8_t bits = 0; // the number of lsb bits of w
436
437 while(i < outlen && (j < inlen || ((j == inlen) && (bits > 0)))) {
438 /*
439 in: | | | | | | |**|**|...
440 ^
441 j
442 w : | *|
443 ^
444 bits
445 out:| *****| *****| *** | |...
446 ^ ^
447 i b
448 */
449 uint8_t b = 0; // bits in out[i] already filled in
450 while(b < lsb) {
451 const uint8_t nbits = std::min(static_cast<uint8_t>(lsb - b), bits);
452 const uint16_t mask = static_cast<uint16_t>(1 << nbits) - 1;
453 uint8_t t = (w >> (bits - nbits)) & mask; // the bits to copy from w to out
454
455 elements.at(i) = elements.at(i) + static_cast<uint16_t>(t << (lsb - b - nbits));
456 b += nbits;
457 bits -= nbits;
458 w &= static_cast<uint8_t>(~(mask << bits)); // not strictly necessary; mostly for debugging
459
460 if(bits == 0) {
461 if(j < inlen) {
462 w = packed_bytes[j];
463 bits = 8;
464 j++;
465 } else {
466 break; // the input vector is exhausted
467 }
468 }
469 }
470 if(b == lsb) { // out[i] is filled in
471 i++;
472 }
473 }
474
475 return FrodoMatrix(dimensions, std::move(elements));
476}
Botan::ceil_tobytes
constexpr T ceil_tobytes(T bits)
Definition bit_ops.h:144

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().

Member Data Documentation

◆ make_sample_generator

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

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

The documentation for this class was generated from the following files:
Generated by doxygen 1.10.0