tor-browser

kyber-pqcrystals-ref.c (90148B)

---

/*
* SPDX-License-Identifier: Apache-2.0
*
* This file was generated from
*   https://github.com/pq-crystals/kyber/commit/e0d1c6ff
*
* Files from that repository are listed here surrounded by
* "* begin: [file] *" and "* end: [file] *" comments.
*
* The following changes have been made:
*  - include guards have been removed,
*  - include directives have been removed,
*  - "#ifdef KYBER90S" blocks have been evaluated with "KYBER90S" undefined,
*  - functions outside of kem.c have been made static.
*/

/** begin: ref/LICENSE **
Public Domain (https://creativecommons.org/share-your-work/public-domain/cc0/);
or Apache 2.0 License (https://www.apache.org/licenses/LICENSE-2.0.html).

For Keccak and AES we are using public-domain
code from sources and by authors listed in
comments on top of the respective files.
** end: ref/LICENSE **/

/** begin: ref/AUTHORS **
Joppe Bos,
Léo Ducas,
Eike Kiltz,
Tancrède Lepoint,
Vadim Lyubashevsky,
John Schanck,
Peter Schwabe,
Gregor Seiler,
Damien Stehlé
** end: ref/AUTHORS **/

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

#ifdef FREEBL_NO_DEPEND
#include "stubs.h"
#endif

#include "secport.h"

// We need to provide an implementation of randombytes to avoid an unused
// function warning. We don't use the randomized API in freebl, so we'll make
// calling randombytes an error.
static void
randombytes(uint8_t *out, size_t outlen)
{
   // this memset is to avoid "maybe-uninitialized" warnings that gcc-11 issues
   // for the (unused) crypto_kem_keypair and crypto_kem_enc functions.
   memset(out, 0, outlen);
   assert(0);
}

/*************************************************
* Name:        verify
*
* Description: Compare two arrays for equality in constant time.
*
* Arguments:   const uint8_t *a: pointer to first byte array
*              const uint8_t *b: pointer to second byte array
*              size_t len:       length of the byte arrays
*
* Returns 0 if the byte arrays are equal, 1 otherwise
**************************************************/
static int
verify(const uint8_t *a, const uint8_t *b, size_t len)
{
   return NSS_SecureMemcmp(a, b, len);
}

/*************************************************
* Name:        cmov
*
* Description: Copy len bytes from x to r if b is 1;
*              don't modify x if b is 0. Requires b to be in {0,1};
*              assumes two's complement representation of negative integers.
*              Runs in constant time.
*
* Arguments:   uint8_t *r:       pointer to output byte array
*              const uint8_t *x: pointer to input byte array
*              size_t len:       Amount of bytes to be copied
*              uint8_t b:        Condition bit; has to be in {0,1}
**************************************************/
static void
cmov(uint8_t *r, const uint8_t *x, size_t len, uint8_t b)
{
   NSS_SecureSelect(r, r, x, len, b);
}

/** begin: ref/params.h **/
#ifndef KYBER_K
#define KYBER_K 3 /* Change this for different security strengths */
#endif

//#define KYBER_90S	/* Uncomment this if you want the 90S variant */

/* Don't change parameters below this line */
#if (KYBER_K == 2)
#define KYBER_NAMESPACE(s) pqcrystals_kyber512_ref_##s
#elif (KYBER_K == 3)
#define KYBER_NAMESPACE(s) pqcrystals_kyber768_ref_##s
#elif (KYBER_K == 4)
#define KYBER_NAMESPACE(s) pqcrystals_kyber1024_ref_##s
#else
#error "KYBER_K must be in {2,3,4}"
#endif

#define KYBER_N 256
#define KYBER_Q 3329

#define KYBER_SYMBYTES 32 /* size in bytes of hashes, and seeds */
#define KYBER_SSBYTES 32  /* size in bytes of shared key */

#define KYBER_POLYBYTES 384
#define KYBER_POLYVECBYTES (KYBER_K * KYBER_POLYBYTES)

#if KYBER_K == 2
#define KYBER_ETA1 3
#define KYBER_POLYCOMPRESSEDBYTES 128
#define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320)
#elif KYBER_K == 3
#define KYBER_ETA1 2
#define KYBER_POLYCOMPRESSEDBYTES 128
#define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320)
#elif KYBER_K == 4
#define KYBER_ETA1 2
#define KYBER_POLYCOMPRESSEDBYTES 160
#define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 352)
#endif

#define KYBER_ETA2 2

#define KYBER_INDCPA_MSGBYTES (KYBER_SYMBYTES)
#define KYBER_INDCPA_PUBLICKEYBYTES (KYBER_POLYVECBYTES + KYBER_SYMBYTES)
#define KYBER_INDCPA_SECRETKEYBYTES (KYBER_POLYVECBYTES)
#define KYBER_INDCPA_BYTES (KYBER_POLYVECCOMPRESSEDBYTES + KYBER_POLYCOMPRESSEDBYTES)

#define KYBER_PUBLICKEYBYTES (KYBER_INDCPA_PUBLICKEYBYTES)
/* 32 bytes of additional space to save H(pk) */
#define KYBER_SECRETKEYBYTES (KYBER_INDCPA_SECRETKEYBYTES + KYBER_INDCPA_PUBLICKEYBYTES + 2 * KYBER_SYMBYTES)
#define KYBER_CIPHERTEXTBYTES (KYBER_INDCPA_BYTES)
/** end: ref/params.h **/

/** begin: ref/reduce.h **/
#define MONT -1044 // 2^16 mod q
#define QINV -3327 // q^-1 mod 2^16

#define montgomery_reduce KYBER_NAMESPACE(montgomery_reduce)
static int16_t montgomery_reduce(int32_t a);

#define barrett_reduce KYBER_NAMESPACE(barrett_reduce)
static int16_t barrett_reduce(int16_t a);
/** end: ref/reduce.h **/

/** begin: ref/ntt.h **/
#define zetas KYBER_NAMESPACE(zetas)
extern const int16_t zetas[128];

#define ntt KYBER_NAMESPACE(ntt)
static void ntt(int16_t poly[256]);

#define invntt KYBER_NAMESPACE(invntt)
static void invntt(int16_t poly[256]);

#define basemul KYBER_NAMESPACE(basemul)
static void basemul(int16_t r[2], const int16_t a[2], const int16_t b[2], int16_t zeta);
/** end: ref/ntt.h **/

/** begin: ref/poly.h **/
/*
* Elements of R_q = Z_q[X]/(X^n + 1). Represents polynomial
* coeffs[0] + X*coeffs[1] + X^2*coeffs[2] + ... + X^{n-1}*coeffs[n-1]
*/
typedef struct {
   int16_t coeffs[KYBER_N];
} poly;

#define poly_compress KYBER_NAMESPACE(poly_compress)
static void poly_compress(uint8_t r[KYBER_POLYCOMPRESSEDBYTES], const poly *a);
#define poly_decompress KYBER_NAMESPACE(poly_decompress)
static void poly_decompress(poly *r, const uint8_t a[KYBER_POLYCOMPRESSEDBYTES]);

#define poly_tobytes KYBER_NAMESPACE(poly_tobytes)
static void poly_tobytes(uint8_t r[KYBER_POLYBYTES], const poly *a);
#define poly_frombytes KYBER_NAMESPACE(poly_frombytes)
static void poly_frombytes(poly *r, const uint8_t a[KYBER_POLYBYTES]);

#define poly_frommsg KYBER_NAMESPACE(poly_frommsg)
static void poly_frommsg(poly *r, const uint8_t msg[KYBER_INDCPA_MSGBYTES]);
#define poly_tomsg KYBER_NAMESPACE(poly_tomsg)
static void poly_tomsg(uint8_t msg[KYBER_INDCPA_MSGBYTES], const poly *r);

#define poly_getnoise_eta1 KYBER_NAMESPACE(poly_getnoise_eta1)
static void poly_getnoise_eta1(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce);

#define poly_getnoise_eta2 KYBER_NAMESPACE(poly_getnoise_eta2)
static void poly_getnoise_eta2(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce);

#define poly_ntt KYBER_NAMESPACE(poly_ntt)
static void poly_ntt(poly *r);
#define poly_invntt_tomont KYBER_NAMESPACE(poly_invntt_tomont)
static void poly_invntt_tomont(poly *r);
#define poly_basemul_montgomery KYBER_NAMESPACE(poly_basemul_montgomery)
static void poly_basemul_montgomery(poly *r, const poly *a, const poly *b);
#define poly_tomont KYBER_NAMESPACE(poly_tomont)
static void poly_tomont(poly *r);

#define poly_reduce KYBER_NAMESPACE(poly_reduce)
static void poly_reduce(poly *r);

#define poly_add KYBER_NAMESPACE(poly_add)
static void poly_add(poly *r, const poly *a, const poly *b);
#define poly_sub KYBER_NAMESPACE(poly_sub)
static void poly_sub(poly *r, const poly *a, const poly *b);
/** end: ref/poly.h **/

/** begin: ref/cbd.h **/
#define poly_cbd_eta1 KYBER_NAMESPACE(poly_cbd_eta1)
static void poly_cbd_eta1(poly *r, const uint8_t buf[KYBER_ETA1 * KYBER_N / 4]);

#define poly_cbd_eta2 KYBER_NAMESPACE(poly_cbd_eta2)
static void poly_cbd_eta2(poly *r, const uint8_t buf[KYBER_ETA2 * KYBER_N / 4]);
/** end: ref/cbd.h **/

/** begin: ref/polyvec.h **/
typedef struct {
   poly vec[KYBER_K];
} polyvec;

#define polyvec_compress KYBER_NAMESPACE(polyvec_compress)
static void polyvec_compress(uint8_t r[KYBER_POLYVECCOMPRESSEDBYTES], const polyvec *a);
#define polyvec_decompress KYBER_NAMESPACE(polyvec_decompress)
static void polyvec_decompress(polyvec *r, const uint8_t a[KYBER_POLYVECCOMPRESSEDBYTES]);

#define polyvec_tobytes KYBER_NAMESPACE(polyvec_tobytes)
static void polyvec_tobytes(uint8_t r[KYBER_POLYVECBYTES], const polyvec *a);
#define polyvec_frombytes KYBER_NAMESPACE(polyvec_frombytes)
static void polyvec_frombytes(polyvec *r, const uint8_t a[KYBER_POLYVECBYTES]);

#define polyvec_ntt KYBER_NAMESPACE(polyvec_ntt)
static void polyvec_ntt(polyvec *r);
#define polyvec_invntt_tomont KYBER_NAMESPACE(polyvec_invntt_tomont)
static void polyvec_invntt_tomont(polyvec *r);

#define polyvec_basemul_acc_montgomery KYBER_NAMESPACE(polyvec_basemul_acc_montgomery)
static void polyvec_basemul_acc_montgomery(poly *r, const polyvec *a, const polyvec *b);

#define polyvec_reduce KYBER_NAMESPACE(polyvec_reduce)
static void polyvec_reduce(polyvec *r);

#define polyvec_add KYBER_NAMESPACE(polyvec_add)
static void polyvec_add(polyvec *r, const polyvec *a, const polyvec *b);
/** end: ref/polyvec.h **/

/** begin: ref/indcpa.h **/
#define gen_matrix KYBER_NAMESPACE(gen_matrix)
static void gen_matrix(polyvec *a, const uint8_t seed[KYBER_SYMBYTES], int transposed);

#define indcpa_keypair_derand KYBER_NAMESPACE(indcpa_keypair_derand)
static void indcpa_keypair_derand(uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
                                 uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES],
                                 const uint8_t coins[KYBER_SYMBYTES]);

#define indcpa_enc KYBER_NAMESPACE(indcpa_enc)
static void indcpa_enc(uint8_t c[KYBER_INDCPA_BYTES],
                      const uint8_t m[KYBER_INDCPA_MSGBYTES],
                      const uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
                      const uint8_t coins[KYBER_SYMBYTES]);

#define indcpa_dec KYBER_NAMESPACE(indcpa_dec)
static void indcpa_dec(uint8_t m[KYBER_INDCPA_MSGBYTES],
                      const uint8_t c[KYBER_INDCPA_BYTES],
                      const uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES]);
/** end: ref/indcpa.h **/

/** begin: ref/fips202.h **/
#define SHAKE128_RATE 168
#define SHAKE256_RATE 136
#define SHA3_256_RATE 136
#define SHA3_512_RATE 72

#define FIPS202_NAMESPACE(s) pqcrystals_kyber_fips202_ref_##s

