| 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) |
| 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 |
|
| 25 |
namespace Botan { |
| 26 |
|
| 27 |
class FrodoMatrix final { |
| 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 |
|
| 52 |
FrodoSerializedMatrix serialize() const; |
| 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, |
| 60 |
const Dimensions& dimensions, |
| 61 |
StrongSpan<const FrodoPackedMatrix> packed_bytes); |
| 62 |
|
| 63 |
static FrodoMatrix deserialize(const Dimensions& dimensions, StrongSpan<const FrodoSerializedMatrix> bytes); |
| 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, |
| 73 |
const Dimensions& dimensions, |
| 74 |
StrongSpan<const FrodoSampleR> r); |
| 75 |
|
| 76 |
// Helper function that calls FrodoMatrix::sample on initially provided constants 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, |
| 87 |
StrongSpan<const FrodoSeedA> seed_a); |
| 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, |
| 97 |
StrongSpan<const FrodoSeedA> seed_a); |
| 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 |
|
| 124 |
CT::Mask<uint8_t> constant_time_compare(const FrodoMatrix& other) const; |
| 125 |
|
| 126 |
size_t element_count() const { return m_elements.size(); } |
| 127 |
|
| 128 |
void reduce(const FrodoKEMConstants& constants); |
| 129 |
|
| 130 |
constexpr void _const_time_poison() const { CT::poison(m_elements); } |
| 131 |
|
| 132 |
constexpr void _const_time_unpoison() const { CT::unpoison(m_elements); } |
| 133 |
|
| 134 |
private: |
| 135 |
FrodoMatrix(const Dimensions& dimensions, secure_vector<uint16_t> elements) : |
| 136 |
m_dim1(std::get<0>(dimensions)), m_dim2(std::get<1>(dimensions)), m_elements(std::move(elements)) {} |
| 137 |
|
| 138 |
private: |
| 139 |
size_t m_dim1; |
| 140 |
size_t m_dim2; |
| 141 |
|
| 142 |
secure_vector<uint16_t> m_elements; |
| 143 |
}; |
| 144 |
|
| 145 |
} // namespace Botan |
| 146 |
|
| 147 |
#endif |