This is smart. PQC schemes often add too much overhead for interoperable cookie sizes. Instead of trying to cram a PQC signature into a cookie, just stop using the stateless cookie designs that require asymmetric signatures.
I'm not sure I buy the Global Risk Institute chart. I get that they need to motivate adoption, but practical cryptanalytic work with quantum computers seems unpromising right now.
Which means it's only sent once per connection.
Is it just us failing to find one, or something more fundamental prevents a quantum resistant short signature like?
Yeah; that doesn't look right to me either. Perhaps "cryptographically relevant" has some unusual meaning (parity with conventional computing?). Otherwise, the consensus view is that there's, pessimistically, a 4% probability of a total break of all public key cryptography within 5 years.
That's practically "abandon all hope right now" territory rather than "motivate adoption" territory.
Personally, it seems reasonable to at least spend some effort preparing for it, given the rather long lead time required to develop, study and stress the constructions needed. It might be a long time (if ever) before cryptographically relevant quantum computers show up, but if they do, we'll be glad we had a decade or two to get ready. The alternative of scrambling at the last minute while everything gets cracked seems unenviable.
[1] https://www.cs.auckland.ac.nz/~pgut001/pubs/heffalump_crypto...
That's what everybody said about AI, then sudden advances ~2013 led to the situation today.
Don’t be so sure. From the article, Google seems to believe quantum computers will arrive in the next 10 years.
What can be done from a design point of view to make it as hard as possible to deter attackers?
Would it make sense to segregate different types of data into other dbs rather than as a separate table?
“Name DB” “Account DB” “Address DB”
An attacker would need to have advanced knowledge of the app backend to know you have to snag both the account db and address db. Otherwise, the decrypted data is useless with only 1 db.
Drawbacks of course include “performance degradation”, “increasingly complex app”.
Ideally, if you did not need to store sensitive data or collect other user info such as address or zip code. Then not asking for it at all would be optimal. Maybe regulation is needed here.
As for regular assessment of your secure infrastructure, you can read latest “Algorithms, Key Size and Protocols Report”:
https://www.ecrypt.eu.org/csa/documents/D5.4-FinalAlgKeySize...
and practical part of ENISA report:
https://www.enisa.europa.eu/publications/post-quantum-crypto...
If you're encrypting data at rest, just keep using an appropriate mode of AES (or ChaCha20 or whatever+) and exercising good key management practices. Quantum computing is largely irrelevant to conventional symmetric ciphers.
+ for tightly constrained values of 'whatever'
If I only could get access to nothing but one database, and every table / segment of it were encrypted differently, it would likely take as much effort to break into each of them, as if they were "physically separate" databases.
- i think encryption at rest would probably just use symmeyric encryption which is unaffected by shor
- how does the attacker get into your network in this scenario. Stuff encrypted at rest by definition is not flying around the network.
- what sort of scenario would be involved where the attacker knows how to get one db but not the others? The hard part is figuring out the first db
> Drawbacks of course include “performance degradation”, “increasingly complex app”.
On the contrary, sharding is a super common performance technique.
The only real protection is encryption.
Does anyone know what those alternatives might be? Some way to collapse a chain of signatures into one? Long-term symmetric session keys? Neither of those sound like good ideas but I'm grasping at straws.
Let’s give IBM credit for attempting to factor in the number 35 in 2022, although they failed there [1]. Before that, the successful factorisation happened for the number 21 in 2012 [2] and the first factorisation of 15 in 2001 [3].
Now we have three points. There is a trend that the factorised number grows by a number of 10 for every ten years. Thus, to get a quantum computer that facilitates RSA-2048, we shall wait for 2^2048 years.
[1]: https://arxiv.org/pdf/2103.13855v1.pdf
It seems like a reasonable bet on their part, in the sense that Google has a lot of money to play with. Even if it is unlikely that it takes off, behind hit by quantum attacks would be pretty bad for them, so maybe they see it as insurance against an unlikely but catastrophic event.
The issue is the emphasis on the importance of an inevitable threat. Organisations start to justify implementing QC-resistant algorithms on the basis that others are doing so, and in that way, they justify themselves that the threat is real. After that, we would end up with government agencies issuing a requirement that only QC-safe algorithms are acceptable for security in the process, killing useful cryptographic primitives like ElGamal cryptosystems, homomorphic encryption, blind signatures and a class of zero-knowledge proofs.
At the moment, there are only three points from which one can extrapolate further advancements. The Shor algorithm requires exponential suppression of errors with the number of qubits. This is why, although we have hundred qubit QCs, the most significant factorisation is being done at most with five qubits. Threfore, if we would have “exponential progress” in advancing QC, the advancement of factoring integers would be linear. Faster progress requires miracles. QC error correction would be no panacea either, as it would require repeated application and would require an unreasonable number of qubits as well as would increase runtime.
The miracle as well be that we figure out a way to factorize numbers on classical computers in polynomial time. Or as well break lattice based crypto on classical computers.
> We implemented the algorithm on IBM quantum processors using only 5 qubits
Last December, a team based out of Harvard demonstrated the ability to scale up to 48 logical qubits: https://arxiv.org/abs/2312.03982
It has been shown that, to factor an integer with n bits, Shor's algorithm requires ~2n logical qubits: https://arxiv.org/pdf/quant-ph/0205095.pdf
The core issue why Schor algorithm is hard is that it requires exponential supppression of error with number of qubits to produce meaningful results. Therefore we don’t actually see much results here as the error rates have not yet reached thresholds to do it with more qubits. The error correction would not be a panacea either because it would necessitate it’s repeated application to get necessary threshold to run Schor algorithm. This would require unreasonable amount of physical qubits.
Is SPHINCS+ more lightweight?
Symmetric algorithms (AES-256 in particular) are generally considered to be quantum resistant. Here is what written about it in the article.
> Symmetric cryptography, using a single secret key to encrypt and authenticate data: In our current understanding, symmetric cryptography is not impacted by quantum computers for all practical purposes. Grover's algorithm could be used as an attack here, but is currently considered infeasible for even medium-term quantum computers. (See "Reassessing Grover's Algorithm, 2017")
The algorithms most affected by quantum cryptanalysis are public key (asymmetrical) algorithms, because we already have effective quantum algorithms against them (Shor's in particular). We are not even close to having the computer though.
How do you distribute your pads? (hint: it's a chicken-and-egg problem, you need a secure channel)
How do you ensure they're only ever used once?
In its most obvious instantiation, you get no authentication. So now you have to build an authentication mechanism on top. There's simply no point, when we have better solutions already.
And to top it all off, symmetric ciphers aren't threatened by quantum computing in the first place.
[0]: https://globalriskinstitute.org/publication/2023-quantum-thr...