typedef struct {
   uint64_t s[25];
   unsigned int pos;
} keccak_state;

#define shake128_init FIPS202_NAMESPACE(shake128_init)
void shake128_init(keccak_state *state);
#define shake128_absorb FIPS202_NAMESPACE(shake128_absorb)
void shake128_absorb(keccak_state *state, const uint8_t *in, size_t inlen);
#define shake128_finalize FIPS202_NAMESPACE(shake128_finalize)
void shake128_finalize(keccak_state *state);
#define shake128_squeeze FIPS202_NAMESPACE(shake128_squeeze)
void shake128_squeeze(uint8_t *out, size_t outlen, keccak_state *state);
#define shake128_absorb_once FIPS202_NAMESPACE(shake128_absorb_once)
void shake128_absorb_once(keccak_state *state, const uint8_t *in, size_t inlen);
#define shake128_squeezeblocks FIPS202_NAMESPACE(shake128_squeezeblocks)
void shake128_squeezeblocks(uint8_t *out, size_t nblocks, keccak_state *state);

#define shake256_init FIPS202_NAMESPACE(shake256_init)
void shake256_init(keccak_state *state);
#define shake256_absorb FIPS202_NAMESPACE(shake256_absorb)
void shake256_absorb(keccak_state *state, const uint8_t *in, size_t inlen);
#define shake256_finalize FIPS202_NAMESPACE(shake256_finalize)
void shake256_finalize(keccak_state *state);
#define shake256_squeeze FIPS202_NAMESPACE(shake256_squeeze)
void shake256_squeeze(uint8_t *out, size_t outlen, keccak_state *state);
#define shake256_absorb_once FIPS202_NAMESPACE(shake256_absorb_once)
void shake256_absorb_once(keccak_state *state, const uint8_t *in, size_t inlen);
#define shake256_squeezeblocks FIPS202_NAMESPACE(shake256_squeezeblocks)
void shake256_squeezeblocks(uint8_t *out, size_t nblocks, keccak_state *state);

#define shake128 FIPS202_NAMESPACE(shake128)
void shake128(uint8_t *out, size_t outlen, const uint8_t *in, size_t inlen);
#define shake256 FIPS202_NAMESPACE(shake256)
void shake256(uint8_t *out, size_t outlen, const uint8_t *in, size_t inlen);
#define sha3_256 FIPS202_NAMESPACE(sha3_256)
void sha3_256(uint8_t h[32], const uint8_t *in, size_t inlen);
#define sha3_512 FIPS202_NAMESPACE(sha3_512)
void sha3_512(uint8_t h[64], const uint8_t *in, size_t inlen);
/** end: ref/fips202.h **/

/** begin: ref/symmetric.h **/
typedef keccak_state xof_state;

#define kyber_shake128_absorb KYBER_NAMESPACE(kyber_shake128_absorb)
static void kyber_shake128_absorb(keccak_state *s,
                                 const uint8_t seed[KYBER_SYMBYTES],
                                 uint8_t x,
                                 uint8_t y);

#define kyber_shake256_prf KYBER_NAMESPACE(kyber_shake256_prf)
static void kyber_shake256_prf(uint8_t *out, size_t outlen, const uint8_t key[KYBER_SYMBYTES], uint8_t nonce);

#define XOF_BLOCKBYTES SHAKE128_RATE

#define hash_h(OUT, IN, INBYTES) sha3_256(OUT, IN, INBYTES)
#define hash_g(OUT, IN, INBYTES) sha3_512(OUT, IN, INBYTES)
#define xof_absorb(STATE, SEED, X, Y) kyber_shake128_absorb(STATE, SEED, X, Y)
#define xof_squeezeblocks(OUT, OUTBLOCKS, STATE) shake128_squeezeblocks(OUT, OUTBLOCKS, STATE)
#define prf(OUT, OUTBYTES, KEY, NONCE) kyber_shake256_prf(OUT, OUTBYTES, KEY, NONCE)
#define kdf(OUT, IN, INBYTES) shake256(OUT, KYBER_SSBYTES, IN, INBYTES)
/** end: ref/symmetric.h **/

/** begin: ref/kem.h **/
#define CRYPTO_SECRETKEYBYTES KYBER_SECRETKEYBYTES
#define CRYPTO_PUBLICKEYBYTES KYBER_PUBLICKEYBYTES
#define CRYPTO_CIPHERTEXTBYTES KYBER_CIPHERTEXTBYTES
#define CRYPTO_BYTES KYBER_SSBYTES

#if (KYBER_K == 2)
#define CRYPTO_ALGNAME "Kyber512"
#elif (KYBER_K == 3)
#define CRYPTO_ALGNAME "Kyber768"
#elif (KYBER_K == 4)
#define CRYPTO_ALGNAME "Kyber1024"
#endif

#define crypto_kem_keypair_derand KYBER_NAMESPACE(keypair_derand)
int crypto_kem_keypair_derand(uint8_t *pk, uint8_t *sk, const uint8_t *coins);

#define crypto_kem_keypair KYBER_NAMESPACE(keypair)
int crypto_kem_keypair(uint8_t *pk, uint8_t *sk);

#define crypto_kem_enc_derand KYBER_NAMESPACE(enc_derand)
int crypto_kem_enc_derand(uint8_t *ct, uint8_t *ss, const uint8_t *pk, const uint8_t *coins);

#define crypto_kem_enc KYBER_NAMESPACE(enc)
int crypto_kem_enc(uint8_t *ct, uint8_t *ss, const uint8_t *pk);

#define crypto_kem_dec KYBER_NAMESPACE(dec)
int crypto_kem_dec(uint8_t *ss, const uint8_t *ct, const uint8_t *sk);
/** end: ref/kem.h **/

/** begin: ref/reduce.c **/
/*************************************************
* Name:        montgomery_reduce
*
* Description: Montgomery reduction; given a 32-bit integer a, computes
*              16-bit integer congruent to a * R^-1 mod q, where R=2^16
*
* Arguments:   - int32_t a: input integer to be reduced;
*                           has to be in {-q2^15,...,q2^15-1}
*
* Returns:     integer in {-q+1,...,q-1} congruent to a * R^-1 modulo q.
**************************************************/
static int16_t
montgomery_reduce(int32_t a)
{
   int16_t t;

   t = (int16_t)a * QINV;
   t = (a - (int32_t)t * KYBER_Q) >> 16;
   return t;
}

/*************************************************
* Name:        barrett_reduce
*
* Description: Barrett reduction; given a 16-bit integer a, computes
*              centered representative congruent to a mod q in {-(q-1)/2,...,(q-1)/2}
*
* Arguments:   - int16_t a: input integer to be reduced
*
* Returns:     integer in {-(q-1)/2,...,(q-1)/2} congruent to a modulo q.
**************************************************/
static int16_t
barrett_reduce(int16_t a)
{
   int16_t t;
   const int16_t v = ((1 << 26) + KYBER_Q / 2) / KYBER_Q;

   t = ((int32_t)v * a + (1 << 25)) >> 26;
   t *= KYBER_Q;
   return a - t;
}
/** end: ref/reduce.c **/

/** begin: ref/cbd.c **/
/*************************************************
* Name:        load32_littleendian
*
* Description: load 4 bytes into a 32-bit integer
*              in little-endian order
*
* Arguments:   - const uint8_t *x: pointer to input byte array
*
* Returns 32-bit unsigned integer loaded from x
**************************************************/
static uint32_t
load32_littleendian(const uint8_t x[4])
{
   uint32_t r;
   r = (uint32_t)x[0];
   r |= (uint32_t)x[1] << 8;
   r |= (uint32_t)x[2] << 16;
   r |= (uint32_t)x[3] << 24;
   return r;
}

/*************************************************
* Name:        load24_littleendian
*
* Description: load 3 bytes into a 32-bit integer
*              in little-endian order.
*              This function is only needed for Kyber-512
*
* Arguments:   - const uint8_t *x: pointer to input byte array
*
* Returns 32-bit unsigned integer loaded from x (most significant byte is zero)
**************************************************/
#if KYBER_ETA1 == 3
static uint32_t
load24_littleendian(const uint8_t x[3])
{
   uint32_t r;
   r = (uint32_t)x[0];
   r |= (uint32_t)x[1] << 8;
   r |= (uint32_t)x[2] << 16;
   return r;
}
#endif

/*************************************************
* Name:        cbd2
*
* Description: Given an array of uniformly random bytes, compute
*              polynomial with coefficients distributed according to
*              a centered binomial distribution with parameter eta=2
*
* Arguments:   - poly *r: pointer to output polynomial
*              - const uint8_t *buf: pointer to input byte array
**************************************************/
static void
cbd2(poly *r, const uint8_t buf[2 * KYBER_N / 4])
{
   unsigned int i, j;
   uint32_t t, d;
   int16_t a, b;

   for (i = 0; i < KYBER_N / 8; i++) {
       t = load32_littleendian(buf + 4 * i);
       d = t & 0x55555555;
       d += (t >> 1) & 0x55555555;

       for (j = 0; j < 8; j++) {
           a = (d >> (4 * j + 0)) & 0x3;
           b = (d >> (4 * j + 2)) & 0x3;
           r->coeffs[8 * i + j] = a - b;
       }
   }
}

/*************************************************
* Name:        cbd3
*
* Description: 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
*
* Arguments:   - poly *r: pointer to output polynomial
*              - const uint8_t *buf: pointer to input byte array
**************************************************/
#if KYBER_ETA1 == 3
static void
cbd3(poly *r, const uint8_t buf[3 * KYBER_N / 4])
{
   unsigned int i, j;
   uint32_t t, d;
   int16_t a, b;

   for (i = 0; i < KYBER_N / 4; i++) {
       t = load24_littleendian(buf + 3 * i);
       d = t & 0x00249249;
       d += (t >> 1) & 0x00249249;
       d += (t >> 2) & 0x00249249;

       for (j = 0; j < 4; j++) {
           a = (d >> (6 * j + 0)) & 0x7;
           b = (d >> (6 * j + 3)) & 0x7;
           r->coeffs[4 * i + j] = a - b;
       }
   }
}
#endif

static void
poly_cbd_eta1(poly *r, const uint8_t buf[KYBER_ETA1 * KYBER_N / 4])
{
#if KYBER_ETA1 == 2
   cbd2(r, buf);
#elif KYBER_ETA1 == 3
   cbd3(r, buf);
#else
#error "This implementation requires eta1 in {2,3}"
#endif
}

static void
poly_cbd_eta2(poly *r, const uint8_t buf[KYBER_ETA2 * KYBER_N / 4])
{
#if KYBER_ETA2 == 2
   cbd2(r, buf);
#else
#error "This implementation requires eta2 = 2"
#endif
}
/** end: ref/cbd.c **/

/** begin: ref/ntt.c **/
/* Code to generate zetas and zetas_inv used in the number-theoretic transform:

#define KYBER_ROOT_OF_UNITY 17

static const uint8_t tree[128] = {
 0, 64, 32, 96, 16, 80, 48, 112, 8, 72, 40, 104, 24, 88, 56, 120,
 4, 68, 36, 100, 20, 84, 52, 116, 12, 76, 44, 108, 28, 92, 60, 124,
 2, 66, 34, 98, 18, 82, 50, 114, 10, 74, 42, 106, 26, 90, 58, 122,
 6, 70, 38, 102, 22, 86, 54, 118, 14, 78, 46, 110, 30, 94, 62, 126,
 1, 65, 33, 97, 17, 81, 49, 113, 9, 73, 41, 105, 25, 89, 57, 121,
 5, 69, 37, 101, 21, 85, 53, 117, 13, 77, 45, 109, 29, 93, 61, 125,
 3, 67, 35, 99, 19, 83, 51, 115, 11, 75, 43, 107, 27, 91, 59, 123,
 7, 71, 39, 103, 23, 87, 55, 119, 15, 79, 47, 111, 31, 95, 63, 127
};

static void init_ntt() {
 unsigned int i;
 int16_t tmp[128];

 tmp[0] = MONT;
 for(i=1;i<128;i++)
   tmp[i] = fqmul(tmp[i-1],MONT*KYBER_ROOT_OF_UNITY % KYBER_Q);

 for(i=0;i<128;i++) {
   zetas[i] = tmp[tree[i]];
   if(zetas[i] > KYBER_Q/2)
     zetas[i] -= KYBER_Q;
   if(zetas[i] < -KYBER_Q/2)
     zetas[i] += KYBER_Q;
 }
}
*/

