[Cryptography] SHA-3 FIPS-202: no SHAKE512 but SHAKE128; confusing SHAKE security

[Samuel Neves]

On 08/17/2015 06:56 PM, Viktor Dukhovni wrote:
> For the record I don't see a compelling difference between a 112-bit
> work-factor and a 128-bit work-factor, provided the estimates hold
> up reasonably well.  Also it seems that memory requirement for the
> matrix stage of GNFS for large moduli are quite prohibitive.  Are
> the work-factor estimates for large RSA moduli too conservative?

It is arguable that the metric used, which only cares about operation counts, is not the right one. For typical
parameter choices the storage cost (aka machine size) of the NFS is roughly proportional to the square root of the
computational cost. To see this, note that the cost of the matrix step is matrix_size^(2 + o(1)), and the matrix step is
asymptotically as costly as sieving. So at 15k bits, we get ~2^256 time complexity and ~2^128 memory. Multiplying area
and time, the asymptotic cost here is L[1/3, 2.85], much larger than the L[1/3, 1.901] usually advertised.

Taking the machine size into account gets you to the circuit or batch NFS, whose complexity is worked out in the AT
(area-time) metric. For a single 15k-bit factorization this gets you time ~2^165 on a machine of size ~2^110 (as usual,
ignoring o(1) factors in the asymptotic complexities). The asymptotic AT cost here is L[1/3, 1.976]. 12288-bit keys
would suffice to thwart an attack of AT cost significantly below 2^256; 5120-bit keys would be enough for 256-bit AT
security against the conventional, non-circuit, NFS.