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.