const int16_t zetas[128] = {
   -1044, -758, -359, -1517, 1493, 1422, 287, 202,
   -171, 622, 1577, 182, 962, -1202, -1474, 1468,
   573, -1325, 264, 383, -829, 1458, -1602, -130,
   -681, 1017, 732, 608, -1542, 411, -205, -1571,
   1223, 652, -552, 1015, -1293, 1491, -282, -1544,
   516, -8, -320, -666, -1618, -1162, 126, 1469,
   -853, -90, -271, 830, 107, -1421, -247, -951,
   -398, 961, -1508, -725, 448, -1065, 677, -1275,
   -1103, 430, 555, 843, -1251, 871, 1550, 105,
   422, 587, 177, -235, -291, -460, 1574, 1653,
   -246, 778, 1159, -147, -777, 1483, -602, 1119,
   -1590, 644, -872, 349, 418, 329, -156, -75,
   817, 1097, 603, 610, 1322, -1285, -1465, 384,
   -1215, -136, 1218, -1335, -874, 220, -1187, -1659,
   -1185, -1530, -1278, 794, -1510, -854, -870, 478,
   -108, -308, 996, 991, 958, -1460, 1522, 1628
};

/*************************************************
* Name:        fqmul
*
* Description: Multiplication followed by Montgomery reduction
*
* Arguments:   - int16_t a: first factor
*              - int16_t b: second factor
*
* Returns 16-bit integer congruent to a*b*R^{-1} mod q
**************************************************/
static int16_t
fqmul(int16_t a, int16_t b)
{
   return montgomery_reduce((int32_t)a * b);
}

/*************************************************
* Name:        ntt
*
* Description: Inplace number-theoretic transform (NTT) in Rq.
*              input is in standard order, output is in bitreversed order
*
* Arguments:   - int16_t r[256]: pointer to input/output vector of elements of Zq
**************************************************/
static void
ntt(int16_t r[256])
{
   unsigned int len, start, j, k;
   int16_t t, zeta;

   k = 1;
   for (len = 128; len >= 2; len >>= 1) {
       for (start = 0; start < 256; start = j + len) {
           zeta = zetas[k++];
           for (j = start; j < start + len; j++) {
               t = fqmul(zeta, r[j + len]);
               r[j + len] = r[j] - t;
               r[j] = r[j] + t;
           }
       }
   }
}

/*************************************************
* Name:        invntt_tomont
*
* Description: Inplace inverse number-theoretic transform in Rq and
*              multiplication by Montgomery factor 2^16.
*              Input is in bitreversed order, output is in standard order
*
* Arguments:   - int16_t r[256]: pointer to input/output vector of elements of Zq
**************************************************/
static void
invntt(int16_t r[256])
{
   unsigned int start, len, j, k;
   int16_t t, zeta;
   const int16_t f = 1441; // mont^2/128

   k = 127;
   for (len = 2; len <= 128; len <<= 1) {
       for (start = 0; start < 256; start = j + len) {
           zeta = zetas[k--];
           for (j = start; j < start + len; j++) {
               t = r[j];
               r[j] = barrett_reduce(t + r[j + len]);
               r[j + len] = r[j + len] - t;
               r[j + len] = fqmul(zeta, r[j + len]);
           }
       }
   }

   for (j = 0; j < 256; j++)
       r[j] = fqmul(r[j], f);
}

/*************************************************
* Name:        basemul
*
* Description: Multiplication of polynomials in Zq[X]/(X^2-zeta)
*              used for multiplication of elements in Rq in NTT domain
*
* Arguments:   - int16_t r[2]: pointer to the output polynomial
*              - const int16_t a[2]: pointer to the first factor
*              - const int16_t b[2]: pointer to the second factor
*              - int16_t zeta: integer defining the reduction polynomial
**************************************************/
static void
basemul(int16_t r[2], const int16_t a[2], const int16_t b[2], int16_t zeta)
{
   r[0] = fqmul(a[1], b[1]);
   r[0] = fqmul(r[0], zeta);
   r[0] += fqmul(a[0], b[0]);
   r[1] = fqmul(a[0], b[1]);
   r[1] += fqmul(a[1], b[0]);
}
/** end: ref/ntt.c **/

/** begin: ref/poly.c **/
/*************************************************
* Name:        poly_compress
*
* Description: Compression and subsequent serialization of a polynomial
*
* Arguments:   - uint8_t *r: pointer to output byte array
*                            (of length KYBER_POLYCOMPRESSEDBYTES)
*              - const poly *a: pointer to input polynomial
**************************************************/
static void
poly_compress(uint8_t r[KYBER_POLYCOMPRESSEDBYTES], const poly *a)
{
   unsigned int i, j;
   int16_t u;
   uint32_t d0;
   uint8_t t[8];

#if (KYBER_POLYCOMPRESSEDBYTES == 128)
   for (i = 0; i < KYBER_N / 8; i++) {
       for (j = 0; j < 8; j++) {
           // map to positive standard representatives
           u = a->coeffs[8 * i + j];
           u += (u >> 15) & KYBER_Q;
           /*    t[j] = ((((uint16_t)u << 4) + KYBER_Q/2)/KYBER_Q) & 15; */
           d0 = u << 4;
           d0 += 1665;
           d0 *= 80635;
           d0 >>= 28;
           t[j] = d0 & 0xf;
       }

       r[0] = t[0] | (t[1] << 4);
       r[1] = t[2] | (t[3] << 4);
       r[2] = t[4] | (t[5] << 4);
       r[3] = t[6] | (t[7] << 4);
       r += 4;
   }
#elif (KYBER_POLYCOMPRESSEDBYTES == 160)
   for (i = 0; i < KYBER_N / 8; i++) {
       for (j = 0; j < 8; j++) {
           // map to positive standard representatives
           u = a->coeffs[8 * i + j];
           u += (u >> 15) & KYBER_Q;
           /*      t[j] = ((((uint32_t)u << 5) + KYBER_Q/2)/KYBER_Q) & 31; */
           d0 = u << 5;
           d0 += 1664;
           d0 *= 40318;
           d0 >>= 27;
           t[j] = d0 & 0x1f;
       }

       r[0] = (t[0] >> 0) | (t[1] << 5);
       r[1] = (t[1] >> 3) | (t[2] << 2) | (t[3] << 7);
       r[2] = (t[3] >> 1) | (t[4] << 4);
       r[3] = (t[4] >> 4) | (t[5] << 1) | (t[6] << 6);
       r[4] = (t[6] >> 2) | (t[7] << 3);
       r += 5;
   }
#else
#error "KYBER_POLYCOMPRESSEDBYTES needs to be in {128, 160}"
#endif
}

/*************************************************
* Name:        poly_decompress
*
* Description: De-serialization and subsequent decompression of a polynomial;
*              approximate inverse of poly_compress
*
* Arguments:   - poly *r: pointer to output polynomial
*              - const uint8_t *a: pointer to input byte array
*                                  (of length KYBER_POLYCOMPRESSEDBYTES bytes)
**************************************************/
static void
poly_decompress(poly *r, const uint8_t a[KYBER_POLYCOMPRESSEDBYTES])
{
   unsigned int i;

#if (KYBER_POLYCOMPRESSEDBYTES == 128)
   for (i = 0; i < KYBER_N / 2; i++) {
       r->coeffs[2 * i + 0] = (((uint16_t)(a[0] & 15) * KYBER_Q) + 8) >> 4;
       r->coeffs[2 * i + 1] = (((uint16_t)(a[0] >> 4) * KYBER_Q) + 8) >> 4;
       a += 1;
   }
#elif (KYBER_POLYCOMPRESSEDBYTES == 160)
   unsigned int j;
   uint8_t t[8];
   for (i = 0; i < KYBER_N / 8; i++) {
       t[0] = (a[0] >> 0);
       t[1] = (a[0] >> 5) | (a[1] << 3);
       t[2] = (a[1] >> 2);
       t[3] = (a[1] >> 7) | (a[2] << 1);
       t[4] = (a[2] >> 4) | (a[3] << 4);
       t[5] = (a[3] >> 1);
       t[6] = (a[3] >> 6) | (a[4] << 2);
       t[7] = (a[4] >> 3);
       a += 5;

       for (j = 0; j < 8; j++)
           r->coeffs[8 * i + j] = ((uint32_t)(t[j] & 31) * KYBER_Q + 16) >> 5;
   }
#else
#error "KYBER_POLYCOMPRESSEDBYTES needs to be in {128, 160}"
#endif
}

/*************************************************
* Name:        poly_tobytes
*
* Description: Serialization of a polynomial
*
* Arguments:   - uint8_t *r: pointer to output byte array
*                            (needs space for KYBER_POLYBYTES bytes)
*              - const poly *a: pointer to input polynomial
**************************************************/
static void
poly_tobytes(uint8_t r[KYBER_POLYBYTES], const poly *a)
{
   unsigned int i;
   uint16_t t0, t1;

   for (i = 0; i < KYBER_N / 2; i++) {
       // map to positive standard representatives
       t0 = a->coeffs[2 * i];
       t0 += ((int16_t)t0 >> 15) & KYBER_Q;
       t1 = a->coeffs[2 * i + 1];
       t1 += ((int16_t)t1 >> 15) & KYBER_Q;
       r[3 * i + 0] = (t0 >> 0);
       r[3 * i + 1] = (t0 >> 8) | (t1 << 4);
       r[3 * i + 2] = (t1 >> 4);
   }
}

/*************************************************
* Name:        poly_frombytes
*
* Description: De-serialization of a polynomial;
*              inverse of poly_tobytes
*
* Arguments:   - poly *r: pointer to output polynomial
*              - const uint8_t *a: pointer to input byte array
*                                  (of KYBER_POLYBYTES bytes)
**************************************************/
static void
poly_frombytes(poly *r, const uint8_t a[KYBER_POLYBYTES])
{
   unsigned int i;
   for (i = 0; i < KYBER_N / 2; i++) {
       r->coeffs[2 * i] = ((a[3 * i + 0] >> 0) | ((uint16_t)a[3 * i + 1] << 8)) & 0xFFF;
       r->coeffs[2 * i + 1] = ((a[3 * i + 1] >> 4) | ((uint16_t)a[3 * i + 2] << 4)) & 0xFFF;
   }
}

/*************************************************
* Name:        poly_frommsg
*
* Description: Convert 32-byte message to polynomial
*
* Arguments:   - poly *r: pointer to output polynomial
*              - const uint8_t *msg: pointer to input message
**************************************************/
static void
poly_frommsg(poly *r, const uint8_t msg[KYBER_INDCPA_MSGBYTES])
{
   unsigned int i, j;
   int16_t mask;

#if (KYBER_INDCPA_MSGBYTES != KYBER_N / 8)
#error "KYBER_INDCPA_MSGBYTES must be equal to KYBER_N/8 bytes!"
#endif

   for (i = 0; i < KYBER_N / 8; i++) {
       for (j = 0; j < 8; j++) {
           mask = -(int16_t)((msg[i] >> j) & 1);
           r->coeffs[8 * i + j] = mask & ((KYBER_Q + 1) / 2);
       }
   }
}

/*************************************************
* Name:        poly_tomsg
*
* Description: Convert polynomial to 32-byte message
*
* Arguments:   - uint8_t *msg: pointer to output message
*              - const poly *a: pointer to input polynomial
**************************************************/
static void
poly_tomsg(uint8_t msg[KYBER_INDCPA_MSGBYTES], const poly *a)
{
   unsigned int i, j;
   uint32_t t;

   for (i = 0; i < KYBER_N / 8; i++) {
       msg[i] = 0;
       for (j = 0; j < 8; j++) {
           t = a->coeffs[8 * i + j];
           // t += ((int16_t)t >> 15) & KYBER_Q;
           // t  = (((t << 1) + KYBER_Q/2)/KYBER_Q) & 1;
           t <<= 1;
           t += 1665;
           t *= 80635;
           t >>= 28;
           t &= 1;
           msg[i] |= t << j;
       }
   }
}

/*************************************************
* Name:        poly_getnoise_eta1
*
* Description: Sample a polynomial deterministically from a seed and a nonce,
*              with output polynomial close to centered binomial distribution
*              with parameter KYBER_ETA1
*
* Arguments:   - poly *r: pointer to output polynomial
*              - const uint8_t *seed: pointer to input seed
*                                     (of length KYBER_SYMBYTES bytes)
*              - uint8_t nonce: one-byte input nonce
**************************************************/
static void
poly_getnoise_eta1(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce)
{
   uint8_t buf[KYBER_ETA1 * KYBER_N / 4];
   prf(buf, sizeof(buf), seed, nonce);
   poly_cbd_eta1(r, buf);
}

/*************************************************
* Name:        poly_getnoise_eta2
*
* Description: Sample a polynomial deterministically from a seed and a nonce,
*              with output polynomial close to centered binomial distribution
*              with parameter KYBER_ETA2
*
* Arguments:   - poly *r: pointer to output polynomial
*              - const uint8_t *seed: pointer to input seed
*                                     (of length KYBER_SYMBYTES bytes)
*              - uint8_t nonce: one-byte input nonce
**************************************************/
static void
poly_getnoise_eta2(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce)
{
   uint8_t buf[KYBER_ETA2 * KYBER_N / 4];
   prf(buf, sizeof(buf), seed, nonce);
   poly_cbd_eta2(r, buf);
}

/*************************************************
* Name:        poly_ntt
*
* Description: Computes negacyclic number-theoretic transform (NTT) of
*              a polynomial in place;
*              inputs assumed to be in normal order, output in bitreversed order
*
* Arguments:   - uint16_t *r: pointer to in/output polynomial
**************************************************/
static void
poly_ntt(poly *r)
{
   ntt(r->coeffs);
   poly_reduce(r);
}

/*************************************************
* Name:        poly_invntt_tomont
*
* Description: Computes inverse of negacyclic number-theoretic transform (NTT)
*              of a polynomial in place;
*              inputs assumed to be in bitreversed order, output in normal order
*
* Arguments:   - uint16_t *a: pointer to in/output polynomial
**************************************************/
static void
poly_invntt_tomont(poly *r)
{
   invntt(r->coeffs);
}

/*************************************************
* Name:        poly_basemul_montgomery
*
* Description: Multiplication of two polynomials in NTT domain
*
* Arguments:   - poly *r: pointer to output polynomial
*              - const poly *a: pointer to first input polynomial
*              - const poly *b: pointer to second input polynomial
**************************************************/
static void
poly_basemul_montgomery(poly *r, const poly *a, const poly *b)
{
   unsigned int i;
   for (i = 0; i < KYBER_N / 4; i++) {
       basemul(&r->coeffs[4 * i], &a->coeffs[4 * i], &b->coeffs[4 * i], zetas[64 + i]);
       basemul(&r->coeffs[4 * i + 2], &a->coeffs[4 * i + 2], &b->coeffs[4 * i + 2], -zetas[64 + i]);
   }
}

/*************************************************
* Name:        poly_tomont
*
* Description: Inplace conversion of all coefficients of a polynomial
*              from normal domain to Montgomery domain
*
* Arguments:   - poly *r: pointer to input/output polynomial
**************************************************/
static void
poly_tomont(poly *r)
{
   unsigned int i;
   const int16_t f = (1ULL << 32) % KYBER_Q;
   for (i = 0; i < KYBER_N; i++)
       r->coeffs[i] = montgomery_reduce((int32_t)r->coeffs[i] * f);
}

/*************************************************
* Name:        poly_reduce
*
* Description: Applies Barrett reduction to all coefficients of a polynomial
*              for details of the Barrett reduction see comments in reduce.c
*
* Arguments:   - poly *r: pointer to input/output polynomial
**************************************************/
static void
poly_reduce(poly *r)
{
   unsigned int i;
   for (i = 0; i < KYBER_N; i++)
       r->coeffs[i] = barrett_reduce(r->coeffs[i]);
}

/*************************************************
* Name:        poly_add
*
* Description: Add two polynomials; no modular reduction is performed
*
* Arguments: - poly *r: pointer to output polynomial
*            - const poly *a: pointer to first input polynomial
*            - const poly *b: pointer to second input polynomial
**************************************************/
static void
poly_add(poly *r, const poly *a, const poly *b)
{
   unsigned int i;
   for (i = 0; i < KYBER_N; i++)
       r->coeffs[i] = a->coeffs[i] + b->coeffs[i];
}

/*************************************************
* Name:        poly_sub
*
* Description: Subtract two polynomials; no modular reduction is performed
*
* Arguments: - poly *r:       pointer to output polynomial
*            - const poly *a: pointer to first input polynomial
*            - const poly *b: pointer to second input polynomial
**************************************************/
static void
poly_sub(poly *r, const poly *a, const poly *b)
{
   unsigned int i;
   for (i = 0; i < KYBER_N; i++)
       r->coeffs[i] = a->coeffs[i] - b->coeffs[i];
}
/** end: ref/poly.c **/

/** begin: ref/polyvec.c **/
/*************************************************
* Name:        polyvec_compress
*
* Description: Compress and serialize vector of polynomials
*
* Arguments:   - uint8_t *r: pointer to output byte array
*                            (needs space for KYBER_POLYVECCOMPRESSEDBYTES)
*              - const polyvec *a: pointer to input vector of polynomials
**************************************************/
static void
polyvec_compress(uint8_t r[KYBER_POLYVECCOMPRESSEDBYTES], const polyvec *a)
{
   unsigned int i, j, k;
   uint64_t d0;

#if (KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * 352))
   uint16_t t[8];
   for (i = 0; i < KYBER_K; i++) {
       for (j = 0; j < KYBER_N / 8; j++) {
           for (k = 0; k < 8; k++) {
               t[k] = a->vec[i].coeffs[8 * j + k];
               t[k] += ((int16_t)t[k] >> 15) & KYBER_Q;
               /*      t[k]  = ((((uint32_t)t[k] << 11) + KYBER_Q/2)/KYBER_Q) & 0x7ff; */
               d0 = t[k];
               d0 <<= 11;
               d0 += 1664;
               d0 *= 645084;
               d0 >>= 31;
               t[k] = d0 & 0x7ff;
           }

           r[0] = (t[0] >> 0);
           r[1] = (t[0] >> 8) | (t[1] << 3);
           r[2] = (t[1] >> 5) | (t[2] << 6);
           r[3] = (t[2] >> 2);
           r[4] = (t[2] >> 10) | (t[3] << 1);
           r[5] = (t[3] >> 7) | (t[4] << 4);
           r[6] = (t[4] >> 4) | (t[5] << 7);
           r[7] = (t[5] >> 1);
           r[8] = (t[5] >> 9) | (t[6] << 2);
           r[9] = (t[6] >> 6) | (t[7] << 5);
           r[10] = (t[7] >> 3);
           r += 11;
       }
   }
#elif (KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * 320))
   uint16_t t[4];
   for (i = 0; i < KYBER_K; i++) {
       for (j = 0; j < KYBER_N / 4; j++) {
           for (k = 0; k < 4; k++) {
               t[k] = a->vec[i].coeffs[4 * j + k];
               t[k] += ((int16_t)t[k] >> 15) & KYBER_Q;
               /*      t[k]  = ((((uint32_t)t[k] << 10) + KYBER_Q/2)/ KYBER_Q) & 0x3ff; */
               d0 = t[k];
               d0 <<= 10;
               d0 += 1665;
               d0 *= 1290167;
               d0 >>= 32;
               t[k] = d0 & 0x3ff;
           }

           r[0] = (t[0] >> 0);
           r[1] = (t[0] >> 8) | (t[1] << 2);
           r[2] = (t[1] >> 6) | (t[2] << 4);
           r[3] = (t[2] >> 4) | (t[3] << 6);
           r[4] = (t[3] >> 2);
           r += 5;
       }
   }
#else
#error "KYBER_POLYVECCOMPRESSEDBYTES needs to be in {320*KYBER_K, 352*KYBER_K}"
#endif
}

/*************************************************
* Name:        polyvec_decompress
*
* Description: De-serialize and decompress vector of polynomials;
*              approximate inverse of polyvec_compress
*
* Arguments:   - polyvec *r:       pointer to output vector of polynomials
*              - const uint8_t *a: pointer to input byte array
*                                  (of length KYBER_POLYVECCOMPRESSEDBYTES)
**************************************************/
static void
polyvec_decompress(polyvec *r, const uint8_t a[KYBER_POLYVECCOMPRESSEDBYTES])
{
   unsigned int i, j, k;

#if (KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * 352))
   uint16_t t[8];
   for (i = 0; i < KYBER_K; i++) {
       for (j = 0; j < KYBER_N / 8; j++) {
           t[0] = (a[0] >> 0) | ((uint16_t)a[1] << 8);
           t[1] = (a[1] >> 3) | ((uint16_t)a[2] << 5);
           t[2] = (a[2] >> 6) | ((uint16_t)a[3] << 2) | ((uint16_t)a[4] << 10);
           t[3] = (a[4] >> 1) | ((uint16_t)a[5] << 7);
           t[4] = (a[5] >> 4) | ((uint16_t)a[6] << 4);
           t[5] = (a[6] >> 7) | ((uint16_t)a[7] << 1) | ((uint16_t)a[8] << 9);
           t[6] = (a[8] >> 2) | ((uint16_t)a[9] << 6);
           t[7] = (a[9] >> 5) | ((uint16_t)a[10] << 3);
           a += 11;

           for (k = 0; k < 8; k++)
               r->vec[i].coeffs[8 * j + k] = ((uint32_t)(t[k] & 0x7FF) * KYBER_Q + 1024) >> 11;
       }
   }
#elif (KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * 320))
   uint16_t t[4];
   for (i = 0; i < KYBER_K; i++) {
       for (j = 0; j < KYBER_N / 4; j++) {
           t[0] = (a[0] >> 0) | ((uint16_t)a[1] << 8);
           t[1] = (a[1] >> 2) | ((uint16_t)a[2] << 6);
           t[2] = (a[2] >> 4) | ((uint16_t)a[3] << 4);
           t[3] = (a[3] >> 6) | ((uint16_t)a[4] << 2);
           a += 5;

           for (k = 0; k < 4; k++)
               r->vec[i].coeffs[4 * j + k] = ((uint32_t)(t[k] & 0x3FF) * KYBER_Q + 512) >> 10;
       }
   }
#else
#error "KYBER_POLYVECCOMPRESSEDBYTES needs to be in {320*KYBER_K, 352*KYBER_K}"
#endif
}

/*************************************************
* Name:        polyvec_tobytes
*
* Description: Serialize vector of polynomials
*
* Arguments:   - uint8_t *r: pointer to output byte array
*                            (needs space for KYBER_POLYVECBYTES)
*              - const polyvec *a: pointer to input vector of polynomials
**************************************************/
static void
polyvec_tobytes(uint8_t r[KYBER_POLYVECBYTES], const polyvec *a)
{
   unsigned int i;
   for (i = 0; i < KYBER_K; i++)
       poly_tobytes(r + i * KYBER_POLYBYTES, &a->vec[i]);
}

/*************************************************
* Name:        polyvec_frombytes
*
* Description: De-serialize vector of polynomials;
*              inverse of polyvec_tobytes
*
* Arguments:   - uint8_t *r:       pointer to output byte array
*              - const polyvec *a: pointer to input vector of polynomials
*                                  (of length KYBER_POLYVECBYTES)
**************************************************/
static void
polyvec_frombytes(polyvec *r, const uint8_t a[KYBER_POLYVECBYTES])
{
   unsigned int i;
   for (i = 0; i < KYBER_K; i++)
       poly_frombytes(&r->vec[i], a + i * KYBER_POLYBYTES);
}

/*************************************************
* Name:        polyvec_ntt
*
* Description: Apply forward NTT to all elements of a vector of polynomials
*
* Arguments:   - polyvec *r: pointer to in/output vector of polynomials
**************************************************/
static void
polyvec_ntt(polyvec *r)
{
   unsigned int i;
   for (i = 0; i < KYBER_K; i++)
       poly_ntt(&r->vec[i]);
}

/*************************************************
* Name:        polyvec_invntt_tomont
*
* Description: Apply inverse NTT to all elements of a vector of polynomials
*              and multiply by Montgomery factor 2^16
*
* Arguments:   - polyvec *r: pointer to in/output vector of polynomials
**************************************************/
static void
polyvec_invntt_tomont(polyvec *r)
{
   unsigned int i;
   for (i = 0; i < KYBER_K; i++)
       poly_invntt_tomont(&r->vec[i]);
}

/*************************************************
* Name:        polyvec_basemul_acc_montgomery
*
* Description: Multiply elements of a and b in NTT domain, accumulate into r,
*              and multiply by 2^-16.
*
* Arguments: - poly *r: pointer to output polynomial
*            - const polyvec *a: pointer to first input vector of polynomials
*            - const polyvec *b: pointer to second input vector of polynomials
**************************************************/
static void
polyvec_basemul_acc_montgomery(poly *r, const polyvec *a, const polyvec *b)
{
   unsigned int i;
   poly t;

   poly_basemul_montgomery(r, &a->vec[0], &b->vec[0]);
   for (i = 1; i < KYBER_K; i++) {
       poly_basemul_montgomery(&t, &a->vec[i], &b->vec[i]);
       poly_add(r, r, &t);
   }

   poly_reduce(r);
}

