1128 views

Skip to first unread message

Aug 17, 2020, 1:41:56 PM8/17/20

to pqc-forum

Dear all,

We’ve gotten a lot of questions from submitters of lattice schemes, regarding what parameters we think meet security strength category 1. The short answer is that we aren’t sure yet – we think there are still scientific questions that
need to be resolved. We're interested in having the best possible estimates of the security of each scheme; but we also realize that, to compare different schemes, we have to evaluate them using a common methodology. In round 3, we are aiming to find the right
balance between these two goals. As we’ve asked submitters to be ready with tweaks by October 1, and we are aware that several of the teams are working towards better understanding the true costs of lattice reductions, we think it would be good to share our
preliminary thoughts at this time.

At this point, we think the submitters are better able than us to precisely quantify the best known attacks along the various dimensions of number of bit operations (gates), total memory used, number of reads and writes, and memory access
patterns (local vs nonlocal). (Note here that we expect classical attacks to be the deciding factor for whether any of the Round 3 candidates meets category 1.) One place where we feel we might be able to add a bit to the discussion is how to combine these
numbers into a single cost estimate.

There have been various cost metrics in the literature for doing this. The most common metrics we’ve seen are

- The RAM model (with basic operations converted to equivalent gate count)
- Time * Area (Circuit Model)
- Time * Volume (Circuit Model)

These models have the virtue of being fairly simple, but based on fundamental physical considerations, there are various aspects of each that suggest they may overestimate or underestimate real world costs of some attacks. An alternative
approach, given that a category 1 classical attack is “only” something like 6 to 10 orders of magnitude more expensive than what a nation state adversary might be capable of, is to extrapolate from current technology.

We can start out by assigning a dollar cost to NIST’s estimate that brute force AES key search requires 2^143 gates. We’re pretty sure any attack on that scale would need to use custom hardware, like what’s used in bitcoin mining. By
doing a little comparison shopping for bitcoin mining equipment, we estimated that the cost of 2^143 bit operations was about 2^64 US$. Most of this went towards paying for energy. The amount of energy involved is roughly what could be collected over the course
of 500 years if the earth’s entire surface was tiled with solar panels.

For $2^64 / 500 years, we estimated that something like 2^95-2^100 bits of memory could be maintained. Most of this cost was the cost of periodically replacing hardware, although the cost of power, e.g. assuming the technology in question
was hard drive, was sometimes within an order of magnitude.

Given that heat dissipation considerations and the scale of the attack suggest that computing units making random access queries would be distributed around the globe, we found the limiting factor on memory access would probably be long
distance communication, e.g. via fiber optics. The cost was somewhat difficult to estimate, so we had a wide range of estimates regarding how much memory bandwidth could be afforded, but we think it’s fairly safe to say that it’s somewhere in the range of
2^105-2^120 bits worth of random access memory queries, with hardware costs exceeding energy costs by a couple of orders of magnitude. Sources of uncertainty included how much installation costs could be amortized away, how long various components last, and
whether we should estimate based on market prices for commercial products (which typically transmit less than 100Gbps on a single fiber optic) or based on wildly guessing the cost, if mass produced, of experimentally demonstrated hardware that can transmit
10s of Tbps on a single core fiber optic cable or 100s of Tbps on a multicore fiber optic cable. Note, at the high end, local memory access speeds start mattering.

This left us fairly confident that, for borderline category 1 attacks where memory costs make up a significant portion of the cost of an attack, the RAM model would almost always underestimate the cost, the time*area model would almost
always overestimate the cost, and the time*volume may either be an underestimate or an overestimate, depending on the details. For reference, the RAM model suggests no limit on memory size or memory bandwidth below 2^143 bits for category 1, and the time*
area model suggests a limit of 2^95 bits of accesses to a memory of size 2^95 bit or 2^105 accesses to a memory of size 2^76. The time*volume model suggests a limit of 2^107 accesses to a memory of size 2^107 or 2^110 accesses to a memory of size 2^100. Additionally,
we expect both time*area and time*volume to overestimate the cost of memory access when the memory size per processing unit is large or the memory is infrequently accessed.

We can also consider the latency cost of random memory access on a global scale. Two random points on earth are about 10000 km apart. Sending a request and a reply 10000 km would take at least about 2^-4 seconds. This means that for random
access memory, in 500 years we could compute to a RAM depth of up to 2^38. Let’s say we model depth by treating RAM access as a cubic nearest neighbor circuit. Assuming a memory size of 2^99 cubic nearest neighbor model would model the depth of the request
and response as having depth 2^34, yielding a total depth of 2^72.

Overall, we’re open to arguments that a given attack requiring fewer than 2^143 gates when costed in the RAM model might not contradict category 1 security if for example, the depth of the computation (assuming a 3-d nearest neighbor
arrangement) exceeds 2^75, or the number of bits written or read from random access memory exceeds 2^120, or the total size of the memory exceeds 2^100. We would of course need to be convinced that the attack was well optimized given the above criteria, e.g.
that the attack really requires random access to memory as opposed to a more local memory access pattern. We’re also not sure how these limits should be extrapolated to the higher security strength categories. A rough guess is that everything other than depth
should scale linearly in the exponent, but we’re even less sure about that than everything we’ve previously said.

Attached are slides from a recent internal presentation where we discussed these issues. (Labeling has been added to slide 1, references have been added at the end, a commercial disclaimer has been added to slide 16, and a typo in an
equation on slide 19 has been corrected. The slides are otherwise identical.)

We hope to be able to get a better understanding of the concrete analysis of lattice attacks, so we can determine how much the real world costs of these attacks are increased by memory considerations. Any comments on our thoughts thus
far would be greatly appreciated.

Thanks,

NIST PQC team

__ __

Aug 17, 2020, 2:19:07 PM8/17/20

to pqc-forum, Perlner, Ray A. (Fed), pqc-forum

Hi Ray,

Speaking for myself.

I still think there had to have been a good slide in there somewhere where you could legitimately add an image of a Death Star.

Just saying. =)

Best,

--Daniel

Speaking for myself.

I still think there had to have been a good slide in there somewhere where you could legitimately add an image of a Death Star.

Just saying. =)

Best,

--Daniel

Aug 17, 2020, 5:26:19 PM8/17/20

to pqc-forum

Many (not all) numbers seem to be missing from the slides under Linux.

Can you please post a PDF?

> 2^105-2^120 bits worth of random access memory queries

To clarify, that's 2^120 bits from random spots around the globe fitting

the energy budget of 2^143 bit operations, so retrieving N bits from N

random spots costs <=2^23*N bit operations? (Let's assume big enough

chunks of bits that the routing data isn't the issue.)

Intel said in

https://www.openfabrics.org/images/eventpresos/workshops2015/DevWorkshop/Tuesday/tuesday_10.pdf

that a double-precision floating-point multiplication costs 6.4 pJ at

22nm (scaling "well with process and voltage", so actually <6.4 pJ with

a more modern process). That's around 2^14 bit operations, so 2^23*N bit

operations are around 512*6.4*N pJ (or less).

Intel also said that moving 64 bits straight through a wire costs 11.20

pJ per 5 mm ("more difficult to scale down"). Moving 18752*N bits

through the same 5mm wire thus costs 512*6.4*N pJ.

For comparison, a bit at some random spot on the globe is typically

around 10000000000 mm away. That's five orders of magnitude farther away

than 18752*5 mm, and it's at one of a huge number of different possible

positions. I understand that you have in mind fiber optics for the

long-distance communication, but fiber optics don't magically avoid

per-distance costs, plus there's a massive parallel routing problem at

every moment since we're talking about attacks bottlenecked by RAM

access. What's the global RAM architecture that you're referring to, and

how did you evaluate its costs?

For comparison, supercomputers on much smaller scales (tens of meters)

spend large fractions of their budgets on fiber-optic communication but

still don't have the bisection bandwidth necessary to constantly feed

new data to their processors. For example,

https://www.nextplatform.com/2018/06/26/peeling-the-covers-off-the-summit-supercomputer/

reports Summit's 200 petaflops dropping to 3 petaflops when there's lots

of communication: the bisection bandwidth is only 920 Tb/sec.

> the time*area model would almost always overestimate the cost

Sorry, can you please clarify the source of this claim?

---Dan

Can you please post a PDF?

> 2^105-2^120 bits worth of random access memory queries

the energy budget of 2^143 bit operations, so retrieving N bits from N

random spots costs <=2^23*N bit operations? (Let's assume big enough

chunks of bits that the routing data isn't the issue.)

Intel said in

https://www.openfabrics.org/images/eventpresos/workshops2015/DevWorkshop/Tuesday/tuesday_10.pdf

that a double-precision floating-point multiplication costs 6.4 pJ at

22nm (scaling "well with process and voltage", so actually <6.4 pJ with

a more modern process). That's around 2^14 bit operations, so 2^23*N bit

operations are around 512*6.4*N pJ (or less).

Intel also said that moving 64 bits straight through a wire costs 11.20

pJ per 5 mm ("more difficult to scale down"). Moving 18752*N bits

through the same 5mm wire thus costs 512*6.4*N pJ.

For comparison, a bit at some random spot on the globe is typically

around 10000000000 mm away. That's five orders of magnitude farther away

than 18752*5 mm, and it's at one of a huge number of different possible

positions. I understand that you have in mind fiber optics for the

long-distance communication, but fiber optics don't magically avoid

per-distance costs, plus there's a massive parallel routing problem at

every moment since we're talking about attacks bottlenecked by RAM

access. What's the global RAM architecture that you're referring to, and

how did you evaluate its costs?

For comparison, supercomputers on much smaller scales (tens of meters)

spend large fractions of their budgets on fiber-optic communication but

still don't have the bisection bandwidth necessary to constantly feed

new data to their processors. For example,

https://www.nextplatform.com/2018/06/26/peeling-the-covers-off-the-summit-supercomputer/

reports Summit's 200 petaflops dropping to 3 petaflops when there's lots

of communication: the bisection bandwidth is only 920 Tb/sec.

> the time*area model would almost always overestimate the cost

---Dan

Aug 17, 2020, 6:05:16 PM8/17/20

to D. J. Bernstein, pqc-forum

Here's a pdf

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20200817212602.2154049.qmail%40cr.yp.to.

You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20200817212602.2154049.qmail%40cr.yp.to.

Aug 18, 2020, 7:25:13 PM8/18/20

to ray.p...@nist.gov, pqc-forum

"Perlner, Ray A. (Fed)" wrote:

> We’ve gotten a lot of questions from submitters of lattice

> schemes, regarding what parameters we think meet

> security strength category 1. The short answer is that we

> aren’t sure yet ...

> We hope to be able to get a better understanding of the

> concrete analysis of lattice attacks, so we can determine

> how much the real world costs of these attacks are

> increased by memory considerations.

It's important to avoid thinking of this as a problem just for

lattices. Many attacks against non-lattice schemes also

lattices. Many attacks against non-lattice schemes also

require exponential memory. Information set decoding is

a clear example of this.

The LEDAcrypt team have released code which gives

non-asymptotic cost estimates for six classical and two

quantum information set decoding algorithms. The

non-asymptotic cost estimates for six classical and two

quantum information set decoding algorithms. The

classical estimates are expressed in bit operations and

include a logarithmic cost for memory. The code is

available from github.com/LEDAcrypt/LEDAtools. More

include a logarithmic cost for memory. The code is

available from github.com/LEDAcrypt/LEDAtools. More

details can be found in [Baldi, Barenghi, Chiaraluce,

Pelosi and Santini. "A finite regime analysis of information

set decoding algorithms." Algorithms, 2019].

Modifying the LEDAcrypt code so that it includes no cost,

logarithmic cost, cube root cost, or square root cost for

memory gives the following classical estimates for BJMM

with the Classic McEliece round 2 parameter sets.

with the Classic McEliece round 2 parameter sets.

Parameter Set Free Log Cbrt Sqrt

mceliece-3488-064: 142.5 148.8 156.7 160.4

mceliece-4608-096: 182.9 189.0 198.2 202.0

mceliece-6688-128: 253.4 260.1 275.5 279.6

mceliece-6960-119: 252.7 259.6 276.8 281.0

mceliece-8192-128: 285.1 292.2 313.8 318.4

mceliece-3488-064: 142.5 148.8 156.7 160.4

mceliece-4608-096: 182.9 189.0 198.2 202.0

mceliece-6688-128: 253.4 260.1 275.5 279.6

mceliece-6960-119: 252.7 259.6 276.8 281.0

mceliece-8192-128: 285.1 292.2 313.8 318.4

There are a few interesting things to point out here.

- mceliece-4608-096 fails to meet the classical target for

Category 3 using any of the memory cost models.

- mceliece-6688-128 and mceliece-6960-119 both appear

to meet the classical target for Category 5 when a cube

root or square root memory cost is included but Stern

needs less than 2^50 memory for these parameter sets.

Assuming a logarithmic memory cost for Stern gives

estimates that are marginally below Category 5 (see

Tables 4 and 5 in the paper).

- Of the five Classic McEliece parameter sets only two,

mceliece-3488-064 and mceliece-8192-128, clearly meet

their classical targets.

Kirk

Aug 18, 2020, 8:40:42 PM8/18/20

to pqc-...@list.nist.gov

Kirk Fleming writes:

> - Of the five Classic McEliece parameter sets only two,

> mceliece-3488-064 and mceliece-8192-128, clearly meet

> their classical targets.

That submission already says for (e.g.) mceliece6960119 that "Subsequent
> - Of the five Classic McEliece parameter sets only two,

> mceliece-3488-064 and mceliece-8192-128, clearly meet

> their classical targets.

ISD variants have reduced the number of bit operations considerably

below 2^256" but that "We expect that switching from a bit-operation

analysis to a cost analysis will show that this parameter set is more

expensive to break than AES-256 pre-quantum and much more expensive to

break than AES-256 post-quantum." The 281 that you mention matches this.

I agree with your broader point that the lack of clear, stable metrics

for NIST's category definitions isn't just a lattice issue. There's also

massive memory usage in state-of-the-art MQ attacks, SIKE attacks, the

BHT hash-collision algorithm, etc.

Why does the call for proposals say that SHA3-384 collisions require

2^210 gates, when BHT clearly does much better than this? A separate

NIST document cited my paper

https://cr.yp.to/papers.html#collisioncost

as a rationale for dismissing BHT, but that paper uses a different

metric (the 1981 Brent--Kung metric and a quantum version of it) to

account for communication costs. In other words, NIST already rejected

BHT on the basis of communication costs, but then mislabeled this as a

gates calculation, giving two contradictory messages regarding which

metrics NIST is using to define its categories.

---Dan (speaking for myself)

Aug 19, 2020, 10:53:51 AM8/19/20

to D. J. Bernstein, pqc-forum

Hi Dan.

You ask:

" Why does the call for proposals say that SHA3-384 collisions require

2^210 gates, when BHT clearly does much better than this?"

The CFP specifically estimates the cost of a SHA3-384 collision as 2^210 classical gates. BHT only has fewer gates than this if its cost is evaluated in the quantum RAM model. In the circuit model, which is used in almost all concrete quantum resource estimates in the literature, BHT gives no advantage over the van Oorschot-Wiener algorithm (vOW97: https://people.scs.carleton.ca/~paulv/papers/JoC97.pdf ) -- the classical algorithm that was used to arrive at our estimate of 2^210 classical gates. I would argue that there are strong theoretical reasons to suspect that the quantum RAM model is a much less realistic model of computation than the classical RAM model, since I know of no proposal for a physically plausible implementation of a fault tolerant quantum RAM that performs significantly better than would be suggested by the circuit model cost of simulating the RAM via the methods in Beals et al. 2012 ( https://arxiv.org/abs/1207.2307 .)

A better case could be made that the hybrid classical/quantum algorithm of C, N-P, S 2017 (https://eprint.iacr.org/2017/847 ) may offer some small advantage over vOW when quantum operations adhere to a circuit model and classical operations adhere to a RAM model. But, even here, the advantage only exists when a computational depth of greater than O(2^(n/4)) for an n bit hash function is achievable. For SHA3-384, this is 2^96, ignoring constant factors which probably make it significantly worse. And, if one assumes something like Bennett's Brownian computation (See http://www.pitt.edu/~jdnorton/lectures/Rotman_Summer_School_2013/thermo_computing_docs/Bennett_1982.pdf ), where the energy cost of a gate is inversely proportional to how long it takes to perform, then any advantage from C, N-P, S 2017 disappears. An argument of this form was applied to BHT in my own paper with Yi-Kai Liu https://arxiv.org/abs/1709.10510 and it extends straightforwardly to C, N-P, S 2017.

You also mention your own paper: https://cr.yp.to/papers.html#collisioncost . I don't see the main conclusion of that paper (that vOW is at least as good as BHT) as relying on assuming communication costs proportional to the square root of the width of the computation. E.g. figure 1.2 from your paper already shows the main conclusion while assuming that communication is free.

-- Ray

-----Original Message-----

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of D. J. Bernstein

Sent: Tuesday, August 18, 2020 8:40 PM

To: pqc-forum <pqc-...@list.nist.gov>

Subject: Re: [pqc-forum] Update on category 1 security

You ask:

" Why does the call for proposals say that SHA3-384 collisions require

2^210 gates, when BHT clearly does much better than this?"

A better case could be made that the hybrid classical/quantum algorithm of C, N-P, S 2017 (https://eprint.iacr.org/2017/847 ) may offer some small advantage over vOW when quantum operations adhere to a circuit model and classical operations adhere to a RAM model. But, even here, the advantage only exists when a computational depth of greater than O(2^(n/4)) for an n bit hash function is achievable. For SHA3-384, this is 2^96, ignoring constant factors which probably make it significantly worse. And, if one assumes something like Bennett's Brownian computation (See http://www.pitt.edu/~jdnorton/lectures/Rotman_Summer_School_2013/thermo_computing_docs/Bennett_1982.pdf ), where the energy cost of a gate is inversely proportional to how long it takes to perform, then any advantage from C, N-P, S 2017 disappears. An argument of this form was applied to BHT in my own paper with Yi-Kai Liu https://arxiv.org/abs/1709.10510 and it extends straightforwardly to C, N-P, S 2017.

You also mention your own paper: https://cr.yp.to/papers.html#collisioncost . I don't see the main conclusion of that paper (that vOW is at least as good as BHT) as relying on assuming communication costs proportional to the square root of the width of the computation. E.g. figure 1.2 from your paper already shows the main conclusion while assuming that communication is free.

-- Ray

-----Original Message-----

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of D. J. Bernstein

Sent: Tuesday, August 18, 2020 8:40 PM

To: pqc-forum <pqc-...@list.nist.gov>

Subject: Re: [pqc-forum] Update on category 1 security

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20200819004024.2200029.qmail%40cr.yp.to.
You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

Aug 19, 2020, 11:09:26 PM8/19/20

to pqc-...@list.nist.gov

'Perlner, Ray A. (Fed)' via pqc-forum writes:

> The CFP specifically estimates the cost of a SHA3-384 collision as

> 2^210 classical gates. BHT only has fewer gates than this if its cost

> is evaluated in the quantum RAM model.

That's a standard model in the literature on quantum algorithms. The
> The CFP specifically estimates the cost of a SHA3-384 collision as

> 2^210 classical gates. BHT only has fewer gates than this if its cost

> is evaluated in the quantum RAM model.

word "gates" doesn't exclude this model. See, e.g., Ambainis's famous

element-distinctness paper https://arxiv.org/pdf/quant-ph/0311001.pdf

using "random access gates" in the model of computation.

Excluding RAM gates would be an earthquake for pretty much the entire

literature building interesting quantum-walk algorithms, including

cryptanalytic algorithms such as 2018 Kirshanova. If NIST wants to

exclude RAM gates then it needs to make this clear.

In June 2020 you announced four principles for evaluating a metric.

Three of those principles say that it's bad to switch from the metric in

Ambainis's paper to a metric that excludes RAM gates:

* "The value of the proposed metric can be accurately measured (or at

least lower bounded) for all known attacks": Quantum algorithms,

notably quantum-walk papers, are constantly using RAM gates.

Forcing these gates to be replaced by sequences of (e.g.) T, H, and

CNOT complicates the analysis and optimization. How do you expect

people to come up with measurements, or useful lower bounds, for

these algorithms within the NISTPQC timeframe?

* "We can be reasonably confident that all known attacks have been

optimized with respect to the proposed metric": Again, quantum-walk

papers are _trying_ to optimize in a model that allows low-cost RAM

gates. There's little evidence of people trying to re-optimize

these algorithms for more restricted models of computation.

* "The proposed metric will more accurately reflect the real-world

feasibility of implementing attacks with future technology": This

is the only principle that favors discarding low-cost RAM gates.

* "The proposed metric will not replace these underestimates with

overestimates": This again opposes eliminating RAM gates. People

forced to produce estimates of RAM cost in a more restricted model

of quantum computation will plug in 2018 Babbush--Gidney--Berry--

Wiebe--McClean--Paler--Fowler--Neven, which gives an upper bound on

the number of T-gates used, with free H and CNOT, to simulate a RAM

lookup of an n-bit table entry x[i] given an m-bit index i. This

gives an overestimate in the context of typical higher-level

algorithms, since it's missing all the opportunities to share work

across multiple table lookups by, e.g., sorting.

Note also that counting CNOT as _zero_ cost, as in the 2018 paper,

raises questions that show up in some algorithmic contexts but that

most algorithm designers haven't considered: how much can we reduce

multiplications if we can do massive linear maps for free? Instead

counting CNOT as, say, 1% the cost of T makes me think that

Kronrod-type algorithms would beat the 2018 paper when m and n are

both large, but I haven't seen any papers quantifying this. The

general theme here is that, no, people have not been optimizing

most attack algorithms with respect to these metrics.

It's not clear what weights NIST is applying to these principles when

they are in conflict, as in this case. (I'm a big fan of accuracy, and

I'm not a big fan of encouraging fake confidence, so I'd be happy to see

NIST throwing away RAM gates, faster-than-light communication, magical

power transport into three-dimensional parallel databases, etc.)

It's astonishing that, four years into NISTPQC, we still don't have

clear, stable definitions of the metrics that NIST is using to specify

its security "categories". It doesn't look good for NIST to be applying

definitions selectively to _some_ attack algorithms and to _some_

submissions. Clear, stable definitions would let everybody go through

the exercise of evaluating, e.g., BHT in the announced metrics and

seeing whether BHT outperforms VoW in any of those metrics.

> In the circuit model, which is used in almost all concrete quantum

> resource estimates in the literature

literature, just as in the non-quantum literature. Ambainis's paper uses

a circuit model. The details matter.

I agree that there are papers quantifying gates for Shor (vs., e.g.,

RSA) and Grover (vs., e.g., AES) and Kuperberg (vs., e.g., CSIDH) while

not using RAM gates. However, the fact that a paper isn't using some

feature of a model does _not_ imply that the paper is opposing the

model. These papers are meaningful in, e.g., Ambainis's model. RAM gates

can help for a few extra optimizations in some of these algorithms but

don't seem to have the sort of dramatic impact that one sees in BHT etc.

The 2018 paper mentioned above is an exception---the paper would be

silly in a model that assigns low cost to RAM gates---but this is very

far from "almost all" papers on "concrete quantum resource estimates".

The bigger picture is that algorithm designers naturally gravitate

towards models that make their algorithms simple, such as RAM models.

This isn't the same as making the definitions simple, and it isn't the

same as reality. Single-tape Turing machines are simpler to define than

RAM models but harder to program. VLSI models are more realistic than

RAM models but harder to program. There's a subcommunity digging into

bit-level optimizations, layout optimizations, etc., but there's also a

strong argument for optimizing algorithms at the easy level first.

> I would argue that there are strong theoretical reasons to suspect

> that the quantum RAM model is a much less realistic model of

> computation than the classical RAM model

across the room at a wall of data (encoded as filters and mirrors), and

seeing what comes back?

Of course reality is more complicated: e.g., real lasers spread. The

communication costs end up being Omega(distance), just like every other

known communication mechanism. But I haven't seen any papers claiming to

prove that low-cost quantum RAM is contrary to the laws of physics.

Meanwhile you seem to have been saying that, since the laws of physics

aren't known to prevent data from moving without energy to a specified

location any distance away, we should allow this operation for free in

our algorithms. What makes this plausible and quantum RAM implausible?

When I look at a supposedly physical model of computation, I ask where

the data is stored and how errors are corrected. 2-D quantum circuits

have had clear answers to this for many years: if we can place atoms

close enough to a specified configuration then, according to everything

we know about physics, they'll run a quantum computation. Other models

that say "We don't know where the atoms should go but maybe someone will

have an idea" sound to me like "We don't know how to use less memory in

this algorithm but maybe someone will have an idea". Sure, we should

recognize the security risks of possible attack improvements, but in the

meantime let's accurately analyze the _known_ attacks.

One important purpose of accurate analyses of known algorithms is to be

able to see when algorithms are improving. ("Maturity of analysis" is

one of the NISTPQC evaluation criteria.) This evaluation is damaged if

accurate analyses are replaced by claimed or proven lower bounds: this

hides small improvements, and then people are surprised when the small

improvements add up to breaking the lower bounds, as we've seen for

lattices. It's a mistake to confuse known attacks with possible

improvements, whether the confusion is at an "algorithmic" level or an

"implementation" level or an "architectural" level.

> I don't see the main conclusion of that paper (that vOW is at least as

> good as BHT) as relying on assuming communication costs proportional

> to the square root of the width of the computation. E.g. figure 1.2

> from your paper already shows the main conclusion while assuming that

> communication is free.

resource allocation, saying that someone who can afford massive storage

can also afford a maybe-not-quite-as-massive number of processing units.

#2 is locality, saying that costs increase with distance. The paper

computes all results in a #1+#2 model, while also showing results in a

#1 model to make the component effects clear. The paper doesn't endorse

leaving out #2: on the contrary, it says that leaving out #2 is making

"the naive assumption that communication is free".

(The gap between two-dimensional models such as Brent--Kung and

science-fiction three-dimensional models such as Preparata makes a

smaller difference in the numbers, basically going 1/3 of the way from

#1+#2 to #1. The paper briefly mentions three-dimensional models.)

Regarding BHT, I'm not sure what you're disagreeing with in what I

wrote. I'm disputing NIST's claim in the call for proposals that BHT

requires as many gates as VoW, around 2^210 for SHA3-384. There are

various other metrics that account for communication costs and make BHT

as expensive than VoW, and NIST rejected BHT on this basis, but NIST

mislabeled this as a gates calculation. The fact that BHT can be

rejected by #1 _or_ #1+#2 _or_ other possibilities helps illustrate the

lack of clarity regarding the definitions of the categories.

---Dan (speaking for myself)

Aug 22, 2020, 4:27:43 PM8/22/20

to pqc-forum, D. J. Bernstein, pqc-...@list.nist.gov

Hi Dan,

(Speaking for myself)

As is typical when you write a 14-paragraph response (sorry!-- 26 paragraph response), I am happy to respond to this point or that that seem to me to be the most important, or otherwise best explain my current thinking (or NIST's thinking, insofar as I understand it myself as a member of the team). When the situation with some technical issue rises to a sufficient threshold, we will discuss beforehand and respond as a team.

So, it is my hope that this effort in responding to a specific point does not come across as a "lack of transparency" simply by the effort to respond, nor on the other hand, as a bad-faith "Gish gallop" argument on your part simply by the multitude of paragraphs you've presented. (Hopefully we can work through whatever issues you feel are the most important before you present another ~26 paragraphs for discussion on unrelated topics.)

Please note that we have our own work to do aside from responding to every single comment you personally make on this forum.

For example, we (as human beings) judge the importance of responding to issues raised on this forum, in part, by the presence of commentary by multiple people from the broader community as well as our own availability.

(We can all agree that it would be quite unfortunate if the NIST PQC team's entire work days were consumed by working through responses to a pqc-forum filibuster by one member of the community on the forum.)

-----

That said--

Dan wrote:

> * "The proposed metric will more accurately reflect the real-world

> feasibility of implementing attacks with future technology": This

> is the only principle that favors discarding low-cost RAM gates.

Yes, this is the core point here.

As you wrote:

> I'm a big fan of accuracy, and I'm not a big fan of encouraging fake confidence, so

> **I'd be happy to see NIST throwing away RAM gates**...

it is clear that the RAM model excludes a number of real-world issues regarding the costing of memory access.

Naturally, the RAM model is most useful in the context of efficiently sorting a list of a few thousand elements on one's home PC for an introductory algorithms course assignment in undergrad or grad school.

However, as the computation becomes more complex and much larger, the RAM model no longer "properly models" what is going on in real life.

Much of our perspective on this issue so far is laid out in the slides that Ray posted in the initial thread here. Yes, the issue is complex, and we hope that submission teams independently work through these issues when they consider tweaks for the 3rd Round (the final round for many such submissions, one way or the other).

As a separate matter, it was our hope that posting the slides of our internal meeting on this topic represents an__extraordinary, historically unique instance of transparency to the public__. You are welcome to tweet otherwise.

-----

Further, while I'll leave the BHT vs VoW issue (or other issues) as something Ray might respond to, you wrote:

> It's astonishing that, four years into NISTPQC, we still don't have

> clear, stable definitions of the metrics that NIST is using to specify

> its security "categories". It doesn't look good for NIST to be applying

> definitions selectively to _some_ attack algorithms and to _some_ submissions.

The definitions of the metrics NIST is using to specify security categories has not changed since the Call for Proposals. They have been stable for the entire process.

Indeed, NIST's role in measurement science includes an active effort in specializing the prior, stable definitions to precision of very low-order targets as the process proceeds.

In particular, the definition of Category 1 as "hard to break as AES-128" has not changed since the Call for Proposals.

Nonetheless, when one specializes to the exact issue of NIST PQC lattice-based KEMs' real-world security with respect to CoreSVP strength in the context of "as real-world as possible" machine and memory modeling, there remains a difference of scientific opinion within the broader scientific/research community on the low-order details of this issue.

(This should not be a surprise to you. You've argued on this issue at length elsewhere.)

As we've indicated with you (via your private input to us) and with other teams previously, one can simply 'mask' the imprecision with this issue by increasing CoreSVP strength of given parameter sets by a very small amount; i.e. a handful of bits, 6-7 or so. Alternatively, a team could choose to make a very rigorous argument that they can get away with 2 or 3 bits of lower CoreSVP strength by diving down the rabbit hole of machine and memory modeling. We have chosen to leave both of those options open to every team in the 3rd Round, and make those decisions available for public vetting over the next 11-17 months.

Hope this is helpful,

--Daniel Apon

(Speaking for myself)

As is typical when you write a 14-paragraph response (sorry!-- 26 paragraph response), I am happy to respond to this point or that that seem to me to be the most important, or otherwise best explain my current thinking (or NIST's thinking, insofar as I understand it myself as a member of the team). When the situation with some technical issue rises to a sufficient threshold, we will discuss beforehand and respond as a team.

So, it is my hope that this effort in responding to a specific point does not come across as a "lack of transparency" simply by the effort to respond, nor on the other hand, as a bad-faith "Gish gallop" argument on your part simply by the multitude of paragraphs you've presented. (Hopefully we can work through whatever issues you feel are the most important before you present another ~26 paragraphs for discussion on unrelated topics.)

Please note that we have our own work to do aside from responding to every single comment you personally make on this forum.

For example, we (as human beings) judge the importance of responding to issues raised on this forum, in part, by the presence of commentary by multiple people from the broader community as well as our own availability.

(We can all agree that it would be quite unfortunate if the NIST PQC team's entire work days were consumed by working through responses to a pqc-forum filibuster by one member of the community on the forum.)

-----

That said--

Dan wrote:

> * "The proposed metric will more accurately reflect the real-world

> feasibility of implementing attacks with future technology": This

> is the only principle that favors discarding low-cost RAM gates.

As you wrote:

> I'm a big fan of accuracy, and I'm not a big fan of encouraging fake confidence, so

it is clear that the RAM model excludes a number of real-world issues regarding the costing of memory access.

Naturally, the RAM model is most useful in the context of efficiently sorting a list of a few thousand elements on one's home PC for an introductory algorithms course assignment in undergrad or grad school.

However, as the computation becomes more complex and much larger, the RAM model no longer "properly models" what is going on in real life.

Much of our perspective on this issue so far is laid out in the slides that Ray posted in the initial thread here. Yes, the issue is complex, and we hope that submission teams independently work through these issues when they consider tweaks for the 3rd Round (the final round for many such submissions, one way or the other).

As a separate matter, it was our hope that posting the slides of our internal meeting on this topic represents an

-----

Further, while I'll leave the BHT vs VoW issue (or other issues) as something Ray might respond to, you wrote:

> It's astonishing that, four years into NISTPQC, we still don't have

> clear, stable definitions of the metrics that NIST is using to specify

> its security "categories". It doesn't look good for NIST to be applying

> definitions selectively to _some_ attack algorithms and to _some_ submissions.

Indeed, NIST's role in measurement science includes an active effort in specializing the prior, stable definitions to precision of very low-order targets as the process proceeds.

In particular, the definition of Category 1 as "hard to break as AES-128" has not changed since the Call for Proposals.

Nonetheless, when one specializes to the exact issue of NIST PQC lattice-based KEMs' real-world security with respect to CoreSVP strength in the context of "as real-world as possible" machine and memory modeling, there remains a difference of scientific opinion within the broader scientific/research community on the low-order details of this issue.

(This should not be a surprise to you. You've argued on this issue at length elsewhere.)

As we've indicated with you (via your private input to us) and with other teams previously, one can simply 'mask' the imprecision with this issue by increasing CoreSVP strength of given parameter sets by a very small amount; i.e. a handful of bits, 6-7 or so. Alternatively, a team could choose to make a very rigorous argument that they can get away with 2 or 3 bits of lower CoreSVP strength by diving down the rabbit hole of machine and memory modeling. We have chosen to leave both of those options open to every team in the 3rd Round, and make those decisions available for public vetting over the next 11-17 months.

Hope this is helpful,

--Daniel Apon

Aug 24, 2020, 9:52:27 AM8/24/20

to daniel.apon, D. J. Bernstein, pqc-...@list.nist.gov

On Sat, Aug 22, 2020 at 4:27 PM 'daniel.apon' via pqc-forum

<pqc-...@list.nist.gov> wrote:

<snip>

submissions A and B we'd be able to compare their security and

performance against the best attacks and relative to AES-128. But if

team B goes and adds a few more dimensions, while team A argues the

exact same attack that applies to B and A is actually a few bits worse

than anticipated, then submission B is slower and might not get

"credit" for being more secure than submission A. This may cast doubt

on the final choice, akin to the issues with SHA3, where an

unrealistic preimage security parameter was later changed post-contest

despite influencing the performance of many submissions negatively.

Imagine we had a PreQuantum contest, and were tasked with evaluating

RSA vs prime field Diffie Hellman. The impact of parallelism and multi

targets matters for both, and does so differently from AES, and does

so differently in different models of computation. But the underlying

attacks are very similar, differing in one slight way. In this

hypothetical I think the right thing would be to look at the

similarity of the problems underlying them, and separately develop the

best attacks in the models, vs. letting the RSA team carefully

evaluate the asymptotics while the prime field DH team throws on more

bits.

Sincerely,

Watson Ladd

<pqc-...@list.nist.gov> wrote:

<snip>

> Indeed, NIST's role in measurement science includes an active effort in specializing the prior, stable definitions to precision of very low-order targets as the process proceeds.

> In particular, the definition of Category 1 as "hard to break as AES-128" has not changed since the Call for Proposals.

>

> Nonetheless, when one specializes to the exact issue of NIST PQC lattice-based KEMs' real-world security with respect to CoreSVP strength in the context of "as real-world as possible" machine and memory modeling, there remains a difference of scientific opinion within the broader scientific/research community on the low-order details of this issue.

>

> (This should not be a surprise to you. You've argued on this issue at length elsewhere.)

>

> As we've indicated with you (via your private input to us) and with other teams previously, one can simply 'mask' the imprecision with this issue by increasing CoreSVP strength of given parameter sets by a very small amount; i.e. a handful of bits, 6-7 or so. Alternatively, a team could choose to make a very rigorous argument that they can get away with 2 or 3 bits of lower CoreSVP strength by diving down the rabbit hole of machine and memory modeling. We have chosen to leave both of those options open to every team in the 3rd Round, and make those decisions available for public vetting over the next 11-17 months.

I think this is unfortunate from a process perspective. Ideally given
> In particular, the definition of Category 1 as "hard to break as AES-128" has not changed since the Call for Proposals.

>

> Nonetheless, when one specializes to the exact issue of NIST PQC lattice-based KEMs' real-world security with respect to CoreSVP strength in the context of "as real-world as possible" machine and memory modeling, there remains a difference of scientific opinion within the broader scientific/research community on the low-order details of this issue.

>

> (This should not be a surprise to you. You've argued on this issue at length elsewhere.)

>

> As we've indicated with you (via your private input to us) and with other teams previously, one can simply 'mask' the imprecision with this issue by increasing CoreSVP strength of given parameter sets by a very small amount; i.e. a handful of bits, 6-7 or so. Alternatively, a team could choose to make a very rigorous argument that they can get away with 2 or 3 bits of lower CoreSVP strength by diving down the rabbit hole of machine and memory modeling. We have chosen to leave both of those options open to every team in the 3rd Round, and make those decisions available for public vetting over the next 11-17 months.

submissions A and B we'd be able to compare their security and

performance against the best attacks and relative to AES-128. But if

team B goes and adds a few more dimensions, while team A argues the

exact same attack that applies to B and A is actually a few bits worse

than anticipated, then submission B is slower and might not get

"credit" for being more secure than submission A. This may cast doubt

on the final choice, akin to the issues with SHA3, where an

unrealistic preimage security parameter was later changed post-contest

despite influencing the performance of many submissions negatively.

Imagine we had a PreQuantum contest, and were tasked with evaluating

RSA vs prime field Diffie Hellman. The impact of parallelism and multi

targets matters for both, and does so differently from AES, and does

so differently in different models of computation. But the underlying

attacks are very similar, differing in one slight way. In this

hypothetical I think the right thing would be to look at the

similarity of the problems underlying them, and separately develop the

best attacks in the models, vs. letting the RSA team carefully

evaluate the asymptotics while the prime field DH team throws on more

bits.

Sincerely,

Watson Ladd

Aug 24, 2020, 2:30:03 PM8/24/20

to pqc-forum, watso...@gmail.com, D. J. Bernstein, pqc-...@list.nist.gov, daniel.apon

Hi Watson,

(Again, speaking for myself)

Thanks for your comments! (Apologies for the length of my response ahead of time. =))

Let me explain my view of the core of the situation as follows: This memory / machine modeling issue (underlying this thread, and with a plethora of discussion in previous threads that motivated creating this discussion thread) is essentially specific to the case of the real-world, concrete security of the lattice-based candidates (mainly KEMs, but also certainly relevant to signatures as well). As this issue is entirely generic, it would naturally have implications for the non-lattice candidates as well. However, for each possible comparison case involving purely non-lattice schemes, it doesn't appear that machine / memory modeling is a critical issue regarding the decision-point of whether to standardize this or that scheme. (That is, we will or will not standardize some non-lattice scheme essentially independent of this issue.)

So, in Round 3, we (still) have a plethora of lattice schemes, for which this issue is*potentially* relevant: DILITHIUM, Falcon, Frodo, KYBER, NTRU, sNTRUPrime, NTRULRPrime, Saber.

Please allow me to point out the following issues:

1) For the most part, the lattice schemes' practical efficiency has a logarithmic dependence on CoreSVP strength. That is, if you want to increase CoreSVP strength from 2^X to 2^{X+5}, say, then roughly real-world security would increase from 2^Y to 2^{Y+5}. Correspondingly, in order to meet this goal, the dimension, modulus, and error distribution may change slightly, and the overall performance of the system (in terms of PK/SK/CT size, and KeyGen/Enc/Dec timing) would increase by, say, ~5-6%. (This is in the context of Category 1 security, where the security parameter is noticeably close to 100.)

2) While most schemes can target their choice of CoreSVP strength, there is one caveat: For most lattice schemes, there are 'algebraic constraints' on the choice of dimension, module-rank, modulus, etc. These constraints imply that certain CoreSVP values may not be naturally achievable. For example, a scheme may be able to efficiently target, say, 124 CoreSVP strength and 130 CoreSVP strength, but the scheme may not naturally be able to target something in the range 125-129 without significant additional efficiency-cost. (Many submissions include a script that allows one to find such 'equilibrium points' in their parameter selections, and then choose among those.)

Therefore, the choice for each lattice-candidate in the 3rd Round will be something as follows:

a) Hit 128/129/130 CoreSVP strength (as their parameter options allow), and definitely meet the Category 1 security target -- at the cost of definitely over-shooting the minimum real-world security for Category 1.

b) Hit (something like) 122/123/124 CoreSVP strength (as their parameter options allow), and make a simple argument that real-world memory costing makes up the 4-6 bit difference.

c) Hit (something like) 116-120 CoreSVP strength (as their parameter options allow), and then*really convince everyone(!)* that this is sufficient CoreSVP strength based on a strong argument of the possibilities of memory costs of future machines.

d) Hit something noticeably lower than the above thresholds, make a unique breakthrough argument, and hope that it can be formally vetted (by*everyone*, not just NIST) within the duration of the 3rd Round. (We'll call this the "risky option.")

Again, speaking for myself -- this is an attempt to convey information about my view of where people should target their tweaks for the 3rd Round. Historically (looking back at Round 1 and Round 2), some teams were very good about presenting exact CoreSVP strength values for each parameter set, and an even fewer number of teams were very good about arguing the exact details of why their selection truly met the Category 1 requirements. On the other hand, some teams merely described the nature of BKZ-like attacks against their underlying computational assumptions and simply deferred to the (now, somewhat outdated) "Estimate All The...!" paper/website.

Further, it's worth noting that the only "TLS-ready" (meaning, the 'closest to a drop-in replacement' for online protocols) signature schemes appear to be the lattice schemes: DILITHIUM and Falcon. At the same time, the lattice signature schemes tend to have presented parameters*with noticeably lower CoreSVP strengths* than the lattice KEMs. This is somewhat of a Catch-22: As a process issue, NIST would strongly prefer to standardize a TLS-ready post-quantum signature scheme at the end of the 3rd Round, and so we need to give the lattice signature teams an opportunity to re-evaluate their parameter *of their own volition*, and then provide a sufficient period of time for public vetting. At the same time, we need to treat the lattice KEM schemes fairly.

So, here is the final point:

__The key deciding factor between this lattice KEM and that lattice KEM is extremely unlikely to be a 5% (or even 10%) difference in performance__. (In that sense, the topic we're discussing now is not so important for the process..)

There are a variety of subtle, non-performance-related issues still to be resolved, which must take precedence. Here is a short list:

1) What is the relative effectiveness and cost of masking the lattice KEM candidates against side-channel attacks, like DPA/cold boot/template attacks/etc? (This requires masked implementations to be published, and then attacked or not, within the timespan of the 3rd Round..)

2) Does the side-channel situation change in the context of hardware implementations of these schemes?

4) Are there significant implementation challenges with one lattice scheme compared to another? How difficult is it for a 'reasonably-informed' engineer to produce safe, efficient code for this scheme or that?

5) Are lattices over cyclotomic number fields vulnerable to algebraic cryptanalysis, or not? (Related: Is the sNTRUPrime/NTRULRPrime field vulnerable in a way that the cyclotomic rings of the Finalists are not?)

6) Are structured lattices*generally* vulnerable in a way unstructured lattices are not?

7) Are any of the remaining lattice KEMS overly patent-encumbered, particularly in a way that would dissuade free commercial adoption?

8) etc

While it may end up that very specific, low-order efficiency-comparisons of lattice schemes w.r.t. multi-target attack issues or parallelism or machine / memory modeling issues factor noticeably into the decision between this lattice scheme and that lattice scheme, these would only be a key factor in a decision-point for NIST (speaking for myself) if and only if the above non-performance issues end up essentially "all equal."

Let me know if I can answer any other questions!

Best,

--Daniel

(Again, speaking for myself)

Thanks for your comments! (Apologies for the length of my response ahead of time. =))

