> -----Original Message----- > From: Michael Richardson [mailto:[email protected]] > Sent: Wednesday, August 24, 2016 1:08 AM > To: Derek Atkins > Cc: Paul Hoffman; [email protected]; Paul Wouters; Tero Kivinen; Scott Fluhrer > (sfluhrer) > Subject: Re: [IPsec] 4307bis/7321bis key sizes > > > Derek Atkins <[email protected]> wrote: > >> The proposed change is based on the existence of quantum computers > that > >> have a sufficient number of properly-interacting qbits. We have > >> literally no idea if those computers will ever exist. All current data > >> indicates that we will see the progressing of "sufficient number" and > >> "properly-interacting" and be able to increase key sizes well ahead of > >> widespread use of quantum computers. > > > Just to play devil's advocate here, are you implying that we'll see a > > 5-10-year lead time on quantum computer development sufficiently in > order > > to spend those 5-10 years: > > 1) having this discussion again, > > 2) revving the documents > > 3) getting the revved documents through the process > > 4) getting the revved documents published > > 5) getting the revved documents implemented > > 6) getting that new implementation into the field, and (most > importantly) > > 7) getting the OLD hardware decommissioned? > > Forgive my ignorance here; my BSc in particle physics is ~20 years out of > date. > (this %#@*$ internet thing distracted me...) > > My understanding is we currently have a small number of qbits "properly- > interacting". I think that I read an article saying it was 4 or so, but I > just read > that we are at 12 qbits in 2006, 28 in 2007 (maybe), and >1000 in 2015 > (maybe). On the other hand, "2 qubit silicon gate" in 2016. > > I believe that we need 128 to interact to break AES-128?
Actually, rather more than that; see http://arxiv.org/pdf/1512.04965.pdf for one rather detailed estimate. However, it doesn't appear that the number of qbits is the limiting factor; instead, it is simply time. The best known quantum attack against AES is Grover's algorithm; against AES-128, that would take O(2**64) entangled evaluations of AES (where the constant of proportionality is somewhat larger than 1). In contrast, AES-256 would take O(2**128) such evaluations; we generally agree that performing that many operations is infeasible for any practical attacker, and so we consider AES-256 safe. Actually, it's even worse than that for the attacker, even for AES-128; Grover's algorithm isn't parallelizable, and so instead of 2**64 operations spread over a large computing cluster, we're talking about 2**64 run on a single thread, and that's far more difficult. There's no known parallelized approach that's better than dividing up the keyspace into 2**k regions, and running a separate instance of Grovers over each region (using 2**k independent quantum computers); this ends up taking 2**(128-k)/2 time. If the bound on the number of evaluations a single quantum computer can do is 2**50 (for example, 2**25 evaluations per second for a year), then the attacker will need 2**28 separate quantum computers. Does this mean that attacking AES-128 is infeasible? No; there are too many unknowns involved; it should be clear that applying the same argument to AES-256 implies that the attacker has no hope. > > I'm just trying understand how the revolution that will take us from ~12 to > 128, won't take us to 256 the following week. > > I feel kinda like we are re-arranging the chairs on the titanic here. No, the debate between AES-128 and AES-256 is more like "AES-128 *might* be quantum secure; AES-256 is (baring some unexpected crypto development) *very* secure" > > -- > ] Never tell me the odds! | ipv6 mesh networks [ > ] Michael Richardson, Sandelman Software Works | network architect [ > ] [email protected] http://www.sandelman.ca/ | ruby on rails > [ > _______________________________________________ IPsec mailing list [email protected] https://www.ietf.org/mailman/listinfo/ipsec
