Quantum Resistance and the Signal Protocol • Hacker News Board

Re: Quantum Resistance and the Signal Protocol

#111

Post by vlovich123 » Wed, Sep 20, 2023, 7:46 AM UTC

bawolff wrote: post #104

vlovich123 wrote: post #73

Earlier quoted context omitted.

> The main twist is that we don't know the future but we know how theorical QCs are able to break currently used cryptography Under the constraints of us correctly modelling the math of QC. Isn't it possible that we have gaps between our models of QC and how it works in reality that could make it such that these algorithms can't actually offer any speedup over classical approaches in the real world? Or similarly, eve…

> Isn't it possible that we have gaps between our models of QC and how it works in reality that could make it such that these algorithms can't actually offer any speedup over classical approaches in the real world? If BQP=BPP or if BQP did not accurately model a quantum computer, i think that would be a much more interesting result than an actual working quantum computer. It would be world shattering.

Or BQP is a purely theoretical construct with no real-world counterpart. No world shattering result necessarily.

There’s plenty of math that exists purely in the virtual real with no connection to physical reality. Math is a language to describe any possible universe. That doesn’t mean anything we say in it necessarily applies to our universe.

Re: Quantum Resistance and the Signal Protocol

#112

Post by Tutanota » Wed, Sep 20, 2023, 8:03 AM UTC

bawolff wrote: post #106

Tutanota wrote: post #94

Congrats to Signal, this is a great step! At Tutanota we also use the Signal protocol to build post-quantum secure encryption for email and drive: https://tutanota.com/blog/pqdrive-project Post-quantum secure encryption can't be developed early enough. In the end all our data today will be at risk of being decrypted in the future - unless we secure it now!

That's not exactly the most compelling blog post. Way too many buzz words. Why would end-end cloud storage even be using public-key cryptography? You're sending the encrypted data to yourself forward in time.

Not for storing the data, no, but public-key cryptography is needed for sharing encrypted files.

Re: Quantum Resistance and the Signal Protocol

#113

Post by pyinstallwoes » Wed, Sep 20, 2023, 8:05 AM UTC

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'…

Doubly more that the recommended best practices have actually reduced the key length.

Re: Quantum Resistance and the Signal Protocol

#114

Post by pyinstallwoes » Wed, Sep 20, 2023, 8:08 AM UTC

tptacek wrote: post #22

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 attractiv…

Yet if you followed the money those programs are funded by government adjacent entities that usually have 3 letters.

Re: Quantum Resistance and the Signal Protocol

#115

Post by pyinstallwoes » Wed, Sep 20, 2023, 8:09 AM UTC

hannob wrote: post #24

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

Why create backdoors if you can convince everyone to use less effective cryptography?

Re: Quantum Resistance and the Signal Protocol

#116

Post by bawolff » Wed, Sep 20, 2023, 10:22 AM UTC

vlovich123 wrote: post #111

bawolff wrote: post #104

Earlier quoted context omitted.

> Isn't it possible that we have gaps between our models of QC and how it works in reality that could make it such that these algorithms can't actually offer any speedup over classical approaches in the real world? If BQP=BPP or if BQP did not accurately model a quantum computer, i think that would be a much more interesting result than an actual working quantum computer. It would be world shattering.

Or BQP is a purely theoretical construct with no real-world counterpart. No world shattering result necessarily. There’s plenty of math that exists purely in the virtual real with no connection to physical reality. Math is a language to describe any possible universe. That doesn’t mean anything we say in it necessarily applies to our universe.

> Or BQP is a purely theoretical construct with no real-world counterpart.

I would consider that world shattering. It would suggest significant flaws in our understanding of the universe which would be very exciting.

Honestly i can't think of a more earth shattering discovery. It would be on par with aliens landing and saying we come in peace.

> There’s plenty of math that exists purely in the virtual real with no connection to physical reality.

Obviously.

The earth shattering part is if quantum physics goes from an accurate description of most of the universe to one that isn't.

What you are basically saying is any theory could be wrong. Well duh, but that describes literally all earth shattering scientific discoveries.

Re: Quantum Resistance and the Signal Protocol

#117

Post by eigenket » Wed, Sep 20, 2023, 10:56 AM UTC

upofadown wrote: post #60

eigenket wrote: post #32

Earlier quoted context omitted.

People have already said here most of what I want to say in this comment, but just to make it as explicit as possible: Essentially the only reason anyone thinks that useful quantum computation is possible is because of things called threshold theorems, which state that as long as the noise in each qubit is less than some small but non-zero error rate you can add more qubits and use quantum error correction to make yo…