Let me explain my view of the core of the situation as follows: This memory / machine modeling issue (underlying this thread, and with a plethora of discussion in previous threads that motivated creating this discussion thread) is essentially specific to the case of the real-world, concrete security of the lattice-based candidates (mainly KEMs, but also certainly relevant to signatures as well). As this issue is entirely generic, it would naturally have implications for the non-lattice candidates as well. However, for each possible comparison case involving purely non-lattice schemes, it doesn't appear that machine / memory modeling is a critical issue regarding the decision-point of whether to standardize this or that scheme. (That is, we will or will not standardize some non-lattice scheme essentially independent of this issue.)

So, in Round 3, we (still) have a plethora of lattice schemes, for which this issue is

Please allow me to point out the following issues:

1) For the most part, the lattice schemes' practical efficiency has a logarithmic dependence on CoreSVP strength. That is, if you want to increase CoreSVP strength from 2^X to 2^{X+5}, say, then roughly real-world security would increase from 2^Y to 2^{Y+5}. Correspondingly, in order to meet this goal, the dimension, modulus, and error distribution may change slightly, and the overall performance of the system (in terms of PK/SK/CT size, and KeyGen/Enc/Dec timing) would increase by, say, ~5-6%. (This is in the context of Category 1 security, where the security parameter is noticeably close to 100.)

