Microsoft Research published an approach to Quantum-safe TLS here, namely RLWE-ECDSA-AES128-GCM-SHA256.

One highlight is that when it's used with ECC, there is only a slight performance hit.

Assuming this becomes a popular way to have quantum-safe TLS, how important is it that manufacturers optimize for this?... in other words, is a brand new CPU instruction needed, or will the existing cryptographic instructions be sufficient?

As a layman, I'm trying to get an idea how long it would take to get quantum safe TLS on a mobile device, where power and other constraints apply.

My assumption is if websites aggressively implement RLWE-ECDSA-AES128-GCM-SHA256, battery life and performance will suffer on most phones, until the hardware market catches up.

  • $\begingroup$ Please note that this proposal is not quantum safe TLS,. It has only quantum safe forward secrecy . Authentication is still only classically secure. $\endgroup$
    – user27950
    Aug 16 '17 at 18:09

Ring LWE schemes are relatively simple on a computation level -- the large majority of time is spent doing vector multiplication (another significant portion is sampling the error distribution). This is ideal for parallelization. So typically, RLWE implemented using the AVX2 instruction sets are significantly faster (for example, see a 3x speed improvement for one popular RLWE scheme: New Hope). I'm not sure on the ubiquity of AVX2 instructions on mobile devices, perhaps someone else can chime in.

That said, RLWE just isn't very computationally expensive in general. The paper above mentions that in terms of performance, the AVX2 implementation is in "the same ballpark" as state of the art ECDH implementations that use Curve25519 (which is one of the fastest ECC curves). I couldn't immediately find benchmarks comparing the two, and I don't know how to quantify "the same ballpark", but I've never heard anyone complain that RLWE is too costly performance-wise. So I don't think that the mobile CPU is the bottleneck.

Concerning RLWE, people do complain about the bandwidth of the key exchange. Even the best RLWE schemes still require much more data transfer (see the nice chart in the Frodo paper), which can significantly increase latency for poor connections. This appears to be corroborated by the results of Google's post-quantum TLS experiment, CECPQ1.

So I don't think battery life and/or performance will suffer much at all. Users with poor internet connections will certainly suffer a bit, but let's be honest -- they already suffer. The average page weight is in the megabytes, even for mobile. A few extra kilobytes in the handshake is a pittance compared to the amount of javascript and other assets most websites require. I realize this argument may not be valid for other protocols, but it does show that the average user probably doesn't have to worry about websites aggressively implementing hybrid post-quantum cipher suites.

  • $\begingroup$ Even 1/2 meg for this page on desktop, and that's without any pretty pictures. I hate it. $\endgroup$
    – Paul Uszak
    Jun 3 '17 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.