Re: [Cfrg] A big, big Elliptic Curve

Hi,

I noticed that Roetteler et al. have now published their work and that the verdict seems to have changed again. The current understanding is now that RSA offers slightly more quantum security than ECC (at a comparable classical security level), but that the margin is much smaller than previously claimed by Proos and Zalka.

https://arxiv.org/pdf/1706.06752.pdf

An overview of the required number of qubits and Toffoli gates can be found in Table 2.

Cheers,
John

On 2016-04-11, 05:22, "Cfrg on behalf of Tanja Lange" <cfrg-bounces@irtf.org on behalf of tanja@hyperelliptic.org> wrote:

    > As mentioned in the meeting, QC attacks don't use the same algorithms
    > as conventional attacks and so the difficulty of breaking Curve 25519
    > is considerably less than breaking RSA2048.
    > 

    Could you point me to sources for this? There is an old paper by
    Proos and Zalka which has claims like this, but more recent work
    by Roetteler and Steinwandt properly considers reversibility and 
    ends up taking longer (time & qubits) for a 160 bit curve than 
    1024 bit RSA. They did detailed work for binary curves and last
    I talked to them were looking into odd characteristic. The jury
    is still out for larger curves and larger RSA but between a
    256-bit curve DLP and a 2048 RSA; I'd be surprised if RSA was 
    harder.

    > Interpreting the NSA advice is error prone. But the straight reading
    > would be 'we think it more likely that a quantum computer will be
    > built that can break current ECC schemes before someone works out how
    > to break RSA 3096.
    >
    If I take them at face value they basically say: Don't complain 
    if we ask you to upgrade to new crypto soon; here, as a concession 
    you may continue using the old stuff as long as it is not super 
    small. 

    I'd rather not speculate about their intention and whether those 
    are in our interest or not.

    	Tanja 

    _______________________________________________
    Cfrg mailing list
    Cfrg@irtf.org
    https://www.irtf.org/mailman/listinfo/cfrg