360 views

Skip to first unread message

Oct 14, 2017, 7:43:06 AM10/14/17

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

Some recent proposals for post-quantum KEMs, starting from plausible

one-wayness assumptions, have falsely claimed proofs of "QROM" security.

The reason I'm saying "falsely" is that the theorems are quantitatively

so weak as to be vacuous for the proposed parameters---the proposals

would have to switch to larger parameters for the theorems to reach

meaningful security levels.

one-wayness assumptions, have falsely claimed proofs of "QROM" security.

The reason I'm saying "falsely" is that the theorems are quantitatively

so weak as to be vacuous for the proposed parameters---the proposals

would have to switch to larger parameters for the theorems to reach

meaningful security levels.

Given this background, it's interesting to see a new paper

https://eprint.iacr.org/2017/1005

with the first claim of a _tight_ QROM proof for a reasonable-looking

KEM starting from plausible assumptions. From an initial skim it looks

like you have to do all of the following to invoke the paper:

* Use a deterministic one-way function. (For example, in the

terminology of the NTRU Prime paper, "Rounded NTRU" works but

"Noisy NTRU" doesn't. If you want to add random errors then those

need to be _inputs_ to the one-way function.)

* Eliminate decryption failures for the one-way function.

* Eliminate decryption failures for the KEM as follows: return

PRF(secret,ciphertext) if trapdoor decryption fails or reencryption

produces a different ciphertext. (Of course the subsequent protocol

will then have a MAC failure.)

* Security assumption: Keys are indistinguishable from random

elements of the key space. (This worries me---it has been

articulated before but not studied very much.)

* Security assumption: The set of ciphertexts for a real key is a

negligible fraction of the ciphertext space. (The paper says

something slightly different but I think this is equivalent.)

* Security assumption: Ciphertexts for random elements of the key

space are indistiguishable from random elements of the ciphertext

space.

Of course it would be good to figure out which assumptions are really

needed, and to check the correctness of the proof.

I _don't_ see key confirmation (sending a separate hash of the one-way

input as part of the ciphertext); hashing the public key into the

session key; or hashing the ciphertext into the session key (in the

success case). All of these feel like they should have generic proofs

that they don't hurt security, but the details should be checked

carefully, especially in the QROM context.

Key confirmation is often miscredited to Targhi and Unruh. The TU proof

isn't very useful (it's quantitatively weak; also, as discussed in

https://eprint.iacr.org/2017/667, it requires the hash to be at least as

long as the one-way input) but this doesn't mean that key confirmation

is a bad idea. Key confirmation is easy to audit (anyone who produces

the hash must have known the input) and avoids some pre-quantum

