Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

[mcgrew <[e-mail]>]

Hi Ruslan,

> On Apr 15, 2019, at 2:04 PM, Ruslan Kiyanchuk <[e-mail]> wrote:
> 
> @Uri, the link statement reads fishy. I am also not a professional quantum physicist, but my understanding was that D-Wave computers can only do quantum annealing, which makes them applicable to a very narrow set of quantum problems, and makes them unsuitable for running Shor's or Grover's algorithms, which are not quantum annealing problems. At least that's how it used to be couple of years ago. Did D-Wave broaden the scope of their computers recently?

It is not that D-Wave can run Shor’s algorithm, but rather that researchers are studying how an adiabatic quantum computer can be used for factoring.  See for instance "Quantum Annealing for Prime Factorization”, https://www.nature.com/articles/s41598-018-36058-z:
We have developed a framework to convert an arbitrary integer factorization problem to an executable Ising model by first writing it as an optimization function then transforming the k-bit coupling (k ≥ 3) terms to quadratic terms using ancillary variables. Our resource-efficient method uses O(log_2(N)) binary variables (qubits) for finding the factors of an integer N. We present how to factorize 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits, respectively. This method was tested using the D-Wave 2000Q for finding an embedding and determining the prime factors for a given composite number.  

David

> 
> On Mon, Apr 15, 2019 at 9:09 AM Blumenthal, Uri - 0553 - MITLL <[e-mail] <mailto:[e-mail]>> wrote:
> While not a quantum physicist myself, I do think you are downplaying the risks:
> 
> https://www.insidequantumtechnology.com/news/new-hope-quantum-computers-factorizations-rsa-thousand-fold-excess/?utm_source=IQT+Daily+Newsletter&utm_campaign=a7528b4239-RSS_EMAIL_CAMPAIGN&utm_medium=email&utm_term=0_e8f238b4dd-a7528b4239-72197729 <https://www.insidequantumtechnology.com/news/new-hope-quantum-computers-factorizations-rsa-thousand-fold-excess/?utm_source=IQT+Daily+Newsletter&utm_campaign=a7528b4239-RSS_EMAIL_CAMPAIGN&utm_medium=email&utm_term=0_e8f238b4dd-a7528b4239-72197729> 
> 
> I understand Peter's point that unlike QC, attacks against implementations are really bad *now* (and probably will stay that way), but that's not an excuse to ignore the upcoming threat on the algorithmic level.
> --
> Regards,
> Uri 
> 
> On 4/14/2019, 23:37, "Peter Gutmann" <[e-mail] <mailto:[e-mail]>> wrote:
> 
>     Björn Haase <[e-mail] <mailto:[e-mail]>> writes:
> 
>     >Saying this, I think that it is important to have researchers working on PQ-
>     >Crypto such that we have a solution "in the box", even if the actual
>     >probability that we'd actually need it might be small..
> 
>     If it was researchers publishing via standard academic venues that'd be fine,
>     the problem is that the CFRG is a de facto standards body so anything
>     published will become an Internet standard.  At that point the yet-to-be-
>     given-a-cool-name rule [0] which says that the best crypto is the latest
>     trendiest bleeding-edge stuff and not the long-established stuff that we have
>     a lot of experience with will kick in, and whatever PQC is written up will
>     start being deployed and rushed into production before the RFC is even
>     published.
> 
>     The end result will be the worst of both worlds, we'll have a bunch of PQC
>     algorithms that work nothing like existing stuff so that people will be able
>     revisit thirty years of mistakes in applying it, alongside the existing crypto
>     that also needs to be supported.
> 
>     So standardising PQC at this point is hugely premature.  Leave it for academic
>     conferences from which it can be pulled as required, but don't give
>     implementers an excuse to re-make all the mistakes that have been made in the
>     past with an entirely new set of algorithms.
> 
>     Peter.
> 
>     [0] Suggestions for a name welcome, currently "The Hipster Crypto Rule" but
>         I'm not too happy with that.
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail] <mailto:[e-mail]>
> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg