NIST requests ideas for crypto that can survive quantum computers The United States' National Institute of Standards and Technology has issued a “Notice and request for nominations for candidate post-quantum algorithms.” The Institute (NIST) has cottoned on to the fact that “If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems …
There was a news item not that long ago about a major browser maker testing a new form of public-key cryptography that might have some resistance to quantum computers. One of the problems, though, was that it wasn't certain the method would even be secure against ordinary computers. As I recall, it was based on lattice problems.
That's been the current situation. Creating a truly robust encryption system is HARD because it's a case of having to be lucky everywhere. Just ONE slip and you'll blow your whole scheme wide open.
Such has been the case with all the post-quantum systems proposed so far. As I recall, all of them have either had flaws uncovered or are so computationally demanding in the classic sense as to be impractical for all but small pieces of information.
What can be done in case the overhead is acceptable is (obviously) to use one traditional and one fancy scheme and combine the results (eg. for key exchange you'd hash them together to get the actual session key, for signature checks you'd need both signatures accepted).
This can also be leveraged to give somewhat better protection against things such as side-channel attacks.
I have a somewhat foolproof solution for point to point communications, using a digital one time pad communicated physically via USB or external HDD.
It wouldn't work for any random website for blatantly obvious reasons, but between two known entities it'd be fine. For instance, between home and business and between you and bank would work perfectly well.
The biggest problem is that 1 megabyte worth of data would require 1 megabyte worth of unique one time key pads, but with multiple terabyte sized external HDD's that's not THAT much of a limitation since transferring 2GB a day would take 1024 days, or 2.8 years to go through. High levels of data transfer such as 250GB a day would still take ~8 days to go through 2TB's worth.
It'd be theoretically unbreakable if done correctly.
Depends. That's moving from one threat class to another.
If the threat your trying to defend against is interception and remote decryption through quantum computing then one time pads work perfectly well and it would be feasible to have software wipe keys that have been used.
Against local attacks with physical access to the device, or the infamous $5 spanner attack with physical access to the user popularised by XKCD, then you really haven't got much security regardless.
Thing is, one dovetails into the other. The moment you use OTP or some other quantum-hardened system, you're likely to have just thrown up a big fat bullseye on yourself. At which point, you better be either a wimp or a masochist.
It's even easier though* given quantum computing. Bob can tell if the qubit from Alice has been observed by the waveform collapsing. Makes a very nice key exchange channel.
* It's getting the quantum qubits to survive without near absolute zero and for more than a handful of milliseconds that's the hard bit.
Bob can tell if the qubit from Alice has been observed by the waveform collapsing.
Dude! You cannot just check whether "the waveform collapsed" any more than you check the probability of of the next dice throw showing snakes.
The second use is to send an equal size replacement block of One Time Pad (noise). Kilobits blocks is probably about right.
Noise .XOR. New Noise provides nothing. This 2nd use to refill the One Time Pads seems to be doable.
The messages (info) being sent would need to be hashed into pseudo-whitenoise. Deterministically / algorithmically should be fine. Trivial. That's required to eliminate the obvious attack over the long run.
Even if this process was arbitrarily truncated after N repetitions, if N=1000 then it's still a vast improvement in the practical application of One Time Pads.
Call it Two Time Pads.
If anyone else can figure out how to insert even the tiniest sliver of Pad growth into this algorithm, then it'd be the champ forever. That seems impossible to me.
That's the thing. This sort of code would be unbreakable against pretty much anything code breaking wise from decryption from interception in transit. What it doesn't guard against is compromise of the hardware/endpoint or the user. A small bit of thermite over the circuit board with an anti tamper device would probably be the solution to that, although it'd require military type R&D and severly paranoid users with an acceptence of their office/house being burnt down if their computer gets compromised.
I'm not convinced that using a one time pad twice as suggested above is a good idea, since as soon as one code is cracked you'd then have the next pad, which would give you the next pad, etc. I think physical transfer of keys would be the way to go if you needed to be paranoid enough to implement this.
The Key problem with this subject, is that people start spouting "Well because Quantum Computers can break all encryption, therefore the following holds true....." que some logical and straight-forward reasoning that is fundamentally wrong as the initial premise is wrong.
Quantum computers are best suited for Optimization problems, classic examples being the "Travelling Salesman Problem" or TSP. Public-Private Key is likely to be problematic and not suitable in the age of the Quantum Computer, but currently it's looking likely that Symmetric keys can provide some protection and even developments like Grovers algorithm can be defeated by increasing Key-size.
Post-quantum Cryptography will only advance, if we as a community actually learn about the subject and stop using "pseudo-intellectual" rules of thumb, and general positions like "ALL ENCRYPTION IS DOOMED IN THE AGE OF QUANTUM COMPUTING". It's sensationalist, and fundamentally wrong.
sensationalist
YES!
Quantum computers are best suited for Optimization problems, classic examples being the "Travelling Salesman Problem" or TSP.
NO. There is no indication that Quantum Computers can solve NP-complete problems in polynomial time.
See: BQP
And also: MUST READ COMIC
Again another fail from The Register re basic Crypto....
NST are trying to find a POST Quantum Crypto algorithm (PQC in the jargon). That is a classical algorithm which resists a quantum computer. The current top favourite is based on lattices, which is something Google has been testing, based on a technique developed at Microsoft.
The reference to the Microsoft work in the article is about Quantum Key Distribution (QKD). This is something very different, which uses quantum mechanics to solve a very very tiny part of the security problems.
Its in the letters folks PQC != QKD
Quantum computing news (98% Trump-free)
As many of you will have seen, my former MIT colleagues, Lior Eldar and Peter Shor, recently posted an arXiv preprint claiming a bombshell result: namely, a polynomial-time quantum algorithm to solve a variant of the Closest Vector Problem in lattices. Their claimed algorithm wouldn’t yet break lattice-based cryptography, but if the approximation factors could be improved, it would be well on the way to doing so. This has been one of the most tempting targets for quantum algorithms research for more than twenty years—ever since Shor’s “original” algorithm laid waste to RSA, Diffie-Hellman, elliptic-curve cryptography, and more in a world with scalable quantum computers, leaving lattice-based cryptography as one of the few public-key crypto proposals still standing.
Unfortunately, Lior tells me that Oded Regev has discovered a flaw in the algorithm, which he and Peter don’t currently know how to fix. So for now, they’re withdrawing the paper (because of the Thanksgiving holiday, the withdrawal won’t take effect on the arXiv until Monday). It’s still a worthy attempt on a great problem—here’s hoping that they or someone else manage to, as Lior put it to me, “make the algorithm great again.”
The legacy commercial crypto systems currently in use are subject to QC. The advent of QC guarantees that nation states-- first movers for QC since early tech is almost invariably atrociously expensive-- can sign an update to anyone's device, including those devices for which the nation-state has not yet obtained the keys. Who needs zero-days, complicated drive by attacks, Rowhammer, phishing attacks, rubber hoses, satchels of cash, or any of the others when you can just rewrite the software after stealing the source code which is secured by computers subject to QC attack. Presuming you can't steal the source code using simple ordinary means.
There are a few speed bumps that can be thrown up, local keys using TPC add very slightly to the effort (or maybe not, most implementations are sadly deficient), air gap (really? What did you say your productivity is? military can afford this but can YOU?), or one can just block software updates but then mundane security holes blow up (XP users rejoice! You are ahead of the curve!) not to speak of network comms being broken.
One needs PQC, or some other alternative new invention (at least for software updates)...
Europe has already some initial recommendations/ under investigation algorithms here: https://pqcrypto.eu.org/docs/initial-recommendations.pdf
Symmetric encryption:
- AES-256
- Salsa20 with a 256-bit key
Symmetric authentication:
- GCM using a 96-bit nonce and a 128-bit authenticator.
- Poly1305
Public-key encryption:
- McEliece with binary Goppa codes using length n = 6960, dimension k = 5413 and adding t = 119 errors.
- Quasi-cyclic MDPC codes for McEliece with parameters at least n = 2 elevated to 16 + 6; k = 2 elevated to 15 + 3; d = 274 and adding t = 264 errors.
- The Stehlé-Steinfeld version of the NTRU lattice-based cryptosystem.
Public-key signatures:
- XMSS
- SPHINCS-256
- HFEv- multivariate-quadratic signature system
----
Right now, between friends, or similar, when both can meet personally, they can exchange elliptic curve public keys or even passwords, and then encrypt and send to the other everything inside encrypted capsules.
It is free and open source:
https://www.fh-wedel.de/~an/crypto/Academic_signature_eng.html
From the author:
"There is increasing political pressure in my country(Germany) to criminalize encryption, further deteriorate civil rights and march into an Orwellian society. Thus the day may be near when we will all need steganography, hide our enforcement of privacy and need "plausible deniability".
To get closer to this defense I introduced the concept of a "NADA Cap". NADA stands for No Access Data Available. A NADA Cap is an additional layer, which protects all format information and access data. A capped cipher file is indistinguishable from noise in toto. You can feed it to whatever "Die the Hardest" test of randomness without detecting the slightest sign of deviation from randomness. (Achieving this beautiful, perfect cipher state in Academic Signature gave me deep satisfaction.) Thus you will now always be able to claim your EC-cipher is just data from your last SETI search round, or you XOR it with your favourite Michael Jackson video and claim the cipher were just a one time pad for your illegally downloaded video. A featureless cipher is the ideal input for any steganography tool. There is always a good explanation for noise in your pictures or audio files if it truly looks like noise.
Upon producing en elliptic curve cipher you can now tick a box "apply NADA Cap". If you do so, you will be asked for a NADA Cap key. If you use "intrinsic" the Cap key will be deterministically set from the public key data of the recipient. The "public key" should then be kept somewhat confidential, like confidential in the group of say your 10 coworkers. The recipient has to guess then, which of his private keys the file was encrypted to. Alternatively you could share a newly agreed on keyword within your group and keep that confidential. In this case you may even have your plain public key accessible to anyone. Please note, that this would also render your ECC-cipher secure against Shor's Algorithm which may become a threat after the future advent of Quantum Computing. Without knowledge of the ecc-header file, quantum computing doesn't help them shit."
( in. https://www.fh-wedel.de/~an/crypto/Read_me.html )
The Register 
Biting the hand that feeds IT
Copyright. All rights reserved © 1998–2024
