#include <kyber_structures.h>

Public Member Functions
void	csubq ()

void	invntt_tomont ()

void	ntt ()

Polynomial &	operator+= (const Polynomial &other)

Polynomial &	operator-= (const Polynomial &other)

int16_t &	operator[] (size_t idx)

int16_t	operator[] (size_t idx) const

	Polynomial ()

void	reduce ()

size_t	size () const

void	to_bytes (std::span< uint8_t > out)

KyberMessage	to_message ()

void	tomont ()

Static Public Member Functions
static Polynomial	basemul_montgomery (const Polynomial &a, const Polynomial &b)

static Polynomial	cbd2 (StrongSpan< const KyberSamplingRandomness > buf)

static Polynomial	cbd3 (StrongSpan< const KyberSamplingRandomness > buf)

static Polynomial	from_bytes (std::span< const uint8_t > a)

static Polynomial	from_message (StrongSpan< const KyberMessage > msg)

static Polynomial	getnoise_eta1 (KyberSigmaOrEncryptionRandomness seed, uint8_t nonce, const KyberConstants &mode)

static Polynomial	getnoise_eta2 (StrongSpan< const KyberEncryptionRandomness > seed, uint8_t nonce, const KyberConstants &mode)

static Polynomial	sample_rej_uniform (std::unique_ptr< XOF > xof)

Detailed Description

Definition at line 59 of file kyber_structures.h.

Constructor & Destructor Documentation

◆ Polynomial()

Botan::Polynomial::Polynomial ( )

inline

Definition at line 61 of file kyber_structures.h.

61: m_coeffs({0}) {}

Member Function Documentation

◆ basemul_montgomery()

static Polynomial Botan::Polynomial::basemul_montgomery	(	const Polynomial &	a,
		const Polynomial &	b )

inlinestatic

Multiplication of two polynomials in NTT domain

Multiplication of polynomials in Zq[X]/(X^2-zeta) used for multiplication of elements in Rq in NTT domain.

Definition at line 252 of file kyber_structures.h.

                                                                                     {
         /**
          * Multiplication of polynomials in Zq[X]/(X^2-zeta) used for
          * multiplication of elements in Rq in NTT domain.
          */
         auto basemul = [](int16_t r[2], const int16_t s[2], const int16_t t[2], const int16_t zeta) {
            r[0] = fqmul(s[1], t[1]);
            r[0] = fqmul(r[0], zeta);
            r[0] += fqmul(s[0], t[0]);
 
            r[1] = fqmul(s[0], t[1]);
            r[1] += fqmul(s[1], t[0]);
         };
 
         Polynomial r;
 
         for(size_t i = 0; i < r.size() / 4; ++i) {
            basemul(&r.m_coeffs[4 * i], &a.m_coeffs[4 * i], &b.m_coeffs[4 * i], KyberConstants::zetas[64 + i]);
            basemul(
               &r.m_coeffs[4 * i + 2], &a.m_coeffs[4 * i + 2], &b.m_coeffs[4 * i + 2], -KyberConstants::zetas[64 + i]);
         }
 
         return r;
      }

References Botan::KyberConstants::zetas.

Referenced by Botan::PolynomialVector::pointwise_acc_montgomery().

◆ cbd2()

static Polynomial Botan::Polynomial::cbd2 ( StrongSpan< const KyberSamplingRandomness > buf )

inlinestatic

Given an array of uniformly random bytes, compute polynomial with coefficients distributed according to a centered binomial distribution with parameter eta=2

Definition at line 101 of file kyber_structures.h.

                                                                            {
         Polynomial r;
 
         BOTAN_ASSERT(buf.size() == (2 * r.size() / 4), "wrong input buffer size for cbd2");
 
         BufferSlicer bs(buf);
         for(size_t i = 0; i < r.size() / 8; ++i) {
            uint32_t t = load_le(bs.take<4>());
            uint32_t d = t & 0x55555555;
            d += (t >> 1) & 0x55555555;
 
            for(size_t j = 0; j < 8; ++j) {
               int16_t a = (d >> (4 * j + 0)) & 0x3;
               int16_t b = (d >> (4 * j + 2)) & 0x3;
               r.m_coeffs[8 * i + j] = a - b;
            }
         }
         BOTAN_ASSERT_NOMSG(bs.empty());
 
         return r;
      }

References BOTAN_ASSERT, BOTAN_ASSERT_NOMSG, Botan::BufferSlicer::empty(), Botan::load_le(), size(), Botan::StrongSpan< T >::size(), and Botan::BufferSlicer::take().

Referenced by getnoise_eta1(), and getnoise_eta2().

◆ cbd3()

static Polynomial Botan::Polynomial::cbd3 ( StrongSpan< const KyberSamplingRandomness > buf )

inlinestatic