assumptions (see Dent's tight Theorem 8 from 2003).

Hashing the public key (or, shorter, a collision-resistant hash of the

public key) into the session key could help against multi-user attacks.

Hashing the ciphertext into the session key is something that Kyber does

for unified constant-time handling of the success and failure cases:

decapsulation always produces H(something,ciphertext), where "something"

is the one-way input (in the success case) or a separate secret (in the

failure case).

On a related note, several people have been discussing the question of

how to deal with implementor screwups such as mishandling crypto_kem_dec

return values or not bothering to implement reencryption. Eliminating

decryption failures for the KEM deals with the return-value issue but

doesn't deal with implementors who don't reencrypt.

One way to force implementors to implement at least part of the

reencryption process is to include intermediate results of the one-way

function in the hash. For example, if the ciphertext c is supposed to be

round(Ar) where r is the one-way input, then defining a session key as

H(r,Ar,c) forces the implementor to recompute Ar, although this still

doesn't check that c is the same as round(Ar).

---Dan

Oct 15, 2017, 2:39:01 PM10/15/17

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

This seems to imply consistency over completeness, correct?

A tight reduction would necessarily require consistency, yet proposals of an "LWE-Complete" primitive given by Regev frames the scheme in terms of mathematical completeness.

My question is where the tradeoff between the two occur.

This issue could largely be tangential to our post-quantum project, but it seems strong security guarantees would require consistency over completeness.? Then again, I could be mistaken in my interpretation of this discussion.

- I M

On Oct 14, 2017 6:43 AM, "D. J. Bernstein" <djb at cr.yp.to> wrote:

>

> Some recent proposals for post-quantum KEMs, starting from plausible

> one-wayness assumptions, have falsely claimed proofs of "QROM" security.

> The reason I'm saying "falsely" is that the theorems are quantitatively

> so weak as to be vacuous for the proposed parameters---the proposals

> would have to switch to larger parameters for the theorems to reach

> meaningful security levels.

>

> Given this background, it's interesting to see a new paper

>

> ?? https://eprint.iacr.org/2017/1005

>

> with the first claim of a _tight_ QROM proof for a reasonable-looking

> KEM starting from plausible assumptions. From an initial skim it looks

> like you have to do all of the following to invoke the paper:

>

> ?? * Use a deterministic one-way function. (For example, in the

> ???? terminology of the NTRU Prime paper, "Rounded NTRU" works but

> ???? "Noisy NTRU" doesn't. If you want to add random errors then those

> ???? need to be _inputs_ to the one-way function.)

> ??

> ?? * Eliminate decryption failures for the one-way function.

>

> ?? * Eliminate decryption failures for the KEM as follows: return

> ???? PRF(secret,ciphertext) if trapdoor decryption fails or reencryption

> ???? produces a different ciphertext. (Of course the subsequent protocol

> ???? will then have a MAC failure.)

>

> ?? * Security assumption: Keys are indistinguishable from random

> ???? elements of the key space. (This worries me---it has been

> ???? articulated before but not studied very much.)

>

> ?? * Security assumption: The set of ciphertexts for a real key is a

> ???? negligible fraction of the ciphertext space. (The paper says

> ???? something slightly different but I think this is equivalent.)

>

> ?? * Security assumption: Ciphertexts for random elements of the key

> ???? space are indistiguishable from random elements of the ciphertext

> ???? space.

> _______________________________________________

> pqc-forum mailing list

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

> (_internal_name)s

>

Nov 20, 2017, 8:30:43 AM11/20/17

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

There's another new paper

https://eprint.iacr.org/2017/1096

from Jian--Zhang--Chen--Wang--Ma (JZCWM) regarding QROM tightness.

Apparently this was submitted two days after

https://eprint.iacr.org/2017/1005

appeared from Saito--Xagawa--Yamakawa (SXY), but for some reason the

JZCWM paper took almost a month to be posted. This is a particularly

unfortunate delay given how close the NIST submission deadline is and

given how many submissions will presumably be using CCA2 conversions.

(I hope this wasn't eprint imposing a secret review process---something

that has happened in the past, often creating big delays or even papers

not being allowed onto eprint.)

Anyway, the basic message of the JZCWM paper seems to be that attacks on

various systems can't succeed with probability above essentially

q*sqrt(delta)+q*sqrt(eps),

where delta is the probability of decryption failures, and eps is the

success probability of lower-level attacks such as inversion attacks.

This is still quite loose---the bound doesn't even start to say anything

until both delta and eps are pushed below 1/q^2; people choosing

parameters almost never think about such low-probability attacks---but

it's a big step forward compared to previous theorems.

The SXY results are much tighter but put much heavier constraints on the

cryptosystem. Internally, there seems to be an overlap between the SXY

techniques and the JZCWM techniques, and I think that factoring the

theorems into composable pieces---with a clear statement of which pieces

lose tightness---will help clarify what's going on. There was already

serious effort in this direction in

https://eprint.iacr.org/2017/604

(including a "major revision" in September "with many bug fixes and new

transformations") but clearly more work has to be done to integrate the

SXY and JZCWM ideas into one big picture, and to make sure that

everything is checked.

In the end it seems highly unlikely that there will be a perfect match

between

* the set of CCA2 conversions used in submissions and

* the CCA2 conversions that the theory ends up concluding are best.

I wonder what effect this will have on the post-quantum competition. In

general, a submission that has made a suboptimal (or breakable!) choice

of CCA2 conversion will easily be able to switch to something better,

and what will really matter for users is the strength of the underlying

one-way function---but I guess we'll see quite a bit of sniping at the

preliminary choices of CCA2 conversions.

---Dan

https://eprint.iacr.org/2017/1096

from Jian--Zhang--Chen--Wang--Ma (JZCWM) regarding QROM tightness.

Apparently this was submitted two days after

https://eprint.iacr.org/2017/1005

appeared from Saito--Xagawa--Yamakawa (SXY), but for some reason the

JZCWM paper took almost a month to be posted. This is a particularly

unfortunate delay given how close the NIST submission deadline is and

given how many submissions will presumably be using CCA2 conversions.

(I hope this wasn't eprint imposing a secret review process---something

that has happened in the past, often creating big delays or even papers

not being allowed onto eprint.)

Anyway, the basic message of the JZCWM paper seems to be that attacks on

various systems can't succeed with probability above essentially

q*sqrt(delta)+q*sqrt(eps),

where delta is the probability of decryption failures, and eps is the

success probability of lower-level attacks such as inversion attacks.

This is still quite loose---the bound doesn't even start to say anything

until both delta and eps are pushed below 1/q^2; people choosing

parameters almost never think about such low-probability attacks---but

it's a big step forward compared to previous theorems.

The SXY results are much tighter but put much heavier constraints on the

cryptosystem. Internally, there seems to be an overlap between the SXY

techniques and the JZCWM techniques, and I think that factoring the

theorems into composable pieces---with a clear statement of which pieces

lose tightness---will help clarify what's going on. There was already

serious effort in this direction in

https://eprint.iacr.org/2017/604

(including a "major revision" in September "with many bug fixes and new

transformations") but clearly more work has to be done to integrate the

SXY and JZCWM ideas into one big picture, and to make sure that

everything is checked.

In the end it seems highly unlikely that there will be a perfect match

between

* the set of CCA2 conversions used in submissions and

* the CCA2 conversions that the theory ends up concluding are best.

I wonder what effect this will have on the post-quantum competition. In

general, a submission that has made a suboptimal (or breakable!) choice

of CCA2 conversion will easily be able to switch to something better,

and what will really matter for users is the strength of the underlying

one-way function---but I guess we'll see quite a bit of sniping at the

preliminary choices of CCA2 conversions.

---Dan

Nov 20, 2017, 10:15:31 AM11/20/17

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

Thanks Dan for raising the matter.

Best,

Indeed, I agree that, given the variety of ROM/QROM conversions appearing recently and within a very short timeframe, and given that a perfect matching seems hard, we will see several different approaches used among the proposals.

My idea is that submitters should not worry too much about which conversion is used at this stage (unless it is weak/breakable, of course) and, exactly as you say, what matters the most is the inherent strength of the underlying one-way function.

I hope NIST shares this point of view.

Best,

Edoardo

--

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.

Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.

Nov 20, 2017, 10:38:24 AM11/20/17

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

>*My idea is that submitters should not worry too much about which conversion is used at this stage (unless it is weak/breakable, of course) and, exactly as you say, what matters the most is the inherent strength of the underlying one-way
function.*

__ __

__ __

That certainly seems reasonable to us. These type of issues could be addressed later on in the process when submissions are allowed minor changes (tweaks).

__ __

Dustin

Nov 20, 2017, 4:40:43 PM11/20/17

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

The Chrysalis team was unable to produce a satisfactory one way function, and the resulting decryption errors were too high.

Instead, we'll be moving forward to implement the cryptanalytic application of the Riemann primitive using IBM's QISKIT. Given the intersections this has with QROM developments, we appreciate you sharing these articles.

At PQCrypto '17 I know some expressed a belief that oracle models were sufficient, but we still believe the Riemann primitive may have some utility.

It will be interesting to watch these bounds be refined over time.

--

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+unsubscribe@list.nist.gov.

Nov 23, 2017, 4:22:46 AM11/23/17

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

I'd like to inquire where NIST draws the line between "substantial" changes, and changes that don't require justification.

I know the response in the past has been that a change from a Gaussian distribution to something like Hamming weights, for lattice based cryptography, would be seen as substantial.

What is NIST's position regarding CCA2 conversions based on "breakable" parameters and what can be regarded as an "easy" transition to something more secure?

If the underlying one-way function is the final measure, will it be more in line with what Chris Peikert says is the only OWF (lattice), or will some measure be drawn for all OWF in submissions?

Thank you.

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

Nov 24, 2017, 5:13:23 AM11/24/17

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

First I apologize if this is not the right place to make the following comment on this post.

QROM (quantum random oracle) is a very important area to investigate.

But for this NIST effort, I think that QROM proof should not be a requirement.

In many cases, traditional ROM proof should be sufficient if the random oracle

query output length is appropriately chosen. My justification is as follows:

In the NIST CFP, it seems that security categories are based on AES/SHA2/SHA3

security levels in quantum world. These categories are based on the following assumption:

ASSUMPTION: the best available attacks are: Shor-algorithm (may not be related to AES/SHA though)

and Grover-style algorithms (or perhaps we should also include Deutsch-style algorithms).

------If this assumption is not valid (e.g., there are other efficient attacks), then these

categories in NIST CFP should be revised

Justification for no QROM requirement:

Yes, the adversary can evaluate the hash function on super-positions. But according

to quantum mechanics, the random oracle does not need to evaluate to the same output

on a given input for different queries (thus history-free is not needed). It is only required

that the random oracle output should be consistent with the adversary observation (measurement).

Based on the ASSUMPTION, if the random oracle query output is longer than the hash function output,

the adversary essentially only learns two potential outputs per random oracle query

(that is, pre-image or collision). Or if Deutch algorithm is used, the adversary learns

some collective information about the random oracle, but we may assume that is

not useful for the adversary, otherwise, this kind of information may be useful for attacking

AES/SHA2 also? Since we are assuming AES/SHA2/SHA3 is secure against

these attacks, we may assume that if the propose protocol is secure in the traditional

RO model proof, it should be considered as secure in the quantum world.

Furthermore, we should also think about the MAXDEPTH (2^40 to 2^64) in NIST CFP.

So if the adversary needs to learn more than one output information from a random oracle access,

the attack must have a circuit with MAXDEPTH < 2^64. Otherwise, the QROM has no difference

from traditional ROM.

The current artificial separation result for QROM and ROM is based on the

Grover-style collision attacks. Furthermore, the "history-free reduction" is sufficient

for the QROM proof. But it should never be interpreted as a necessary requirement.

Yongge

Nov 24, 2017, 5:49:23 AM11/24/17

to Yongge Wang, pqc-...@list.nist.gov

Apologies if I'm misunderstanding you, but are you essentially saying the assumptions are ones of scalability? For example, the trade-off between the oracle and MAXDEPTH?

I agree QROM research is important, mostly because I don't think we can completely see which algorithms may be created as this technology advances.

I'd be happy to continue this conversion outside of this forum.

--

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+unsubscribe@list.nist.gov.

Nov 24, 2017, 3:04:09 PM11/24/17

to Yongge Wang, pqc-...@list.nist.gov

By my reading, there is no requirement for a proof at all, only a security analysis with

respect to known attacks, which would include Grover and Shor. Furthermore, NIST

has said that they expect people to change the CCA transform once the science on

that is more certain. But it’d be nice to have evaluations of those CCA transforms so

that we might get them right in the submission, and not have to change them.

QROM proofs are a component of that evaluation. They're useful to increase our

confidence that we didn’t miss a subtle attack on those transforms.

— Mike

--

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.

Nov 24, 2017, 3:07:10 PM11/24/17

to Mike Hamburg, Yongge Wang, pqc-...@list.nist.gov

I believe NIST has said as much about security proofs several months ago. They are strictly optional if I remember correctly.

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

--

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

Dec 1, 2017, 7:06:59 PM12/1/17

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

> The current artificial separation result for QROM and ROM

How hard is it to find a preimage for an n-bit hash output? For example,
suppose a signature scheme signs an n-bit hash H(R,M) where M is the

message and R is chosen randomly by the signer. How hard is it for the

attacker to find another message M' with H(R,M') = H(R,M)?

Of course in post-quantum cryptography we say that the answer is around

2^(n/2) hash computations (if H isn't horribly broken), because that's

how long Grover's algorithm takes.

ROM, on the other hand, says that finding a preimage takes around 2^n

hash computations. That's quite a different security level!

Is this because ROM is doing a careful evaluation of the overheads and

non-parallelizability of Grover's algorithm, and concluding that

Grover's algorithm is useless? No. It's because the definition of ROM

attacks doesn't allow superposition queries to H.

If the literature makes the separation between ROM and QROM sound

artificial then someone has done a very bad job of explaining QROM.

> But for this NIST effort, I think that QROM proof should not be a

> requirement.

attackers will certainly be able to carry out superposition queries to

public hash functions.

A more difficult question is how proofs will be evaluated. For example,

how much extra value is there in a proof regarding QROM attacks,

compared to a proof regarding the narrower class of ROM attacks?

As another example, I presume that there will be quite a few submissions

that

(1) advertise the performance of a proposed parameter set P_1 and

(2) advertise proofs that, upon closer inspection, don't say anything

about P_1---they say something about a much larger parameter set,

say P_50, that wasn't actually proposed.

Loose QROM proofs are one source of this problem but there are many

other sources. For example, https://eprint.iacr.org/2016/360.pdf reports

an amazing 2^504 looseness factor in Regev's LWE reduction (for common

LWE sizes), and I haven't noticed any papers disputing this or showing a

smaller number.

How are such proofs going to be treated? Here are three possibilities:

* Fall for the bait and switch: treat the irrelevant proof about P_50

as adding assurance to P_1, even though the proof says nothing

about P_1. (This is a common reaction, which presumably is why this

sort of bait and switch keeps happening.)

* Ignore the irrelevant proofs.

* Penalize the submissions for the bait and switch---for mislabeling

irrelevant proofs as relevant proofs, creating a distraction in the

analysis of the security of what was actually proposed.

I don't see where NIST addressed this important issue in the call:

Submitters are not required to provide a proof of security, although

such proofs will be considered if they are available. ... While

security proofs are generally based on unproven assumptions, they can

often rule out common classes of attacks or relate the security of a

new scheme to an older and better studied computational problem.

No matter how solid the underlying assumption is, and no matter how

broad the analyzed attack class is, a proof that requires parameter set

P_50 is failing to address the risk of an attack against P_1.

---Dan

Dec 2, 2017, 12:21:37 AM12/2/17

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

> Of course in post-quantum cryptography we say that the answer is around

> 2^(n/2) hash computations (if H isn't horribly broken), because that's

> how long Grover's algorithm takes.

> 2^(n/2) hash computations (if H isn't horribly broken), because that's

> how long Grover's algorithm takes.

agreed for this claim and other claims in the post.

I am not a quantum mechanics guy. so my comments could make no sense at all.

my understanding/comment was based on the following interpretation (could be completely wrong):

In the book (let us call this book [NC]) "Nielsen, M.A., and Chuang, I.. Quantum computation and quantum information."

it has a crude estimates for decoherence time and unitary transformation time.

From the [NC Figure 7.1], it seems that "Ion Trap" has the best potential

for quantum circuit depth. That is, the decoherence time is 10^-1 seconds

and one unitary transformation takes 10^-14 seconds. Thus the best quantum

computer one can build could have a quantum circuit depth 10^13 (approximately 2^43).

this matches well with the NIST CFP MAXDEPTH (2^40 to 2^64).

I am not sure whether this is a theoretical limit or it is just an engineering problem.

Let us assume that the limit for a quantum computer circuit depth is at most 2^64 (could be

a wrong assumption due to my limited knowledge in quantum mechanics).

If the random oracle (or hash function) has an output length of at least 256-bits such as SHA-512,

then Grover's algorithm is useless for QROM to learn any essential information since no collision

could be found by any quantum computer. In this way, QROM seems to have limited advantage

over ROM in the NIST recommended security categories.

Again, I am not trying to say QROM is not good. I just try to understand the importance

of QROM in these security categories in NIST CFP.

Secondly, no matter we use QROM or ROM model for proof, the reduction complexity

could be interpreted in various ways in practice. For example, based on ROM proof for

RSA-OAEP, one needs a 5000-bit RSA modulus to achieve 80 bits of security. But in practice,

one may just use RSA-OAEP with a 1024-bit modulus for 80 bits of security. If we strictly

follow the ROM proof and use 5000-bit RSA modulus to achieve 80 bits security, I doubt whether

we would really use RSA for PKI systems.

(see the comments at the end of section 4.1 in the following paper:

Koblitz, N. and A. J. Menezes. Another look at "provable security", J. Cryptology 20.1 (2007): 3-37.

thanks and apology if the comments make no sense.

Yongge

Dec 2, 2017, 12:47:14 AM12/2/17

to Yongge Wang, pqc-...@list.nist.gov

Does this text also potentiate for applications of "time crystals" in addressing decoherence? The application may be a few years away, but advances in addressing decoherence times should be expected in my humble opinion.

Also, regarding parallelism and Grover's algorithm, I'd hope that the concept of multiple 50 qubit systems updating a cloud structure, IBM's commercial qc and Watson for example, is thoroughly considered.

Dec 2, 2017, 3:13:32 AM12/2/17

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

> As another example, I presume that there will be quite a few submissions

> that

>

> (1) advertise the performance of a proposed parameter set P_1 and

>

> (2) advertise proofs that, upon closer inspection, don't say anything

> about P_1---they say something about a much larger parameter set,

> say P_50, that wasn't actually proposed.

>

> Loose QROM proofs are one source of this problem but there are many

> other sources. For example, https://eprint.iacr.org/2016/360.pdf reports

> an amazing 2^504 looseness factor in Regev's LWE reduction (for common

> LWE sizes), and I haven't noticed any papers disputing this or showing a

> smaller number.

>

> How are such proofs going to be treated? Here are three possibilities:

>

> * Fall for the bait and switch: treat the irrelevant proof about P_50

> as adding assurance to P_1, even though the proof says nothing

> about P_1. (This is a common reaction, which presumably is why this

> sort of bait and switch keeps happening.)

If anyone is inclined to take at face value the vague accusation that
> that

>

> (1) advertise the performance of a proposed parameter set P_1 and

>

> (2) advertise proofs that, upon closer inspection, don't say anything

> about P_1---they say something about a much larger parameter set,

> say P_50, that wasn't actually proposed.

>

> Loose QROM proofs are one source of this problem but there are many

> other sources. For example, https://eprint.iacr.org/2016/360.pdf reports

> an amazing 2^504 looseness factor in Regev's LWE reduction (for common

> LWE sizes), and I haven't noticed any papers disputing this or showing a

> smaller number.

>

> How are such proofs going to be treated? Here are three possibilities:

>

> * Fall for the bait and switch: treat the irrelevant proof about P_50

> as adding assurance to P_1, even though the proof says nothing

> about P_1. (This is a common reaction, which presumably is why this

> sort of bait and switch keeps happening.)

"this sort of bait and switch keeps happening" -- smearing everybody

and nobody at once -- perhaps first request a specific example or two.

If the fraud is so endemic, a few cases should not be hard to provide.

I have previously asked Dan for examples of exactly what's described

above, but none were provided. But see here for several papers that

*don’t* do that:

https://groups.google.com/d/msg/cryptanalytic-algorithms/y-wAnhmGsIo/mjAt-smTBAAJ

, regarding "Myth #1."

Because Regev's worst-case reduction for LWE was raised, let's see

what Micciancio and Regev wrote about such reductions in their

influential 2009 survey (from the book Post-Quantum Cryptography,

edited by Dan Bernstein), which to my knowledge was the first work to

propose concrete LWE parameters:

"The importance of the worst-case security guarantee is twofold.

First, it assures us that attacks on the cryptographic construction

are likely to be effective only for small choices of parameters and

not asymptotically. In other words, it assures us that there are no

fundamental flaws in the design of our cryptographic construction. In

fact, in some cases, the worst-case security guarantee can even guide

us in making design decisions. Second, in principle the worst-case

security guarantee can help us in choosing concrete parameters for the

cryptosystem, although in practice this leads to what seems like

overly conservative estimates, and as we shall see later, one often

sets the parameters based on the best known attacks."

To reiterate:

1. Worst-case reductions/proofs help us make sound design decisions,

helping to avoid unexpected structural flaws.

Indeed, there are many lattice-based systems that lacked such

reductions, and turned out to be unexpectedly weak or completely

broken (for any realistic parameters): Merkle-Hellman, NTRUSign, and

SOLILOQUY come to mind. To my knowledge, this has never happened to a

system that competently parameterized a scheme having a worst-case

reduction.

2. Relying on worst-case reductions alone yields quite large and

conservative parameters, because those reductions are obviously quite

loose.

3. One usually sets concrete parameters by cryptanalysis via known or

extrapolated attacks.

There are many papers that do exactly this, prominently distinguishing

between the asymptotic proofs that aided the discovery and design of a

system, and the cryptanalysis of its concrete parameters.

Based on all this, the reader can be the judge of whether such proofs

are "irrelevant" or are being "mislabeled," and more generally whether

there's any underhandedness going on.

Sincerely yours in cryptography,

Chris

Dec 2, 2017, 3:35:48 AM12/2/17

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

With all due respect, hasn't worst case been demonstrated equivalent with average case per Regev?

-------- Original message --------

From: Christopher J Peikert <cpei...@alum.mit.edu>

Date: 12/02/2017 2:13 AM (GMT-06:00)

To: "D. J. Bernstein" <d...@cr.yp.to>

Cc: pqc-...@list.nist.gov

--

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

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.

Dec 2, 2017, 5:51:05 AM12/2/17

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

This article specifically references applications of DTC in quantum information memory.

The difficulties of predicting QC advances were the motivation behind my colleague and I proposing the Riemann primitive. The Riemann sphere was to act as a model in correspondence with the Bloch diagram to gauge post-quantum security.

Unfortunately, the utility of the Riemann primitive has not yet been demonstrated.

-------- Original message --------

From: Yongge Wang <Yongg...@uncc.edu>

Date: 12/01/2017 11:21 PM (GMT-06:00)

To:

Cc: pqc-...@list.nist.gov

Subject: Re: [pqc-forum] qrom security etc.

Dec 2, 2017, 9:34:05 AM12/2/17

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

CSO writes:

> With all due respect, hasn't worst case been demonstrated equivalent

> with average case per Regev?

No. This is another example of the gap between what the theorems are
> With all due respect, hasn't worst case been demonstrated equivalent

> with average case per Regev?

commonly viewed as saying and what they actually say.

Something else to keep in mind is that it's easy to build cryptosystems

that have the following two features simultaneously:

* The key-recovery problem for the cryptosystem has a polynomial

reduction from the worst case to the average case.

In other words, if someone gives you a magic box to break the

average case then you can break _any_ case with a polynomial number

of calls to the magic box plus a polynomial amount of additional

computation.

* The cryptosystem is broken by a completely reliable polynomial-time

key-recovery attack.

We know a much wider variety of these broken cryptosystems with

worst-case-to-average-case reductions than _unbroken_ cryptosystems with

worst-case-to-average-case reductions. The reason is that (1) the second

feature implies the first, and (2) it's an easy exercise to build

cryptosystems with the second feature.

---Dan

Dec 2, 2017, 11:11:46 AM12/2/17

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

My question is how the following types of proofs will be treated:

* a submission advertises the proof; and

* the same submission proposes parameter set P_1; but

* the proof doesn't actually apply to parameter set P_1 (for example,

the proof relies on QROM bounds that need larger parameters).

This is an objectively recognizable situation, and a situation that I

presume will occur in quite a few submissions (extrapolating from the

history surveyed in, e.g., https://www.youtube.com/watch?v=l56ORg5xXkk).

I'm unable to figure out whether Peikert is claiming that this won't

happen in the submissions. This seems pointless to discuss, since we'll

all see the (complete and proper) submissions soon.

I'm also unable to figure out what Peikert is trying to say regarding

his recommended answer to the question. "Structural flaws" sound bad and

"competently parameterized" sounds good, but the severe lack of clarity

in these phrases becomes obvious when one looks at real examples. What

are the "competent" parameters for Ideal-SVP?

---Dan

* a submission advertises the proof; and

* the same submission proposes parameter set P_1; but

* the proof doesn't actually apply to parameter set P_1 (for example,

the proof relies on QROM bounds that need larger parameters).

This is an objectively recognizable situation, and a situation that I

presume will occur in quite a few submissions (extrapolating from the

history surveyed in, e.g., https://www.youtube.com/watch?v=l56ORg5xXkk).

I'm unable to figure out whether Peikert is claiming that this won't

happen in the submissions. This seems pointless to discuss, since we'll

all see the (complete and proper) submissions soon.

I'm also unable to figure out what Peikert is trying to say regarding

his recommended answer to the question. "Structural flaws" sound bad and

"competently parameterized" sounds good, but the severe lack of clarity

in these phrases becomes obvious when one looks at real examples. What

are the "competent" parameters for Ideal-SVP?

---Dan

Dec 2, 2017, 11:13:14 AM12/2/17

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

> Something else to keep in mind is that it's easy to build cryptosystems

> that have the following two features simultaneously:

>

> * The key-recovery problem for the cryptosystem has a polynomial

> reduction from the worst case to the average case.

>

> In other words, if someone gives you a magic box to break the

> average case then you can break _any_ case with a polynomial number

> of calls to the magic box plus a polynomial amount of additional

> computation.

>

> * The cryptosystem is broken by a completely reliable polynomial-time

> key-recovery attack.

Yes, but why be so obscure? In case there's any confusion, here's
> that have the following two features simultaneously:

>

> * The key-recovery problem for the cryptosystem has a polynomial

> reduction from the worst case to the average case.

>

> In other words, if someone gives you a magic box to break the

> average case then you can break _any_ case with a polynomial number

> of calls to the magic box plus a polynomial amount of additional

> computation.

>

> * The cryptosystem is broken by a completely reliable polynomial-time

> key-recovery attack.

such a system:

* The secret key is always "DUMB SYSTEM".

* To encrypt a message m, do nothing: the ciphertext is also m.

(Decryption is left as an exercise for the reader.)

There is a trivial reduction from the worst-case to the average-case

key-recovery problem. Indeed, the worst and average cases are

equivalent (because no randomness is used), and obviously easy.

There's also a trivial reduction from the above worst-case problem to

the average-case problem of breaking *any* cryptosystem you can name.

Is any of this reason to be suspicious of worst-case/average-case

reductions themselves, or the cryptosystems that admit them? No, it's

reason to not consider easy worst-case problems.

What makes such reductions interesting for LWE is that the underlying

worst-case problems -- e.g., approximating short vectors in lattices

-- have been deeply studied by some of the great mathematicians and

computer scientists going back at least to Gauss, and appear to be

very hard.

Dec 2, 2017, 11:37:13 AM12/2/17

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

> My question is how the following types of proofs will be treated:

>

> * a submission advertises the proof; and

> * the same submission proposes parameter set P_1; but

> * the proof doesn't actually apply to parameter set P_1 (for example,

> the proof relies on QROM bounds that need larger parameters).

In case it wasn't clear, my answer is that even in this situation,
>

> * a submission advertises the proof; and

> * the same submission proposes parameter set P_1; but

> * the proof doesn't actually apply to parameter set P_1 (for example,

> the proof relies on QROM bounds that need larger parameters).

such a proof is not necessarily "irrelevant" or "mislabeled" (to use a

few words Dan applied), because it can give evidence that the core

design does not have surprising weaknesses (or total breaks) like

those found in many systems that lacked such proofs.

Of course, submissions should not overstate what their proofs actually

mean for concrete security. (Dan seems to think this is endemic in

the literature, but still hasn't provided any examples.)

> I'm also unable to figure out what Peikert is trying to say regarding

> his recommended answer to the question. "Structural flaws" sound bad and

> "competently parameterized" sounds good, but the severe lack of clarity

> in these phrases becomes obvious when one looks at real examples. What

> are the "competent" parameters for Ideal-SVP?

make sense in this context. A specific cryptosystem based on, say,

LWE would have parameters to set concretely. There are several works

that describe approaches for doing this.

Dec 2, 2017, 1:28:53 PM12/2/17

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

There's a mountain of broken systems with worst-case-to-average-case

reductions. Peikert admits this but nevertheless appears to believe that

in _some_ circumstances such reductions actually _reduce_ the risk of

attack. What, precisely, are those circumstances?

Surely Peikert has some sort of answer in mind, but I'm having trouble

figuring out what this answer is. Saying "Worst-case-to-average-case

reductions are an indication of security for systems that are secure"

would be uselessly circular---yes, it's trivially correct, but "not

having reductions is an indication of security for systems that are

secure" is also trivially correct.

Christopher J Peikert writes:

> reason to not consider easy worst-case problems

Let me see if I understand. You seem to be saying that

* we should first throw away worst-case-to-average-case reductions

that are _known_ to be vacuous (the worst-case problem is already

known to be easy); and, after this is done,

* you think that the systems with known not-known-to-be-vacuous

worst-case-to-average-case reductions are more likely to resist

future attacks than unbroken systems not known to have such

reductions.

Did I get this right?

---Dan

reductions. Peikert admits this but nevertheless appears to believe that

in _some_ circumstances such reductions actually _reduce_ the risk of

attack. What, precisely, are those circumstances?

Surely Peikert has some sort of answer in mind, but I'm having trouble

figuring out what this answer is. Saying "Worst-case-to-average-case

reductions are an indication of security for systems that are secure"

would be uselessly circular---yes, it's trivially correct, but "not

having reductions is an indication of security for systems that are

secure" is also trivially correct.

Christopher J Peikert writes:

> reason to not consider easy worst-case problems

* we should first throw away worst-case-to-average-case reductions

that are _known_ to be vacuous (the worst-case problem is already

known to be easy); and, after this is done,

* you think that the systems with known not-known-to-be-vacuous

worst-case-to-average-case reductions are more likely to resist

future attacks than unbroken systems not known to have such

reductions.

Did I get this right?

---Dan

Dec 2, 2017, 1:40:17 PM12/2/17

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

Christopher J Peikert writes:

> the underlying worst-case problems -- e.g., approximating short

> vectors in lattices -- have been deeply studied by some of the great

> mathematicians and computer scientists going back at least to Gauss,

> and appear to be very hard.

Gauss's complete works are online. Can you please point to where he
> the underlying worst-case problems -- e.g., approximating short

> vectors in lattices -- have been deeply studied by some of the great

> mathematicians and computer scientists going back at least to Gauss,

> and appear to be very hard.

studied the problem of quickly finding somewhat short nonzero vectors in

high-dimensional lattices?

---Dan

Dec 2, 2017, 2:38:03 PM12/2/17

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

In 1773, Lagrange gave an efficient SVP algorithm for 2-dimensional

lattices. Gauss and others used it in reduction theory for quadratic

forms. Given how prolific they were, it's not a leap to guess that

they might have considered algorithms for larger dimensions, but I

don't know offhand if they published anything. (Can anyone comment?)

The 2-dimensional algorithm is a key component of the algorithms by

Lenstra-Lenstra-Lovasz and Schnorr (among others) for finding "not

extremely long" vectors in high-dimensional lattices.

Here's a good summary with more information (I couldn't find the talk

video online):

https://iacr.org/archive/eurocrypt2011/66320002/66320002.pdf

Dec 2, 2017, 2:50:50 PM12/2/17

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

On Sat, Dec 2, 2017 at 1:28 PM, D. J. Bernstein <d...@cr.yp.to> wrote:

> There's a mountain of broken systems with worst-case-to-average-case

> reductions.

This "mountain" is "all broken systems," and isn't even limited to
> There's a mountain of broken systems with worst-case-to-average-case

> reductions.

broken ones: just take any *trivially easy* worst-case problem, and

voila, you have a trivial such reduction (which says nothing about the

security or insecurity of the system).

> Peikert admits this but nevertheless appears to believe that

> in _some_ circumstances such reductions actually _reduce_ the risk of

> attack. What, precisely, are those circumstances?

>

> Surely Peikert has some sort of answer in mind, but I'm having trouble

> figuring out what this answer is.

believe that the worst-case problem is very hard.

At this point I'll invoke Brandolini's law and sign off from this thread.

Dec 2, 2017, 3:42:28 PM12/2/17

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

On Sat, Dec 02, 2017 at 12:06:41AM -0000, D. J. Bernstein wrote:

> I don't see where NIST addressed this important issue in the call:

>

> Submitters are not required to provide a proof of security, although

> such proofs will be considered if they are available. ... While

> security proofs are generally based on unproven assumptions, they can

> often rule out common classes of attacks or relate the security of a

> new scheme to an older and better studied computational problem.

>

> No matter how solid the underlying assumption is, and no matter how

> broad the analyzed attack class is, a proof that requires parameter set

> P_50 is failing to address the risk of an attack against P_1.

Hi Dan,
> I don't see where NIST addressed this important issue in the call:

>

> Submitters are not required to provide a proof of security, although

> such proofs will be considered if they are available. ... While

> security proofs are generally based on unproven assumptions, they can

> often rule out common classes of attacks or relate the security of a

> new scheme to an older and better studied computational problem.

>

> No matter how solid the underlying assumption is, and no matter how

> broad the analyzed attack class is, a proof that requires parameter set

> P_50 is failing to address the risk of an attack against P_1.

from this and your other posts to this list it's clear that you have strong

opinions about how cryptographic competitions should be announced and run, the

exact details of what API they should provide to submissions, etc.

Perhaps you should lead by example, and demonstrate the value of your approach,

by running your own crypto competition? For instance, this one:

https://competitions.cr.yp.to/caesar.html

I notice that the remaining timeline items have all been "TBA" for over a year,

with the exception of the final announcement in two weeks. I'm surprised

you're able to commit so much time to improving the NIST competition, with that

impending deadline.

Cheers,

Henry de Valence

Dec 2, 2017, 4:14:40 PM12/2/17

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

Gauss' circle problem asks to find a lower and upper bound on uniform lattice in a circle.

-------- Original message --------

From: "D. J. Bernstein" <d...@cr.yp.to>

Date: 12/02/2017 12:40 PM (GMT-06:00)

To: pqc-...@list.nist.gov

Subject: [pqc-forum] Gauss

Christopher J Peikert writes:

> the underlying worst-case problems -- e.g., approximating short

> vectors in lattices -- have been deeply studied by some of the great

> mathematicians and computer scientists going back at least to Gauss,

> and appear to be very hard.

Gauss's complete works are online. Can you please point to where he

studied the problem of quickly finding somewhat short nonzero vectors in

high-dimensional lattices?

---Dan

Dec 2, 2017, 4:18:16 PM12/2/17

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

Here is an article on Gauss' circle problem, which bears some resemblance to bounded distance decoding in my humble opinion.

-------- Original message --------

From: Christopher J Peikert <cpei...@alum.mit.edu>

Date: 12/02/2017 1:37 PM (GMT-06:00)

To: "D. J. Bernstein" <d...@cr.yp.to>

On Sat, Dec 2, 2017 at 1:40 PM, D. J. Bernstein <d...@cr.yp.to> wrote:

> Christopher J Peikert writes:

>> the underlying worst-case problems -- e.g., approximating short

>> vectors in lattices -- have been deeply studied by some of the great

>> mathematicians and computer scientists going back at least to Gauss,

>> and appear to be very hard.

>

> Gauss's complete works are online. Can you please point to where he

> studied the problem of quickly finding somewhat short nonzero vectors in

> high-dimensional lattices?

As you can see, I didn't claim that.

In 1773, Lagrange gave an efficient SVP algorithm for 2-dimensional

lattices. Gauss and others used it in reduction theory for quadratic

forms. Given how prolific they were, it's not a leap to guess that

they might have considered algorithms for larger dimensions, but I

don't know offhand if they published anything. (Can anyone comment?)

The 2-dimensional algorithm is a key component of the algorithms by

Lenstra-Lenstra-Lovasz and Schnorr (among others) for finding "not

extremely long" vectors in high-dimensional lattices.

Here's a good summary with more information (I couldn't find the talk

video online):

