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

Hi,

I read that Nature paper at the time it appeared. It was not clear to me that they had actually factored any number larger than 143 using a D-wave machine. Certainly, the paper presents no experimental data beyond N=143 (for which case, see Figure 3, but with no data concerning success probabilities, numbers of experiments, etc).

So I sent the authors some basic questions about scaling and about details of their computations and experiments. (Naturally I first tried to establish my scientific credentials so as not to look like too much of a crank.)

I also asked the authors for data concerning the larger and more impressive numbers mentioned throughout the paper (e.g. 249919).

The authors did not provide this information, in contrast to the statement made towards the end of the paper concerning data availability:

“The data that support the plots within this paper and other findings of this study are available from the corresponding author upon reasonable request.”

Readers may draw their own conclusions from this.

Cheers,

Kenny

PS for those wondering, 143 = 13*11.

From: Cfrg <cfrg-bounces@irtf.org> on behalf of mcgrew <mcgrew@cisco.com>
Date: Monday, 15 April 2019 at 21:11
To: Ruslan Kiyanchuk <ruslan.kiyanchuk@gmail.com>
Cc: Björn Haase <bjoern.haase@endress.com>, CFRG <cfrg@irtf.org>, Peter Gutmann <pgut001@cs.auckland.ac.nz>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

Hi Ruslan,

On Apr 15, 2019, at 2:04 PM, Ruslan Kiyanchuk <ruslan.kiyanchuk@gmail.com<mailto:ruslan.kiyanchuk@gmail.com>> 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 <uri@ll.mit.edu<mailto:uri@ll.mit.edu>> 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

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" <pgut001@cs.auckland.ac.nz<mailto:pgut001@cs.auckland.ac.nz>> wrote:

    Björn Haase <bjoern.haase@endress.com<mailto:bjoern.haase@endress.com>> 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
Cfrg@irtf.org<mailto:Cfrg@irtf.org>
https://www.irtf.org/mailman/listinfo/cfrg
_______________________________________________
Cfrg mailing list
Cfrg@irtf.org<mailto:Cfrg@irtf.org>
https://www.irtf.org/mailman/listinfo/cfrg