/*************************************************
* Name:        polyvec_reduce
*
* Description: Applies Barrett reduction to each coefficient
*              of each element of a vector of polynomials;
*              for details of the Barrett reduction see comments in reduce.c
*
* Arguments:   - polyvec *r: pointer to input/output polynomial
**************************************************/
static void
polyvec_reduce(polyvec *r)
{
   unsigned int i;
   for (i = 0; i < KYBER_K; i++)
       poly_reduce(&r->vec[i]);
}

/*************************************************
* Name:        polyvec_add
*
* Description: Add vectors of polynomials
*
* Arguments: - polyvec *r: pointer to output vector of polynomials
*            - const polyvec *a: pointer to first input vector of polynomials
*            - const polyvec *b: pointer to second input vector of polynomials
**************************************************/
static void
polyvec_add(polyvec *r, const polyvec *a, const polyvec *b)
{
   unsigned int i;
   for (i = 0; i < KYBER_K; i++)
       poly_add(&r->vec[i], &a->vec[i], &b->vec[i]);
}
/** end: ref/polyvec.c **/

/** begin: ref/indcpa.c **/
/*************************************************
* Name:        pack_pk
*
* Description: Serialize the public key as concatenation of the
*              serialized vector of polynomials pk
*              and the public seed used to generate the matrix A.
*
* Arguments:   uint8_t *r: pointer to the output serialized public key
*              polyvec *pk: pointer to the input public-key polyvec
*              const uint8_t *seed: pointer to the input public seed
**************************************************/
static void
pack_pk(uint8_t r[KYBER_INDCPA_PUBLICKEYBYTES],
       polyvec *pk,
       const uint8_t seed[KYBER_SYMBYTES])
{
   size_t i;
   polyvec_tobytes(r, pk);
   for (i = 0; i < KYBER_SYMBYTES; i++)
       r[i + KYBER_POLYVECBYTES] = seed[i];
}

/*************************************************
* Name:        unpack_pk
*
* Description: De-serialize public key from a byte array;
*              approximate inverse of pack_pk
*
* Arguments:   - polyvec *pk: pointer to output public-key polynomial vector
*              - uint8_t *seed: pointer to output seed to generate matrix A
*              - const uint8_t *packedpk: pointer to input serialized public key
**************************************************/
static void
unpack_pk(polyvec *pk,
         uint8_t seed[KYBER_SYMBYTES],
         const uint8_t packedpk[KYBER_INDCPA_PUBLICKEYBYTES])
{
   size_t i;
   polyvec_frombytes(pk, packedpk);
   for (i = 0; i < KYBER_SYMBYTES; i++)
       seed[i] = packedpk[i + KYBER_POLYVECBYTES];
}

/*************************************************
* Name:        pack_sk
*
* Description: Serialize the secret key
*
* Arguments:   - uint8_t *r: pointer to output serialized secret key
*              - polyvec *sk: pointer to input vector of polynomials (secret key)
**************************************************/
static void
pack_sk(uint8_t r[KYBER_INDCPA_SECRETKEYBYTES], polyvec *sk)
{
   polyvec_tobytes(r, sk);
}

/*************************************************
* Name:        unpack_sk
*
* Description: De-serialize the secret key; inverse of pack_sk
*
* Arguments:   - polyvec *sk: pointer to output vector of polynomials (secret key)
*              - const uint8_t *packedsk: pointer to input serialized secret key
**************************************************/
static void
unpack_sk(polyvec *sk, const uint8_t packedsk[KYBER_INDCPA_SECRETKEYBYTES])
{
   polyvec_frombytes(sk, packedsk);
}

/*************************************************
* Name:        pack_ciphertext
*
* Description: Serialize the ciphertext as concatenation of the
*              compressed and serialized vector of polynomials b
*              and the compressed and serialized polynomial v
*
* Arguments:   uint8_t *r: pointer to the output serialized ciphertext
*              poly *pk: pointer to the input vector of polynomials b
*              poly *v: pointer to the input polynomial v
**************************************************/
static void
pack_ciphertext(uint8_t r[KYBER_INDCPA_BYTES], polyvec *b, poly *v)
{
   polyvec_compress(r, b);
   poly_compress(r + KYBER_POLYVECCOMPRESSEDBYTES, v);
}

/*************************************************
* Name:        unpack_ciphertext
*
* Description: De-serialize and decompress ciphertext from a byte array;
*              approximate inverse of pack_ciphertext
*
* Arguments:   - polyvec *b: pointer to the output vector of polynomials b
*              - poly *v: pointer to the output polynomial v
*              - const uint8_t *c: pointer to the input serialized ciphertext
**************************************************/
static void
unpack_ciphertext(polyvec *b, poly *v, const uint8_t c[KYBER_INDCPA_BYTES])
{
   polyvec_decompress(b, c);
   poly_decompress(v, c + KYBER_POLYVECCOMPRESSEDBYTES);
}

/*************************************************
* Name:        rej_uniform
*
* Description: Run rejection sampling on uniform random bytes to generate
*              uniform random integers mod q
*
* Arguments:   - int16_t *r: pointer to output buffer
*              - unsigned int len: requested number of 16-bit integers (uniform mod q)
*              - const uint8_t *buf: pointer to input buffer (assumed to be uniformly random bytes)
*              - unsigned int buflen: length of input buffer in bytes
*
* Returns number of sampled 16-bit integers (at most len)
**************************************************/
static unsigned int
rej_uniform(int16_t *r,
           unsigned int len,
           const uint8_t *buf,
           unsigned int buflen)
{
   unsigned int ctr, pos;
   uint16_t val0, val1;

   ctr = pos = 0;
   while (ctr < len && pos + 3 <= buflen) {
       val0 = ((buf[pos + 0] >> 0) | ((uint16_t)buf[pos + 1] << 8)) & 0xFFF;
       val1 = ((buf[pos + 1] >> 4) | ((uint16_t)buf[pos + 2] << 4)) & 0xFFF;
       pos += 3;

       if (val0 < KYBER_Q)
           r[ctr++] = val0;
       if (ctr < len && val1 < KYBER_Q)
           r[ctr++] = val1;
   }

   return ctr;
}

#define gen_a(A, B) gen_matrix(A, B, 0)
#define gen_at(A, B) gen_matrix(A, B, 1)

/*************************************************
* Name:        gen_matrix
*
* Description: Deterministically generate matrix A (or the transpose of A)
*              from a seed. Entries of the matrix are polynomials that look
*              uniformly random. Performs rejection sampling on output of
*              a XOF
*
* Arguments:   - polyvec *a: pointer to ouptput matrix A
*              - const uint8_t *seed: pointer to input seed
*              - int transposed: boolean deciding whether A or A^T is generated
**************************************************/
#define GEN_MATRIX_NBLOCKS ((12 * KYBER_N / 8 * (1 << 12) / KYBER_Q + XOF_BLOCKBYTES) / XOF_BLOCKBYTES)
// Not static for benchmarking
static void
gen_matrix(polyvec *a, const uint8_t seed[KYBER_SYMBYTES], int transposed)
{
   unsigned int ctr, i, j, k;
   unsigned int buflen, off;
   uint8_t buf[GEN_MATRIX_NBLOCKS * XOF_BLOCKBYTES + 2];
   xof_state state;

   for (i = 0; i < KYBER_K; i++) {
       for (j = 0; j < KYBER_K; j++) {
           if (transposed)
               xof_absorb(&state, seed, i, j);
           else
               xof_absorb(&state, seed, j, i);

           xof_squeezeblocks(buf, GEN_MATRIX_NBLOCKS, &state);
           buflen = GEN_MATRIX_NBLOCKS * XOF_BLOCKBYTES;
           ctr = rej_uniform(a[i].vec[j].coeffs, KYBER_N, buf, buflen);

           while (ctr < KYBER_N) {
               off = buflen % 3;
               for (k = 0; k < off; k++)
                   buf[k] = buf[buflen - off + k];
               xof_squeezeblocks(buf + off, 1, &state);
               buflen = off + XOF_BLOCKBYTES;
               ctr += rej_uniform(a[i].vec[j].coeffs + ctr, KYBER_N - ctr, buf, buflen);
           }
       }
   }
}

/*************************************************
* Name:        indcpa_keypair_derand
*
* Description: Generates public and private key for the CPA-secure
*              public-key encryption scheme underlying Kyber
*
* Arguments:   - uint8_t *pk: pointer to output public key
*                             (of length KYBER_INDCPA_PUBLICKEYBYTES bytes)
*              - uint8_t *sk: pointer to output private key
*                             (of length KYBER_INDCPA_SECRETKEYBYTES bytes)
*              - const uint8_t *coins: pointer to input randomness
*                             (of length KYBER_SYMBYTES bytes)
**************************************************/
static void
indcpa_keypair_derand(uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
                     uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES],
                     const uint8_t coins[KYBER_SYMBYTES])
{
   unsigned int i;
   uint8_t buf[2 * KYBER_SYMBYTES];
   const uint8_t *publicseed = buf;
   const uint8_t *noiseseed = buf + KYBER_SYMBYTES;
   uint8_t nonce = 0;
   polyvec a[KYBER_K], e, pkpv, skpv;

   hash_g(buf, coins, KYBER_SYMBYTES);

   gen_a(a, publicseed);

   for (i = 0; i < KYBER_K; i++)
       poly_getnoise_eta1(&skpv.vec[i], noiseseed, nonce++);
   for (i = 0; i < KYBER_K; i++)
       poly_getnoise_eta1(&e.vec[i], noiseseed, nonce++);

   polyvec_ntt(&skpv);
   polyvec_ntt(&e);

   // matrix-vector multiplication
   for (i = 0; i < KYBER_K; i++) {
       polyvec_basemul_acc_montgomery(&pkpv.vec[i], &a[i], &skpv);
       poly_tomont(&pkpv.vec[i]);
   }

   polyvec_add(&pkpv, &pkpv, &e);
   polyvec_reduce(&pkpv);

   pack_sk(sk, &skpv);
   pack_pk(pk, &pkpv, publicseed);
}

/*************************************************
* Name:        indcpa_enc
*
* Description: Encryption function of the CPA-secure
*              public-key encryption scheme underlying Kyber.
*
* Arguments:   - uint8_t *c: pointer to output ciphertext
*                            (of length KYBER_INDCPA_BYTES bytes)
*              - const uint8_t *m: pointer to input message
*                                  (of length KYBER_INDCPA_MSGBYTES bytes)
*              - const uint8_t *pk: pointer to input public key
*                                   (of length KYBER_INDCPA_PUBLICKEYBYTES)
*              - const uint8_t *coins: pointer to input random coins used as seed
*                                      (of length KYBER_SYMBYTES) to deterministically
*                                      generate all randomness
**************************************************/
static void
indcpa_enc(uint8_t c[KYBER_INDCPA_BYTES],
          const uint8_t m[KYBER_INDCPA_MSGBYTES],
          const uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
          const uint8_t coins[KYBER_SYMBYTES])
{
   unsigned int i;
   uint8_t seed[KYBER_SYMBYTES];
   uint8_t nonce = 0;
   polyvec sp, pkpv, ep, at[KYBER_K], b;
   poly v, k, epp;

   unpack_pk(&pkpv, seed, pk);
   poly_frommsg(&k, m);
   gen_at(at, seed);

   for (i = 0; i < KYBER_K; i++)
       poly_getnoise_eta1(sp.vec + i, coins, nonce++);
   for (i = 0; i < KYBER_K; i++)
       poly_getnoise_eta2(ep.vec + i, coins, nonce++);
   poly_getnoise_eta2(&epp, coins, nonce++);

   polyvec_ntt(&sp);

   // matrix-vector multiplication
   for (i = 0; i < KYBER_K; i++)
       polyvec_basemul_acc_montgomery(&b.vec[i], &at[i], &sp);

   polyvec_basemul_acc_montgomery(&v, &pkpv, &sp);

   polyvec_invntt_tomont(&b);
   poly_invntt_tomont(&v);

   polyvec_add(&b, &b, &ep);
   poly_add(&v, &v, &epp);
   poly_add(&v, &v, &k);
   polyvec_reduce(&b);
   poly_reduce(&v);

   pack_ciphertext(c, &b, &v);
}

