Botan 3.14.1
Crypto and TLS for C&
kyber_algos.h
Go to the documentation of this file.
1/*
2 * Crystals Kyber Internal Algorithms
3 * Based on the public domain reference implementation by the
4 * designers (https://github.com/pq-crystals/kyber)
5 *
6 * Further changes
7 * (C) 2021-2024 Jack Lloyd
8 * (C) 2021-2022 Manuel Glaser and Michael Boric, Rohde & Schwarz Cybersecurity
9 * (C) 2021-2022 René Meusel and Hannes Rantzsch, neXenio GmbH
10 * (C) 2024 René Meusel, Rohde & Schwarz Cybersecurity
11 *
12 * Botan is released under the Simplified BSD License (see license.txt)
13 */
14
15#ifndef BOTAN_KYBER_ALGOS_H_
16#define BOTAN_KYBER_ALGOS_H_
17
18#include <botan/internal/concat_util.h>
19#include <botan/internal/kyber_symmetric_primitives.h>
20#include <botan/internal/kyber_types.h>
21
22#include <array>
23
24namespace Botan::Kyber_Algos {
25
26void encode_polynomial_vector(std::span<uint8_t> out, const KyberPolyVecNTT& p);
27
28KyberPolyVecNTT decode_polynomial_vector(std::span<const uint8_t> a, const KyberConstants& mode);
29
30KyberPoly polynomial_from_message(StrongSpan<const KyberMessage> msg);
31
33
34KyberInternalKeypair expand_keypair(KyberPrivateKeySeed seed, KyberConstants mode);
35
36void compress_ciphertext(StrongSpan<KyberCompressedCiphertext> out,
37 const KyberPolyVec& u,
38 const KyberPoly& v,
39 const KyberConstants& m_mode);
40
41std::pair<KyberPolyVec, KyberPoly> decompress_ciphertext(StrongSpan<const KyberCompressedCiphertext> ct,
42 const KyberConstants& mode);
43
44KyberPolyMat sample_matrix(StrongSpan<const KyberSeedRho> seed, bool transposed, const KyberConstants& mode);
45
48 StrongSpan<const KyberSamplingRandomness> randomness);
49
50template <concepts::resizable_byte_buffer T = secure_vector<uint8_t>>
52 T r(mode.polynomial_vector_bytes());
54 return r;
55}
56
57/**
58 * Allows sampling multiple polynomials from a single seed via a XOF.
59 *
60 * Used in Algorithms 13 (K-PKE.KeyGen) and 14 (K-PKE.Encrypt), and takes care
61 * of the continuous nonce value internally.
62 */
63template <typename SeedT>
64 requires std::same_as<KyberSeedSigma, SeedT> || std::same_as<KyberEncryptionRandomness, SeedT>
66 public:
68 m_seed(seed), m_mode(mode), m_nonce(0) {}
69
71 KyberPolyVec vec(m_mode.k());
72 sample_polys_cbd(vec.polynomials(), m_mode.eta1());
73 return vec;
74 }
75
76 /// Samples two polynomial vectors in a single PRF batch
77 std::pair<KyberPolyVec, KyberPolyVec> sample_polynomial_vector_pair_cbd_eta1() {
78 auto result = std::make_pair(KyberPolyVec(m_mode.k()), KyberPolyVec(m_mode.k()));
79 sample_polys_cbd(concat(result.first.polynomials(), //
80 result.second.polynomials()),
81 m_mode.eta1());
82 return result;
83 }
84
85 /// Samples a polynomial vector and a single polynomial in one PRF batch
86 std::pair<KyberPolyVec, KyberPoly> sample_polynomial_vector_and_poly_cbd_eta2()
87 requires std::same_as<KyberEncryptionRandomness, SeedT>
88 {
89 std::pair<KyberPolyVec, KyberPoly> result{KyberPolyVec(m_mode.k()), KyberPoly()};
90 sample_polys_cbd(concat(result.first.polynomials(), std::array{&result.second}), m_mode.eta2());
91 return result;
92 }
93
94 private:
95 static size_t cbd_randomness_bytes(const KyberPoly& poly, KyberConstants::KyberEta eta) {
96 switch(eta) {
98 return 2 * poly.size() / 4;
100 return 3 * poly.size() / 4;
101 }
102
104 }
105
106 /// Samples all @p polys with consecutive nonces, allowing the PRF
107 /// outputs to be produced in one batch
108 void sample_polys_cbd(std::span<KyberPoly* const> polys, KyberConstants::KyberEta eta) {
109 BOTAN_ASSERT_NOMSG(!polys.empty());
110 const size_t poly_bytes = cbd_randomness_bytes(*polys[0], eta);
111
112 KyberSamplingRandomness randomness(polys.size() * poly_bytes);
113 std::vector<StrongSpan<KyberSamplingRandomness>> outputs(polys.size());
114 for(size_t i = 0; i < polys.size(); ++i) {
115 outputs[i] = StrongSpan(randomness).subspan(i * poly_bytes, poly_bytes);
116 }
117
118 const auto& sym = m_mode.symmetric_primitives();
119 sym.PRF_batch(outputs, m_seed, m_nonce);
120 m_nonce += static_cast<uint8_t>(polys.size());
121
122 for(size_t i = 0; i < polys.size(); ++i) {
123 sample_polynomial_from_cbd(*polys[i], eta, outputs[i]);
124 }
125 }
126
127 private:
128 StrongSpan<const SeedT> m_seed;
129 const KyberConstants& m_mode;
130 uint8_t m_nonce;
131};
132
133template <typename T>
135
136} // namespace Botan::Kyber_Algos
137
138#endif
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ASSERT_UNREACHABLE()
Definition assert.h:173
std::vector< Polynomial< Trait, D > * > polynomials()
Definition pqcrystals.h:484
constexpr size_t size() const
Definition pqcrystals.h:278
size_t polynomial_vector_bytes() const
byte length of an encoded polynomial vector
PolynomialSampler(StrongSpan< const SeedT > seed, const KyberConstants &mode)
Definition kyber_algos.h:67
std::pair< KyberPolyVec, KyberPolyVec > sample_polynomial_vector_pair_cbd_eta1()
Samples two polynomial vectors in a single PRF batch.
Definition kyber_algos.h:77
KyberPolyVec sample_polynomial_vector_cbd_eta1()
Definition kyber_algos.h:70
std::pair< KyberPolyVec, KyberPoly > sample_polynomial_vector_and_poly_cbd_eta2()
Samples a polynomial vector and a single polynomial in one PRF batch.
Definition kyber_algos.h:86
PolynomialSampler(T, const KyberConstants &) -> PolynomialSampler< T >
void encode_polynomial_vector(std::span< uint8_t > out, const KyberPolyVecNTT &vec)
KyberMessage polynomial_to_message(const KyberPoly &p)
KyberPolyMat sample_matrix(StrongSpan< const KyberSeedRho > seed, bool transposed, const KyberConstants &mode)
void compress_ciphertext(StrongSpan< KyberCompressedCiphertext > out, const KyberPolyVec &u, const KyberPoly &v, const KyberConstants &m_mode)
KyberInternalKeypair expand_keypair(KyberPrivateKeySeed seed, KyberConstants mode)
KyberPoly polynomial_from_message(StrongSpan< const KyberMessage > msg)
void sample_polynomial_from_cbd(KyberPoly &poly, KyberConstants::KyberEta eta, StrongSpan< const KyberSamplingRandomness > randomness)
std::pair< KyberPolyVec, KyberPoly > decompress_ciphertext(StrongSpan< const KyberCompressedCiphertext > ct, const KyberConstants &mode)
KyberPolyVecNTT decode_polynomial_vector(std::span< const uint8_t > a, const KyberConstants &mode)
Strong< secure_vector< uint8_t >, struct KyberEncryptionRandomness_ > KyberEncryptionRandomness
Random value used to generate the Kyber ciphertext.
Definition kyber_types.h:48
Strong< secure_vector< uint8_t >, struct KyberMessage_ > KyberMessage
Random message value to be encrypted by the CPA-secure Kyber encryption scheme.
Definition kyber_types.h:45
Botan::CRYSTALS::Polynomial< KyberPolyTraits, Botan::CRYSTALS::Domain::Normal > KyberPoly
Definition kyber_types.h:29
Botan::CRYSTALS::PolynomialVector< KyberPolyTraits, Botan::CRYSTALS::Domain::NTT > KyberPolyVecNTT
Definition kyber_types.h:26
Strong< secure_vector< uint8_t >, struct KyberSamplingRandomness_ > KyberSamplingRandomness
PRF value used for sampling of error polynomials.
Definition kyber_types.h:51
constexpr auto concat(Rs &&... ranges)
Definition concat_util.h:95
std::pair< std::shared_ptr< const Kyber_PublicKeyInternal >, std::shared_ptr< const Kyber_PrivateKeyInternal > > KyberInternalKeypair
Definition kyber_types.h:73
Botan::CRYSTALS::PolynomialMatrix< KyberPolyTraits > KyberPolyMat
Definition kyber_types.h:27
Botan::CRYSTALS::PolynomialVector< KyberPolyTraits, Botan::CRYSTALS::Domain::Normal > KyberPolyVec
Definition kyber_types.h:30