Re: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE, CPACE, J-PAKE)

On Sun, Sep 8, 2019 at 9:14 AM Hao, Feng <Feng.Hao@warwick.ac.uk> wrote:
>
>
>
>
> How much harder are many logs then one on a quantum computer? Not very.
>
>
>
> I believe that it is about one million times harder to do one million discrete logs than it is to do one (given that Shor’s algorithm doesn’t generate any side information from one run that would help you with the next; I also can’t think of any way to combine N points, and solve fewer than N discrete logs in a way that would allow you to recover the DLogs of the original N points).
>
>
>
> Looking at the likely progression of Quantum Computers, it appears probable that, once someone creates a real one (as opposed to the toys that exist now), they could break a ECDLog problem, but it may take weeks to do so (and there are not likely to be a number of them available).  Hence, one a TLA gets one, it might gain the capability to solve dozens of ECDlog problems a year, but no more than that; hence this vulnerability of SPAKE2 might be relevant.  Now, this is entirely speculation, and also it would be reasonable to suspect that the speed/cost of QCs would rise/drop fairly rapidly, and so a few years after that it might be feasible to attack the other schemes as well (at least for their high-value targets).  This scenario did seem plausible enough for me to mention it.
>
>
>
> In addition, for most other methods, it may be that a single discrete log might not be sufficient to break a single instance of the other schemes; however that really is currently speculation, as I have not seriously studied the issue, nor do I know anyone else who has
>
>
>
> IMHO, the threat is not so much a quantum computer, but a state actor (a three-letter agency) who breaks one instance of DL simply by brute-force, which will be justified if this single attack allows the adversary to break everywhere.

Maybe you shouldn't use brute-forceable parameters? Making a DLOG
instance in the prequantum world a billion times harder is simple: add
32 bytes.

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

--
"Man is born free, but everywhere he is in chains".
--Rousseau.