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

Quantum Resistance and the Signal Protocol

signal.org

Post reply on HN
Print view View original

21–30 of 135 posts

Re: Quantum Resistance and the Signal Protocol

#21

Post by keurrr »

swamp40 wrote: post #14

There are 20 bitcoin wallets worth more than a billion dollars each. I think it will be pretty obvious when someone gets a quantum computer working.

I don't think these incentives make sense at all. Government organizations suspected to be developing quantum computers probably have larger annual budgets than 20 billion. The ability to undermine virtually all cryptographic systems is unquantifiably large.

Once the cat is out of the bag, everyone will rush to post-quantum cryptography and all that value will be lost in a relatively short period. Indeed, we already witnessed this in the 2010s following the Snowden revelations when big tech, in a concerted effort, adopted HTTPS. Now that is the standard.

For example, "The Fiscal Year 2022 budget appropriation included $65.7 billion for the National Intelligence Program, and $24.1 billion for the Military Intelligence Program."

Source: https://irp.fas.org/budget/index.html

Re: Quantum Resistance and the Signal Protocol

#22

Post by tptacek »

JanisErdmanis wrote: post #18

It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. It'…

CRYSTALS-Kyber was designed by an academic team, not a government (though a government standards body refereed the competition that selected it; that competition, in turn, was driven by technical feedback that came predominantly from academic cryptography teams around the world). In general, with some exceptions (like curve isogenies), the "math" behind PQ crypto is pretty well established; it was just less attractive than curves were for performance reasons, but is now more attractive if you presume curves will be broken in 20 years by QC.

Re: Quantum Resistance and the Signal Protocol

#23

Post by krastanov »

JanisErdmanis wrote: post #18

It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. It'…

Doesn't your argument apply to classical bits too? The more interconnected a classical bit is, the more parasitic coupling it will experience. That used to be an argument used against the feasibility of classical computers in the 40s (until von Neumann published work on fault tolerant classical computing).

Both classical and quantum computers (1) can not "scale" without error correction because of analog noise (although it is less crucial on the classical side), but (2) can be build with error correction codes integrated in them to overcome that noise.

Also, you do not need all-to-all connectivity between your qubits (or bits) to build a scalable quantum (or classical) computer.

Edit: To add to your FM radio metaphor: you can have way more FM radio channels if each channel is on a separate coax cable (or in physics speak, if you multiplex not only by frequency but by spacial mode). No need to have all your qubits be controlled by the same optical or microwave mode, you can have physically separate control lines for each qubit and then eliminating cross-talk is as simple as inverting an n-by-n matrix.

Re: Quantum Resistance and the Signal Protocol

#24

Post by hannob »

JanisErdmanis wrote: post #18

It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. It'…

I've heard physicists raise opinions like yours (i.e. QC will never be built for practical reasons), but I also hear ones that say the opposite. I'd err on the side of caution.

As for your conspiracy: The conclusion of that would be to continue using hybrid constructions.

Though, and I know crypto more than physics, I'd consider it as highly unlikely. Creating backdoors that others won't find is next to impossible. Why do I say that? Because we have some historic evidence how "NSA wants to plant a backdoor into an algorithm" works. Usually they've been discovered quickly. They can still be successful, because as we have seen with dual ec drbg, it was discovered quickly, yet nobody really cared and industry still used the algorithm.

But something like that won't happen in a transparent process. You can be sure that every expert in the field had a look at crystals-kyber. If anything about it was suspicious, we would know.

Re: Quantum Resistance and the Signal Protocol

#25

Post by keurrr »

JanisErdmanis wrote: post #18

It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. It'…

So you are claiming the protocol that Signal has adopted is already backdoored by the government. Extraordinary claims require extraordinary evidence. You need to provide some kind of evidence of this. We are talking 20+ years of open and public research on post-quantum cryptography.

Re: Quantum Resistance and the Signal Protocol

#26

Post by simcop2387 »

woodruffw wrote: post #20
JanisErdmanis wrote: post #18

It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. It'…

To a first approximation, the US government uses the same cryptography that US consumers do -- AES, SHA-2, the NIST P curves, ECDSA, etc. are all categorized for various levels of data integrity and confidentiality within the government. The same will be true of PQ signing schemes, meaning that a backdoor would be predicated on the USG believing that they have some truly remarkable NOBUS breakthrough in PQC. That fee…

> NSA interventions in cryptographic design have historically gone in the opposite direction[1].

I'm not sure I'd say that given that there are some other designs and things that have gone on[1][2]. Particularly the Dual EC debacle. They have a history of helping make suspect or down right compromised crypto if they think they can get away with it. That said it does look like they avoid doing it to anything that gets USA GOV approval for use internally but it's difficult to say to what level they would actually go to for getting a backdoor out into the world that would let them look at other secrets.

[1] https://en.wikipedia.org/wiki/Export_of_cryptography_from_th... [2] https://en.wikipedia.org/wiki/Dual_EC_DRBG

Re: Quantum Resistance and the Signal Protocol

#27

Post by zie »

rjmunro wrote: post #3
awestroke wrote: post #2

Super cool. If current quantum computers were scaled up to more qubits, could they break modern crypto? Or would we need both more qubits and a new quantum computer architecture?

15 was factorised on a 7 qbit computer by IBM, so yes, they could break RSA if scaled up. I'm not sure about elliptic curve. That was over 20 years ago: https://research.ibm.com/blog/factor-15-shors-algorithm I wonder how possible it is that IBM could have already gone further and are already cracking modern crypto in secret, e.g. funded by the NSA. Is that a crazy conspiracy idea, or actually a possibility?

I bet at the very least, the US govt and other large govts have some way of knowing whatever is actually possible TODAY and have plans in place to make sure whenever it is practical, they get the very first useful ones built.

I would guess they probably don't have any actually useful and in production right now, but they probably have a few secreted away in development, so they will be ready to put them to use if/when they do become useful.

Re: Quantum Resistance and the Signal Protocol

#29

Post by adgjlsfhk1 »

JanisErdmanis wrote: post #18

It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. It'…

The good news is that if you're willing to take a 2x slowdown for asymmetric encryption (which basically everyone is) you can get the best of both worlds by wrapping your quantum resistant crypto in regular crypto.

Re: Quantum Resistance and the Signal Protocol

#30

Post by kevvok »

rjmunro wrote: post #3
awestroke wrote: post #2

Super cool. If current quantum computers were scaled up to more qubits, could they break modern crypto? Or would we need both more qubits and a new quantum computer architecture?

15 was factorised on a 7 qbit computer by IBM, so yes, they could break RSA if scaled up. I'm not sure about elliptic curve. That was over 20 years ago: https://research.ibm.com/blog/factor-15-shors-algorithm I wonder how possible it is that IBM could have already gone further and are already cracking modern crypto in secret, e.g. funded by the NSA. Is that a crazy conspiracy idea, or actually a possibility?

Algorithms using elliptic curves can also be broken using Shor’s algorithm
Post reply on HN