Given an array of uniformly random bytes, compute polynomial with coefficients distributed according to a centered binomial distribution with parameter eta=3

This function is only needed for Kyber-512

Definition at line 129 of file kyber_structures.h.

                                                                            {
         Polynomial r;
 
         BOTAN_ASSERT(buf.size() == (3 * r.size() / 4), "wrong input buffer size for cbd3");
 
         // Note: load_le<> does not support loading a 3-byte value
         const auto load_le = [](std::span<const uint8_t, 3> in) { return make_uint32(0, in[2], in[1], in[0]); };
 
         BufferSlicer bs(buf);
         for(size_t i = 0; i < r.size() / 4; ++i) {
            uint32_t t = load_le(bs.take<3>());
            uint32_t d = t & 0x00249249;
            d += (t >> 1) & 0x00249249;
            d += (t >> 2) & 0x00249249;
 
            for(size_t j = 0; j < 4; ++j) {
               int16_t a = (d >> (6 * j + 0)) & 0x7;
               int16_t b = (d >> (6 * j + 3)) & 0x7;
               r.m_coeffs[4 * i + j] = a - b;
            }
         }
         BOTAN_ASSERT_NOMSG(bs.empty());
 
         return r;
      }

References BOTAN_ASSERT, BOTAN_ASSERT_NOMSG, Botan::BufferSlicer::empty(), Botan::load_le(), Botan::make_uint32(), size(), Botan::StrongSpan< T >::size(), and Botan::BufferSlicer::take().

Referenced by getnoise_eta1().

◆ csubq()

void Botan::Polynomial::csubq ( )

inline

Applies conditional subtraction of q to each coefficient of the polynomial.

Definition at line 66 of file kyber_structures.h.

                   {
         for(auto& coeff : m_coeffs) {
            coeff -= KyberConstants::Q;
            coeff += (coeff >> 15) & KyberConstants::Q;
         }
      }

References Botan::KyberConstants::Q.

Referenced by to_bytes(), and to_message().

◆ from_bytes()

static Polynomial Botan::Polynomial::from_bytes ( std::span< const uint8_t > a )

inlinestatic

Definition at line 184 of file kyber_structures.h.

                                                             {
         Polynomial r;
         for(size_t i = 0; i < r.size() / 2; ++i) {
            r.m_coeffs[2 * i] = ((a[3 * i + 0] >> 0) | (static_cast<uint16_t>(a[3 * i + 1]) << 8)) & 0xFFF;
            r.m_coeffs[2 * i + 1] = ((a[3 * i + 1] >> 4) | (static_cast<uint16_t>(a[3 * i + 2]) << 4)) & 0xFFF;
         }
         return r;
      }

References size().

Referenced by Botan::PolynomialVector::from_bytes().

◆ from_message()

static Polynomial Botan::Polynomial::from_message ( StrongSpan< const KyberMessage > msg )

inlinestatic

Definition at line 193 of file kyber_structures.h.

                                                                         {
         BOTAN_ASSERT(msg.size() == KyberConstants::N / 8, "message length must be Kyber_N/8 bytes");
 
         Polynomial r;
         for(size_t i = 0; i < r.size() / 8; ++i) {
            for(size_t j = 0; j < 8; ++j) {
               const auto mask = CT::Mask<uint16_t>::is_zero((msg[i] >> j) & 1);
               r.m_coeffs[8 * i + j] = mask.if_not_set_return((KyberConstants::Q + 1) / 2);
            }
         }
         return r;
      }

References BOTAN_ASSERT, Botan::CT::Mask< T >::is_zero(), Botan::KyberConstants::N, Botan::KyberConstants::Q, size(), and Botan::StrongSpan< T >::size().

Referenced by Botan::Kyber_PublicKeyInternal::indcpa_encrypt().

◆ getnoise_eta1()

static Polynomial Botan::Polynomial::getnoise_eta1	(	KyberSigmaOrEncryptionRandomness	seed,
		uint8_t	nonce,
		const KyberConstants &	mode )

inlinestatic

Sample a polynomial deterministically from a seed and a nonce, with output polynomial close to centered binomial distribution with parameter mode.eta1()

Definition at line 173 of file kyber_structures.h.

                                                                  {
         const auto eta1 = mode.eta1();
         BOTAN_ASSERT(eta1 == 2 || eta1 == 3, "Invalid eta1 value");
 
         const auto outlen = eta1 * KyberConstants::N / 4;
         return (eta1 == 2) ? Polynomial::cbd2(mode.symmetric_primitives().PRF(seed, nonce, outlen))
                            : Polynomial::cbd3(mode.symmetric_primitives().PRF(seed, nonce, outlen));
      }

References BOTAN_ASSERT, cbd2(), cbd3(), Botan::KyberConstants::eta1(), Botan::KyberConstants::N, Botan::Kyber_Symmetric_Primitives::PRF(), and Botan::KyberConstants::symmetric_primitives().

