4
$\begingroup$

Noob alert! Can we run quantum safe algorithms on commercial devices (like phones, laptops, etc)? I've seen some messaging apps and vpn providers marketing themselves as quantum-proof. How likely is that all these claims are bogus for marketing (imo, very)?

$\endgroup$
  • 2
    $\begingroup$ "Post-Quantum" commonly refers to algorithms that are secure against classical computers and quantum computers. They can run on classical computers. We are searching for practical PQC algorithms that we can use in place of classical asymmetric key algorithms. There is also "Quantum Cryptography" which refers to communication that exploits quantum mechanics for security. QC can't be done with the classical internet. Nor does QC include algorithms you can use offline (for tasks like encrypting a hard-drive.) They sound similar but are only related by the "quantum" part (in name and theory). $\endgroup$ – Future Security Aug 31 '18 at 17:23
  • 4
    $\begingroup$ It's extremely likely that apps that use post-quantum in their descriptions are bogus. They could be scams, or they could be implemented incorrectly, or use a weak algorithm. Apps that claim to use quantum cryptography (not post-quantum) are definitely lying, since phones don't have the necessary hardware. $\endgroup$ – Future Security Aug 31 '18 at 17:30
  • 1
    $\begingroup$ Are you asking if it is physically possible, or if the algorithms are light-weight enough to be used practically on a commercial device? $\endgroup$ – forest Sep 1 '18 at 0:35
10
$\begingroup$

Post-quantum cryptography addresses the problem of developing public-schemes whose underlying assumptions are (believed to be) quantum resilient, i.e., the assumptions hold even in the presence of quantum computers.

There are many proposals for the underlying assumption and this leads to several branches like lattice-based cryptography, multivariate cryptography, code-based cryptography, hash-based cryptography or isogeny-based cryptography, among others. The cool thing about these assumptions and techniques is that they can be implemented in classical computers. In fact, many of these are already implemented and there is a competition driven by NIST to standardize some of these.

So, yes, these primitives are usable nowadays. Maybe these companies use a scheme of this nature, that may be the case.

$\endgroup$
3
$\begingroup$

Yes you can.

Post-quantum algorithms do not require a quantum computer to run. In fact, symmetric ciphers are quantum-proof, i.e. remains secure even quantum computers exsit. Many lattice-based cryptographic schemes (including, for example, some Fully homomorphic encryption schemes) have been implemented. They can be run on a normal PC or laptop.

$\endgroup$
  • 1
    $\begingroup$ As I recall, quantum computers get a significant speedup when attacking symmetric algorithms, amounting to a halving of bit strength (eg. a quantum computer can attack AES-128 as if it were a 64-bit cipher). The fix, of course, is simply to double your key lengths (use AES-256 instead of AES-128). $\endgroup$ – Mark Aug 31 '18 at 19:58

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.