Comments on "Proposed Submission Requirements and Evaluation Criteria
for the Post-Quantum Cryptography Standardization Process", draft from August 2016
Tanja Lange

In general I'm positively impressed with the document and how it reflects discussions
e.g. during the PQCrypto workshop. In the following I will raise one major and one 
minor issue and then give some detailed comments and suggestions. Please feel free 
to contact me if any of this is unclear. 

The current document is still inconsistent in what categories NIST is asking for
submissions. This matches the discussions in February when it was left open whether 
NIST would ask for a key exchange mechanism. The current document first speaks of 
'key exchange' and later of 'key establishment'. The API documentation uses both 
words interchangeably.

It should be made clear what precisely is asked for. Most people understand key 
exchange to match the functionality that Diffie-Hellman key exchange is offering: 
two keypairs determine a shared secret without communication; keys can be reused, 
e.g. A's published key can lead to a shared secret with Bob, using Bob's public 
key, and one with Charlie, using Charlie's public key. This is the functionality 
matching eBACS's DH function API: given one public key and one secret key, compute 
the shared key.

The functionality described early in the draft call for proposals changes this to
distinguish between an initiator message and a responder message. This does not 
match common understanding of key exchange, which is also why the eBACS API does 
not fit.

Later on the call document -- now speaking about key establishment -- highlights the
desired result: key transport and forward secrecy. The latter implies that new public
keys must be generated frequently, requiring efficient key generation and small key
sizes for transmission. I think it makes much more sense to ask for submissions for
this scenario and a scenario with long-term public keys instead of asking for 
submissions for key exchange and encryption. 

Realistically, public-key encryption is used only to transmit a key which is then 
used in a symmetric cipher; this is also recognized in the call document. The formal
treatment of this is most advanced in the KEM/DEM framework: the public-key system is
used as a key-encapsulation mechanism, which ensures that sender and receiver obtain 
the same key, and that key is then used in the data-encapsulation mechanism to encrypt 
the message. This avoids issues of padding.

To summarize, I recommend asking for submissions for two types of KEM:
* KEMs in which the receiver has a long-term public key; obtaining the key is outside
  the scope of specifying the KEM and
* KEMs in which at least one side generates and transmits a fresh public key.
instead of submissions for encryption and key exchange/establishment.

The second type of KEM scheme should be efficient enough that keys can be generated 
for each key transport, but ideally not break down completely if keys are reused. It 
would be good for the submitters to specify how key reuse would affect the security 
of their system. I understand that the latter might be captured under the property
of 'robustness'.

The minor issue is that I would recommend to request a constant-time implementation
of each retained algorithm in the second round. Timing attacks are one of the most
basic and thus most powerful attacks and each implementation (in software or
hardware) needs to be protected against it. The call currently says that you'll take
ease of SCA protection into account; that will be much easier and more meaningful
if the submitter has to send in a protected implementation. This might be seen as a
burden by some, so I wouldn't require it as part of the submission package, but each 
proposer group can get help by the time the second round comes along.

Editorial comments:

p.2 "in the event that large-scale quantum computers" should be replaced by
"to prepare for the event that large-scale quantum computers" (or similar).
It is too late to change once a QC is built. Even if long-term security is
not a concern, roll out would take too long. (This is captured well a few
paragraphs further down but confusing here).

p.4 It is unusual for key-exchange schemes to distinguish between initiator
and responder messages. It is normal to request that the scheme defines a
shared secret for each pair of public keys. If the definition is different this
should be stated early on. It might be that you're instead asking for public-key
encryption schemes for one-time use public keys with fast key generation (which
is different from the typical DH message flow). See above.

p.5 In case a submitter has submitted his implementation to eBACS there will
be benchmarks on a multitude of processors. Describing all the platforms and 
all the results would unnecessarily blow up the submission document. I 
recommend to allow inclusion by reference to the page for the primitive on 
bench.cr.yp.to. Of course, the submitter should still be free to highlight 
some processors and implementations if he chooses to and then be required to
describe the platform, so this is a suggestion to permit a reference in 
addition.

p.7 Do you really want to receive all pdf files of papers or are links to 
public versions of the paper sufficient? Can people set up a webpage with
supplemental material including links? I foresee a problem with copyrights:
authors usually have the right to put their author copy online; if their 
work is relevant to my submission, I can put a link to their work on my
homepage without violating any copyright, but I cannot submit the paper to
NIST and make a statement about the copyright. This basically means that I
cannot use papers published by others.