Referenced by Botan::PolynomialVector::getnoise_eta1().

◆ getnoise_eta2()

static Polynomial Botan::Polynomial::getnoise_eta2	(	StrongSpan< const KyberEncryptionRandomness >	seed,
		uint8_t	nonce,
		const KyberConstants &	mode )

inlinestatic

Sample a polynomial deterministically from a seed and a nonce, with output polynomial close to centered binomial distribution with parameter eta=2.

Definition at line 159 of file kyber_structures.h.

                                                                  {
         const auto eta2 = mode.eta2();
         BOTAN_ASSERT(eta2 == 2, "Invalid eta2 value");
 
         const auto outlen = eta2 * KyberConstants::N / 4;
         return Polynomial::cbd2(mode.symmetric_primitives().PRF(seed, nonce, outlen));
      }

References BOTAN_ASSERT, cbd2(), Botan::KyberConstants::eta2(), Botan::KyberConstants::N, Botan::Kyber_Symmetric_Primitives::PRF(), and Botan::KyberConstants::symmetric_primitives().

Referenced by Botan::PolynomialVector::getnoise_eta2(), and Botan::Kyber_PublicKeyInternal::indcpa_encrypt().

◆ invntt_tomont()

void Botan::Polynomial::invntt_tomont ( )

inline

Computes inverse of negacyclic number-theoretic transform (NTT) of a polynomial in place; inputs assumed to be in bitreversed order, output in normal order.

Definition at line 337 of file kyber_structures.h.

                           {
         for(size_t len = 2, k = 0; len <= size() / 2; len *= 2) {
            for(size_t start = 0, j = 0; start < size(); start = j + len) {
               const auto zeta = KyberConstants::zetas_inv[k++];
               for(j = start; j < start + len; ++j) {
                  const auto t = m_coeffs[j];
                  m_coeffs[j] = barrett_reduce(t + m_coeffs[j + len]);
                  m_coeffs[j + len] = fqmul(zeta, t - m_coeffs[j + len]);
               }
            }
         }
 
         for(auto& c : m_coeffs) {
            c = fqmul(c, KyberConstants::zetas_inv[127]);
         }
      }

References size(), and Botan::KyberConstants::zetas_inv.

◆ ntt()

void Botan::Polynomial::ntt ( )

inline

Computes negacyclic number-theoretic transform (NTT) of a polynomial in place; inputs assumed to be in normal order, output in bitreversed order.

Definition at line 318 of file kyber_structures.h.

                 {
         for(size_t len = size() / 2, k = 0; len >= 2; len /= 2) {
            for(size_t start = 0, j = 0; start < size(); start = j + len) {
               const auto zeta = KyberConstants::zetas[++k];
               for(j = start; j < start + len; ++j) {
                  const auto t = fqmul(zeta, m_coeffs[j + len]);
                  m_coeffs[j + len] = m_coeffs[j] - t;
                  m_coeffs[j] = m_coeffs[j] + t;
               }
            }
         }
 
         reduce();
      }

References reduce(), size(), and Botan::KyberConstants::zetas.

Referenced by Botan::Kyber_PrivateKeyInternal::indcpa_decrypt().

◆ operator+=()

Polynomial & Botan::Polynomial::operator+= ( const Polynomial & other )

inline

Adds two polynomials element-wise. Does not perform a reduction after the addition. Therefore this operation might cause an integer overflow.

Definition at line 227 of file kyber_structures.h.

                                                      {
         for(size_t i = 0; i < this->size(); ++i) {
            BOTAN_DEBUG_ASSERT(static_cast<int32_t>(this->m_coeffs[i]) + other.m_coeffs[i] <=
                               std::numeric_limits<int16_t>::max());
            this->m_coeffs[i] = this->m_coeffs[i] + other.m_coeffs[i];
         }
         return *this;
      }

References BOTAN_DEBUG_ASSERT, and size().

◆ operator-=()

Polynomial & Botan::Polynomial::operator-= ( const Polynomial & other )

inline

Subtracts two polynomials element-wise. Does not perform a reduction after the subtraction. Therefore this operation might cause an integer underflow.

Definition at line 240 of file kyber_structures.h.

                                                      {
         for(size_t i = 0; i < this->size(); ++i) {
            BOTAN_DEBUG_ASSERT(static_cast<int32_t>(other.m_coeffs[i]) - this->m_coeffs[i] >=
                               std::numeric_limits<int16_t>::min());
            this->m_coeffs[i] = other.m_coeffs[i] - this->m_coeffs[i];
         }
         return *this;
      }

References BOTAN_DEBUG_ASSERT, and size().

◆ operator[]() [1/2]

int16_t & Botan::Polynomial::operator[] ( size_t idx )

inline

Definition at line 358 of file kyber_structures.h.