/*************************************************
* Name:        indcpa_dec
*
* Description: Decryption function of the CPA-secure
*              public-key encryption scheme underlying Kyber.
*
* Arguments:   - uint8_t *m: pointer to output decrypted message
*                            (of length KYBER_INDCPA_MSGBYTES)
*              - const uint8_t *c: pointer to input ciphertext
*                                  (of length KYBER_INDCPA_BYTES)
*              - const uint8_t *sk: pointer to input secret key
*                                   (of length KYBER_INDCPA_SECRETKEYBYTES)
**************************************************/
static void
indcpa_dec(uint8_t m[KYBER_INDCPA_MSGBYTES],
          const uint8_t c[KYBER_INDCPA_BYTES],
          const uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES])
{
   polyvec b, skpv;
   poly v, mp;

   unpack_ciphertext(&b, &v, c);
   unpack_sk(&skpv, sk);

   polyvec_ntt(&b);
   polyvec_basemul_acc_montgomery(&mp, &skpv, &b);
   poly_invntt_tomont(&mp);

   poly_sub(&mp, &v, &mp);
   poly_reduce(&mp);

   poly_tomsg(m, &mp);
}
/** end: ref/indcpa.c **/

/** begin: ref/fips202.c **/
/* Based on the public domain implementation in crypto_hash/keccakc512/simple/ from
* http://bench.cr.yp.to/supercop.html by Ronny Van Keer and the public domain "TweetFips202"
* implementation from https://twitter.com/tweetfips202 by Gilles Van Assche, Daniel J. Bernstein,
* and Peter Schwabe */

#define NROUNDS 24
#define ROL(a, offset) ((a << offset) ^ (a >> (64 - offset)))

/*************************************************
* Name:        load64
*
* Description: Load 8 bytes into uint64_t in little-endian order
*
* Arguments:   - const uint8_t *x: pointer to input byte array
*
* Returns the loaded 64-bit unsigned integer
**************************************************/
static uint64_t
load64(const uint8_t x[8])
{
   unsigned int i;
   uint64_t r = 0;

   for (i = 0; i < 8; i++)
       r |= (uint64_t)x[i] << 8 * i;

   return r;
}

/*************************************************
* Name:        store64
*
* Description: Store a 64-bit integer to array of 8 bytes in little-endian order
*
* Arguments:   - uint8_t *x: pointer to the output byte array (allocated)
*              - uint64_t u: input 64-bit unsigned integer
**************************************************/
static void
store64(uint8_t x[8], uint64_t u)
{
   unsigned int i;

   for (i = 0; i < 8; i++)
       x[i] = u >> 8 * i;
}

/* Keccak round constants */
static const uint64_t KeccakF_RoundConstants[NROUNDS] = {
   (uint64_t)0x0000000000000001ULL,
   (uint64_t)0x0000000000008082ULL,
   (uint64_t)0x800000000000808aULL,
   (uint64_t)0x8000000080008000ULL,
   (uint64_t)0x000000000000808bULL,
   (uint64_t)0x0000000080000001ULL,
   (uint64_t)0x8000000080008081ULL,
   (uint64_t)0x8000000000008009ULL,
   (uint64_t)0x000000000000008aULL,
   (uint64_t)0x0000000000000088ULL,
   (uint64_t)0x0000000080008009ULL,
   (uint64_t)0x000000008000000aULL,
   (uint64_t)0x000000008000808bULL,
   (uint64_t)0x800000000000008bULL,
   (uint64_t)0x8000000000008089ULL,
   (uint64_t)0x8000000000008003ULL,
   (uint64_t)0x8000000000008002ULL,
   (uint64_t)0x8000000000000080ULL,
   (uint64_t)0x000000000000800aULL,
   (uint64_t)0x800000008000000aULL,
   (uint64_t)0x8000000080008081ULL,
   (uint64_t)0x8000000000008080ULL,
   (uint64_t)0x0000000080000001ULL,
   (uint64_t)0x8000000080008008ULL
};

/*************************************************
* Name:        KeccakF1600_StatePermute
*
* Description: The Keccak F1600 Permutation
*
* Arguments:   - uint64_t *state: pointer to input/output Keccak state
**************************************************/
static void
KeccakF1600_StatePermute(uint64_t state[25])
{
   int round;

   uint64_t Aba, Abe, Abi, Abo, Abu;
   uint64_t Aga, Age, Agi, Ago, Agu;
   uint64_t Aka, Ake, Aki, Ako, Aku;
   uint64_t Ama, Ame, Ami, Amo, Amu;
   uint64_t Asa, Ase, Asi, Aso, Asu;
   uint64_t BCa, BCe, BCi, BCo, BCu;
   uint64_t Da, De, Di, Do, Du;
   uint64_t Eba, Ebe, Ebi, Ebo, Ebu;
   uint64_t Ega, Ege, Egi, Ego, Egu;
   uint64_t Eka, Eke, Eki, Eko, Eku;
   uint64_t Ema, Eme, Emi, Emo, Emu;
   uint64_t Esa, Ese, Esi, Eso, Esu;

   // copyFromState(A, state)
   Aba = state[0];
   Abe = state[1];
   Abi = state[2];
   Abo = state[3];
   Abu = state[4];
   Aga = state[5];
   Age = state[6];
   Agi = state[7];
   Ago = state[8];
   Agu = state[9];
   Aka = state[10];
   Ake = state[11];
   Aki = state[12];
   Ako = state[13];
   Aku = state[14];
   Ama = state[15];
   Ame = state[16];
   Ami = state[17];
   Amo = state[18];
   Amu = state[19];
   Asa = state[20];
   Ase = state[21];
   Asi = state[22];
   Aso = state[23];
   Asu = state[24];

   for (round = 0; round < NROUNDS; round += 2) {
       //    prepareTheta
       BCa = Aba ^ Aga ^ Aka ^ Ama ^ Asa;
       BCe = Abe ^ Age ^ Ake ^ Ame ^ Ase;
       BCi = Abi ^ Agi ^ Aki ^ Ami ^ Asi;
       BCo = Abo ^ Ago ^ Ako ^ Amo ^ Aso;
       BCu = Abu ^ Agu ^ Aku ^ Amu ^ Asu;

       // thetaRhoPiChiIotaPrepareTheta(round, A, E)
       Da = BCu ^ ROL(BCe, 1);
       De = BCa ^ ROL(BCi, 1);
       Di = BCe ^ ROL(BCo, 1);
       Do = BCi ^ ROL(BCu, 1);
       Du = BCo ^ ROL(BCa, 1);

       Aba ^= Da;
       BCa = Aba;
       Age ^= De;
       BCe = ROL(Age, 44);
       Aki ^= Di;
       BCi = ROL(Aki, 43);
       Amo ^= Do;
       BCo = ROL(Amo, 21);
       Asu ^= Du;
       BCu = ROL(Asu, 14);
       Eba = BCa ^ ((~BCe) & BCi);
       Eba ^= (uint64_t)KeccakF_RoundConstants[round];
       Ebe = BCe ^ ((~BCi) & BCo);
       Ebi = BCi ^ ((~BCo) & BCu);
       Ebo = BCo ^ ((~BCu) & BCa);
       Ebu = BCu ^ ((~BCa) & BCe);

       Abo ^= Do;
       BCa = ROL(Abo, 28);
       Agu ^= Du;
       BCe = ROL(Agu, 20);
       Aka ^= Da;
       BCi = ROL(Aka, 3);
       Ame ^= De;
       BCo = ROL(Ame, 45);
       Asi ^= Di;
       BCu = ROL(Asi, 61);
       Ega = BCa ^ ((~BCe) & BCi);
       Ege = BCe ^ ((~BCi) & BCo);
       Egi = BCi ^ ((~BCo) & BCu);
       Ego = BCo ^ ((~BCu) & BCa);
       Egu = BCu ^ ((~BCa) & BCe);

       Abe ^= De;
       BCa = ROL(Abe, 1);
       Agi ^= Di;
       BCe = ROL(Agi, 6);
       Ako ^= Do;
       BCi = ROL(Ako, 25);
       Amu ^= Du;
       BCo = ROL(Amu, 8);
       Asa ^= Da;
       BCu = ROL(Asa, 18);
       Eka = BCa ^ ((~BCe) & BCi);
       Eke = BCe ^ ((~BCi) & BCo);
       Eki = BCi ^ ((~BCo) & BCu);
       Eko = BCo ^ ((~BCu) & BCa);
       Eku = BCu ^ ((~BCa) & BCe);

       Abu ^= Du;
       BCa = ROL(Abu, 27);
       Aga ^= Da;
       BCe = ROL(Aga, 36);
       Ake ^= De;
       BCi = ROL(Ake, 10);
       Ami ^= Di;
       BCo = ROL(Ami, 15);
       Aso ^= Do;
       BCu = ROL(Aso, 56);
       Ema = BCa ^ ((~BCe) & BCi);
       Eme = BCe ^ ((~BCi) & BCo);
       Emi = BCi ^ ((~BCo) & BCu);
       Emo = BCo ^ ((~BCu) & BCa);
       Emu = BCu ^ ((~BCa) & BCe);

       Abi ^= Di;
       BCa = ROL(Abi, 62);
       Ago ^= Do;
       BCe = ROL(Ago, 55);
       Aku ^= Du;
       BCi = ROL(Aku, 39);
       Ama ^= Da;
       BCo = ROL(Ama, 41);
       Ase ^= De;
       BCu = ROL(Ase, 2);
       Esa = BCa ^ ((~BCe) & BCi);
       Ese = BCe ^ ((~BCi) & BCo);
       Esi = BCi ^ ((~BCo) & BCu);
       Eso = BCo ^ ((~BCu) & BCa);
       Esu = BCu ^ ((~BCa) & BCe);

       //    prepareTheta
       BCa = Eba ^ Ega ^ Eka ^ Ema ^ Esa;
       BCe = Ebe ^ Ege ^ Eke ^ Eme ^ Ese;
       BCi = Ebi ^ Egi ^ Eki ^ Emi ^ Esi;
       BCo = Ebo ^ Ego ^ Eko ^ Emo ^ Eso;
       BCu = Ebu ^ Egu ^ Eku ^ Emu ^ Esu;

       // thetaRhoPiChiIotaPrepareTheta(round+1, E, A)
       Da = BCu ^ ROL(BCe, 1);
       De = BCa ^ ROL(BCi, 1);
       Di = BCe ^ ROL(BCo, 1);
       Do = BCi ^ ROL(BCu, 1);
       Du = BCo ^ ROL(BCa, 1);

       Eba ^= Da;
       BCa = Eba;
       Ege ^= De;
       BCe = ROL(Ege, 44);
       Eki ^= Di;
       BCi = ROL(Eki, 43);
       Emo ^= Do;
       BCo = ROL(Emo, 21);
       Esu ^= Du;
       BCu = ROL(Esu, 14);
       Aba = BCa ^ ((~BCe) & BCi);
       Aba ^= (uint64_t)KeccakF_RoundConstants[round + 1];
       Abe = BCe ^ ((~BCi) & BCo);
       Abi = BCi ^ ((~BCo) & BCu);
       Abo = BCo ^ ((~BCu) & BCa);
       Abu = BCu ^ ((~BCa) & BCe);

       Ebo ^= Do;
       BCa = ROL(Ebo, 28);
       Egu ^= Du;
       BCe = ROL(Egu, 20);
       Eka ^= Da;
       BCi = ROL(Eka, 3);
       Eme ^= De;
       BCo = ROL(Eme, 45);
       Esi ^= Di;
       BCu = ROL(Esi, 61);
       Aga = BCa ^ ((~BCe) & BCi);
       Age = BCe ^ ((~BCi) & BCo);
       Agi = BCi ^ ((~BCo) & BCu);
       Ago = BCo ^ ((~BCu) & BCa);
       Agu = BCu ^ ((~BCa) & BCe);

       Ebe ^= De;
       BCa = ROL(Ebe, 1);
       Egi ^= Di;
       BCe = ROL(Egi, 6);
       Eko ^= Do;
       BCi = ROL(Eko, 25);
       Emu ^= Du;
       BCo = ROL(Emu, 8);
       Esa ^= Da;
       BCu = ROL(Esa, 18);
       Aka = BCa ^ ((~BCe) & BCi);
       Ake = BCe ^ ((~BCi) & BCo);
       Aki = BCi ^ ((~BCo) & BCu);
       Ako = BCo ^ ((~BCu) & BCa);
       Aku = BCu ^ ((~BCa) & BCe);

       Ebu ^= Du;
       BCa = ROL(Ebu, 27);
       Ega ^= Da;
       BCe = ROL(Ega, 36);
       Eke ^= De;
       BCi = ROL(Eke, 10);
       Emi ^= Di;
       BCo = ROL(Emi, 15);
       Eso ^= Do;
       BCu = ROL(Eso, 56);
       Ama = BCa ^ ((~BCe) & BCi);
       Ame = BCe ^ ((~BCi) & BCo);
       Ami = BCi ^ ((~BCo) & BCu);
       Amo = BCo ^ ((~BCu) & BCa);
       Amu = BCu ^ ((~BCa) & BCe);

       Ebi ^= Di;
       BCa = ROL(Ebi, 62);
       Ego ^= Do;
       BCe = ROL(Ego, 55);
       Eku ^= Du;
       BCi = ROL(Eku, 39);
       Ema ^= Da;
       BCo = ROL(Ema, 41);
       Ese ^= De;
       BCu = ROL(Ese, 2);
       Asa = BCa ^ ((~BCe) & BCi);
       Ase = BCe ^ ((~BCi) & BCo);
       Asi = BCi ^ ((~BCo) & BCu);
       Aso = BCo ^ ((~BCu) & BCa);
       Asu = BCu ^ ((~BCa) & BCe);
   }

   // copyToState(state, A)
   state[0] = Aba;
   state[1] = Abe;
   state[2] = Abi;
   state[3] = Abo;
   state[4] = Abu;
   state[5] = Aga;
   state[6] = Age;
   state[7] = Agi;
   state[8] = Ago;
   state[9] = Agu;
   state[10] = Aka;
   state[11] = Ake;
   state[12] = Aki;
   state[13] = Ako;
   state[14] = Aku;
   state[15] = Ama;
   state[16] = Ame;
   state[17] = Ami;
   state[18] = Amo;
   state[19] = Amu;
   state[20] = Asa;
   state[21] = Ase;
   state[22] = Asi;
   state[23] = Aso;
   state[24] = Asu;
}