>...as long as you're below the threshold rate quantum computers scale well. Last I heard, getting below that threshold was going to take one or two orders of magnitude of noise improvement. That seems unlikely. Say you were at a VC presentation and the company said that they had this really great system and the only thing stopping their immense success was the requirement to reduce the noise by an order or two of ma…

I agree with you that the general optimism towards quantum computing needs some tempering. It is certainly possible it doesn't work out and we never get a universal fault-tolerant quantum computer.

I think part of the reason for optimism is that there are a lot of different ways to make a quantum computer. Ion traps, linear optics, resonant superconducting circuits, topological quantum computing (if anyone ever actually discovers an anyon) and many more.

Different groups are working on wildly different directions right now, i.e. Google and IBM are doing superconducting stuff, microsoft loves topological stuff, researchers at various places are doing trapped ions and at least one company (psi-quantum) is working on linear optics.

It certainly wouldn't be surprising if several of these approaches fail to work, but the hope is that they don't all fail.

Re: Quantum Resistance and the Signal Protocol

#118

Post by eigenket » Wed, Sep 20, 2023, 11:09 AM UTC

plank wrote: post #97

krastanov wrote: post #23

Earlier quoted context omitted.

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 (altho…

Not the parent (and gotten my PhD more then 25 years ago), but the answer is no. Quantum mechanics is a fickly thing. Schrödingers cat has not been observed ;-) because scaling kills the quantum mechanical properties. My (entirely theoretical) PhD project dealt with a 2 dimensional electromagnetic cavity, with one 'perfect' mirror (100% reflecting) and one 'imperfect', say 99.999999999% reflecting. My results were th…

It doesn't change the overall point you're making but your "gut feeling" was already wrong 20 years ago. A group working for IBM factored 15 = 3x5 with a quantum computer in 2001.

You are also somewhat wrong about the combining N approximate answers and combining them. It is correct that that the "repetition code" approach (repeat the same calculation a bunch of time and average the results) does not work for quantum computers. However there are quantum error correcting codes which do appear to work, although they require sufficiently small initial error rates (so-called thresholds) in order to help.

Re: Quantum Resistance and the Signal Protocol

#119

Post by Boogie_Man » Wed, Sep 20, 2023, 12:37 PM UTC

lxgr wrote: post #67

Boogie_Man wrote: post #5

Actively resisting future attackers and hardware is an incredibly forward-thinking thing to do, bravo. How long into the future is an achievable and desirable duration for encryption (barring any rapid, unforeseen paradigm shift)? If ten years is acceptable for declassification of standard documents in the US, is this a reasonable target for day to day signal chats?

> How long into the future is an achievable and desirable duration for encryption (barring any rapid, unforeseen paradigm shift)? I don't think "years of expected security" (as used to be popular for e.g. RSA key lengths for some time) is a meaningful metric anymore: AES-256 and elliptic curve encryption are resistant against classical attackers until beyond the heat death of the universe, so their "time of security"…

>I'd expect that, for quantum-safe asymmetric algorithms as well as for AES, there is a similar number corresponding to fundamental physical infeasibility, and then we can also just pick that rather than any low or high number of years.

Ah! My understanding is out of date. Thank you for the detailed answer.

Re: Quantum Resistance and the Signal Protocol

#120

Post by matthewdgreen » Wed, Sep 20, 2023, 1:27 PM UTC

andyferris wrote: post #59

krastanov wrote: post #23

Earlier quoted context omitted.

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 (altho…

To add to the sibling comment, the reason our classical computers work is because the individual transistor errors in your CPU are basically zero. We do use “error correction” on storage (and do see bit errors creep into data stored on disk and in RAM over time) but not “fault tolerance” on the compute. In fact there is no such thing as fault-tolerant classical compute - the CPU only works if it “perfect” or “near pe…

This isn't really accurate. Fault-tolerant classical computing absolutely does exist as a field, and plenty of work has been done there. Some of the early work was done by von Neumann [1] because early computing hardware was extremely error-prone. Over time it turned out that these techniques were not really needed due to the fact that modern solid-state hardware is extremely reliable. The field of quantum computing actually resurrected a handful of ideas that were originally developed for classical computers.

More generally, nobody needs "perfect" classical computing either to make quantum computing work. Given a (quantum or classical) processor with some degree of error, the idea behind these techniques is to "boost" that into a processor with arbitrarily small error. It just turns out that with modern classical processors the error is so small that we suffer it rather than pay the cost of using these techniques.

[1] https://www.cs.ucf.edu/~dcm/Teaching/COP5611-Spring2013/Pape...