[Cryptography] NSA looking for quantum-computing resistant encryption. How will encryption be affected by quantum computing

[ianG]

On 2/09/2015 17:51 pm, Steve Weis wrote:
> On Wed, Sep 2, 2015 at 8:47 AM, ianG <iang at iang.org> wrote:
>> On 31/08/2015 17:36 pm, Jerry Leichter wrote:
>>> Just for comparison:
>>>    The current record for factoring an integer using a quantum computer
>>> is 56153, which you could factor by hand.
>>
>> Seems to be some discordance on that one - any chance of a cite?
>
> This is the paper "Quantum factorization of 56153 with only 4 qubits":
> http://arxiv.org/pdf/1411.6758v3.pdf
>
> The authors rely on the factors of 56153 only differing in two
> different bit positions (233 = 0b11101001, 241 = 0b11110001). They can
> only factor composites with that special form (e.g. 143, 3599, 11663).
> As the authors say in the paper: "[U]nless we know in advance that the
> factors will differ at two bits, this reduction will not allow us to
> crack big RSA codes." They also acknowledge that this "can easily be
> solved by a classical computer, since there are only 4 variables".


Hmmm, which could be considered a weak keys test, if one was worried 
about the generality of the result.

> As far as I know, the record of factoring with Shor's algorithm is 21
> and described in this paper:
> http://www.nature.com/nphoton/journal/v6/n11/abs/nphoton.2012.259.html
>
> Here's a poster of their results:
> http://new.qcmc2012.org/wp-content/uploads/2012/08/Poster_Martin-Lopez.pdf


Excellent summary, thanks!

iang