Something to remember: One-Time Pads are unbreakable, and as storage costs continue to drop, there are certainly many scenarios where they could be used and never cracked.
Think about it. How much actual secure data do you and your bank need to transfer back and forth? Certainly not web UI elements or site chrome. For each use of your online account, there's probably 3 or 4k max actual data that you need to be secure. Your bank could mail you a 1GB random noise file, perhaps a backup, and you two could communicate for the rest of your life without any fear of anybody understanding what you're saying.
I understand that there's an entire e-commerce ease-of-use scenario where secure communications becomes mission-critical. And I'm certainly not suggesting to replace all secured comms. My only point is that there are parts of this problem that are very tough and there are parts of this problem that we have made more difficult than it has to be simply in an effort to standardize and abstract everything.
The problem with this method is that it requires a side channel. This is the real beauty of public key cryptography, you can negotiate a secure channel over an open channel. (*Authentication sold separately)
I don't get why this argument is used so often as if it was valid. Setting up a banking account and many other things require a secure side channel anyway - physical presence :)
This is the real beauty of public key cryptography, you can negotiate a secure channel over an open channel.
You still need sufficient shared information as a starting point to authenticate the other party, so that doesn't really avoid the need for a secure side channel. In practice we often trust that the baseline of certificates that come with a new device or built into a browser are sufficient for this purpose, but there is still an attack surface there and our existing CA infrastructure and processes are not perfect.
There exists quantum key distribution https://en.wikipedia.org/wiki/Quantum_key_distribution#Quant... which is provably secure (up to side channel attacks), and allows two parties (say you and your bank) to remotely create a symmetric key. This will certainly require infrastructure to be built, but its possible that this infrastructure consists of beaming signals from bank->satellite->receiver in your home.
In practice schemes based on cryptographic hash functions work just as well and are quantum resistant. 512-bit key length is safe from quantum computers. Use bcrypt, Argon2 if you are pessimistic.
Using side channel to share single 512-bit key that is used to generate other keys keys is enough.
The best known quantum attack against symmetric ciphers uses Grover's algorithm to effectively halve the key size. AES-128 is considered secure against classical attacks, so assuming you have a secure side channel for key distribution, AES-256 is sufficient to defeat quantum attacks.
Do you mean like literally mail it to you, or email it to you? If it’s the latter you still have the problem of needing it to be encrypted. If it’s the former, it’s damned inconvenient.
I mean, sure, but how are you going to protect the one time key?
What might make more sense is if they gave you a usb drive that was good for a thousand transactions or whatever. Then you could get it replaced in person after the pad was used it.
I didn’t read the article (paywall), but unless they are talking about quantum computers, the computation required to break the key and encrypt the data has a exponential difference. If we all started using keys that were, say, 2^32 bits long, we would be fine for the forseeable future.
There is some cognitive dissonance in associating what after more than 30 years is currently, for all purposes still a Sci-Fi concept and Cryptography.
After billions spent and decades of no progress, this is the same repeated article that has been rewritten every other year hyping about the promisses of what, for all purposes, is currently expensive vaporware.
You are judging an endeavor by how the media reports on it and not how the actual community's estimate of the progress. You are certainly right that a quantum computer big enough to solve a practical computational problem has not been built [1]. The quantum computing community certainly thought a 20 year timeline to QC was viable in the late 90s and early 2000s. However, after the failures of early experimental efforts, the consensus stance at conferences and such is always that QCs will come when they will come. The challenges are big but the path through them is straightforward - keep improving manufacturing capabilities till we can scale [2].
If you follow the literature, you will realize everyone is busy optimizing their manufacturing capabilities instead of going for short term goals of factoring ever larger numbers. We have to go from a regime where grad students spend months/years carefully crafting a handful of small parts to mini-industrial processes which can be used to manufacture thousands or millions of identical parts. It takes time and effort to do build such setups, but progress has been consistent over the last decade or so, and will only get better in the next decade.
I think many are seriously underestimating the engineering breakthroughs needed for a computer that can break 2048 bit RSA. Hopefully I'm proven wrong.
Successfully developing functional fusion power is considerably more plausible than practical quantum computers in the near term. The problem with fusion research is that it is and has been massively, chronically underfunded.
I've heard a similar sentiment from a researcher that's specialized in fusion. How do you know that money is the main hindrance? Could we say the same thing for other areas of research, like room temperature super conductors or the unification of quantum theory with gravity? In any area more money may or may not lead to a significant progress, but how do you know that's definitely the case for fusion?
It's likely the case for fusion, in that fusion is an extremely high energy research area. Room temp superconductor research is several orders of magnitude lower in energy usage. Energy has a intrinsic cost, and the more energy involved, the more infrastructure required to manage it. There is no data here, but I imagine the total cost is logarithmic, with several hockey stick bends where certain materials are no longer viable in those energy levels.
An example: casting
You can cast wax nearly for free, given that you salvage the mold materials and carve them by hand, sunlight can be used to melt the wax (~70C), and almost no materials are needed to control heat. Casting pewter is a bit more difficult, as a wooden mold will burn a bit, and you'll need some type of heat control tech, such as an oven or microwave or solar forge (~200C). The temperature has only tripled, but already materials no longer work and costs are significantly higher. I've worked in a titanium foundry and the cost is enormous compared to low energy areas.
What's the guarantee of payoff for that level of investment? LFTR always seemed much more likely to produce such a payoff if given sufficient investment.
But I doubt either can beat what solar and wind are poised to produce. They are cheaper than installed coal now, and are targeting installed natural gas.
Battery will handle the rest of storage/load needs.
Quantum computers that can do fast factorisation have been demonstrated, they just haven't yet been able to factor large enough numbers to be dangerous.
> they just haven't yet been able to factor large enough numbers to be dangerous.
According to [1], the current highest factorization using Schor's algorithm is 21=3 * 7 published in 2012, up from the 15=3 * 5 that was demonstrated in 2001. This pace is not all that promising.
Sure, there are other quantum factorizations, but they are either stunts (work only for very narrow classes), or are based on a different algorithm than Schor, which does not show hope to scale up.
Your 3 * 7 and 3 * 5 got interpreted as a highlighting of the text surrounded by the asterisks. You can edit your comment to fix it. Here are the complete HN markup rules:
Blank lines separate paragraphs.
Text surrounded by asterisks is italicized, if the character after the first asterisk isn't whitespace.
Text after a blank line that is indented by two or more spaces is reproduced verbatim. (This is intended for code.)
Urls become links, except in the text field of a submission.
Factoring by Quantum computers able to implement Shor's algorithm (which is the proposed apocalypse for the family of public key algorithms used today) so far isn't just short of "dangerous" it's short of what you'd expect school children to achieve. 21 is 7 times 3. Really, I'm not exagerrating, that's what they've achieved.
As with the work done to try to figure out how we should handle a big rock coming our way, work on post-quantum cryptography is justifiable because it's something we would really regret not working on if it suddenly becomes necessary and it's not _that_ expensive. But just because the threat justifies relatively modest research expenditure doesn't make it worth a newspaper article that will invariably distort the facts and confuse more than it illuminates.
Agreed. Consider that we don't even know if one-way functions exist, and all public-key cryptography depends on the assumption that they do. Maybe some classical attack will break all the commonly used systems before a big enough quantum computer is built.
is there a single practical example of a real world problem being solved by a current quantum computer? all the talks i have seen involve a lot of hand waving and talk of the future. i’m very skeptical that these capabilities are around the corner
Yeah a couple of related problems in fact: You are a professor and working on cold quantum gases, synthetic quantum systems, ... and can semi-plausibly claim that this has applications to quantum computing: Problem solved, you will get a whole bunch of funding. You found a bunch of linear algebra algebra algorithms and they use unitary matrices: Problem solved, founding secured.
It is also a good buzzword prefix: Just prepend Quantum to any word and immediately get funding (See the recently 1 Billion Euro funded EU quantum initiative).
In this respect it has similar applications as Neuro-something: A great way to get funding for a few years. (See Human Brain Project)
AFAIK, currently probably not, but this would be a bad basis for extrapolation about future capabilities. Conventional supercomputers are insanely fast and current quantum computers do not yet have many qubits yet. But - very loosely speaking - if you add one qubit, the processing power can double. See the first answer here: [1]
If the history of technology and cryptography teaches us anything, then quantum computers will break current encryption sooner than expected. If you're very paranoid, you may switch, in certain areas, to "quantum safe" symmetric encryption (higher key size, higher round numbers) with reasonably secure channel for key exchange instead of public key cryptography.
Any quantum experts able to share a technical article on (a) what are the main obstacles to a universal quantum decryptor, and (b) what is the current progress curve on those obstacles?
With this much on the line, someone has to have a detailed model they keep up to date...
Not a crypto expert, but wondering if we could make a classical encryption function where every bit of the output depends nontrivially on every bit of the input, so a long message would be harder to decrypt, even for a QC.
(First hashing the input counts as trivial because that would reduce the effective number of bits)
Some ciphers use this method, it’s not the problem.
QC isn’t going to break all crypto traditional symmetric ciphers are safe and one of the simplest classical ciphers a one time pad is still the safest method of encryption when it’s done correctly.
QC may break some asymmetric encryption which relies on factoring numbers.
Asymmetric encryption is on some level security through obscurity as you publicly display a key from which your encryption key can be mathematically derived and you rely solely on the fact that it’s a very hard thing to do.
But as far as classical encryption goes XORing a message against a random number of bits equal to the message length would always be secure, especially for long messages the problem is that it ain’t very practical.
That said however we do have QC resistant key exchange and signature algorithms so I don’t think there is that much reason to panic.
I’m pretty sure you can still find 1024bit and lower RSA key systems still in use arguably these are less secure today than 2048 and 4096bit RSA keys will be during the first years of a post QC world.
> That said however we do have QC resistant key exchange and signature algorithms so I don’t think there is that much reason to panic.
Interesting. Then shouldn't we
(and PR people involved in QC) stop focusing on the cryptographical capabilities of QC, and start focusing on its other potential applications, like protein folding? Until now in the media, it seems like QC is synonymous with crypto
...
If it’s criminals stealing your passwords then it would take decades after QC until it would become universal enough to be a problem, by then likely current traffic would not be affected.
If it’s state level actors then you might be in a bigger bind.
If we take the NSA for example today there isn’t a single cryptographic system they can’t compromise.
And I’m using the term system intentionally as the NSA can’t break 4096bit RSA or AES or any other competent cipher.
They can and do break cryptographic systems on a daily basis by compromising the hardware, software and people which the system relies on.
But this is a very targeted and costly operation which means that general internet traffic isn’t looked at because it’s not worth it.
However if they also capture encrypted traffic and store it indefinitely as most key exchanges today are not necessarily QC resistant they could potentially go back and decrypt all that traffic.
This is why while the house is not on fire I think there is value in pushing post-QC ciphers sooner rather than later.
And even if the NSA can be kept in check we have little control over Russia and China and the list of actors capable of operating at large enough scales for this to be a problem grows bigger every day.
OFC they will, it would be criminally negligent of them not to.
However if the NSA is currently your adversary and you are worried of being targeted then pre QC or post QC encryption isn't going to matter push comes to shove they'll beat it out of you.
But as I said if the NSA or any other agency is currently capturing and storing encrypted data they can't afford to decrypt via targeted means they'll be able to retroactively decrypt it if they do manage to build a quantum computer and quantum supremacy would be a definite thing.
But right now there isn't an encryption the NSA can't break as long as there are people and additional assets involved in the process.
In fact I would be that for targeted attacks it would still bet easier to bribe, raid/hack the server farm or beat the snot out of someone in a black site than to use a quantum computer for quite a while after these things would be become a reality to factor the RSA private key corresponding with the key exchange of the traffic you want to decrypt.
> Interesting. Then shouldn't we (and PR people involved in QC) stop focusing on the cryptographical capabilities of QC, and start focusing on its other potential applications, like protein folding? Until now in the media, it seems like QC is synonymous with crypto ...
Yeah SIDH/SIKE are some of the stronger proposals in the NIST competition. But for now I'd consider them to be proposals, not something that should be deployed widely.
Yeah they haven't been standardised yet and if we want to push back as much as possible on retroactive decryption then we should move faster on standardising and deploying post QC key exchanges but it's not like these are completely flaky, untested and not well understood (I'm sure some of them are tho... which is why NIST competitions and their EU counterparts are important).
No classical functions as they exist now without added strengthening will be able to secure secrets against QC for long. OTOH, classical computing is reaching the limits of Moore's law, so barring process and fab cost reductions, CC ASIC costs will approach stability. If one wants to secure secrets without traditional digital logic (CC), it would get pricey, awkward and/or slow. I think we'll have to gradually keep looking more closely at cost to crack functions (i.e., GPU, ASIC, classical and q computation) much closer, in the spirit of scrypt and argon2. Zillions of rounds (is adding orders of magnitude in existing implementations) of AES or SHA3 maybe the tradeoff needed to thwart QC collisions / breakage with reasonable attacker costs & timeframe goals.
That's correct. Quantum computers can effectively halve the key size of symmetric encryption, but 128 bits is still secure, and we could always go to 512-bit keys.
However, in practice modern systems do ephemeral DH key agreement. Now, Shor's algorithm can be brought to bear on DH as well, but it ratchets up your costs because now you're attacking every single connection individually.
Suppose, miraculously, that you have a Quantum Computer which breaks any modern assymetric crypto for $1M in one hour. That's very impressive, but you won't use it to snoop on somebody's Google searches, that's $1M and an hour per search. "Big booobs", an hour and $1M later, "Big boobs" (ah, that first one was a typo), another hour, another $1M, "Bigger boobs". Not practical.
You _could_ attack the signature algorithm, allowing you to sign messages "as Google" and MITM connections but that's an active attack so it will have very poor deniability. Not a problem if you're the SVR or Mossad, deniability was never part of your mandate anyway, but awkward for the NSA or GCHQ whose governments prefer not to admit what they're up to. And lack of deniability is very awkward if you're organised crooks, that's going to get you banged up.
Right, which is why you'd cut out asymmetric step if possible (obviously not for the general HTTPS case, but okay for backups) or replace the asymmetric step with quantum-safe asymmetric crypto. What confused me was that the parent post was worried about scaling up AES to become quantum-safe, which is unnecessary. It's already safe.
> Early public-key systems are secure assuming that it is difficult to factor a large integer composed of two or more large prime factors. For elliptic-curve-based protocols, it is assumed that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible: this is the "elliptic curve discrete logarithm problem" (ECDLP). The security of elliptic curve cryptography depends on the ability to compute a point multiplication and the inability to compute the multiplicand given the original and product points. The size of the elliptic curve determines the difficulty of the problem.
All current public-key encryption, and short-key private-key encryption yes. XChaCha20-Poly1305 will still be safe. AES-256 (in an appropriate authenticated mode of operation and side-channel free implementation) will still be safe.
As for public-key encryption there are as-yet standardized algorithms that are likely secure. They're just slow. The NIST standardization should wrap up decades before any practical quantum computer is created, giving plenty of time to add some of these as options in protocols.
I can't get over the picture in the middle. Why is the intercepting computer a turret? Why is the secure bank on a slanted platform? I can just picture a meeting of the graphics team with facepalms and groans all around at having to come up with "something".
In the race between arms and armor, arms have always won. I wonder if the reverse is true in crypto. Will crypto always evolve to be one step ahead, or make a massive leap such that it will be multiple steps ahead.
I store moderately sensitive files in VeraCrypt containers. Are there post-quantum encryption algorithms on the roadmap for this type of storage software?
Its not here yet. Im surprised the problem wasn't already solved with ai/ml, big data, and blockchain. I think the problem personally is the sheer amount of ram that is needed and the ram aint ever gonna be fast enough to fill the buffers or to access. But it will be solved, soon im sure.
Gee, are all the down votes because of the issue that quantum computers will have with random access memory
Think about it. How much actual secure data do you and your bank need to transfer back and forth? Certainly not web UI elements or site chrome. For each use of your online account, there's probably 3 or 4k max actual data that you need to be secure. Your bank could mail you a 1GB random noise file, perhaps a backup, and you two could communicate for the rest of your life without any fear of anybody understanding what you're saying.
I understand that there's an entire e-commerce ease-of-use scenario where secure communications becomes mission-critical. And I'm certainly not suggesting to replace all secured comms. My only point is that there are parts of this problem that are very tough and there are parts of this problem that we have made more difficult than it has to be simply in an effort to standardize and abstract everything.