2) While most schemes can target their choice of CoreSVP strength, there is one caveat: For most lattice schemes, there are 'algebraic constraints' on the choice of dimension, module-rank, modulus, etc. These constraints imply that certain CoreSVP values may not be naturally achievable. For example, a scheme may be able to efficiently target, say, 124 CoreSVP strength and 130 CoreSVP strength, but the scheme may not naturally be able to target something in the range 125-129 without significant additional efficiency-cost. (Many submissions include a script that allows one to find such 'equilibrium points' in their parameter selections, and then choose among those.)

Therefore, the choice for each lattice-candidate in the 3rd Round will be something as follows:

a) Hit 128/129/130 CoreSVP strength (as their parameter options allow), and definitely meet the Category 1 security target -- at the cost of definitely over-shooting the minimum real-world security for Category 1.

b) Hit (something like) 122/123/124 CoreSVP strength (as their parameter options allow), and make a simple argument that real-world memory costing makes up the 4-6 bit difference.

c) Hit (something like) 116-120 CoreSVP strength (as their parameter options allow), and then

d) Hit something noticeably lower than the above thresholds, make a unique breakthrough argument, and hope that it can be formally vetted (by

Again, speaking for myself -- this is an attempt to convey information about my view of where people should target their tweaks for the 3rd Round. Historically (looking back at Round 1 and Round 2), some teams were very good about presenting exact CoreSVP strength values for each parameter set, and an even fewer number of teams were very good about arguing the exact details of why their selection truly met the Category 1 requirements. On the other hand, some teams merely described the nature of BKZ-like attacks against their underlying computational assumptions and simply deferred to the (now, somewhat outdated) "Estimate All The...!" paper/website.

Further, it's worth noting that the only "TLS-ready" (meaning, the 'closest to a drop-in replacement' for online protocols) signature schemes appear to be the lattice schemes: DILITHIUM and Falcon. At the same time, the lattice signature schemes tend to have presented parameters

So, here is the final point:

There are a variety of subtle, non-performance-related issues still to be resolved, which must take precedence. Here is a short list:

1) What is the relative effectiveness and cost of masking the lattice KEM candidates against side-channel attacks, like DPA/cold boot/template attacks/etc? (This requires masked implementations to be published, and then attacked or not, within the timespan of the 3rd Round..)

