Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Google's threat model for post-quantum cryptography

bughunters.google.com

Post reply on HN
Print view View original

11–20 of 81 posts

Re: Google's threat model for post-quantum cryptography

#11

Post by xyst »

Besides encrypting your user data at rest using these post-quantum cryptography algo.

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.

Re: Google's threat model for post-quantum cryptography

#12

Post by JanisErdmanis »

The threat estimate for a quantum computer that breaks cryptography shall be based on currently available data and the understanding that only the Schor algorithm is known to provide exponential speedup for factorisation.

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

[2]: https://www.nature.com/articles/nphoton.2012.259

[3]: https://www.nature.com/articles/414883a

Re: Google's threat model for post-quantum cryptography

#13

Post by bawolff »

xyst wrote: post #11

Besides encrypting your user data at rest using these post-quantum cryptography algo. 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 bot…

This doesn't make sense:

- 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.

Re: Google's threat model for post-quantum cryptography

#14

Post by comex »

> There are several alternatives to simply replacing classical signatures with quantum-safe signatures, which could address the performance issues when it comes to PKI. We are currently looking to experiment in this space to gather data for more solid recommendations, which we will share in a future blog post.

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.

Re: Google's threat model for post-quantum cryptography

#15

Post by dist-epoch »

tptacek wrote: post #5

Stateless tokens come with independent security concerns, and moving towards stateful tokens is prudent just to ensure more robust systems. [...] Our main recommendation is to use stateful tokens where possible, given their additional security benefits. 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 st…

Is there any insight why there is no PQC signature with a short signature?

Is it just us failing to find one, or something more fundamental prevents a quantum resistant short signature like?

Re: Google's threat model for post-quantum cryptography

#16

Post by smburdick »

JanisErdmanis wrote: post #12

The threat estimate for a quantum computer that breaks cryptography shall be based on currently available data and the understanding that only the Schor algorithm is known to provide exponential speedup for factorisation. 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 firs…

From [1]:

> 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

Re: Google's threat model for post-quantum cryptography

#17

Post by arccy »

xyst wrote: post #11

Besides encrypting your user data at rest using these post-quantum cryptography algo. 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 bot…

Typically once you get access you just try to dump everything and figure it out later. Splitting into separate stores is just convoluting your day to day for minimal inconvenience to a possibly non-existent an adversary.

The only real protection is encryption.

Re: Google's threat model for post-quantum cryptography

#18

Post by ogurechny »

xyst wrote: post #11

Besides encrypting your user data at rest using these post-quantum cryptography algo. 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 bot…

Assumed attackers owning quantum computers probably have much better “Address DB” than yours.

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...

Re: Google's threat model for post-quantum cryptography

#19

Post by some_furry »

dist-epoch wrote: post #15
tptacek wrote: post #5

Stateless tokens come with independent security concerns, and moving towards stateful tokens is prudent just to ensure more robust systems. [...] Our main recommendation is to use stateful tokens where possible, given their additional security benefits. 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 st…

Is there any insight why there is no PQC signature with a short signature? Is it just us failing to find one, or something more fundamental prevents a quantum resistant short signature like?

The kind of math problems that are hard for quantum computers to break tend to produce kilobyte+ outputs at our target security levels.

Re: Google's threat model for post-quantum cryptography

#20

Post by JanisErdmanis »

smburdick wrote: post #16
JanisErdmanis wrote: post #12

The threat estimate for a quantum computer that breaks cryptography shall be based on currently available data and the understanding that only the Schor algorithm is known to provide exponential speedup for factorisation. 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 firs…

From [1]: > 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

It is not enough to place qubits on a single chip or on a grid. We already know how to do that. The hard part is keeping them isolated while allowing arbitrary control of their interference.

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.

Post reply on HN