Subject: Re: [Cfrg] New guidance from NSA on cryptographic algorithms

From: Ryan Carboni <[email-masked]>
Date: Fri, 14 Aug 2015 17:42:34 -0700

I wouldn't be surprised if a time-memory-data (or maybe just
 time-date) tradeoff has been discovered by the NSA for quantum
 computers. But errant speculation shouldn't be used for anything other
 than caution or prudence.

 Given the typical webpage is about 1 megabyte in size now, this makes
 McEliece cryptosystems rather viable now, and it's much faster than
 RSA.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Sat, 15 Aug 2015 03:28:31 +0000

Actually, that’s sublinear scale; that is, N parallel quantum computers, if used jointly to attack a problem, can solve the search problem sqrt(N) times as fast as a single one.

Here is how it works out: suppose we have oneQuantum Computer to search over a space of 2**128; by Grover’s algorithm, this takes O(2**64) time.

Now, consider if we expand our resources to one million (2**20) Quantum Computers.  One approach we can take is to divide the search space into sections of 2**108 each, and assign each subspace to a QC.  Each QC can search its subspace in O(2**108) time, which is O(2**54) time (with the O notation hiding the same constants); hence by adding a million quantum computers, we’ve sped the search by a thousand.

The point of the paper is that this approach is essentially optimal.

From: Cfrg [mailto:[email-masked]] On Behalf Of Mehmet Adalier (Antara Teknik)
Sent: Friday, August 14, 2015 8:24 PM
To: Andy Lutomirski; Mike Hamburg
Cc: [email-masked]; Russ Housley
Subject: Re: [Cfrg] New guidance from NSA on cryptographic algorithms

my understanding is that the paper claims that attempting to parallelize Grover on a single quantum computer does not provide benefits.

however, the paper describes that the search space can be divided into sub-searches and each sub-search executed independently, in parallel, on multiple systems (i.e. a cluster of quantum computers) --which should deliver linear scale.

"This shows that to get a certain success probability we can gain only a factor of √S in T by using S oracles, but this is essentially the same performance as S independent Grover searches, each working on one Sthof the total search space. "

so entities that could afford a (yet-to-be-invented) cluster of quantum computers could do the search in parallel

mehmet

________________________________
From: Andy Lutomirski <[email-masked]<mailto:[email-masked]>>
To: Mike Hamburg <[email-masked]<mailto:[email-masked]>>
Cc: Russ Housley <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]>
Sent: Friday, August 14, 2015 5:12 PM
Subject: Re: [Cfrg] New guidance from NSA on cryptographic algorithms

On Aug 14, 2015 4:44 PM, "Michael Hamburg" <[email-masked]<mailto:[email-masked]>> wrote:
>
>
>> On Aug 14, 2015, at 2:46 PM, Andy Lutomirski <[email-masked]<mailto:[email-masked]>> wrote:
>>
>> On Fri, Aug 14, 2015 at 2:41 PM, Michael Hamburg <[email-masked]<mailto:[email-masked]>> wrote:
>>>
>>>
>>>> On Aug 14, 2015, at 2:29 PM, Andy Lutomirski <[email-masked]<mailto:[email-masked]>> wrote:
>>>>
>>>> On Fri, Aug 14, 2015 at 2:08 PM, Russ Housley <[email-masked]<mailto:[email-masked]>> wrote:
>>>>>
>>>>> See https://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml
>>>>>
>>>>> This guidance suggests mitigation against a yet-to-be-invented quantum computer that will be able to attack existing cryptographic algorithms.
>>>>>
>>>>> I am posting this here because some CFRG participants may be interested in developing ways to add quantum-resistance existing key establishment techniques.
>>>>>
>>>>
>>>> I don't like some of these recommendations.
>>>>
>>>> (Disclaimer: I really did study quantum crypto.  OTOH, I didn't check
>>>> my work here very carefully.)
>>>>
>>>>
>>>> AES: Use 256 bit keys to protect up to TOP SECRET
>>>>
>>>> That's not enough.  If you attack N ciphertexts at once, then any
>>>> trial key has probability 2^256/N of matching one.  Grover search
>>>> finds a match in ~sqrt(2^256/N) tries (there's factor of 4 or so in
>>>> there, but that doesn't matter much).  This isn't a comfortable margin
>>>> as N approaches, say, 2^64.  I think people should use at least
>>>> 384-bit symmetric keys to defend against this type of attack.
>>>
>>>
>>> But Grover only square-roots the time required, right?  Not the space?  So if you have 2^32 quantum computers and 2^64 plaintexts, you still need to run them for 2^80 cycles, right?  That sounds like 50 year protection to me…
>>
>>
>> It square roots the number of queries.  The standard Grover algorithm
>> is serial, but I wouldn't be surprised if there were some way to get
>> at least a bit of parallelism out of it.  But yeah, without some kind
>> of parallelization, the actual running time might still be excessive.
>> I don't think space matters too much, though -- you can just ask "does
>> AES_k(0) hash to something such-and-such".
>>
>> --Andy
>
>
> I should have said area rather than space, though it’s not obvious that
> "hashing to something such-and-such” gives free compression of the
> 2^64 preimages.
Hmm, I was thinking about it wrong.  A classical machine can check membership in a set quickly -- just implement a hash table in memory.  Multiple threads can share the memory.  A quantum machine has a bit more trouble, since you have to activate all memory cells for each query.
So maybe area * time is still pretty bad.
>
> I was curious if anyone on this list knows of a parallel Grover, but
>
> http://arxiv.org/abs/quant-ph/9711070
>
> claims to show that it is impossible.
>
I'll have to read that.

--Andy
> — Mike

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://mail.ietf.org/mailman/listinfo/cfrg

---

From: Ryan Carboni <[email-masked]>
Date: Fri, 14 Aug 2015 23:01:49 -0700

>
> Actually, that’s sublinear scale; that is, N parallel quantum computers,
> if used jointly to attack a problem, can solve the search problem sqrt(N)
> times as fast as a single one.

But if Grover's algorithm was strictly the algorithm the NSA is afraid of,
that wouldn't be a concern?

Assuming the cost of a single quantum computation is equal 2^16 times that
of a classical computation (a gross underestimate given cooling costs),
that would mean the cost of bruteforcing 128-bit AES would be equal to the
cost of 2^80 classical computations. Naturally I have no idea, and would
have no idea, but the whole argument behind ending DES was economics, right?

Against Grover's algorithm, AES-128 would be secure until the cost of
quantum computation becomes much smaller, which doesn't seem likely within
decades. And even DES was approved to protect unclassified material, so
there must be a reason why Suite B has been revised to AES-256 for "Use 256
bit keys to protect up to TOP SECRET." Given the volume of data the NSA
handles, there must be a good reason for it. Classical computations haven't
kept up with the generation of intelligence.

But you know, Google owns a quantum computer, they might know a bit more
about cost projections than I do. And some IETF/IRTF members might know
some people from Google, right?

---

From: Ryan Carboni <[email-masked]>
Date: Sun, 16 Aug 2015 07:11:54 -0700

You are correct. I am clearly wrong. Therefore that argument is incorrect,
and I shall sit quietly in the peanut gallery to wait until everyone else
comes up with a better explanation than I could come up with.