https://iacr.org/archive/eurocrypt2011/66320002/66320002.pdf

In 1773, Lagrange gave an efficient SVP algorithm for 2-dimensional

lattices. Gauss and others used it in reduction theory for quadratic

forms. Given how prolific they were, it's not a leap to guess that

they might have considered algorithms for larger dimensions, but I

don't know offhand if they published anything. (Can anyone comment?)

The 2-dimensional algorithm is a key component of the algorithms by

Lenstra-Lenstra-Lovasz and Schnorr (among others) for finding "not

extremely long" vectors in high-dimensional lattices.

Here's a good summary with more information (I couldn't find the talk

video online):

https://iacr.org/archive/eurocrypt2011/66320002/66320002.pdf

Sincerely yours in cryptography,

Chris

Chris

Dec 2, 2017, 5:23:37 PM12/2/17

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

I'd like to see an erratum issued for the following security claim, in

the absence of a specific reference justifying the claim about Gauss:

What makes such reductions interesting for LWE is that the underlying

quadratic-time SVP algorithm to them. This has at least three major

differences from what appears in the security claim:

* it was two dimensions, whereas the security claim needs many;

* there was no approximation factor; and, most fundamentally,

* this was an _easy_ computation, which is totally backwards from a

hardness claim.

There are other cases where Gauss was quite explicitly considering a

