0
$\begingroup$

Have security assumptions based on quantum computers de facto constrained the emergence and application of many new cryptographic schemes (e.g., fully homomorphic encryption)?

It seems to me that, in addition, too many resources are spent on so-called quantum-resistant cryptography schemes. Even though there is currently no functioning quantum computer, and these anti-quantum schemes perform worse than established public-key schemes.

The intuition I get from these studies is that one assumption is based on another.

$\endgroup$
3
  • 6
    $\begingroup$ The common terms for "anti-quantum" are "quantum-resistant” or “post-quantum” (see NIST's FAQ). Contrary to the question's statement, there are functioning quantum computers; they just don't yet do anything relevant (that is, something useful that a classical computer won't do for less) , and there's no full blueprint for one that would do anything cryptographically relevant. IMHO the reason why marvelous achievements like FHE do not emerge is more the lack of actual applications than fear of Cryptographically Relevant Quantum Computers: people do live with that! $\endgroup$
    – fgrieu
    Feb 2 at 9:21
  • 3
    $\begingroup$ Many people are not comfortable with the security assumption that "there will never be a Cryptographically Relevant Quantum Computer", hence we are making plans in case there is one. $\endgroup$
    – poncho
    Feb 2 at 13:53
  • 1
    $\begingroup$ If the yearly Global Risk Institute reports are anything to go by, most experts do believe CRQCs will exist. From what I've read, the viewpoint that CRQCs will never exist is quite rare unless some sort of significant global disaster happens or funding gets cut. The impact from not being prepared would also be so severe that it seems idiotic to look the other way. Finally, PQC schemes don't all perform worse, they just have larger inputs/outputs, which can have performance implications. $\endgroup$ Feb 2 at 18:36

2 Answers 2

2
$\begingroup$

The reason quantum-resistant schemes are studied, have been standardized and will be deployed widely is really three-fold:

  1. While there is no currently functioning quantum computer which can perform a cryptanalytically useful function, developments indicate that such a computer will probably be a reality. There is widespread disagreement among experts about exactly when that might be, some say years, some say decades. A minority of people (e.g., Gil Kalai) argue that this will never happen but cybersecurity is a conservative business.
  2. In the absence of quantum resistant schemes, and given how storage of the order of petabytes is within budgets of large organizations, store now decrypt later attacks are totally feasible. Since some secrets need to be kept for many years, quantum-resistant schemes are being deployed. There is evidence that governments already do this.
  3. As @poncho points out in the comments: store now decrypt later attacks don't apply to authentication (e.g. certificates), however when one looks at how long it took to transition (say) certificates from using SHA-1, well, it is highly advisable to start on the postquantum transition right away.
$\endgroup$
3
  • 2
    $\begingroup$ For (3), well, store-now-decrypt-later attacks don't apply to authentication (e.g. certificates), however when we look at how long it took to transition (say) certificates from using SHA-1, well, we'd be best advised to start on the postquantum transition now... $\endgroup$
    – poncho
    Feb 2 at 18:12
  • $\begingroup$ I think it's worth mentioning that there's evidence nation states already collect network traffic. $\endgroup$ Feb 2 at 18:40
  • 1
    $\begingroup$ @samuel-lucas6 saying "there is evidence" is underselling it. The united states does this at the Utah Datacenter. $\endgroup$
    – Mark Schultz-Wu
    Feb 2 at 20:22
2
$\begingroup$

While Kodlu's comment has focused on the case of basic public-key operations, I thought I would respond to

Have security assumptions based on quantum computers de facto constrained the emergence and application of many new cryptographic schemes (e.g., fully homomorphic encryption)?

The only known fully homomorphic encryption schemes are built from lattices, which are thought to be post-quantum secure. If there were other cryptosystems that were known to give FHE at some huge efficiency benefit, I'm sure they would be seriously considered. But there are none. Every known FHE scheme is morally [1] lattice-based. This is all to say that the facts that lattices are thought to be post-quantum secure and lattices imply FHE are coincidental.

[1] There is the small caveat of Antoine Joux's "Pseudo-Fermat Nubers-based scheme", but this just takes a lattice-based scheme, defined over $\mathbb{Z}_q[x] / (f(x))\cong \mathbb{Z}_q^{\deg f}$ (where addition is component-wise, and multiplication is complicated, depending on the choice of $f$), and ports it over to artithmetic in $\mathbb{Z}_{p^e}$, e.g. where one views integer arithmetic as a sort of "funny polynomial arithmetic" where addition is no longer component-wise due to carries. I can't remember if this can be formally connected to lattice-based problems, but it is essentially the same construction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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