Subject: Re: [pqc-forum] Rationale for  Benes in Classic McEliece
From: "D. J. Bernstein" <djb@cr.yp.to>
Date: Sat, 5 Dec 2020 16:39:23 +0100
To: pqc-forum <pqc-forum@list.nist.gov>
Message-ID: <20201205153923.965806.qmail@cr.yp.to>

[Speaking on behalf of the Classic McEliece team in this message.]

Please find more details about the rationale in the "Rationale" section
of the Classic McEliece submission document.

The security reasons for fully specifying key formats and key-generation
methods are covered at the beginning of Section 4.4, "Generation of
random objects". This is compatible with specifying multiple safe
options and allowing implementors to choose from among those options.
Leaving implementors free to choose arbitrary options is not safe: it
would allow ROCA-type security failures. Security is our top priority.

Various security and efficiency considerations are covered in the rest
of the section. The "Compression of private keys" subsection notes that
the default private-key format in round 3 is designed to easily support
conversions back and forth to various other formats. The rationale for
taking Benes-network control bits as the default format is also stated
there:

   One can apply the corresponding permutation by sorting, which is
   slower than a Benes network but avoids the need to compute control
   bits. One can also apply the corresponding permutation through RAM
   lookups, but implementors are cautioned that this leaks information
   through timing on many platforms. Specifying control bits as the
   default representation of α has the advantage of encouraging
   constant-time implementations. All implementations should be reviewed
   for timing leaks and other applicable side-channel leaks in any case.

See also the "Modifications for round 3" document:

   This leaves open the option of specifying other private-key formats
   in the future, such as compressed formats (the order of objects in
   this format is designed to allow compression via simple truncation
   with efficient decompression), or a list of (α1,...,αn) instead of
   control bits for environments where permutation via RAM is not a
   concern.

Note that, even if an (α1,...,αn) option is specified for environments
with constant-time RAM, such environments should consider whether they
can decapsulate more efficiently by using Benes networks instead of RAM.
Hardware for applying the (m-1/2)2^m conditional swaps in a Benes
network has better parallelizability and better energy-efficiency than
hardware for a series of (nearly) 2^m lookups in an array of size 2^m.

Regarding RAM usage during this part of key generation, Section 7.3 of
https://cr.yp.to/papers.html#controlbits explains how to fit the
temporary variables in the computation of control bits into 2^m words of
RAM, each word having 4m bits, in total 53248 bytes when 2^m is 8192.
The control bits then fit into just 25% of that space, and are applied
in place to the arrays used during decapsulation.

---Dan