hard problem and making some progress: primality testing, for example,

and integer factorization. It's _conceivable_ that he engaged in a study

of high-dimensional approx-SVP. But the security claim doesn't say

"might have been deeply studied".

It's important to understand which problems have been studied, which

attack avenues have been explored, and how deeply they were explored.

Misinformation on this topic creates unnecessary risks for users.

Christopher J Peikert writes:

> The 2-dimensional algorithm is a key component of the algorithms by

> Lenstra-Lenstra-Lovasz and Schnorr (among others) for finding "not

> extremely long" vectors in high-dimensional lattices.

Arithmetic is also a key component of those algorithms. Does this mean

that everyone who has developed algorithms for arithmetic was studying

the difficulty of high-dimensional basis reduction?

---Dan

the absence of a specific reference justifying the claim about Gauss:

What makes such reductions interesting for LWE is that the underlying

worst-case problems -- e.g., approximating short vectors in lattices

-- have been deeply studied by some of the great mathematicians and

computer scientists going back at least to Gauss, and appear to be

very hard.

Gauss encountered some 2-dimensional lattices and applied a simple
-- have been deeply studied by some of the great mathematicians and

computer scientists going back at least to Gauss, and appear to be

very hard.

quadratic-time SVP algorithm to them. This has at least three major

differences from what appears in the security claim:

* it was two dimensions, whereas the security claim needs many;

* there was no approximation factor; and, most fundamentally,

* this was an _easy_ computation, which is totally backwards from a

