Subject: [Pqc-forum] NIST request for feedback on measurement of security strengths in our upcoming pqc call for proposals. From: "Perlner, Ray (Fed)" Date: Fri, 28 Oct 2016 15:25:55 +0000 To: pqc-forum Message-ID: We got a lot of comments on our target security strengths section in the draft call for proposals. As a result, we feel it is appropriate to request some feedback before committing to an approach for measuring security in our final CFP. Here is a summary of our past and current thinking: Previously we defined 5 security levels giving a classical and a quantum security strength. However, we were defining quantum security a little oddly, and we think this may have led to some misunderstandings. Our goal in defining these levels was to capture the practical cost in time and dollars of breaking a scheme with the listed security strength. The biggest factors we felt were not adequately captured by existing metrics for quantum security are: 1) The difficulty of parallelizing variants of Grover’s algorithm and 2) The relative cost of classical vs quantum gates. However, since most quoted figures in the literature for quantum “bits of security” don’t take these things into account, we feel it was a mistake to use that language to describe what we were asking for. Our current plan shares much with the previous approach. We still think it’s reasonable to categorize submitted parameter sets into 5 rough security strength categories, where categories 1,3, and 5 are at least as hard to break as AES128, AES192, and AES256, respectively, and categories 2 and 4 are at least as hard to break as SHA256 and SHA384 respectively. However, we don’t necessarily think that quantum security can really be captured by a single number: The practical cost of an attack will be parametrized at least by the maximum circuit depth that can be permitted by real world quantum gate times, and the relative cost of classical and quantum gates. So instead, our approach would be to say that, for any reasonable assumptions, regarding maximum circuit depth and relative quantum/classical cost, attacks against the schemes in a given security strength category should not be cheaper than attacks against the defining algorithm (e.g. something in security strength category 4 should be no easier to break, given any reasonable assumption, than SHA384.) For reference, we’d consider a maximum depth ranging from 2^40 to 2^90 logical gates, and a relative quantum/classical cost ranging from 1 to 2^40 to be reasonable. We also wish to clarify that we do not, and did not intend to require that submitters provide different parameter sets for all 5 security levels. In our view, a parameter set with a higher security strength automatically satisfies the requirements for any of the lower security strengths. Our current suggestion is that submitters provide at least one parameter set meeting or exceeding security strength 4 or 5, and as many additional parameter sets as the submitter believes are necessary to take advantage of any security/ performance tradeoffs offered by the design approach. To demonstrate what NIST expects these security strength categories will mean for submitters trying to set their parameters, consider the following hypothetical scenario: Assume you are submitting a postquantum algorithm where there is only one tunable parameter, corresponding to classical security, and there are no quantum attacks, aside from generic ones (i.e. those based on Grover’s algorithm and related stuff like amplitude amplification and quantum walks.) Then, in order to meet security strengths 1,3,5, you simply need to set classical security to equal 128, 192, 256 bits respectively. Meeting security strength 2 will require some amount of classical security between 128 and 192 bits, and meeting security strength 4 will require some amount of classical security between 192 and 256 bits. Whether the required amount of classical security is at the low or high end of this range will depend upon how well the classical attacks against your scheme Groverize (i.e. how effective are the generic techniques for decreasing the cost of the classical attacks, using quantum computers.) If they Groverize well, you will need a classical security strength on the high end of the range, and if they Groverize poorly, you will need a classical security strength on the low end of the range. One possible change we may consider making to the current approach would be to eliminate the security strengths based on hash functions. This would simplify the security analysis somewhat, by effectively making generic quantum cryptanalysis irrelevant to our evaluation criteria. However, it would leave us with no way to give credit to algorithms, if the classical attacks against them are hard to Groverize. A number of commenters suggested making a change in the opposite direction. Some even suggested going so far as to treat an algorithm with 128 bits of classical security and no quantum speedup, as being equivalently strong to a 256-bit block cipher, since both have “128 bits of quantum security.” We don’t think this is reasonable. We can come up with plausible computation models where something with 192 bits of classical security and no quantum speedup might be as hard to break as AES 256 (and we can come up with plausible models where nothing with less than 256 bits of classical security is as hard to break as AES256) but we can’t come up with a reasonable justification for treating something with much less than 192 bits of classical security as being as strong as AES 256. Questions to all interested parties: Does the current approach seem sound? What (if any) changes would you suggest? Questions to potential submitters: Do you feel you will be able to do the analysis we are requesting? Do you need more guidance? Thanks, Ray Perlner NIST