What do you mean by "unusual vulnerabilities"? Would this be e.g. key reuse
in a scheme where decryption failures can be used to determine the secret
key? or the fragility in ECDSA with nonce reuse? It would be good if you 
could be more specific.

For the avoidance of doubt, please specify whether assembly subroutines or
intrinsics are acceptable.

p.10 "the quantum-resistant algorithm evaluation process": elsewhere you've
changed to 'post-quantum' so I suggest to adjust the phrasing here to match.

p.13 Same comment regarding key exchange being asymmetric in initiator and
responder as above.

p.16 You mean 2^k executions of AES on the given architecture? See the detailed
analysis of the costs of using Grover on AES (PQCrypto 2016); are you considering 
the estimated cost of 2^32 to equal 1? I've seen the FAQ on this topic, but that
didn't help. Some algorithms suffer much more from requiring the steps to be 
reversible than others, so it will be necessary for cryptographers to understand
quantum algorithms in any case.

In principle this is not a new problem -- 1 ECC operation is not the same an 
an AES operation and we don't even know how to define the exact security level
of elliptic curves. Counting operations in quantum algorithms is at least as 
hard.

While I think that we cannot reach a way of comparing security between AES
and post-quantum systems, I strongly suggest that systems using similar primitives
count their efficiency the same way, e.g. code-based systems against which 
information-set decoding is the most efficient, should have a consistent way of
using the cost of one loop; same for lattice-based systems using sieving. These
ways might not be accurate in the end, but at least they allow comparisons within
one class of algorithms. Eventually it is necessary to compare systems across
different primitives, but by then more detailed research on current and quantum
attacks will have happened.

p.17 I often encounter practitioners who take "perfect forward secrecy" to mean
that a later attack cannot do harm and misunderstand it to mean that they can
continue to use ECC till quantum computers arrive. They are surprised when they
understand that having the public messages + keys is enough to later on break
the scheme with a quantum computer. Due to this confusion I have started to 
use "key erasure" for this concept; given that this is not yet a common term it
is necessary to add a parenthetical comment "(also known as perfect forward 
secrecy)" for now.

Please be more specific when referring to this concept. Do you accept schemes
that become insecure if the same key is reused or do you mean to ask for schemes
which have very fast key generation time and do not require much space for the
key transmission?

p.17 While it is grammatical to say 'resistance to side-channel attack' I would
suggest to use the plural 'attacks' here, because there are many different 
attacks and a system might not be equally defendable against all of them. It 
might be useful to include a ranking of what types of attacks must be covered, 
e.g. timing attacks are applicable in significantly more situations than power 
analysis.

Regarding multi-key attacks: a brute force attack is always sped up when many
targets can be attacked; you might want to specify that this would be with 
respect to the best attack or be more precise in the 'an advantage'. Also it 
depends on the number of available keys -- after very many keys, brute force
search might be the best possibility, so limiting to 2^64 or 2^96 keys seems
reasonable.

The 'compromise a single key pair' case could be made more precise: I assume 
you mean attack any single key, so 1 out of n vs. n out of n; using a bit of 
notation should help here.

"established body of cryptographic research" is too narrow and excludes work
done in number theory or complexity theory which studies the same problems
but at different venues (compare to RSA drawing on the body of factorization
research, which gets published in crypto venues, but also at ANTS, Math Comp,,
and other journals).

p.18 same comment regarding "perfect forward secrecy" vs "key erasure"
(twice)

4.B.4: I assume that this text deals with accidental decryption failures
which are a nuisance and should thus be avoided. I suggest adding that you 
consider attacks using decryption failures as attacks, if failures are 
sufficiently common or can be triggered by an attacker.

Nitpick: what do you mean by 'encrypting the same _cipher_text'? Btw. I'm
not sure that one can always reach _acceptable_ rates, this really depends
on how bad the scheme is. 

p.20 "All proposed changes must be proposed by the submitter;" I would add that
the submitter can submit implementations prepared by third party with the 
permission of the third party. At least my understanding is that you want to
ensure that the proposer endorses the implementation, but it is not necessary
for the implementer to become part of the proposers team.


Other files:
kat.pdf still includes instructions to Sara. (twice).

api-notes.pdf:
Skipping most comments because the specifications of what is wanted are 
still not fixed. 

Please note that the supercop benchmarking framework generates KATs from 
submissions; submitters can also specify these in a separate file. This means
that you don't need to change the API to include those.