hardness claim.

There are other cases where Gauss was quite explicitly considering a

hard problem and making some progress: primality testing, for example,

and integer factorization. It's _conceivable_ that he engaged in a study

of high-dimensional approx-SVP. But the security claim doesn't say

"might have been deeply studied".

It's important to understand which problems have been studied, which

attack avenues have been explored, and how deeply they were explored.

Misinformation on this topic creates unnecessary risks for users.

Christopher J Peikert writes:

> The 2-dimensional algorithm is a key component of the algorithms by

> Lenstra-Lenstra-Lovasz and Schnorr (among others) for finding "not

> extremely long" vectors in high-dimensional lattices.

that everyone who has developed algorithms for arithmetic was studying

the difficulty of high-dimensional basis reduction?

---Dan

Dec 2, 2017, 5:29:43 PM12/2/17

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

The simple answer, from my perspective, is "standing on the shoulders of giants."

I believe lifting any two dimensional lattice to a higher dimension can increase security. See New Hope for example, which begins in D_2 though operates in D_4.

Of course, you would want such a scheme to apply to randomized reductions. I'm not sure why Gauss would be concerned with computationally difficult problems before computation was really defined.

Best,

Ian

--

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

Dec 2, 2017, 6:08:29 PM12/2/17

to pqc-forum, d...@cr.yp.to, hdeva...@riseup.net, pqc-...@list.nist.gov

Henry,

I do not believe this response is appropriate for this mailing list. However, I do believe that your story as a PhD student:

is something that people should know regarding where our cryptography advice is coming from.

Jonas

Dec 2, 2017, 6:41:09 PM12/2/17

to jonasweber86, pqc-...@list.nist.gov, D. J. Bernstein, hdeva...@riseup.net

Cryptography is a science founded upon formal methods: logic, reason, and computation. I'm less interested in fallacies of logic such as "poisoning the well" and ad hominem assertions than valid critiques of mathematical structures.

I'm hesitant to speak for anyone other than myself, but this list does not seem to be the place to air such grievances.

It'd like to ask we all focus on what lies ahead; rigorous analysis and review of mathematics, not personalities.

Apologies if my comments are out-of-line.

Thank you.

--

Dec 2, 2017, 6:54:15 PM12/2/17

to pqc-forum, d...@cr.yp.to, hdeva...@riseup.net

Ian, I agree with you. In my note to Henry I should have written "your post" (referring to his post) was not appropriate for the NIST mailing list, English isn't my first language and your post allowed me to see my error. Yes, the list should stick to cryptography.

Dec 2, 2017, 10:34:23 PM12/2/17

to jonasweber86, pqc-...@list.nist.gov, hdeva...@riseup.net

Thank you.

I'm sure we all appreciate it.

--

Dec 4, 2017, 9:33:46 AM12/4/17

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

On Sat, Dec 2, 2017 at 5:23 PM, D. J. Bernstein <d...@cr.yp.to> wrote:

> I'd like to see an erratum issued for the following security claim, in

> the absence of a specific reference justifying the claim about Gauss:

>

> What makes such reductions interesting for LWE is that the underlying

> worst-case problems -- e.g., approximating short vectors in lattices

> -- have been deeply studied by some of the great mathematicians and

> computer scientists going back at least to Gauss, and appear to be

> very hard.

Good morning. I'd love to help fix this nonsensical misinterpretation
> I'd like to see an erratum issued for the following security claim, in

> the absence of a specific reference justifying the claim about Gauss:

>

> What makes such reductions interesting for LWE is that the underlying

> worst-case problems -- e.g., approximating short vectors in lattices

> -- have been deeply studied by some of the great mathematicians and

> computer scientists going back at least to Gauss, and appear to be

> very hard.

of what I wrote, but alas, Brandolini's Law remains in effect.

Dec 4, 2017, 10:09:14 AM12/4/17

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

https://eprint.iacr.org/2016/885 obliterated half of the remaining

parameter range for cyclotomic Ideal-SVP, under plausible assumptions.

"Half" is measured on the usual log-log scale: exp(n^(1/2+o(1))) is

leaping halfway from exponential to polynomial.

I'd like to know how this example fits with the claim that there have

never been "unexpected" weaknesses in "lattice-based systems" that were

"competently parameterized" and had a "worst-case reduction".

Are approximation factors exp(n^(1/2+o(1))) not "competent"? Why not?

What's the dividing line between "competent" and "incompetent"?

Or is one of the other words somehow supposed to exclude this example?

Which word is it, how is the word defined, and why does this definition

exclude the example?

---Dan

parameter range for cyclotomic Ideal-SVP, under plausible assumptions.

"Half" is measured on the usual log-log scale: exp(n^(1/2+o(1))) is

leaping halfway from exponential to polynomial.

I'd like to know how this example fits with the claim that there have

never been "unexpected" weaknesses in "lattice-based systems" that were

"competently parameterized" and had a "worst-case reduction".

Are approximation factors exp(n^(1/2+o(1))) not "competent"? Why not?

What's the dividing line between "competent" and "incompetent"?

Or is one of the other words somehow supposed to exclude this example?

Which word is it, how is the word defined, and why does this definition

exclude the example?

---Dan

Dec 4, 2017, 10:22:55 AM12/4/17

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

On Mon, Dec 4, 2017 at 10:08 AM, D. J. Bernstein <d...@cr.yp.to> wrote:

> https://eprint.iacr.org/2016/885 obliterated half of the remaining

> parameter range for cyclotomic Ideal-SVP, under plausible assumptions.

> "Half" is measured on the usual log-log scale: exp(n^(1/2+o(1))) is

> leaping halfway from exponential to polynomial.

There is nothing at all "usual" about this log-log scale for
> https://eprint.iacr.org/2016/885 obliterated half of the remaining

> parameter range for cyclotomic Ideal-SVP, under plausible assumptions.

> "Half" is measured on the usual log-log scale: exp(n^(1/2+o(1))) is

> leaping halfway from exponential to polynomial.

cryptography: ordinary public-key encryption/KEM schemes having

