How Classical Cryptography Will Survive Quantum Computers

Yes π does have a precise definition as the ratio of the circumference of a circle to its diameter, the problem is, π cannot be expressed precisely in mathematical terms which was my original point. Math cannot describe a circle using π because no matter how many decimal places you use, it is never quite accurate.
You could say
π = 3.14159 but if you examine the circle πd microscopically you would find the ends don't quite line up.
You could then define π to a thousand decimal places but microscopically the circle circumference still would not line up exactly. It would be close, but not exact.
If you use the equation of a circle
x^2+y^2=r^2 to define the circumference, no matter how many millions of points you make there is, microscopically gaps between the points. If you join them with lines you create a polygon. It may be microscopic lines but it is still polygon with millions of sides because no math exists to create the curve between those points except by using π and as we know already, π is an irrational that cannot be precisely defined.
Therefore math can only approximate a circle.

 

And not only computers but pretty much anything in the real world.
Laws of math might be precise but physical world never is. It's just not possible.

 

"ratio of the circumference of a circle to its diameter" - this statement based on precise mathematical terms. π is a precise mathematical term.
I think you have too narrow imagination what is a mathematical term. The fact that something is not precisely expressable in actual numbers doesn't mean it is not a mathematical concept, term.

All you are stating are problems when someone wants to apply this mathematical term in other part of human knowledge for example computer engineering.

 

Yes I understand exactly what you mean by that.
Ok let's put it another way
If you do not give π a numerical value and you say π is the ratio of the diameter of a circle to its circumference, that is fine to say, conceptually π represents that undefined ratio.
But, as soon as you give π a numerical value, then, clearly π is not the ratio of the diameter of a circle to its circumference. It is almost, but not.
Math says that does not matter but I think it does when you want to use math to describe the universe.
That is to use math in an abstract sense where numerical values that don't quite fit, are considered irrelevent and there is a school of thought amongst some mathematicians that says we are tailoring math to make it fit things it doesn't.

 

You can google around w/ "photon", "interference", "double slit" or such. Unlike black body radiation, it won't require advanced math to understand (tho explanation is another thing), but in short single photons will be plotted like particle but after thousands of trials those plots make interference fringes. From my understanding of your post #22 I think it can't be explained, but you can try. Other physics fan might wonder why I didn't mention Compton scattering as it shows light have momentum which might be more characteristic to particle, but it doesn't change the conclusion that light is not particle in classical meaning. Well, possibly I had to say that quantum physicist use the term particle in different meaning, i.e. sth countable rather than sth like a ball.

 

@RockLobster @reasonablePrivacy
The fact is both of you are right. Sure, math is cleverly constructed not to be bothered by error. In math there're many ways to define π and you don't need to define it as the ratio of circumference to diameter, but whatever def you use, there's no problem of error. But it doesn't mean math do not include ANY sense of error or approximation. But the meaning or error/approx in math is completely diff from usual sense. Remember how you learned integral. You covered a graph w/ rectangles which have error for section, then you diminished the error by using narrower and narrower rectangles, and defined the section as its limit. Note "lim_{n → ∞}f_n = f" doesn't mean f_n becomes f when you increased n. It just mean you can diminish error whatever degree you want, however, the error will never be 0 (we use ε-δ for precise argument). Put it in another way, in math there're 2 use of "=", the one is equivalence and the other is just a definition, e.g. "0.99999... = 1" comes from the latter. When limit is closed (belongs to the same set which f_n belongs to), mathmatician can construct sth new upon it, but they never confuse that notion. One way to define π is "2∫_0^1 dy/√(1 - y^2)", you see it uses limit in 2 ways, the one is improper integral and the other is integral itself. Regardless of Riemann integral or Lebesgue, it includes error in certain sense.

As to the question whether math can describe circle, a hard problem exists in another aspect. You know a circle can be defined as a set of points in R^2 whose Euclidean metric from certain point are all equal, also axiom of metric and def of Euclidean metric, right? OK, then how those infinite (yeah, uncountable infinite) points can make continuous curve of circumference? You may even know Cauchy sequence and completion, but were you really satisfied when you leaned it? I was not. That seemed to be technique which cleverly bypass the hard problem by, yes, ε-δ. My boss when I was undergraduate said to me, no body really knows what the "continuous" means. I think that's true, not to mention CH, Banach-Tarski, and some other strange "pardoxes" (I'm not saying paradox in mathematical meaning). It's no matter as long as you just want to use math for sth useful, but if current composition of Euclidean figure is good enough is another matter, just like Peano axioms have serious problem to describe natural numbers.

I'm afraid we're going more off-topic.

 

@142395 excellent explanation, you made some points I had not considered I will look them up and yes we did get a little off topic but still, it is all relative in a roundabout way.

 

Going back to the topic of quantum resistant encryption.
What if you use two or more keys instead of one so to re-encrypt the entire text or file after it is encrypted with the first key?
You could still present the separately generated keys as one key, the encryption applications would have to know to split it.
I also would be interested to know, for example, if you take two, 2048 bit keys and use them to encrypt the same text or file twice, would that be more resistant to cryptanalysis than encrypting it once using a single 4096 bit key?
Obviously it would take longer but who is really going to care about that as long as they know their crypto is secure?

 

I think classical brute-force attacks would have take:
1. Twice the time for file encrypted two times
2. Time to decrypt 2048-bit encrypted file to the power of two for one 4096-bit key.
Second option takes more time, so is more secure.

 