2) Does the side-channel situation change in the context of hardware implementations of these schemes?

4) Are there significant implementation challenges with one lattice scheme compared to another? How difficult is it for a 'reasonably-informed' engineer to produce safe, efficient code for this scheme or that?

5) Are lattices over cyclotomic number fields vulnerable to algebraic cryptanalysis, or not? (Related: Is the sNTRUPrime/NTRULRPrime field vulnerable in a way that the cyclotomic rings of the Finalists are not?)

6) Are structured lattices

7) Are any of the remaining lattice KEMS overly patent-encumbered, particularly in a way that would dissuade free commercial adoption?

8) etc

While it may end up that very specific, low-order efficiency-comparisons of lattice schemes w.r.t. multi-target attack issues or parallelism or machine / memory modeling issues factor noticeably into the decision between this lattice scheme and that lattice scheme, these would only be a key factor in a decision-point for NIST (speaking for myself) if and only if the above non-performance issues end up essentially "all equal."

Let me know if I can answer any other questions!

Best,

--Daniel

Aug 24, 2020, 9:06:33 PM8/24/20

to daniel.apon, D. J. Bernstein, pqc-...@list.nist.gov

On Mon, Aug 24, 2020 at 2:30 PM daniel.apon <danie...@nist.gov> wrote:

>

> Hi Watson,

> (Again, speaking for myself)

>

> Thanks for your comments! (Apologies for the length of my response ahead of time. =))

I appreciate its thoroughness!
>

> Hi Watson,

> (Again, speaking for myself)

>

> Thanks for your comments! (Apologies for the length of my response ahead of time. =))

> Further, it's worth noting that the only "TLS-ready" (meaning, the 'closest to a drop-in replacement' for online protocols) signature schemes appear to be the lattice schemes: DILITHIUM and Falcon. At the same time, the lattice signature schemes tend to have presented parameters with noticeably lower CoreSVP strengths than the lattice KEMs. This is somewhat of a Catch-22: As a process issue, NIST would strongly prefer to standardize a TLS-ready post-quantum signature scheme at the end of the 3rd Round, and so we need to give the lattice signature teams an opportunity to re-evaluate their parameter of their own volition, and then provide a sufficient period of time for public vetting. At the same time, we need to treat the lattice KEM schemes fairly.

a TLS-ready signature scheme.

As an occasional implementor and someone involved (albiet

peripherally) in the design of TLS 1.3 I feel this is a nonissue. TLS

worked with a RSA in a KEM like way in TLS 1.2, TLS 1.1, etc. It can

work that way in the future, there has been discussion of what is

necessary to do this because of the problems with signature schemes

already. We at $DAYJOB have deployed mechanisms that can use offline

signatures on short lived KEM if for some reason certificates cannot

be made with KEMs (but again, RSA certs were a thing). Furthermore

the timeline for authentication keys is very different from encryption

keys: data encrypted today can be read tomorrow, but authentication

today cannot be undone tomorrow. This mitigates in favor of not

feeling compelled to approve a high performance signing algorithm.

Verification time matters more: we have perennial problems with P384

for that reason.

I'd hate to see NIST enshrine a signature scheme prematurely or, even

worse, enshrine the use of SIGMA like protocols when KEM based ones

are more efficient in a post-quantum world.

Sincerely,

Watson Ladd

Aug 24, 2020, 11:09:03 PM8/24/20

to Watson Ladd, daniel.apon, pqc-...@list.nist.gov

Hi Watson,

> I'd hate to see NIST enshrine a signature scheme prematurely

I agree. And I would like to see PQ Signature Finalists to come up with new

Level 1 parameters with ~128 bits classical security.

But it would benefit the community to have a PQ signature scheme at the end of

Round 3 imo.

Below are some issues with your suggestion:

> TLS worked with a RSA in a KEM like way in TLS 1.2, TLS 1.1, etc. It can

> work that way in the future,

PQ KEMs cannot serve in place of RSAEncrypt for PKI certs and cert chains. The

verifier will not be able to decapsulate the ciphertest in the cert.

> there has been discussion of what is necessary to do this because of the

> problems with signature schemes already. We at $DAYJOB have deployed

> mechanisms that can use offline signatures on short lived KEM if for some

> reason certificates cannot be made with KEMs (but again, RSA certs were a

> thing). Furthermore

I am not sure every TLS usecase will want to pick potential mechanisms you

have in mind.

Also, I am not sure about the details of these mechanisms, but on a similar

note https://eprint.iacr.org/2020/534 proposes KEMTLS with static and

ephemeral KEM keys. KEMTLS introduces changes to TLS which can definitely not

be deployed trivially, but even then the cert chain still uses PQ signatures.

Additionally, let's not forget there are other long lived usecases that use

signatures and need PQ ones. One example is signed BIOS that lives without

being upgraded and would rather see PQ signatures standardized sooner than

later.

Panos

-----Original Message-----

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Watson

Ladd

Sent: Monday, August 24, 2020 9:06 PM

To: daniel.apon <danie...@nist.gov>

Cc: D. J. Bernstein <d...@cr.yp.to>; pqc-...@list.nist.gov

<pqc-...@list.nist.gov>

Subject: Re: [pqc-forum] Update on category 1 security

> I'd hate to see NIST enshrine a signature scheme prematurely

Level 1 parameters with ~128 bits classical security.

But it would benefit the community to have a PQ signature scheme at the end of

Round 3 imo.

Below are some issues with your suggestion:

> TLS worked with a RSA in a KEM like way in TLS 1.2, TLS 1.1, etc. It can

> work that way in the future,

verifier will not be able to decapsulate the ciphertest in the cert.

> there has been discussion of what is necessary to do this because of the

> problems with signature schemes already. We at $DAYJOB have deployed

> mechanisms that can use offline signatures on short lived KEM if for some

> reason certificates cannot be made with KEMs (but again, RSA certs were a

> thing). Furthermore

have in mind.

Also, I am not sure about the details of these mechanisms, but on a similar

note https://eprint.iacr.org/2020/534 proposes KEMTLS with static and

ephemeral KEM keys. KEMTLS introduces changes to TLS which can definitely not

be deployed trivially, but even then the cert chain still uses PQ signatures.

Additionally, let's not forget there are other long lived usecases that use

signatures and need PQ ones. One example is signed BIOS that lives without

being upgraded and would rather see PQ signatures standardized sooner than

later.

Panos

-----Original Message-----

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Watson

Ladd

Sent: Monday, August 24, 2020 9:06 PM

To: daniel.apon <danie...@nist.gov>

Cc: D. J. Bernstein <d...@cr.yp.to>; pqc-...@list.nist.gov

<pqc-...@list.nist.gov>

Subject: Re: [pqc-forum] Update on category 1 security

--

You received this message because you are subscribed to the Google Groups

"pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an

email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit

https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CACsn0cmf7da0WErxh7%3D0hXJiXYpBjcbAdp%2BGV3NhBc74RAyvZw%40mail.gmail.com.
You received this message because you are subscribed to the Google Groups

"pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an

email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit

Aug 25, 2020, 5:25:49 PM8/25/20

to Panos Kampanakis (pkampana), daniel.apon, pqc-...@list.nist.gov

On Mon, Aug 24, 2020, 11:08 PM Panos Kampanakis (pkampana) <pkam...@cisco.com> wrote:

Hi Watson,

> I'd hate to see NIST enshrine a signature scheme prematurely

I agree. And I would like to see PQ Signature Finalists to come up with new

Level 1 parameters with ~128 bits classical security.

But it would benefit the community to have a PQ signature scheme at the end of

Round 3 imo.

Nothing I said is against that.

Below are some issues with your suggestion:

> TLS worked with a RSA in a KEM like way in TLS 1.2, TLS 1.1, etc. It can

> work that way in the future,

PQ KEMs cannot serve in place of RSAEncrypt for PKI certs and cert chains. The

verifier will not be able to decapsulate the ciphertest in the cert.

Signatures on end-entity certs are the canonical offline case. The chain isn't signed per connnection. This changes the relative importance of signing and verification speed vs. the key in the end entity cert.

> there has been discussion of what is necessary to do this because of the

> problems with signature schemes already. We at $DAYJOB have deployed

> mechanisms that can use offline signatures on short lived KEM if for some

> reason certificates cannot be made with KEMs (but again, RSA certs were a

> thing). Furthermore