reductions from worst-case Ideal-SVP (e.g., the one from

Lyubashevsky-Peikert-Regev EUROCRYPT'10) typically rely on small

polynomial factors for the worst-case problem.

Much more advanced systems, like Fully Homomorphic Encryption schemes

(e.g., Brakerski-Gentry-Vaikuntanathan ITCS'12), have relied on

quasi-polynomial factors.

I'm not aware of any proposed system that needs to rely on anything

close to exp(n^(1/2+o(1)) factors that you artificially consider the

"midpoint" of the parameter range.

Of course, you're already well aware of all of this (or should be by now).

Dec 4, 2017, 3:17:36 PM12/4/17

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

PS: let me be clear that the following refers to the "leveled" FHE

from the title of the BGV'12 paper.

(There is also a "non-leveled" construction, but its analysis uses a

circular security assumption that has not yet been supported by a

reduction from a plausible worst-case hardness assumption on

Approx-Ideal-SVP.)

> Much more advanced systems, like Fully Homomorphic Encryption schemes

> (e.g., Brakerski-Gentry-Vaikuntanathan ITCS'12), have relied on

> quasi-polynomial factors.

from the title of the BGV'12 paper.

(There is also a "non-leveled" construction, but its analysis uses a

circular security assumption that has not yet been supported by a

reduction from a plausible worst-case hardness assumption on

Approx-Ideal-SVP.)

> Much more advanced systems, like Fully Homomorphic Encryption schemes

> (e.g., Brakerski-Gentry-Vaikuntanathan ITCS'12), have relied on

> quasi-polynomial factors.

Dec 7, 2017, 5:25:42 AM12/7/17

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

Unfortunately, there are still no definitions for the "competently

parameterized" security claim.

The attack in https://eprint.iacr.org/2016/885 has the performance that

I summarized before, and looks like a counterexample to the claim, but

maybe some word in the claim has a narrow definition that excludes this

example. Without seeing definitions it's impossible to tell. The same

ambiguity makes the claim actively dangerous: users, not realizing that

X is broken, can interpret the claim as saying that X is secure.

Christopher J Peikert writes:

> There is nothing at all "usual" about this log-log scale for

> cryptography

Actually, the standard BKZ lattice attack takes time 2^(n^t) to reach

approximation factor essentially 2^(n^(1-t)). Taking two logs makes this

relationship linear: lg lg time + lg lg factor is essentially lg lg n.

This log-log scale is inherent in the performance of the algorithm.

There are also standard non-lattice examples. See, e.g., the usual

explanation of how NFS ends up with a 1/3 in the double exponent, and

the usual L(1/3) notation for this.

> I'm not aware of any proposed system that needs to rely on anything

> close to exp(n^(1/2+o(1)) factors that you artificially consider the

> "midpoint" of the parameter range.

This approximation factor is used by, e.g., Smart and Vercauteren, who

described "2^sqrt(N)" as a "typical" choice for their "eta" parameter.

This choice was already mentioned as an example in Gentry's thesis; it

balances two effects that were already described in Gentry's original

STOC 2009 paper. Are you claiming that this is "artificial"?

Or are you saying that these examples don't count because they didn't

have worst-case-to-average-case reductions? I don't see where Gentry

issues any warnings about the parameters being unsuitable for Chapter 19

of his thesis, "Basing Security on Worst-case SIVP in Ideal Lattices".

Or are you going to say that, even though the systems were proposed with

these parameters as examples, they didn't "need" to be proposed with

these parameters? This is of course true for the above examples, but it

doesn't justify your claim that this parameter choice is "artificial".

The whole point here is to assess security risks. If a risk-assessment

method produces bad results on some examples, then saying "People didn't

_need_ to choose those examples" is fundamentally missing the point.

As another example, let me remind you of the lattice-based DH system

spelled out in my email dated 6 Sep 2017 13:38:53 +0000, especially the

following statement: "The ratio q/noise is chosen large enough to drive

the failure probability down to negligible levels." Quantitatively:

* Ensuring failure probability <=1/2^b forces the approximation

factor in this system to be, at a minimum, exp(b^(1+o(1))). Let me

emphasize that this is a _non-interactive_ key-exchange system;

there's no opportunity for reconciliation.

* Forcing BKZ to take time 2^b then requires the lattice dimension n

to be, at a minimum, b^(2+o(1)).

* Taking the smallest key sizes for the target security level---

which is exactly what Lyubashevsky did in a talk describing this

system---ends up with approximation factors exp(n^(1/2+o(1))).

To summarize, optimizing lattice-based DH produces the parameter range

that you call "artificial". Again the parameters don't _need_ to be

chosen this way, but again that's fundamentally missing the point.

Getting back to your original security claim ("To my knowledge,

[unexpected weaknesses] never happened to a system that competently

parameterized a scheme having a worst-case reduction"): Can you please

define "competently parameterized" in enough detail that we can all see

whether these examples from Gentry and Lyubashevsky were "competently

parameterized"?

> Of course, you're already well aware of all of this (or should be by

> now).

Actually, I'm well aware of _counterexamples_ to what you appear to be

claiming; but I can't be sure, given all the unanswered questions about

highly ambiguous words in your claims. I'm reminded of Pauli's comment

"Das ist nicht nur nicht richtig; es ist nicht einmal falsch!"

---Dan

parameterized" security claim.

The attack in https://eprint.iacr.org/2016/885 has the performance that

I summarized before, and looks like a counterexample to the claim, but

maybe some word in the claim has a narrow definition that excludes this

example. Without seeing definitions it's impossible to tell. The same

ambiguity makes the claim actively dangerous: users, not realizing that

X is broken, can interpret the claim as saying that X is secure.

Christopher J Peikert writes:

> There is nothing at all "usual" about this log-log scale for

> cryptography

approximation factor essentially 2^(n^(1-t)). Taking two logs makes this

relationship linear: lg lg time + lg lg factor is essentially lg lg n.

This log-log scale is inherent in the performance of the algorithm.

There are also standard non-lattice examples. See, e.g., the usual

explanation of how NFS ends up with a 1/3 in the double exponent, and

the usual L(1/3) notation for this.

> I'm not aware of any proposed system that needs to rely on anything

> close to exp(n^(1/2+o(1)) factors that you artificially consider the

> "midpoint" of the parameter range.

described "2^sqrt(N)" as a "typical" choice for their "eta" parameter.

This choice was already mentioned as an example in Gentry's thesis; it

balances two effects that were already described in Gentry's original

STOC 2009 paper. Are you claiming that this is "artificial"?

Or are you saying that these examples don't count because they didn't

have worst-case-to-average-case reductions? I don't see where Gentry

issues any warnings about the parameters being unsuitable for Chapter 19

of his thesis, "Basing Security on Worst-case SIVP in Ideal Lattices".

Or are you going to say that, even though the systems were proposed with

these parameters as examples, they didn't "need" to be proposed with

these parameters? This is of course true for the above examples, but it

doesn't justify your claim that this parameter choice is "artificial".

The whole point here is to assess security risks. If a risk-assessment

method produces bad results on some examples, then saying "People didn't

_need_ to choose those examples" is fundamentally missing the point.

As another example, let me remind you of the lattice-based DH system

spelled out in my email dated 6 Sep 2017 13:38:53 +0000, especially the

following statement: "The ratio q/noise is chosen large enough to drive

the failure probability down to negligible levels." Quantitatively:

* Ensuring failure probability <=1/2^b forces the approximation

factor in this system to be, at a minimum, exp(b^(1+o(1))). Let me

emphasize that this is a _non-interactive_ key-exchange system;

there's no opportunity for reconciliation.

* Forcing BKZ to take time 2^b then requires the lattice dimension n

to be, at a minimum, b^(2+o(1)).

* Taking the smallest key sizes for the target security level---

which is exactly what Lyubashevsky did in a talk describing this

system---ends up with approximation factors exp(n^(1/2+o(1))).

To summarize, optimizing lattice-based DH produces the parameter range

that you call "artificial". Again the parameters don't _need_ to be

chosen this way, but again that's fundamentally missing the point.

Getting back to your original security claim ("To my knowledge,

[unexpected weaknesses] never happened to a system that competently

parameterized a scheme having a worst-case reduction"): Can you please

define "competently parameterized" in enough detail that we can all see

whether these examples from Gentry and Lyubashevsky were "competently

parameterized"?

> Of course, you're already well aware of all of this (or should be by

> now).

claiming; but I can't be sure, given all the unanswered questions about

highly ambiguous words in your claims. I'm reminded of Pauli's comment

"Das ist nicht nur nicht richtig; es ist nicht einmal falsch!"

---Dan

Dec 7, 2017, 11:11:21 AM12/7/17

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

> Unfortunately, there are still no definitions for the "competently

> parameterized" security claim.

>

> The attack in https://eprint.iacr.org/2016/885 has the performance that

> I summarized before, and looks like a counterexample to the claim, but

> maybe some word in the claim has a narrow definition that excludes this

> example. Without seeing definitions it's impossible to tell.

Dan, your questions about "competently parameterized" have been
> parameterized" security claim.

>

> The attack in https://eprint.iacr.org/2016/885 has the performance that

> I summarized before, and looks like a counterexample to the claim, but

> maybe some word in the claim has a narrow definition that excludes this

> example. Without seeing definitions it's impossible to tell.

answered, both before and after you asked them: the phrase clearly

refers to cryptanalysis of an actual cryptosystem with concrete

parameters, against known or extrapolated attacks. (See below for a

reminder.) In particular, it has nothing to do with asymptotic

worst-case approximation factors, as you continue to suggest. It's

becoming increasingly hard to believe that you're engaging in good

faith here.

To recap: my original message said, quoting Micciancio and Regev from

the book you edited,

"Second, in principle the worst-case security guarantee can help us

in choosing concrete parameters for the cryptosystem, although in

practice this leads to what seems like overly conservative estimates,

and

"One usually sets concrete parameters by cryptanalysis via known or

extrapolated attacks"

"...there are many lattice-based systems that lacked such

[worst-case-to-average-case] reductions, and turned out to be

unexpectedly weak or completely broken (for any realistic parameters):

Merkle-Hellman, NTRUSign, and SOLILOQUY come to mind. To my

knowledge, this has never happened to a system that competently
Merkle-Hellman, NTRUSign, and SOLILOQUY come to mind. To my

parameterized a scheme having a worst-case reduction."

You subsequently asked "What are the 'competent' parameters for

Ideal-SVP?," to which I replied

"(Approximate) Ideal-SVP is not a cryptosystem, so the question

doesn't make sense in this context. A specific cryptosystem based on,

say, LWE would have parameters to set concretely. There are several

works that describe approaches for doing this."

premised on the above non-sequitur, so I will just make a few brief

points.

The paper https://eprint.iacr.org/2016/885 you cite is about

worst-case approx-Ideal-SVP for asymptotically large (but

subexponential) approximation factors. It does not yield a

"counterexample" to any claim I've made here.

> > I'm not aware of any proposed system that needs to rely on anything

> > close to exp(n^(1/2+o(1)) factors that you artificially consider the

> > "midpoint" of the parameter range.

>

> This approximation factor is used by, e.g., Smart and Vercauteren, who

> described "2^sqrt(N)" as a "typical" choice for their "eta" parameter.

worst-case-to-average-case reduction, so my statements don't apply to

it. Indeed, it is yet another example of such a lattice-based system

that turned out to be breakable by a (quantum) polynomial-time attack

-- even when "scaled down" to an ordinary public-key cryptosystem with

no homomorphic properties, and an eta=poly(n) factor.

There is an FHE system in Gentry's thesis that does have a worst-case

hardness theorem, but to my knowledge no concrete parameters or

security estimates have ever been proposed. (This is probably because

the system was pretty quickly subsumed by BGV-style systems, which are

more efficient in all respects and also involve much smaller

approximation factors.)

> As another example, let me remind you of the lattice-based DH system

> spelled out in my email dated 6 Sep 2017 13:38:53 +0000, especially the

> following statement: "The ratio q/noise is chosen large enough to drive

> the failure probability down to negligible levels." Quantitatively:

>

> * Ensuring failure probability <=1/2^b forces the approximation

> factor in this system to be, at a minimum, exp(b^(1+o(1))). Let me

> emphasize that this is a _non-interactive_ key-exchange system;

> there's no opportunity for reconciliation.

>

> * Forcing BKZ to take time 2^b then requires the lattice dimension n

> to be, at a minimum, b^(2+o(1)).

>

> * Taking the smallest key sizes for the target security level---

> which is exactly what Lyubashevsky did in a talk describing this

> system---ends up with approximation factors exp(n^(1/2+o(1))).

*concrete* parameterization of the system that has an estimated

*concrete* level of security, against known/extrapolated attacks. It's

right there on the slide: "PK sizes of (probably) more than 40 - 50

KB."

But even if one were to consider the above asymptotics, it's still the

case that the best known attacks on the system are conventional

lattice-reduction attacks (with the usual linear speedups arising from

ring symmetries). In particular, https://eprint.iacr.org/2016/885

does not appear to apply to this system, as the paper itself says.

Dec 9, 2017, 5:30:09 PM12/9/17

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

There's a fast worst-case-to-average-case reduction for NIST P-256 ECDL:

simply add a random multiple of the base point. Similarly, there's a

fast worst-case-to-average-case reduction for NIST P-384 ECDL, etc.

These worst-case-to-average-case reductions are important tools in ECDL

attacks. See, e.g., https://blog.cr.yp.to/20151120-batchattacks.html.

The resulting security damage is clear---the well-known reduction of

ECDL attack cost from, asymptotically, p^(1+o(1)) to p^(1/2+o(1)). The

best pre-quantum ECDL attacks we know are slight optimizations of this:

they cost p^(1/2+o(1)) with a marginally smaller o(1).

As for quantum algorithms, Shor's algorithm reuses essentially the same

attack tools with additional quantum techniques to do even more damage,

reducing the ECDL attack cost to polynomial. This of course is a major

motivation for post-quantum cryptography.

I'm making simple asymptotic statements here: 1/2+o(1), polynomial, etc.

These asymptotic speedups imply speedups for every concrete size beyond

some limit. There are various papers doing the more complicated work of

evaluating the speeds of various attacks for various concrete sizes.

Beyond ECDL, there are many more examples (including many lattice

examples) of pairs (Q,R) where we know that

(1) Q in the worst case reduces to R in the average case and

(2) Q is completely broken.

The reason, as I mentioned before, is that the second feature logically

implies the first, and we have many examples of Q with the second

feature. Every interesting algorithm to completely solve a problem Q is

also an interesting worst-case-to-average-case reduction from Q to R.

Characterizing this reduction as "R is strong on average if Q is strong

in the worst case" is logically correct but vacuous: Q is _not_ strong.

Given this mountain of examples where worst-case-to-average-case

reductions are connected to breakability, I'm fascinated by claims that

worst-case-to-average-case reductions in some exceptional circumstances

actually indicate strength. I'd like to know

* what exactly those circumstances are supposed to be---a definition

clear enough that we can all figure out when the claims apply;

* how well the claims match known examples---of course this becomes

impossible to evaluate if the definition is unclear; and

* whether there's any other argument for the claim---of course

assessing this again relies on having a clear definition.

The whole point is to manage security risks, and it's important to

understand ways that people can draw incorrect conclusions about these

risks. For example:

* What if the reality is that worst-case-to-average-case reductions

of type T exist only for problems where there exist worst-case

attacks of type U? An interesting possibility to contemplate is T =

poly reductions, U = quantum poly-time attacks.

* This doesn't mean that the U attack is always obvious from the T

reduction. (As an illustration, Shor's algorithm to break ECDL has

important components beyond the worst-case-to-average-case ECDL

reduction.) Given this gap, presumably there will be cases where

the T reduction is known and the U attack isn't yet known.

* Someone searches through known worst-case-to-average-case

reductions of type T, discards all the cases where the the U attack

is known, and then concludes that the remaining U cases are secure.

This methodology is unscientific---it's pure confirmation bias,

just like "p-hacking"---and the conclusion is wrong.

Maybe the reality is different, and the conclusion is actually correct,

but the methodology provides no evidence for this.

The cryptanalytic literature follows a very different procedure. There's

still a step of picking an unbroken system, but this isn't the end of

the analysis. Quite the opposite! Someone formulates a challenge to

break the system, and then---hopefully---cryptanalysts look closely at

this challenge, and publish papers carefully saying what they've tried

and what the obstacles are. If there's enough attention over enough

years, and if all attack avenues seem to have reached their limits

without breaking the system, then we start to think that _maybe_ the

system is actually secure.

This process relies on the challenges being clearly enough defined that

cryptanalysts can tell when an algorithm with a particular input-output

relationship and a particular performance level constitutes a break of

the challenge. If the challenge relies on unclear words---e.g.,

"competently parameterized"---will any break be met by an assertion that

the thing being broken wasn't "competently parameterized"?

If there's a request for a challenge to be more clearly defined, then

whoever issued the challenge has a responsibility to either clarify or

withdraw the challenge. Same for security claims, security predictions,

etc. It's particularly bad if a poor methodology for assessing risks is

producing one incorrect security prediction after another, but is able

to use ambiguities in the predictions to hide this record of failure.

It's best if the predictions are clear in the first place.

So, to repeat: What exactly are the circumstances supposed to be where

worst-case-to-average-case reductions indicate strength, as opposed to

the aforementioned mountain of examples where they indicate weakness?

The latest claim sounds something like this, with serious ambiguities

that I would like to see resolved:

* if (S) you have a "system" (does it have to be some particular kind

of system, such as a PKE?), and

* it's (L) "lattice-based" (what exactly does this mean? for example,

does it include classic knapsacks? powerline? AJPS?), and

* it has (P) "concrete parameters" (this is clear but really weird---

see below), and

* the parameters are (C) "competent" (it's _extremely_ unclear how

we're supposed to evaluate this), then

* (R) having a worst-case-to-average-case reduction (which worst-case

problems are allowed here?) is supposed to be good rather than bad.

Specifically, there's a historical claim that no "unexpected" weaknesses

have never occurred in such systems _with_ such reductions, while they

_have_ occurred in "Merkle-Hellman, NTRUSign, and SOLILOQUY".

This claim would be contradicted/undermined by examples of past/future

weaknesses in S+L+P+C+R systems, although I suppose such examples would

then be met by retroactive claims that the weakness was "expected". I'd

like to see clarification of S+L+P+C+R+"expected".

It's possible that I'm misunderstanding a basic structural feature of

the claim: I'm phrasing the claim as R being good assuming S+L+P+C, but

the original wording could have been interpreted as instead saying that

C+R is good assuming S+L (or, in the latest revision, S+L+P). Since

"competent"---whatever exactly it means---is surely a very good thing,

claiming that C+R is good (assuming S+L or S+L+P) is entirely compatible

with R being bad. This is yet another point that needs clarification.

Here are six reasons that the focus on "concrete parameters"---rather

than asymptotics---is weird:

* This focus seems incompatible with the claim that SOLILOQUY has

already been broken. Quantum poly-time attacks are known (under

plausible assumptions), but the attack cost has not been computed

for any particular parameters. Maybe the polynomial is so large

that reasonable parameters still qualify for NIST category 5.

* The attack examples that have appeared in this discussion generally

have an impact that's instantly visible in asymptotics (and harder

to compute concretely). If there's some actual reason that R stops

such attacks assuming S+L+P+C, then it would be bizarre for this to

be something that can be seen only for concrete sizes and not

asymptotically.

* The worst-case-to-average-case reductions in the literature for,

e.g., Ring-LWE all appear to be content-free for the "concrete

parameters" in New Hope, Kyber, etc. There seems to be a claim

that such reductions help avoid "structural flaws"; how exactly are

"structural flaws" defined, if not asymptotically?

* If worst-case-to-average-case reductions for very large sizes are

supposed to be relevant to smaller sizes, why are attacks against

very large sizes not relevant? The asymmetry is deeply puzzling.

* The original claim was accompanied by an explicit "asymptotic

proofs" comment that seemed to be referring to these reductions.

Isn't it highly relevant to the risk analysis if the worst-case

problems end up being suddenly _broken_ for some asymptotic

parameter ranges, making the proofs vacuous for those ranges?

* I gave what I think is a lattice-based DH counterexample to the

original claim (no unexpected weaknesses in any lattice-based

difficult to analyze for concrete parameters than for asymptotic

parameters. In response, the claim was suddenly being treated as a

statement purely about concrete parameters.

With all due respect: This security claim does not currently meet, and

does not appear to be on a path to meeting, the standards of clarity and

stability that security evaluators demand.

Christopher J Peikert writes:

> But even if one were to consider the above asymptotics, it's still the

> case that the best known attacks on the system are conventional

> lattice-reduction attacks (with the usual linear speedups arising from

> ring symmetries). In particular, https://eprint.iacr.org/2016/885

> does not appear to apply to this system, as the paper itself says.

We seem to be in agreement regarding each of the following six bullet

items---please speak up if you disagree with something:

* The usual worst-case-to-average-case reduction for Ring-LWE is

applicable to this DH system. Whatever exactly "lattice-based"

means, surely this qualifies.

* Fundamentally, what the reduction theorem tells us is that the

lattice-based DH system is roughly as hard to break as a particular

worst-case problem. "Roughly" refers to a huge looseness factor,

eliminating applicability to small concrete sizes, but

asymptotically the theorem applies.

* The worst-case problem is approx-Ideal-SVP, and in particular

cyclotomic approx-Ideal-SVP when the DH system uses cyclotomics.

* https://eprint.iacr.org/2016/885 has a quantum attack against

cyclotomic approx-Ideal-SVP with approximation factors that look

like exp(n^(1/2+o(1))). Asymptotically, the attack takes poly time,

under plausible assumptions.

* Consequently, the "roughly as hard to break" statement is suddenly

known (under the same plausible assumptions) to be content-free for

quantum attacks against the corresponding parameters for the

cyclotomic DH system.

* This parameter range has optimal or near-optimal key size (optimal

at the level of detail of these asymptotics) for the cyclotomic DH

system for any particular security level against previous attacks.

To me this looks like a counterexample to your original claim. I still

don't know what "competently parameterized" is supposed to mean, but in

any case I don't see how you can use the word "incompetent" to refer to

optimal or near-optimal security-vs.-size tradeoffs against all previous

attacks.

Your response here appears to be that the attack in the paper is only

breaking the worst-case problem, not breaking the DH system. I agree

with this, but I don't see why it's supposed to be relevant. How does a

content-free worst-case-to-average-case reduction, a reduction from a

broken worst-case problem, provide any sort of security assurance?

A theorem reducing the worst case of Q to the average case of R is

devoid of all logical content if Q is broken: it tells us _nothing_

about the strength of R. Maybe R is strong; maybe not. In retrospect,

knowing a (provable) break in Q, we can prove a theorem reducing the

same Q to any selected broken average-case problem R'. This theorem

certainly doesn't say that R' is strong, and the original theorem

doesn't say that R is strong.

Maybe I should ask for clarification of the word "weakness". Suppose

submission R is advertised in part on the basis of a theorem saying "the

system is hard to break if worst-case problem Q is hard". Suppose Q is

then obliterated, removing all logical content from this theorem. That's

certainly a serious weakness in the advertising for R. It's certainly

something that will cast serious doubt on the R submission. Does this

not count as a "weakness" in R unless someone also shows that R is

broken? Is the word "weakness" being used as nothing more than a synonym

for "break"?

I have another example in mind where it seems to me that the proposed R

is also broken, but first I'll need to see clarification of "competently

parameterized" etc.---I'm not interested in spending more time on

cryptanalysis of a moving target.

More importantly, whether or not any particular R is broken, having

examples of Q suddenly collapse raises critical questions about the

alleged security benefits of worst-case-to-average-case reductions.

---Dan

simply add a random multiple of the base point. Similarly, there's a

fast worst-case-to-average-case reduction for NIST P-384 ECDL, etc.

These worst-case-to-average-case reductions are important tools in ECDL

attacks. See, e.g., https://blog.cr.yp.to/20151120-batchattacks.html.

The resulting security damage is clear---the well-known reduction of

ECDL attack cost from, asymptotically, p^(1+o(1)) to p^(1/2+o(1)). The

best pre-quantum ECDL attacks we know are slight optimizations of this:

they cost p^(1/2+o(1)) with a marginally smaller o(1).

As for quantum algorithms, Shor's algorithm reuses essentially the same

attack tools with additional quantum techniques to do even more damage,

reducing the ECDL attack cost to polynomial. This of course is a major

motivation for post-quantum cryptography.

I'm making simple asymptotic statements here: 1/2+o(1), polynomial, etc.

These asymptotic speedups imply speedups for every concrete size beyond

some limit. There are various papers doing the more complicated work of

evaluating the speeds of various attacks for various concrete sizes.

Beyond ECDL, there are many more examples (including many lattice

examples) of pairs (Q,R) where we know that

(1) Q in the worst case reduces to R in the average case and

(2) Q is completely broken.

The reason, as I mentioned before, is that the second feature logically

implies the first, and we have many examples of Q with the second

feature. Every interesting algorithm to completely solve a problem Q is

also an interesting worst-case-to-average-case reduction from Q to R.

Characterizing this reduction as "R is strong on average if Q is strong

in the worst case" is logically correct but vacuous: Q is _not_ strong.

Given this mountain of examples where worst-case-to-average-case

reductions are connected to breakability, I'm fascinated by claims that

worst-case-to-average-case reductions in some exceptional circumstances

actually indicate strength. I'd like to know

* what exactly those circumstances are supposed to be---a definition

clear enough that we can all figure out when the claims apply;

* how well the claims match known examples---of course this becomes

impossible to evaluate if the definition is unclear; and

* whether there's any other argument for the claim---of course

assessing this again relies on having a clear definition.

The whole point is to manage security risks, and it's important to

understand ways that people can draw incorrect conclusions about these

risks. For example:

* What if the reality is that worst-case-to-average-case reductions

of type T exist only for problems where there exist worst-case

attacks of type U? An interesting possibility to contemplate is T =

poly reductions, U = quantum poly-time attacks.

* This doesn't mean that the U attack is always obvious from the T

reduction. (As an illustration, Shor's algorithm to break ECDL has

important components beyond the worst-case-to-average-case ECDL

reduction.) Given this gap, presumably there will be cases where

the T reduction is known and the U attack isn't yet known.

* Someone searches through known worst-case-to-average-case

reductions of type T, discards all the cases where the the U attack

is known, and then concludes that the remaining U cases are secure.

This methodology is unscientific---it's pure confirmation bias,

just like "p-hacking"---and the conclusion is wrong.

Maybe the reality is different, and the conclusion is actually correct,

but the methodology provides no evidence for this.

The cryptanalytic literature follows a very different procedure. There's

still a step of picking an unbroken system, but this isn't the end of

the analysis. Quite the opposite! Someone formulates a challenge to

break the system, and then---hopefully---cryptanalysts look closely at

this challenge, and publish papers carefully saying what they've tried

and what the obstacles are. If there's enough attention over enough

years, and if all attack avenues seem to have reached their limits

without breaking the system, then we start to think that _maybe_ the

system is actually secure.

This process relies on the challenges being clearly enough defined that

cryptanalysts can tell when an algorithm with a particular input-output

relationship and a particular performance level constitutes a break of

the challenge. If the challenge relies on unclear words---e.g.,

"competently parameterized"---will any break be met by an assertion that

the thing being broken wasn't "competently parameterized"?

If there's a request for a challenge to be more clearly defined, then

whoever issued the challenge has a responsibility to either clarify or

withdraw the challenge. Same for security claims, security predictions,

etc. It's particularly bad if a poor methodology for assessing risks is

producing one incorrect security prediction after another, but is able

to use ambiguities in the predictions to hide this record of failure.

It's best if the predictions are clear in the first place.

So, to repeat: What exactly are the circumstances supposed to be where

worst-case-to-average-case reductions indicate strength, as opposed to

the aforementioned mountain of examples where they indicate weakness?

The latest claim sounds something like this, with serious ambiguities

that I would like to see resolved:

* if (S) you have a "system" (does it have to be some particular kind

of system, such as a PKE?), and

* it's (L) "lattice-based" (what exactly does this mean? for example,

does it include classic knapsacks? powerline? AJPS?), and

* it has (P) "concrete parameters" (this is clear but really weird---

see below), and

* the parameters are (C) "competent" (it's _extremely_ unclear how

we're supposed to evaluate this), then

* (R) having a worst-case-to-average-case reduction (which worst-case

problems are allowed here?) is supposed to be good rather than bad.

Specifically, there's a historical claim that no "unexpected" weaknesses

have never occurred in such systems _with_ such reductions, while they

_have_ occurred in "Merkle-Hellman, NTRUSign, and SOLILOQUY".

This claim would be contradicted/undermined by examples of past/future

weaknesses in S+L+P+C+R systems, although I suppose such examples would

then be met by retroactive claims that the weakness was "expected". I'd

like to see clarification of S+L+P+C+R+"expected".

It's possible that I'm misunderstanding a basic structural feature of

the claim: I'm phrasing the claim as R being good assuming S+L+P+C, but

the original wording could have been interpreted as instead saying that

C+R is good assuming S+L (or, in the latest revision, S+L+P). Since

"competent"---whatever exactly it means---is surely a very good thing,

claiming that C+R is good (assuming S+L or S+L+P) is entirely compatible

with R being bad. This is yet another point that needs clarification.

Here are six reasons that the focus on "concrete parameters"---rather

than asymptotics---is weird:

* This focus seems incompatible with the claim that SOLILOQUY has

already been broken. Quantum poly-time attacks are known (under

plausible assumptions), but the attack cost has not been computed

for any particular parameters. Maybe the polynomial is so large

that reasonable parameters still qualify for NIST category 5.

* The attack examples that have appeared in this discussion generally

have an impact that's instantly visible in asymptotics (and harder

to compute concretely). If there's some actual reason that R stops

such attacks assuming S+L+P+C, then it would be bizarre for this to

be something that can be seen only for concrete sizes and not

asymptotically.

* The worst-case-to-average-case reductions in the literature for,

e.g., Ring-LWE all appear to be content-free for the "concrete

parameters" in New Hope, Kyber, etc. There seems to be a claim

that such reductions help avoid "structural flaws"; how exactly are

"structural flaws" defined, if not asymptotically?

* If worst-case-to-average-case reductions for very large sizes are

supposed to be relevant to smaller sizes, why are attacks against

very large sizes not relevant? The asymmetry is deeply puzzling.

* The original claim was accompanied by an explicit "asymptotic

proofs" comment that seemed to be referring to these reductions.

Isn't it highly relevant to the risk analysis if the worst-case

problems end up being suddenly _broken_ for some asymptotic

parameter ranges, making the proofs vacuous for those ranges?

* I gave what I think is a lattice-based DH counterexample to the

original claim (no unexpected weaknesses in any lattice-based

system that "competently parameterized" a scheme having a

worst-case reduction). This counterexample is clearly more
difficult to analyze for concrete parameters than for asymptotic

parameters. In response, the claim was suddenly being treated as a

statement purely about concrete parameters.

With all due respect: This security claim does not currently meet, and

does not appear to be on a path to meeting, the standards of clarity and

stability that security evaluators demand.

Christopher J Peikert writes:

> But even if one were to consider the above asymptotics, it's still the

> case that the best known attacks on the system are conventional

> lattice-reduction attacks (with the usual linear speedups arising from

> ring symmetries). In particular, https://eprint.iacr.org/2016/885

> does not appear to apply to this system, as the paper itself says.

items---please speak up if you disagree with something:

* The usual worst-case-to-average-case reduction for Ring-LWE is

applicable to this DH system. Whatever exactly "lattice-based"

means, surely this qualifies.

* Fundamentally, what the reduction theorem tells us is that the

lattice-based DH system is roughly as hard to break as a particular

worst-case problem. "Roughly" refers to a huge looseness factor,

eliminating applicability to small concrete sizes, but

asymptotically the theorem applies.

* The worst-case problem is approx-Ideal-SVP, and in particular

cyclotomic approx-Ideal-SVP when the DH system uses cyclotomics.

* https://eprint.iacr.org/2016/885 has a quantum attack against

cyclotomic approx-Ideal-SVP with approximation factors that look

like exp(n^(1/2+o(1))). Asymptotically, the attack takes poly time,

under plausible assumptions.

* Consequently, the "roughly as hard to break" statement is suddenly

known (under the same plausible assumptions) to be content-free for

quantum attacks against the corresponding parameters for the

cyclotomic DH system.

* This parameter range has optimal or near-optimal key size (optimal

at the level of detail of these asymptotics) for the cyclotomic DH

system for any particular security level against previous attacks.

To me this looks like a counterexample to your original claim. I still

don't know what "competently parameterized" is supposed to mean, but in

any case I don't see how you can use the word "incompetent" to refer to

optimal or near-optimal security-vs.-size tradeoffs against all previous

attacks.

Your response here appears to be that the attack in the paper is only

breaking the worst-case problem, not breaking the DH system. I agree

with this, but I don't see why it's supposed to be relevant. How does a

content-free worst-case-to-average-case reduction, a reduction from a

broken worst-case problem, provide any sort of security assurance?

A theorem reducing the worst case of Q to the average case of R is

devoid of all logical content if Q is broken: it tells us _nothing_

about the strength of R. Maybe R is strong; maybe not. In retrospect,

knowing a (provable) break in Q, we can prove a theorem reducing the

same Q to any selected broken average-case problem R'. This theorem

certainly doesn't say that R' is strong, and the original theorem

doesn't say that R is strong.

Maybe I should ask for clarification of the word "weakness". Suppose

submission R is advertised in part on the basis of a theorem saying "the

system is hard to break if worst-case problem Q is hard". Suppose Q is

then obliterated, removing all logical content from this theorem. That's

certainly a serious weakness in the advertising for R. It's certainly

something that will cast serious doubt on the R submission. Does this

not count as a "weakness" in R unless someone also shows that R is

broken? Is the word "weakness" being used as nothing more than a synonym

for "break"?

I have another example in mind where it seems to me that the proposed R

is also broken, but first I'll need to see clarification of "competently

parameterized" etc.---I'm not interested in spending more time on

cryptanalysis of a moving target.

More importantly, whether or not any particular R is broken, having

examples of Q suddenly collapse raises critical questions about the

alleged security benefits of worst-case-to-average-case reductions.

---Dan

Dec 9, 2017, 6:00:56 PM12/9/17

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

Hi Dan.

Since you are in fact subscribed to this list, can you adjust your script to not auto generate a reply to this list?

Your qmail script is flooding my inbox.

Thank you.

-------- Original message --------

From: "D. J. Bernstein" <d...@cr.yp.to>

Date: 12/09/2017 4:29 PM (GMT-06:00)

To: pqc-...@list.nist.gov

--

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

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

Dec 9, 2017, 7:13:18 PM12/9/17

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

CSO writes:

> Your qmail script is flooding my inbox.

Just checking: By "flooding" you're referring to the fact that---in
> Your qmail script is flooding my inbox.

response to several messages that you sent not just to the list but also

to d...@cr.yp.to, which is heavily spam-protected---you've received

several bounce messages?

Since, as you note, I'm a pqc-forum subscriber, I'm not sure why you're

sending copies of your pqc-forum messages to d...@cr.yp.to. I'd suggest

that you edit the recipient list on your outgoing mail appropriately.

Alternatively, you can ask the provider of your mail software to support

Mail-Followup-To, so that this editing happens automatically (since my

mail to the list has Mail-Followup-To set appropriately). In case

someone mentions the older idea of having the list overwrite Reply-To,

let me add that I don't like this, since it interferes with standard use

of Reply-To by people who want replies going to a different address.

In checking mail logs I noticed another issue of potentially broader

interest: the mailing-list management system seems to conflate two

separate concepts, namely

* subscription addresses and

* addresses allowed to post.

This is important for people who use private subscription addresses.

Forcing postings to come from the same address reveals the address to

spammers, which NIST shouldn't be doing. Adding a public address as a

subscription address, so as to allow postings from that address, means

generating list mail to that address, which is precisely what the

private subscription addresses are meant to replace.

In my mail logs I see the list sending messages to d...@cr.yp.to (which

is not what I requested), and bounce messages from d...@cr.yp.to going

back to a "bnc" address set by Google. Some bounce-handling tools would

end up removing the subscription address. It seems that the Google

bounce-handling software doesn't do this, so in the end there's simply

some minor waste of computer time, but other people with lighter spam

filtering on their public addresses would find this quite annoying.

---Dan

Dec 9, 2017, 7:22:15 PM12/9/17

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

So you're saying you can't white list responses from lists you belong to sent by other members.

--

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

Reply all

Reply to author

Forward

0 new messages