[Pqc-forum] qrom security etc.

[D. J. Bernstein]

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.

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

[Ian Malloy]

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
>

[D. J. Bernstein]

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

[Edoardo Persichetti]

Thanks Dan for raising the matter.

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/.

[Moody, Dustin (Fed)]

>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

[I M]

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.

[I M]

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.

[Yongge Wang]

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

[I M]

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.

[Mike Hamburg]

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.

[I M]

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.

Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-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.

[D. J. Bernstein]

> 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.

The easy question is what sort of _attacks_ are considered. Quantum
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

[Yongge Wang]

> 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.

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.

https://eprint.iacr.org/2004/152.pdf )

thanks and apology if the comments make no sense.

Yongge

[I M]

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. 

[Christopher J Peikert]

> 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
"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

[CSO]

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.

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

[CSO]

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

https://arxiv.org/abs/1609.08684

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.

[D. J. Bernstein]

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
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

[D. J. Bernstein]

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

[Christopher J Peikert]

> 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
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.

[Christopher J Peikert]

> 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,
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?

(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.

[D. J. Bernstein]

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

[D. J. Bernstein]

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

[Christopher J Peikert]

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

[Christopher J Peikert]

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
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.

I have already said so quite clearly: when we have good reason to
believe that the worst-case problem is very hard.

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

[Henry de Valence]

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,

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

[CSO]

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

[CSO]

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>

Cc: pqc-...@list.nist.gov
Subject: Re: [pqc-forum] Gauss

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

Sincerely yours in cryptography,
Chris

[D. J. Bernstein]

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.

Gauss encountered some 2-dimensional lattices and applied a simple
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

[I M]

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.

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

[jonasweber86]

Henry,

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

https://medium.com/@hdevalence/when-hell-kept-on-payroll-somewhere-is-where-you-are-f419d3022d0

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

Jonas

[I M]

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. 

--

[jonasweber86]

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.

[I M]

Thank you. 

I'm sure we all appreciate it. 

--

[Christopher J Peikert]

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
of what I wrote, but alas, Brandolini's Law remains in effect.

[D. J. Bernstein]

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

[Christopher J Peikert]

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
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).

[Christopher J Peikert]

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.

[D. J. Bernstein]

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

[Christopher J Peikert]

> 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
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 often sets the parameters based on the best known attacks"

and

"One usually sets concrete parameters by cryptanalysis via known or
extrapolated attacks"

and

"...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
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."

I'm not sure how to make it any clearer. The rest of your message is
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.

As you point out, this system does not have any known
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))).

Lyubashevsky roughly estimated the *concrete* key sizes for a
*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.

[D. J. Bernstein]

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

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.

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

[CSO]

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.

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

[D. J. Bernstein]

CSO writes:
> Your qmail script is flooding my inbox.

Just checking: By "flooding" you're referring to the fact that---in
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

[I M]

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.

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