/*************************************************
* Name:        keccak_init
*
* Description: Initializes the Keccak state.
*
* Arguments:   - uint64_t *s: pointer to Keccak state
**************************************************/
static void
keccak_init(uint64_t s[25])
{
   unsigned int i;
   for (i = 0; i < 25; i++)
       s[i] = 0;
}

/*************************************************
* Name:        keccak_absorb
*
* Description: Absorb step of Keccak; incremental.
*
* Arguments:   - uint64_t *s: pointer to Keccak state
*              - unsigned int pos: position in current block to be absorbed
*              - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
*              - const uint8_t *in: pointer to input to be absorbed into s
*              - size_t inlen: length of input in bytes
*
* Returns new position pos in current block
**************************************************/
static unsigned int
keccak_absorb(uint64_t s[25],
             unsigned int pos,
             unsigned int r,
             const uint8_t *in,
             size_t inlen)
{
   unsigned int i;

   while (pos + inlen >= r) {
       for (i = pos; i < r; i++)
           s[i / 8] ^= (uint64_t)*in++ << 8 * (i % 8);
       inlen -= r - pos;
       KeccakF1600_StatePermute(s);
       pos = 0;
   }

   for (i = pos; i < pos + inlen; i++)
       s[i / 8] ^= (uint64_t)*in++ << 8 * (i % 8);

   return i;
}

/*************************************************
* Name:        keccak_finalize
*
* Description: Finalize absorb step.
*
* Arguments:   - uint64_t *s: pointer to Keccak state
*              - unsigned int pos: position in current block to be absorbed
*              - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
*              - uint8_t p: domain separation byte
**************************************************/
static void
keccak_finalize(uint64_t s[25], unsigned int pos, unsigned int r, uint8_t p)
{
   s[pos / 8] ^= (uint64_t)p << 8 * (pos % 8);
   s[r / 8 - 1] ^= 1ULL << 63;
}

/*************************************************
* Name:        keccak_squeeze
*
* Description: Squeeze step of Keccak. Squeezes arbitratrily many bytes.
*              Modifies the state. Can be called multiple times to keep
*              squeezing, i.e., is incremental.
*
* Arguments:   - uint8_t *out: pointer to output
*              - size_t outlen: number of bytes to be squeezed (written to out)
*              - uint64_t *s: pointer to input/output Keccak state
*              - unsigned int pos: number of bytes in current block already squeezed
*              - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
*
* Returns new position pos in current block
**************************************************/
static unsigned int
keccak_squeeze(uint8_t *out,
              size_t outlen,
              uint64_t s[25],
              unsigned int pos,
              unsigned int r)
{
   unsigned int i;

   while (outlen) {
       if (pos == r) {
           KeccakF1600_StatePermute(s);
           pos = 0;
       }
       for (i = pos; i < r && i < pos + outlen; i++)
           *out++ = s[i / 8] >> 8 * (i % 8);
       outlen -= i - pos;
       pos = i;
   }

   return pos;
}

/*************************************************
* Name:        keccak_absorb_once
*
* Description: Absorb step of Keccak;
*              non-incremental, starts by zeroeing the state.
*
* Arguments:   - uint64_t *s: pointer to (uninitialized) output Keccak state
*              - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
*              - const uint8_t *in: pointer to input to be absorbed into s
*              - size_t inlen: length of input in bytes
*              - uint8_t p: domain-separation byte for different Keccak-derived functions
**************************************************/
static void
keccak_absorb_once(uint64_t s[25],
                  unsigned int r,
                  const uint8_t *in,
                  size_t inlen,
                  uint8_t p)
{
   unsigned int i;

   for (i = 0; i < 25; i++)
       s[i] = 0;

   while (inlen >= r) {
       for (i = 0; i < r / 8; i++)
           s[i] ^= load64(in + 8 * i);
       in += r;
       inlen -= r;
       KeccakF1600_StatePermute(s);
   }

   for (i = 0; i < inlen; i++)
       s[i / 8] ^= (uint64_t)in[i] << 8 * (i % 8);

   s[i / 8] ^= (uint64_t)p << 8 * (i % 8);
   s[(r - 1) / 8] ^= 1ULL << 63;
}

/*************************************************
* Name:        keccak_squeezeblocks
*
* Description: Squeeze step of Keccak. Squeezes full blocks of r bytes each.
*              Modifies the state. Can be called multiple times to keep
*              squeezing, i.e., is incremental. Assumes zero bytes of current
*              block have already been squeezed.
*
* Arguments:   - uint8_t *out: pointer to output blocks
*              - size_t nblocks: number of blocks to be squeezed (written to out)
*              - uint64_t *s: pointer to input/output Keccak state
*              - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
**************************************************/
static void
keccak_squeezeblocks(uint8_t *out,
                    size_t nblocks,
                    uint64_t s[25],
                    unsigned int r)
{
   unsigned int i;

   while (nblocks) {
       KeccakF1600_StatePermute(s);
       for (i = 0; i < r / 8; i++)
           store64(out + 8 * i, s[i]);
       out += r;
       nblocks -= 1;
   }
}

/*************************************************
* Name:        shake128_init
*
* Description: Initilizes Keccak state for use as SHAKE128 XOF
*
* Arguments:   - keccak_state *state: pointer to (uninitialized) Keccak state
**************************************************/
void
shake128_init(keccak_state *state)
{
   keccak_init(state->s);
   state->pos = 0;
}

/*************************************************
* Name:        shake128_absorb
*
* Description: Absorb step of the SHAKE128 XOF; incremental.
*
* Arguments:   - keccak_state *state: pointer to (initialized) output Keccak state
*              - const uint8_t *in: pointer to input to be absorbed into s
*              - size_t inlen: length of input in bytes
**************************************************/
void
shake128_absorb(keccak_state *state, const uint8_t *in, size_t inlen)
{
   state->pos = keccak_absorb(state->s, state->pos, SHAKE128_RATE, in, inlen);
}

/*************************************************
* Name:        shake128_finalize
*
* Description: Finalize absorb step of the SHAKE128 XOF.
*
* Arguments:   - keccak_state *state: pointer to Keccak state
**************************************************/
void
shake128_finalize(keccak_state *state)
{
   keccak_finalize(state->s, state->pos, SHAKE128_RATE, 0x1F);
   state->pos = SHAKE128_RATE;
}

/*************************************************
* Name:        shake128_squeeze
*
* Description: Squeeze step of SHAKE128 XOF. Squeezes arbitraily many
*              bytes. Can be called multiple times to keep squeezing.
*
* Arguments:   - uint8_t *out: pointer to output blocks
*              - size_t outlen : number of bytes to be squeezed (written to output)
*              - keccak_state *s: pointer to input/output Keccak state
**************************************************/
void
shake128_squeeze(uint8_t *out, size_t outlen, keccak_state *state)
{
   state->pos = keccak_squeeze(out, outlen, state->s, state->pos, SHAKE128_RATE);
}

/*************************************************
* Name:        shake128_absorb_once
*
* Description: Initialize, absorb into and finalize SHAKE128 XOF; non-incremental.
*
* Arguments:   - keccak_state *state: pointer to (uninitialized) output Keccak state
*              - const uint8_t *in: pointer to input to be absorbed into s
*              - size_t inlen: length of input in bytes
**************************************************/
void
shake128_absorb_once(keccak_state *state, const uint8_t *in, size_t inlen)
{
   keccak_absorb_once(state->s, SHAKE128_RATE, in, inlen, 0x1F);
   state->pos = SHAKE128_RATE;
}

/*************************************************
* Name:        shake128_squeezeblocks
*
* Description: Squeeze step of SHAKE128 XOF. Squeezes full blocks of
*              SHAKE128_RATE bytes each. Can be called multiple times
*              to keep squeezing. Assumes new block has not yet been
*              started (state->pos = SHAKE128_RATE).
*
* Arguments:   - uint8_t *out: pointer to output blocks
*              - size_t nblocks: number of blocks to be squeezed (written to output)
*              - keccak_state *s: pointer to input/output Keccak state
**************************************************/
void
shake128_squeezeblocks(uint8_t *out, size_t nblocks, keccak_state *state)
{
   keccak_squeezeblocks(out, nblocks, state->s, SHAKE128_RATE);
}

/*************************************************
* Name:        shake256_init
*
* Description: Initilizes Keccak state for use as SHAKE256 XOF
*
* Arguments:   - keccak_state *state: pointer to (uninitialized) Keccak state
**************************************************/
void
shake256_init(keccak_state *state)
{
   keccak_init(state->s);
   state->pos = 0;
}

/*************************************************
* Name:        shake256_absorb
*
* Description: Absorb step of the SHAKE256 XOF; incremental.
*
* Arguments:   - keccak_state *state: pointer to (initialized) output Keccak state
*              - const uint8_t *in: pointer to input to be absorbed into s
*              - size_t inlen: length of input in bytes
**************************************************/
void
shake256_absorb(keccak_state *state, const uint8_t *in, size_t inlen)
{
   state->pos = keccak_absorb(state->s, state->pos, SHAKE256_RATE, in, inlen);
}

/*************************************************
* Name:        shake256_finalize
*
* Description: Finalize absorb step of the SHAKE256 XOF.
*
* Arguments:   - keccak_state *state: pointer to Keccak state
**************************************************/
void
shake256_finalize(keccak_state *state)
{
   keccak_finalize(state->s, state->pos, SHAKE256_RATE, 0x1F);
   state->pos = SHAKE256_RATE;
}

/*************************************************
* Name:        shake256_squeeze
*
* Description: Squeeze step of SHAKE256 XOF. Squeezes arbitraily many
*              bytes. Can be called multiple times to keep squeezing.
*
* Arguments:   - uint8_t *out: pointer to output blocks
*              - size_t outlen : number of bytes to be squeezed (written to output)
*              - keccak_state *s: pointer to input/output Keccak state
**************************************************/
void
shake256_squeeze(uint8_t *out, size_t outlen, keccak_state *state)
{
   state->pos = keccak_squeeze(out, outlen, state->s, state->pos, SHAKE256_RATE);
}

/*************************************************
* Name:        shake256_absorb_once
*
* Description: Initialize, absorb into and finalize SHAKE256 XOF; non-incremental.
*
* Arguments:   - keccak_state *state: pointer to (uninitialized) output Keccak state
*              - const uint8_t *in: pointer to input to be absorbed into s
*              - size_t inlen: length of input in bytes
**************************************************/
void
shake256_absorb_once(keccak_state *state, const uint8_t *in, size_t inlen)
{
   keccak_absorb_once(state->s, SHAKE256_RATE, in, inlen, 0x1F);
   state->pos = SHAKE256_RATE;
}

