The `mctiny`

library provides an API for the Classic McEliece cryptosystem with high-security parameters, and for various related McTiny functions. Currently this library uses `mceliece6960119`

and `mctiny6960119`

, but the library is designed so that callers can be agnostic to this choice.

To generate a secret key `sk`

and a corresponding public key `pk`

:

```
#include "mctiny.h"
unsigned char pk[mctiny_PUBLICKEYBYTES];
unsigned char sk[mctiny_SECRETKEYBYTES];
mctiny_keypair(pk,sk);
```

Given a public key `pk`

, to create a ciphertext `c`

that communicates a random session key `k`

:

```
#include "mctiny.h"
unsigned char c[mctiny_CIPHERTEXTBYTES];
unsigned char k[mctiny_SESSIONKEYBYTES];
const unsigned char pk[mctiny_PUBLICKEYBYTES];
mctiny_enc(c,k,pk);
```

Given a secret key `sk`

and a ciphertext `c`

, to recover the session key `k`

:

```
#include "mctiny.h"
unsigned char k[mctiny_SESSIONKEYBYTES];
const unsigned char c[mctiny_CIPHERTEXTBYTES];
const unsigned char sk[mctiny_SECRETKEYBYTES];
mctiny_dec(k,c,sk);
```

Classic McEliece is a “quiet” KEM, meaning that `mctiny_dec`

never fails. Anyone can send ciphertexts to your public key, or make up random strings as ciphertexts, producing random session keys from `mctiny_dec`

.

Currently these functions are simply renamings of the functions `crypto_kem_mceliece6960119_keypair`

, `crypto_kem_mceliece6960119_enc`

, and `crypto_kem_mceliece6960119_dec`

from SUPERCOP.

McTiny divides the Classic McEliece public key into blocks, performs independent computations on each block, and then assembles a ciphertext from the results of these computations. The following functions help build ciphertexts in this way.

**Public-key structure.** The public key communicates a matrix `H`

of integers modulo 2. The number of rows in the matrix is a system parameter `m*t`

, currently 1547. This is the product of a system parameter `m`

, currently 13, and a system parameter `t`

, currently 119. The number of columns in the matrix is another system parameter `n`

, currently 6960.

The leftmost `m*t`

columns in the matrix are always an `m*t`

-by-`m*t`

identity matrix and are not communicated explicitly. The public key communicates the remaining `n-m*t`

columns, currently 5413 columns. The public key consists of the `n-m*t`

bits at the end of the first row of the matrix (in little-endian form, padded to a byte boundary), then the `n-m*t`

bits at the end of the second row of the matrix, etc.

**Extracting blocks from a public key.** McTiny takes the columns of the public key `x`

at a time, where `x`

is a McTiny parameter, currently 544. Within each column, it takes the rows `y`

at a time, where `y`

is another McTiny parameter, currently 16. Each `y`

-row-by-`x`

-column portion of the public key is called a **block**. The following function extracts one block from the public key, starting at row number `y*rowpos`

and column number `x*colpos`

:

```
#include "mctiny.h"
unsigned char block[mctiny_BLOCKBYTES];
const unsigned char pk[mctiny_PUBLICKEYBYTES];
int rowpos;
int colpos;
mctiny_pk2block(block,pk,rowpos,colpos);
```

Here `rowpos`

is allowed to be anything from `0`

through `mctiny_ROWBLOCKS-1`

, and `colpos`

is allowed to be anything from `0`

through `mctiny_COLBLOCKS-1`

. A block can extend beyond the edges of the matrix if `rowpos`

is `mctiny_ROWBLOCKS-1`

or `colpos`

is `mctiny_COLBLOCKS-1`

(or both); the corresponding output bits are set to 0.

Currently a block is represented as `xy`

bits, where the first `x`

bits come from the first row of the block, the next `x`

bits come from the second row of the block, etc. (The parameter `x`

is always a multiple of 8, so there is no padding.)

**Error-vector structure.** A Classic McEliece ciphertext is derived from a secret `n`

-bit vector `e`

. This vector has weight `t`

, i.e., exactly `t`

bits set. Currently this means that `e`

is a 6960-bit vector where exactly 119 bits are set.

**Generating error vectors.** The McTiny server derives the vector `e`

from a randomly chosen 32-byte `seed`

(`E`

in the specification). Rather than communicating the vector `e`

to itself via a cookie, the server communicates the more compact `seed`

to itself via a cookie.

A randomly chosen 32-byte `seed`

is not necessarily valid: i.e., it does not necessarily produce a vector `e`

. In this case the server tries another `seed`

. Here is the complete procedure to generate both `seed`

and `e`

:

```
#include "mctiny.h"
unsigned char seed[32];
unsigned char e[mctiny_EBYTES];
do
randombytes(seed,sizeof seed);
while (!mctiny_seedisvalid(seed));
mctiny_seed2e(e,seed);
```

It would be possible to instead define all seeds as valid: for example, `mctiny_seed2e`

could try deriving `e`

from `seed`

, then try deriving `e`

from a hash of `seed`

, then try deriving `e`

from a hash of the hash of `seed`

, etc. However, the server would then have to compute the same hash chain again to reconstruct `e`

from a cookie. Generating new seeds (as in the code above, or by repeatedly hashing an initial random seed) means that each cookie uses just one `mctiny_seed2e`

call.

It is also possible that a different internal definition of `mctiny_seed2e`

could generate `e`

more efficiently, perhaps also with a larger fraction of valid seeds. The definition of `mctiny_seed2e`

is not visible to the McTiny client, so a server can substitute a different `mctiny_seed2e`

definition without affecting interoperability. Implementors trying to replace `mctiny_seed2e`

with something faster should first understand the relevant security requirements.

**Ciphertext structure.** A Classic McEliece ciphertext `c`

is a concatenation `c0+c1`

. The first part `c0`

is `H`

times `e`

, where `H`

is the matrix communicated by the public key as above, and `e`

is the randomly chosen weight-`t`

error vector described above. This product `H*e`

is called a **syndrome**. The second part `c1`

is the hash of `2+e`

, where `2`

means a string containing the single byte 2. The corresponding session key is the hash of `1+e+c`

, where `1`

means a string containing the single byte 1.

Note that both of the hashes work conveniently with a single array that contains a single byte, then `e`

(of length `mctiny_EBYTES`

), then `c`

(of length `mctiny_CIPHERTEXTBYTES`

).

**Handling a block.** Given `e`

and a block of `H`

, to compute the relevant `y`

-bit contribution to the product `H*e`

:

```
#include "mctiny.h"
unsigned char synd1[mctiny_YBYTES];
const unsigned char e[mctiny_EBYTES];
const unsigned char block[mctiny_BLOCKBYTES];
int colpos;
mctiny_eblock2syndrome(synd1,e,block,colpos);
```

You need to know the `colpos`

used for the block (between `0`

and `mctiny_COLBLOCKS-1`

); this indicates which positions in `e`

are relevant to the block.

**Merging y-bit results into y*v-bit pieces.** The final product

`H*e`

is assembled as a series of `y*v`

-bit `v`

is another parameter, currently 5. Here is how to compute all of these pieces:```
#include "mctiny.h"
unsigned char synd2[mctiny_PIECES][mctiny_PIECEBYTES];
unsigned char synd1[mctiny_YBYTES];
unsigned char block[mctiny_BLOCKBYTES];
const unsigned char pk[mctiny_PUBLICKEYBYTES];
const unsigned char e[mctiny_EBYTES];
int p;
int i;
int colpos;
for (p = 0;p < mctiny_PIECES;++p) {
mctiny_pieceinit(synd2[p],e,p);
for (i = 0;i < mctiny_V;++i) {
for (colpos = 0;colpos < mctiny_COLBLOCKS;++colpos) {
mctiny_pk2block(block,pk,p*mctiny_V+i,colpos);
mctiny_eblock2syndrome(synd1,e,block,colpos);
mctiny_pieceabsorb(synd2[p],synd1,i);
}
}
}
```

`mctiny_pieceinit`

copies the relevant `y*v`

bits of `e`

to `synd2`

. In other words, it handles the identity-matrix portion of the public matrix `H`

.

`mctiny_pieceabsorb`

xors the `y`

bits from `synd1`

into the correct position in `synd2`

.

**Merging y*v-bit pieces into a complete syndrome.** Here is how to merge the pieces into a single

`m*t`

-bit piece:```
#include "mctiny.h"
unsigned char synd3[mctiny_COLBYTES];
const unsigned char synd2[mctiny_PIECES][mctiny_PIECEBYTES];
mctiny_mergepieces(synd3,synd2);
```

`mctiny_mergepieces`

concatenates the input bit strings, stopping after `m*t`

bits.

**Computing a ciphertext.** Finally, here is how to compute the corresponding ciphertext and session key:

```
#include "mctiny.h"
unsigned char c[mctiny_CIPHERTEXTBYTES];
unsigned char k[mctiny_SESSIONKEYBYTES];
const unsigned char synd3[mctiny_COLBYTES];
const unsigned char e[mctiny_EBYTES];
mctiny_finalize(c,k,synd3,e);
```

The resulting ciphertext can be decapsulated by `mctiny_dec`

, just like a ciphertext produced by `mctiny_enc`

.