Yes that's what I thought and while only partially understanding the RSA cryptanalysis, it seems to be based on the fact the original text is encrypted with the same key which somehow causes a repetition, I am wondering if that has something to do with the use of modulus, which in RSA is equal to the prime, so if you can figure out the modulus used, you have the Prime, but if the encrypted text is then re-encrypted I would have thought that would obfuscate any such repetition of values. I think I'm gonna write to Bruce Schneier about this.
Of course all the sneaks and infiltrators would kick up arguments in github about the length of time taken for double encryption, and how it would break the internet and pgp etc like they always do when anyone proposes improvements to secure encryption.

 

That's not necessarily the case in symmetric encryption. Even when you use 2 independent keys, there can be a (kind of) master key which can decrypt both of encryption at once. The question is if that key have to be longer than each key. This is why it have to be proved that the key space of 3DES is wider than DES. While that was proved, the proof don't say if it's 3 times wider (3DES is not exactly DES * 3, but that's not important here). See below.

TBH I don't get what exactly you mean, but note the most basic attack to RSA only require public key. You just need to factorize n (= pq), a part of the public key . So as long as you published both of 2 public keys, attack can be done within at most twice as much effort, assuming 2 keys are independently and randomly generated. But if you didn't publish public key, IDK what attack can be done. Most attack to asymmetric encryption is based on assumption that you have public key.

In RSA, encryption is just a powering a plain text P by encryption key e (ofc you have to encode all characters to numbers before it) and taking mod by n. Decryption is powering a cipher text C by decryption key d and taking mod by n. If P is powered by e and then d, it returns to P on space of mod n. Euler's th ensures such d exists, and thanks to Euclidian algorithm you can calculate d from e, p, q.

 

Yes I did some more reading since I wrote that post, I didnt know if the known attack vectors were against the cipher text or the public key. As you rightly explained they are against the public key, so my idea to double encrypt wouldn't help any.
From a security point of veiw, I think people should look at the way in which users of public key encryption are encouraged to publish their public keys on key servers which also provide their identity and the email address they associate with that identity.
Call me tin foil, but when you put that together with what we have just been discussing, shouldn't common sense suggest something nefarious about that?
Actually, that reminds me, I was reading the issue tracker on the github of one of the public key encryption implementations, someone was saying when they generated new keys, the application rechecked the "upload keys to keyserver" button even after he unchecked it and uploaded the keys regardless.
I would suggest public key encryption users only use published keys for non critical communications, such as introductions and then exchange unpublished public keys thereafter, perhaps by way of a secure email.

 

Today I read about Meet-in-the-middle attack and it turned out you are right. If you use 2 symmetric 256 bit keys, double encryption only add 1 bit, makes it 257 bit security and it means twice the time. For triple encryption however, it will be 512 bit. Note in usual brute force w/out Meet-in-the-middle it's 512 bit and 2^256 times the time. What I said earlier was that attack can be less than 512 bit. I misinterpreted the word "twice".

I don't call you tin-foil. I have GPG key pair but haven't publicly disclosed its pubkey yet. Given Big brother records all internet traffic and 2048 bit key will be broken around 2030, I don't want my private conversation 'mistakenly' going to be revealed even after 12 y later. Yeah, even with 4096 bit key, nobody knows when the quantum computer with RSA-breaking capability will be realized, tho I'm relatively optimistic about it. I think using 2 key pairs for general use & private use will be good (also considering you may not always find your key's compromise) especially for those who need maximum security, as long as your counterpart doesn't complain about it. Not to mention potential risk of publishing email address attached with the key.

 

@yuki I know you didnt call me tin foil. When I say, "call me tin foil, but..."
It is a figure of speech, same as saying, "I know this sounds like tin foil, but..."
Anyway, yeah it seems like we use encryption today, that everyone knows will be broken tomorrow.
OpenKeyChain doesnt even allow to generate ECC keys except for signing.
If you want encryption keys you are limited to RSA 4096.
Seems to me they are reluctant to implement anything better and its not like its hard to do, the algorithms are already in crypto libraries but it seems that some people have patents on eliptic curve math formulas that prevent them being used.
Doesn't it seem ridiculous that people can patent math?

 

I don't think a quantum computer would be programmed to do addition or multiplication. A standard computer is fastest for this. Quantum is faster for division (or rather inversion).
Finding a number X where A multiplied by X = B. In crypto, the problem is harder because it is a log computation i.e. find a number X such that A raised to the the power of X = B.
As for how a quantum computer would do this, you would need to understand Shor's algorithm.
And no, don't ask me to explain Shor's algorithm. I have read several descriptions of it and still don't really feel like I understand how it works.

 

I took casual glance at Shor's algo for curiosity, and it seems the key is the rank estimation can be done in the same computational order of quantum discrete Fourier transform which is polynomial time. So I looked at QDFT, but soon realized it's not I can understand in 30 min or maybe even in 1 day, as it appears to require decent understanding of how q-gate computer works. I'll pass it but may look back in the future.

TBH I didn't know q-gate computer can accelerate DFT tho it seems only for peak and not full spectrum, so I got a hint of why so many effort have been put on it. Considering how FFT made revolution in
first-principles calculation, it will again make revolution for chemistry, physics, pharmacology, etc..

 

Quantum Computing and Cryptography

https://www.schneier.com/blog/archives/2018/09/quantum_computi_2.html

 

Post-quantum cryptography a major challenge, says expert
November 9, 2018
https://www.computerweekly.com/news...um-cryptography-a-major-challenge-says-expert

 

Quantum computing for the qubit curious
Cathal O'Connell prepared this brief primer
July 6, 2019
https://cosmosmagazine.com/physics/quantum-computing-for-the-qubit-curious-1

 

Factoring 2048-bit Numbers Using 20 Million Qubits

https://www.schneier.com/blog/archives/2019/10/factoring_2048-.html

 

Quantum Computing Is Coming, Bit by Qubit

https://www.nytimes.com/2019/10/21/science/quantum-computer-physics-qubits.html