358{ return m_coeffs[idx]; }

◆ operator[]() [2/2]

int16_t Botan::Polynomial::operator[] ( size_t idx ) const

inline

Definition at line 356 of file kyber_structures.h.

356{ return m_coeffs[idx]; }

◆ reduce()

void Botan::Polynomial::reduce ( )

inline

Applies Barrett reduction to all coefficients of the polynomial

Definition at line 76 of file kyber_structures.h.

                    {
         for(auto& c : m_coeffs) {
            c = barrett_reduce(c);
         }
      }

Referenced by ntt(), and Botan::PolynomialVector::pointwise_acc_montgomery().

◆ sample_rej_uniform()

static Polynomial Botan::Polynomial::sample_rej_uniform ( std::unique_ptr< XOF > xof )

inlinestatic

Run rejection sampling on uniform random bytes to generate uniform random integers mod q.

Definition at line 281 of file kyber_structures.h.

                                                                   {
         Polynomial p;
 
         size_t count = 0;
         while(count < p.size()) {
            std::array<uint8_t, 3> buf;
            xof->output(buf);
 
            const uint16_t val0 = ((buf[0] >> 0) | (static_cast<uint16_t>(buf[1]) << 8)) & 0xFFF;
            const uint16_t val1 = ((buf[1] >> 4) | (static_cast<uint16_t>(buf[2]) << 4)) & 0xFFF;
 
            if(val0 < KyberConstants::Q) {
               p.m_coeffs[count++] = val0;
            }
            if(count < p.size() && val1 < KyberConstants::Q) {
               p.m_coeffs[count++] = val1;
            }
         }
 
         return p;
      }

References Botan::KyberConstants::Q, and size().

Referenced by Botan::PolynomialMatrix::generate().

◆ size()

size_t Botan::Polynomial::size ( ) const

inline

Definition at line 354 of file kyber_structures.h.

354{ return m_coeffs.size(); }

Referenced by cbd2(), cbd3(), from_bytes(), from_message(), invntt_tomont(), ntt(), operator+=(), operator-=(), sample_rej_uniform(), to_bytes(), and to_message().

◆ to_bytes()

void Botan::Polynomial::to_bytes ( std::span< uint8_t > out )

inline

Definition at line 82 of file kyber_structures.h.

                                          {
         this->csubq();
 
         BufferStuffer bs(out);
         for(size_t i = 0; i < size() / 2; ++i) {
            const uint16_t t0 = m_coeffs[2 * i];
            const uint16_t t1 = m_coeffs[2 * i + 1];
            auto buf = bs.next<3>();
            buf[0] = static_cast<uint8_t>(t0 >> 0);
            buf[1] = static_cast<uint8_t>((t0 >> 8) | (t1 << 4));
            buf[2] = static_cast<uint8_t>(t1 >> 4);
         }
         BOTAN_ASSERT_NOMSG(bs.full());
      }

References BOTAN_ASSERT_NOMSG, csubq(), Botan::BufferStuffer::full(), Botan::BufferStuffer::next(), and size().

◆ to_message()

KyberMessage Botan::Polynomial::to_message ( )

inline

Definition at line 206 of file kyber_structures.h.

                                {
         KyberMessage result(size() / 8);
 
         this->csubq();
 
         for(size_t i = 0; i < size() / 8; ++i) {
            result[i] = 0;
            for(size_t j = 0; j < 8; ++j) {
               const uint16_t t = detail::ct_int_div_kyber_q((static_cast<uint16_t>(this->m_coeffs[8 * i + j]) << 1) +
                                                             KyberConstants::Q / 2);
               result[i] |= (t & 1) << j;
            }
         }
 
         return result;
      }

References csubq(), Botan::detail::ct_int_div_kyber_q(), Botan::KyberConstants::Q, and size().

◆ tomont()

void Botan::Polynomial::tomont ( )

inline

Inplace conversion of all coefficients of a polynomial from normal domain to Montgomery domain.

Definition at line 307 of file kyber_structures.h.

                    {
         constexpr int16_t f = (1ULL << 32) % KyberConstants::Q;
         for(auto& c : m_coeffs) {
            c = montgomery_reduce(static_cast<int32_t>(c) * f);
         }
      }

References Botan::KyberConstants::Q.

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

src/lib/pubkey/kyber/kyber_common/kyber_structures.h

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ Polynomial()

Member Function Documentation

◆ basemul_montgomery()

◆ cbd2()

◆ cbd3()

◆ csubq()

◆ from_bytes()

◆ from_message()

◆ getnoise_eta1()

◆ getnoise_eta2()

◆ invntt_tomont()

◆ ntt()

◆ operator+=()

◆ operator-=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ reduce()

◆ sample_rej_uniform()

◆ size()

◆ to_bytes()

◆ to_message()

◆ tomont()