I am not sure every TLS usecase will want to pick potential mechanisms you

have in mind.

Also, I am not sure about the details of these mechanisms, but on a similar

note https://eprint.iacr.org/2020/534 proposes KEMTLS with static and

ephemeral KEM keys. KEMTLS introduces changes to TLS which can definitely not

be deployed trivially, but even then the cert chain still uses PQ signatures.

A new signature scheme is not trivial to deploy either, although slightly easier. We've seen substantial changes to TLS over the past 5 years get deployed. Why must TLS always use online signatures when KEMs could be faster? It doesn't!

Additionally, let's not forget there are other long lived usecases that use

signatures and need PQ ones. One example is signed BIOS that lives without

being upgraded and would rather see PQ signatures standardized sooner than

later.

These have tight demands on verification but not signing time, and require very high confidence. That's different from onlining signing in TLS. My comment was purely about the need for signatures for end-entiry authentication in TLS.

Aug 25, 2020, 11:38:41 PM8/25/20

to Watson Ladd, daniel.apon, pqc-...@list.nist.gov

I think I understand your point better now. You were not saying that NIST should not standardize a PQ Signature scheme for TLS. You were suggesting that NIST should not feel pressure to standardize an insecure PQ Signature scheme with fast signing for TLS because we can introduce KEMs for auth instead (similar to what draft-ietf-tls-semistatic-dh does for Diffie-Hellman).

__ __

I don’t think PQ KEMs in TLS are straightforward which I explain more below, but regardless of that I would rephrase your point to “NIST should not feel pressure to standardize any insecure scheme”.

__ __

> A new signature scheme is not trivial to deploy either, although slightly easier. We've seen substantial changes to TLS over the past 5 years get deployed. Why must TLS always use online signatures when KEMs could be faster? It doesn't!

__ __

I would argue that introducing PQ KEMs in the end entity cert is not as simple as with Diffie-Hellman in draft-ietf-tls-semistatic-dh. PQ KEMs in the leaf cert PK would automatically mean an extra round-trip (for the peer to get the PK before encapsulating something), an altered state machine and potentially a different security analysis for the protocol; all with doubtful benefit. The last paragraph of [1] Section VII-C talks about this briefly. Additionally, changes like the ones in [2] with KEMTLS are even more drastic imo.

__ __

I am pretty sure no one wants to jump into standardizing a drastically different or slower TLS handshake that uses KEMs for auth unless we definitely have to. [1] shows that there are a couple of options from the NIST Round 3 Signature candidates that could do satisfactorily in TLS (certs + SCTs + OCSP) (assuming the algorithms are secure of course).

__ __

Anyway, we can have this discussion in the IETF TLS WG in due time, no need to address it here.

__ __

Aug 26, 2020, 10:38:57 AM8/26/20

to Panos Kampanakis (pkampana), Watson Ladd, daniel.apon, pqc-...@list.nist.gov

On Tue, Aug 25, 2020 at 11:38 PM 'Panos Kampanakis (pkampana)' via

pqc-forum <pqc-...@list.nist.gov> wrote:

>

> I would argue that introducing PQ KEMs in the end entity cert is not as simple as with Diffie-Hellman in draft-ietf-tls-semistatic-dh. PQ KEMs in the leaf cert PK would automatically mean an extra round-trip (for the peer to get the PK before encapsulating something), an altered state machine and potentially a different security analysis for the protocol; all with doubtful benefit. The last paragraph of [1] Section VII-C talks about this briefly. Additionally, changes like the ones in [2] with KEMTLS are even more drastic imo.

>

> I am pretty sure no one wants to jump into standardizing a drastically different or slower TLS handshake that uses KEMs for auth unless we definitely have to. [1] shows that there are a couple of options from the NIST Round 3 Signature candidates that could do satisfactorily in TLS (certs + SCTs + OCSP) (assuming the algorithms are secure of course).

KEMTLS is certainly a different handshake than signatures+ephemeral
pqc-forum <pqc-...@list.nist.gov> wrote:

>

> I would argue that introducing PQ KEMs in the end entity cert is not as simple as with Diffie-Hellman in draft-ietf-tls-semistatic-dh. PQ KEMs in the leaf cert PK would automatically mean an extra round-trip (for the peer to get the PK before encapsulating something), an altered state machine and potentially a different security analysis for the protocol; all with doubtful benefit. The last paragraph of [1] Section VII-C talks about this briefly. Additionally, changes like the ones in [2] with KEMTLS are even more drastic imo.

>

> I am pretty sure no one wants to jump into standardizing a drastically different or slower TLS handshake that uses KEMs for auth unless we definitely have to. [1] shows that there are a couple of options from the NIST Round 3 Signature candidates that could do satisfactorily in TLS (certs + SCTs + OCSP) (assuming the algorithms are secure of course).

KEMs for TLS 1.3, but it is not dramatically slower nor does it

automatically mean an extra round trip.

In terms of performance, when using NTRU or Module-LWE/SIS schemes,

KEMTLS is faster than signatures+ephemeral KEMs (although this is

marginal, since NTRU and module-LWE schemes are already very fast),

and has smaller communication bandwidth (especially when switching

server authentication from Dilithium to Kyber). If one chooses to use

SIKE for authentication instead of a faster PQ signature, then yes, it

is slower, but it does have even smaller communication bandwidth, if

that is your priority.

In terms of number of round trips, in the standard

client-request/server-response scenario, KEMTLS allows the client to

send its request in exactly the same flight as would be the case in

TLS 1.3, and receive the response in the same flight as in TLS 1.3.

TLS 1.3 does permit the scenario where the server sends application

data a flight before this, in the flight containing its certificate.

Few applications seem to use this pattern; the SETTINGS frame in

HTTP/3 is one such example. KEMTLS does not fully support that

scenario: data sent at this time in KEMTLS could be kept confidential

against a passive adversary, but would not be authenticated like in