/*************************************************
* Name:        shake256_squeezeblocks
*
* Description: Squeeze step of SHAKE256 XOF. Squeezes full blocks of
*              SHAKE256_RATE bytes each. Can be called multiple times
*              to keep squeezing. Assumes next block has not yet been
*              started (state->pos = SHAKE256_RATE).
*
* Arguments:   - uint8_t *out: pointer to output blocks
*              - size_t nblocks: number of blocks to be squeezed (written to output)
*              - keccak_state *s: pointer to input/output Keccak state
**************************************************/
void
shake256_squeezeblocks(uint8_t *out, size_t nblocks, keccak_state *state)
{
   keccak_squeezeblocks(out, nblocks, state->s, SHAKE256_RATE);
}

/*************************************************
* Name:        shake128
*
* Description: SHAKE128 XOF with non-incremental API
*
* Arguments:   - uint8_t *out: pointer to output
*              - size_t outlen: requested output length in bytes
*              - const uint8_t *in: pointer to input
*              - size_t inlen: length of input in bytes
**************************************************/
void
shake128(uint8_t *out, size_t outlen, const uint8_t *in, size_t inlen)
{
   size_t nblocks;
   keccak_state state;

   shake128_absorb_once(&state, in, inlen);
   nblocks = outlen / SHAKE128_RATE;
   shake128_squeezeblocks(out, nblocks, &state);
   outlen -= nblocks * SHAKE128_RATE;
   out += nblocks * SHAKE128_RATE;
   shake128_squeeze(out, outlen, &state);
}

/*************************************************
* Name:        shake256
*
* Description: SHAKE256 XOF with non-incremental API
*
* Arguments:   - uint8_t *out: pointer to output
*              - size_t outlen: requested output length in bytes
*              - const uint8_t *in: pointer to input
*              - size_t inlen: length of input in bytes
**************************************************/
void
shake256(uint8_t *out, size_t outlen, const uint8_t *in, size_t inlen)
{
   size_t nblocks;
   keccak_state state;

   shake256_absorb_once(&state, in, inlen);
   nblocks = outlen / SHAKE256_RATE;
   shake256_squeezeblocks(out, nblocks, &state);
   outlen -= nblocks * SHAKE256_RATE;
   out += nblocks * SHAKE256_RATE;
   shake256_squeeze(out, outlen, &state);
}

/*************************************************
* Name:        sha3_256
*
* Description: SHA3-256 with non-incremental API
*
* Arguments:   - uint8_t *h: pointer to output (32 bytes)
*              - const uint8_t *in: pointer to input
*              - size_t inlen: length of input in bytes
**************************************************/
void
sha3_256(uint8_t h[32], const uint8_t *in, size_t inlen)
{
   unsigned int i;
   uint64_t s[25];

   keccak_absorb_once(s, SHA3_256_RATE, in, inlen, 0x06);
   KeccakF1600_StatePermute(s);
   for (i = 0; i < 4; i++)
       store64(h + 8 * i, s[i]);
}

/*************************************************
* Name:        sha3_512
*
* Description: SHA3-512 with non-incremental API
*
* Arguments:   - uint8_t *h: pointer to output (64 bytes)
*              - const uint8_t *in: pointer to input
*              - size_t inlen: length of input in bytes
**************************************************/
void
sha3_512(uint8_t h[64], const uint8_t *in, size_t inlen)
{
   unsigned int i;
   uint64_t s[25];

   keccak_absorb_once(s, SHA3_512_RATE, in, inlen, 0x06);
   KeccakF1600_StatePermute(s);
   for (i = 0; i < 8; i++)
       store64(h + 8 * i, s[i]);
}
/** end: ref/fips202.c **/

/** begin: ref/symmetric-shake.c **/
/*************************************************
* Name:        kyber_shake128_absorb
*
* Description: Absorb step of the SHAKE128 specialized for the Kyber context.
*
* Arguments:   - keccak_state *state: pointer to (uninitialized) output Keccak state
*              - const uint8_t *seed: pointer to KYBER_SYMBYTES input to be absorbed into state
*              - uint8_t i: additional byte of input
*              - uint8_t j: additional byte of input
**************************************************/
static void
kyber_shake128_absorb(keccak_state *state,
                     const uint8_t seed[KYBER_SYMBYTES],
                     uint8_t x,
                     uint8_t y)
{
   uint8_t extseed[KYBER_SYMBYTES + 2];

   memcpy(extseed, seed, KYBER_SYMBYTES);
   extseed[KYBER_SYMBYTES + 0] = x;
   extseed[KYBER_SYMBYTES + 1] = y;

   shake128_absorb_once(state, extseed, sizeof(extseed));
}

/*************************************************
* Name:        kyber_shake256_prf
*
* Description: Usage of SHAKE256 as a PRF, concatenates secret and public input
*              and then generates outlen bytes of SHAKE256 output
*
* Arguments:   - uint8_t *out: pointer to output
*              - size_t outlen: number of requested output bytes
*              - const uint8_t *key: pointer to the key (of length KYBER_SYMBYTES)
*              - uint8_t nonce: single-byte nonce (public PRF input)
**************************************************/
static void
kyber_shake256_prf(uint8_t *out, size_t outlen, const uint8_t key[KYBER_SYMBYTES], uint8_t nonce)
{
   uint8_t extkey[KYBER_SYMBYTES + 1];

   memcpy(extkey, key, KYBER_SYMBYTES);
   extkey[KYBER_SYMBYTES] = nonce;

   shake256(out, outlen, extkey, sizeof(extkey));
}
/** end: ref/symmetric-shake.c **/

/** begin: ref/kem.c **/
/*************************************************
* Name:        crypto_kem_keypair_derand
*
* Description: Generates public and private key
*              for CCA-secure Kyber key encapsulation mechanism
*
* Arguments:   - uint8_t *pk: pointer to output public key
*                (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
*              - uint8_t *sk: pointer to output private key
*                (an already allocated array of KYBER_SECRETKEYBYTES bytes)
*              - uint8_t *coins: pointer to input randomness
*                (an already allocated array filled with 2*KYBER_SYMBYTES random bytes)
**
* Returns 0 (success)
**************************************************/
int
crypto_kem_keypair_derand(uint8_t *pk,
                         uint8_t *sk,
                         const uint8_t *coins)
{
   size_t i;
   indcpa_keypair_derand(pk, sk, coins);
   for (i = 0; i < KYBER_INDCPA_PUBLICKEYBYTES; i++)
       sk[i + KYBER_INDCPA_SECRETKEYBYTES] = pk[i];
   hash_h(sk + KYBER_SECRETKEYBYTES - 2 * KYBER_SYMBYTES, pk, KYBER_PUBLICKEYBYTES);
   /* Value z for pseudo-random output on reject */
   for (i = 0; i < KYBER_SYMBYTES; i++)
       sk[KYBER_SECRETKEYBYTES - KYBER_SYMBYTES + i] = coins[KYBER_SYMBYTES + i];
   return 0;
}

/*************************************************
* Name:        crypto_kem_keypair
*
* Description: Generates public and private key
*              for CCA-secure Kyber key encapsulation mechanism
*
* Arguments:   - uint8_t *pk: pointer to output public key
*                (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
*              - uint8_t *sk: pointer to output private key
*                (an already allocated array of KYBER_SECRETKEYBYTES bytes)
*
* Returns 0 (success)
**************************************************/
int
crypto_kem_keypair(uint8_t *pk,
                  uint8_t *sk)
{
   uint8_t coins[2 * KYBER_SYMBYTES];
   randombytes(coins, KYBER_SYMBYTES);
   randombytes(coins + KYBER_SYMBYTES, KYBER_SYMBYTES);
   crypto_kem_keypair_derand(pk, sk, coins);
   return 0;
}

/*************************************************
* Name:        crypto_kem_enc_derand
*
* Description: Generates cipher text and shared
*              secret for given public key
*
* Arguments:   - uint8_t *ct: pointer to output cipher text
*                (an already allocated array of KYBER_CIPHERTEXTBYTES bytes)
*              - uint8_t *ss: pointer to output shared secret
*                (an already allocated array of KYBER_SSBYTES bytes)
*              - const uint8_t *pk: pointer to input public key
*                (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
*              - const uint8_t *coins: pointer to input randomness
*                (an already allocated array filled with KYBER_SYMBYTES random bytes)
**
* Returns 0 (success)
**************************************************/
int
crypto_kem_enc_derand(uint8_t *ct,
                     uint8_t *ss,
                     const uint8_t *pk,
                     const uint8_t *coins)
{
   uint8_t buf[2 * KYBER_SYMBYTES];
   /* Will contain key, coins */
   uint8_t kr[2 * KYBER_SYMBYTES];

   /* Don't release system RNG output */
   hash_h(buf, coins, KYBER_SYMBYTES);

   /* Multitarget countermeasure for coins + contributory KEM */
   hash_h(buf + KYBER_SYMBYTES, pk, KYBER_PUBLICKEYBYTES);
   hash_g(kr, buf, 2 * KYBER_SYMBYTES);

   /* coins are in kr+KYBER_SYMBYTES */
   indcpa_enc(ct, buf, pk, kr + KYBER_SYMBYTES);

   /* overwrite coins in kr with H(c) */
   hash_h(kr + KYBER_SYMBYTES, ct, KYBER_CIPHERTEXTBYTES);
   /* hash concatenation of pre-k and H(c) to k */
   kdf(ss, kr, 2 * KYBER_SYMBYTES);
   return 0;
}

/*************************************************
* Name:        crypto_kem_enc
*
* Description: Generates cipher text and shared
*              secret for given public key
*
* Arguments:   - uint8_t *ct: pointer to output cipher text
*                (an already allocated array of KYBER_CIPHERTEXTBYTES bytes)
*              - uint8_t *ss: pointer to output shared secret
*                (an already allocated array of KYBER_SSBYTES bytes)
*              - const uint8_t *pk: pointer to input public key
*                (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
*
* Returns 0 (success)
**************************************************/
int
crypto_kem_enc(uint8_t *ct,
              uint8_t *ss,
              const uint8_t *pk)
{
   uint8_t coins[KYBER_SYMBYTES];
   randombytes(coins, KYBER_SYMBYTES);
   crypto_kem_enc_derand(ct, ss, pk, coins);
   return 0;
}

/*************************************************
* Name:        crypto_kem_dec
*
* Description: Generates shared secret for given
*              cipher text and private key
*
* Arguments:   - uint8_t *ss: pointer to output shared secret
*                (an already allocated array of KYBER_SSBYTES bytes)
*              - const uint8_t *ct: pointer to input cipher text
*                (an already allocated array of KYBER_CIPHERTEXTBYTES bytes)
*              - const uint8_t *sk: pointer to input private key
*                (an already allocated array of KYBER_SECRETKEYBYTES bytes)
*
* Returns 0.
*
* On failure, ss will contain a pseudo-random value.
**************************************************/
int
crypto_kem_dec(uint8_t *ss,
              const uint8_t *ct,
              const uint8_t *sk)
{
   size_t i;
   int fail;
   uint8_t buf[2 * KYBER_SYMBYTES];
   /* Will contain key, coins */
   uint8_t kr[2 * KYBER_SYMBYTES];
   uint8_t cmp[KYBER_CIPHERTEXTBYTES];
   const uint8_t *pk = sk + KYBER_INDCPA_SECRETKEYBYTES;

   indcpa_dec(buf, ct, sk);

   /* Multitarget countermeasure for coins + contributory KEM */
   for (i = 0; i < KYBER_SYMBYTES; i++)
       buf[KYBER_SYMBYTES + i] = sk[KYBER_SECRETKEYBYTES - 2 * KYBER_SYMBYTES + i];
   hash_g(kr, buf, 2 * KYBER_SYMBYTES);

   /* coins are in kr+KYBER_SYMBYTES */
   indcpa_enc(cmp, buf, pk, kr + KYBER_SYMBYTES);

   fail = verify(ct, cmp, KYBER_CIPHERTEXTBYTES);

   /* overwrite coins in kr with H(c) */
   hash_h(kr + KYBER_SYMBYTES, ct, KYBER_CIPHERTEXTBYTES);

   /* Overwrite pre-k with z on re-encryption failure */
   cmov(kr, sk + KYBER_SECRETKEYBYTES - KYBER_SYMBYTES, KYBER_SYMBYTES, fail);

   /* hash concatenation of pre-k and H(c) to k */
   kdf(ss, kr, 2 * KYBER_SYMBYTES);
   return 0;
}
/** end: ref/kem.c **/