TLS 1.3. (See our just-posted revision which has a more extensive

discussion of the security and downgrade resilience properties of

KEMTLS keys and data. https://eprint.iacr.org/2020/534.pdf)

That we can do PQ authenticated key exchange using KEMs for end-entity

authentication rather than signatures does not mean there is no need

for PQ signatures. And indeed a design like KEMTLS is a bigger change

than just substituting PQ signatures and KEMs into signed+DH

protocols. But there are concrete benefits, and we'll be making

changes anyway to add PQ algorithms, so it is worth keeping on the

table for now.

Douglas

Dec 18, 2020, 5:06:51 PM12/18/20

to Perlner, Ray A. (Fed), pqc-forum

Dear all and NIST team,

On slide 18 of Ray’s talk (“Cost Models”), it is assumed that an attacker has a budget of $2^64 over a period of 500 years. To calculate the memory budget, this becomes an annual budget of $2^64/500 that leads to having access to up to
2^96.5 bits of HDD memory over the period of 500 years.

__ __

However, the analysis of some (if not most) attacks in the literature assumes access to the necessary hardware from the very start, when launching the attack (otherwise the time to carry out an attack successfully would need to take into
the addition/upgrade of hardware for CPU and memory as time goes by).

__ __

If we fix the goal of breaking AES128 to 500 years, I estimate that one needs

__ __

2^128 * (12.7 * 10^-9 sec) / (500 years * 365 * 24 * 3600 sec/year) = 2^67.89 AES engines,

__ __

and this number of engines costs about 2^67.89 * 11590 GEs * $6.57*10^-9/GE = $2^54.21, assuming that an AES computation runs in 12.7nsec, occupies 11,590 gate equivalents (GEs) and that a GE costs 6.57*10^-3 microcents each [1]. Therefore,
an attacker would need $2^54.21 to launch the attack ($2^64/500 per year was actually not a bad approximation if we assume that’s the starting budget at day 1).

__ __

Now let’s look at the cost of attacking some other scheme X with this initial budget ($2^54.21). For simplicity, let’s assume that for breaking X half of the money goes to get computing power and half of the money goes to memory resources
(this of course depends on the scheme and the attack). In this case, we get at most

__ __

2^53.21 * 2^47 bits / $400 = 2^91.6 bits at launch time (compare to the 2^96.5 bits on slide 18). So there might be (at least) a 5-bit difference here, and this appears to affect all the memory estimates on slide 18.

__ __

OTOH, (back to the AES analysis) if we look at the energy costs for the 500-year run, I get

__ __

2^128 * 2.02*10^-6 kW *(12.7 * 10^-9 sec)/(3600 sec/hour) * 0.10 cents/kWh = $2^67.7, which exceeds the total budget of $2^64. This doesn’t include other costs that NIST takes into account in the analysis (e.g., the cost of replacing HDD
hardware every 5 years, and the energy cost of the memory units).

How is NIST calculating the energy cost for AES128 exactly? It’s somewhat unclear by just looking at slide 17.

__ __

(*) The 2.02mW figure for AES was provided by Rei Ueno, based on their implementation [2].

__ __

Apparently, some differences in all these calculations can be due to the numbers we use for AES (actual AES results for area, timing and energy from the implementation in [2] versus NIST’s AES gate complexity of 2^143).

__ __

Overall, I don’t see huge differences between NIST’s numbers and our analysis ([1] presents an analysis of this nature focused on SIKE). But maybe the relatively small differences are still something to think about, given that only a few
bits might make the difference between a parameter set matching a particular security level or not. For some schemes slight differences in the assumptions can change the results of the analysis (this is especially true for attacks that require a large shared
memory and whose costs rely heavily on the CPU:memory cost ratio and the budget that are assumed).

__ __

Any comments?

__ __

Best,

Patrick

__ __

[1] P. Longa, W. Wang and J. Szefer. “The Cost to Break SIKE: A Comparative Hardware-Based Analysis with AES and SHA-3”, 2020.
https://eprint.iacr.org/2020/1457

[2] R. Ueno, N. Homma, S. Morioka, N. Miura, K. Matsuda, M. Nagata, S. Bhasin, Y. Mathieu, T. Graba, and J.-L. Danger.
“High throughput/gate AES hardware architectures based on datapath compression”. IEEE Trans. Computers, 69(4):534–548, 2020.

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to
pqc-forum+...@list.nist.gov.

To view this discussion on the web visit
https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/SA0PR09MB7193FB1D6B1D59091865C9549C5F0%40SA0PR09MB7193.namprd09.prod.outlook.com.

Dec 21, 2020, 12:49:00 PM12/21/20

to Patrick Longa, pqc-forum

Hi Patrick.

__ __

Thanks for checking my calculations. Overall it seems like we’re getting fairly similar numbers. I’m less convinced that a bit or two really matters here, since what we’re actually worried about is technology a couple of orders of magnitude
better than current technology – i.e. technology that might make breaking a category 1 scheme close to feasible. I think we can agree that no one is seriously worried that their keys are going to be cryptanalyzed after 500 years if someone just manages the
simple task of blanketing the entire planet, land and sea, with solar panels. Given that we’re really worried about hypothetical future technology, it seems entirely plausible that the cost of computation and the cost of memory could fall by different amounts.
Thus I see this exercise mostly as a sanity check to see whether an amount of memory, claimed to be prohibitive for the attacks relevant to a given security strength category, is actually prohibitive.

__ __

On specific points: The assumption that all hardware must be purchased in the first year of an attack lasting 500 years seems really weird to me. Also, as you said, the exact portion of the budget which should be allocated to memory as
opposed to computation need not be 50%. This doesn’t make as big a difference as one might think, though, since the assumption I used to do my calculation was that hard drives would wear out and need to be replaced after 5 years. Additionally, re-running the
numbers, I got something closer to 2^95.5 when I multiplied out the equation on slide 18, so it seems there was a typo there. You also asked about the calculation on slide 17: This was based on the specs for the bitcoin mining platform referenced earlier in
the slide and the assumption that a “hash” was a double-SHA2 operation, which was assumed to be about 2^19 gates. This gives:

__ __

2^143 gates * 1 hash / 2^19 gates / ( 1.1x10^14 hash / s) * 3.25 kW * $0.1/(kW h) * (1 h / 3600s) = $2^63.92

__ __

Finally, I should note that while the small differences in our estimates for things like the energy consumption of a single AES computation on optimized hardware don’t make very much difference, what does make a sizable difference is the
methodology for how one deals with the fact that category 1 type attacks are several orders of magnitude beyond both the budget and timeline of real world adversaries, at least with existing technology. For example, the approach in the eprint paper you cited:
https://eprint.iacr.org/2020/1457 is to fix the adversary’s hardware budget at something basically on a human scale (a million to a billion dollars) while allowing attack timelines to stretch as long as they need to in order to compensate, even if that
number turns out to be unfathomably large. For reference, the shortest attack contemplated by this paper was over 250,000,000 years long, or about 1000 times the amount of time anatomically modern humans have existed. The problem with doing things this way
becomes evident when you look at the way the paper combines this model with extrapolations of technological progress. The paper extrapolates technological progress out 20 years, to 2040, or about a ten-millionth the length of the shortest attack contemplated
by the paper. This brings the timeline for a billion dollar AES128 attack down from 8 billion years to 250 million years. Obviously the attacker would be better off waiting for technology to improve. (Also, if the adversary had invested the billion dollars
in the stock market rather than rushing out to buy hardware, assuming historical rates of return, he would have something like a 4 billion dollar hardware budget in 2040 rather than 1 billion.) But, I see no reason to think 2040 would be an optimal time to
start buying hardware either. Most likely, it would be optimal for the attacker to wait for something like 80-100 years if technological improvements and investment returns continue at the same exponential rate, or longer if they slow down, resulting in an
attack that takes decades rather than millions of years. This can significantly change the comparative cost of memory-intensive attacks like the classical attacks on SIKE. The paper says SIKE 377 would take 2^7 times as long to attack as AES 128 with technology
frozen in 2020, but only 2^4 times as long with technology frozen in 2040. If we blindly extrapolate these exponential trends to 2120, we’d find the time to attack AES with technology frozen at that point with a billion dollar budget would be something like
250 years, while the time to attack SIKE 377 would be something like 1 year. (Note: This is a back of the envelope calculation based on exponents rounded to the nearest whole number. I expect using more precise numbers from the paper will result in slightly
different numbers, but I don’t expect it to change the overall conclusion that, barring cryptanalysis improvements, SIKE 377 is likely to be within the reach of an adversary with both a reasonable budget and timeline before AES128.)

__ __

Best,

Ray

Dec 21, 2020, 2:27:49 PM12/21/20

to ray.p...@nist.gov, pqc-...@list.nist.gov

Hi Ray,

Thanks for the reply.

__ __

> The assumption that all hardware must be purchased in the first year of an attack lasting 500 years seems really weird to me.

__ __

What I meant was that the hw available on day 1 should be the one used to estimate the time to run the attack. I agree with the idea of taking into account the cost of replacing hw that breaks as time goes by, but if you want to consider
the possibility of “upgrades” (future faster hw, more memory, etc.) then the analysis gets much more complicated.

__ __

> Finally, I should note that while the small differences in our estimates for things like the energy consumption of a single AES computation

> on optimized hardware don’t make very much difference, what does make a sizable difference is the methodology for how one deals with

> the fact that category 1 type attacks are several orders of magnitude beyond both the budget and timeline of real world adversaries, at least

> with existing technology.

__ __

Yes, this is what I meant by “for some schemes slight differences in the assumptions can change the results of the analysis”. Given the divergence of results depending on the assumptions for a scenario that is purely hypothetical, the main
question is then on how to decide what those assumptions are.

In our paper, we decided to try something that we think is (slightly) closer to reality than assuming an unrealistic budget with an unrealistic timeline. Basically, the convention was to use “somewhat manageable” budgets (we have evaluated
from millions to up to trillions of dollars without too much change in the results) and then determine the time to break AES and SIKE, which gives unrealistic timelines as expected. Of course one can turn this around and decide to assume a reasonably-human
timeline and then determine the cost of cryptanalysis.

__ __

> Obviously the attacker would be better off waiting for technology to improve…. If we blindly extrapolate these exponential trends to 2120, …

__ __

Of course. But then how is that relevant to determine the strength of AES and other algorithms today or during the next few decades?

It should be irrelevant if SIKEp377 is believed to be weaker than AES128 in year 2120 (is it reasonable to try to do a forecast that far in the future anyway?).

__ __

The larger issue boils down to the need of reasonably fair metrics for attacks that require very large shared memory. Should teams avoid more realistic models that use the cost of technology to analyze attacks or should they simplify the
analysis with potentially imprecise theoretical costs (e.g. using a square root cost for memory accesses)? The risk is to penalize otherwise strong algorithms that have a strong cryptanalytic profile (whose best attacks are forced to use huge amounts of shared
memory versus other schemes that fall to attacks that require negligible memory).

__ __

Best,

Patrick

Dec 21, 2020, 3:44:09 PM12/21/20

to Patrick Longa, pqc-forum

Hi Patrick

__ __

I take it as axiomatic that an attack which begins in 100 years and ends in 101 is more relevant to practical security than one that begins in 20 years and ends 250 million years from now. I could see you arguing that what we’re really
worried about are scenarios where an attack might finish even sooner than 101 years from now, and that’s fair. The only scenarios I can come up with involve a larger starting budget, hijacking computation resources without purchasing them, or cryptanalysis.
I would expect the first two scenarios to behave more like my 101 year scenario than your 250 million year scenario in terms of the relative costs of attacking AES128 and SIKE377. Cryptanalysis is probably the biggest concern, but it’s hard to quantify the
relative likelihood of a nontrivial attack on SIKE and AES.

Dec 21, 2020, 6:10:15 PM12/21/20

to ray.p...@nist.gov, pqc-...@list.nist.gov

Hi Ray,

It seems the discussion turns philosophical at this point
😊. The question for me is not about what scenarios we should worry about the most (because it’s clear that we assume level 1 is infeasible with current technological trends for several decades). From my viewpoint, it is more about determining (relative)
security fairly, and for this goal it’s more relevant to evaluate strength as assessed today (or in the next few years), not in 100 years.

__ __

I suppose we agree to disagree.

__ __

> The larger issue boils down to the need of reasonably fair metrics for attacks that require very large shared memory. Should teams avoid

> more realistic models that use the cost of technology to analyze attacks or should they simplify the analysis with potentially imprecise

> theoretical costs (e.g. using a square root cost for memory accesses)? The risk is to penalize otherwise strong algorithms that have a strong

> cryptanalytic profile (whose best attacks are forced to use huge amounts of shared memory versus other schemes that fall to attacks that

> require negligible memory).

__ __

Do you have any additional comments on this aspect, beyond what NIST’s been saying on this forum?

__ __

All the best,

Patrick

To view this discussion on the web visit
https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM8PR09MB637497CBA6692241BF2152479CC00%40DM8PR09MB6374.namprd09.prod.outlook.com.

Reply all

Reply to author

Forward

0 new messages