# How Classical Cryptography Will Survive Quantum Computers

Discussion in 'privacy technology' started by ronjor, Dec 30, 2017.

1. ### ronjorGlobal Moderator

Joined:
Jul 21, 2003
Posts:
64,321
Location:
Texas
Posted By Joshua Holden on Dec 27, 2017

2. ### itachi SempaiRegistered Member

Joined:
Dec 30, 2017
Posts:
4
Location:
Georgia
well classical cryptography cant survive quantum computers... some research said that it would take 7-8 terabyte key to hold quantum computers i just dont remember exactly what type of key they were talking about

3. ### RockLobsterRegistered Member

Joined:
Nov 8, 2007
Posts:
1,791
I wish I could find an article that explains how quantum computing is applied to conventional math problems like calculating an encryption key. Or even how a quantum computer can calculate 1+1.
If the qbits are in a quantum state so each bit is therefore 1 or zero.
1 or 0 + 1 or 0 == 0 or 1 or 11
Edit: 1 or 0 + 1 or 0 == 0 or 1 or 10
How is that useful? It makes no sense to me when we already know without doing the calculation that the sum of two bits must be either 0 or 1 or 10.

Last edited: Dec 31, 2017
4. ### reasonablePrivacyRegistered Member

Joined:
Oct 7, 2017
Posts:
502
Location:
Member state of European Union
11? What is that? Product of boolean or (logical alternation) or can only be one bit value.
Table of truth for or (logical alternation):
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Sometimes symbol ∨ is used instead of + to note that is boolean calculation.

I don't understand quantum physics, but if I understand correctly qubit has probability of being in one state or another. Other interpretation tells that qubit can be in both (0 and 1) states at the same time.

Edit:
Mistakenly used and instead of or.

Last edited: Dec 31, 2017

Joined:
Aug 26, 2011
Posts:
120
Source?

6. ### reasonablePrivacyRegistered Member

Joined:
Oct 7, 2017
Posts:
502
Location:
Member state of European Union
I was thinking you are talking about different operations, but even if you are talking about addition on binary representation of number you are wrong.
01+01 = 10
Decimal representation:
1 + 1 = 2
01 is binary representation of number 1.
10 is binary representation of number 2.
11 is binary representation of number 3.

Last edited: Dec 31, 2017
7. ### RockLobsterRegistered Member

Joined:
Nov 8, 2007
Posts:
1,791
I can't say I really understand it either, except to say quantum computing seems to be an adaptation of the quantum idea that particles can exist in more than one state at the same time, both as wave and a particle, its quantum state is as a wave.
But once that wave is observed, recorded or monitored it becomes a particle. Experiments with light appear to show that is the case.
The two slits experiment appear to show an interference pattern associated with waves while detection equipment detects particles.
So, supposedly quantum computing is going to use quantum state, wave functions which have no defined value as long as no one or nothing observes them but I don't understand how that is possible either.
If you read Robert Lanza's book he says NOTHING exists in solid form until we observe it, up to that point it is in its quantum state, but I'm not sure if he means to say it returns to a quantum state when we cease observing it. I think he does mean that.

Last edited: Dec 31, 2017
8. ### RockLobsterRegistered Member

Joined:
Nov 8, 2007
Posts:
1,791
Yes sorry I meant 10 as the other possible outcome of the sum of two bits

9. ### RockLobsterRegistered Member

Joined:
Nov 8, 2007
Posts:
1,791
Just for fun I'll tell you why I got banned from physics forums, which is related to quantum theory.

I said light particles do not exist because light as we know it is actually a disturbance in an invisible medium that is the fabric of the universe. We cannot normally detect this medium but it is there.
The phenomenon we call light is caused by vibrations at its source, these vibrations are transmitted through the medium as waves. In the same way as vibrations caused when a rock is dropped into a pond travel through the water as waves.
If we are in the pond we detect those waves moving.
So what are we detecting exactly? We are detecting nothing eminating from the rock itself, we are detecting the medium. In this case, particles of the water touching us.
Therefore, rock dropping activity creates waves in the medium AND we detect particles. Of the medium.
I thought this would explain why light appears to be particles AND waves in a far more rational way than quantum theory does.
So the reason light appears to be both wave and particle we are not detecting light particles we are detecting vibrations in the medium which is the invisible fabric of the universe.
Our retinas detect these disturbances and convert it to electrical impulses. Our brain then creates a representation of this in our imagination as light (which of course is only in our imagination)
The moderators at physicsforums.com banned me for suggesting that theory lol.

Last edited: Dec 31, 2017
10. ### FanJUpdates Team

Joined:
Feb 9, 2002
Posts:
3,113
Huh? Here is something going wrong.

01 -> (0 x 2**1) + (1 x 2**0) = (0 x 2) + (1 x 1) = 0 + 1 = 1

and

00 -> (0 x 2**1) + (0 x 2**0) = (0 x 2) + (0 x 1) = 0 + 0 = 0

10 -> (1 x 2**1) + (0 x 2**0) = (1 x 2) + (0 x 1) = 2 + 0 = 2

I leave the rest to you guys. Enjoy

11. ### reasonablePrivacyRegistered Member

Joined:
Oct 7, 2017
Posts:
502
Location:
Member state of European Union
I copy pasted this line and then typed something wrong. Sorry for mistake.

12. ### itachi SempaiRegistered Member

Joined:
Dec 30, 2017
Posts:
4
Location:
Georgia
here i found research it was about RSA public key size that should be 8 terabytes in order to have same strength as it has against todays computers

https://eprint.iacr.org/2017/351.pdf

and this is stive gibsons discussion on this topic:

Joined:
Jul 30, 2014
Posts:
425
14. ### RockLobsterRegistered Member

Joined:
Nov 8, 2007
Posts:
1,791
It seems to me, quantum mechanics is an attempt to describe the universe mathematically, but they don't seem to consider that math cannot even describe something as simple as a circle, anything to be concerned about, but it probably is.

15. ### reasonablePrivacyRegistered Member

Joined:
Oct 7, 2017
Posts:
502
Location:
Member state of European Union
I agree that RSA surely isn't suitable for quantum era, but this kinds of attacks is not RSA fault. This is protocol-level vulnerability, not some primitive crypto alghorithm vulnerability.

16. ### RockLobsterRegistered Member

Joined:
Nov 8, 2007
Posts:
1,791
Well really it is an attack on the algorithm.
I dusted off my old pre calculus book to try and figure out how this works and although I still only partially understand it, seemingly what it amounts to is the quantum computer's ability to easily find the phase period (when the function values recur) of the function fx=m^x(mod n).
That is done by transforming that function to a hyperbolic sin and cos from which the periods can be found using the quantum computer.
Once you have that, cracking the private key is straightforward classical computing.
So basically we should consider, everything the alphabets have accumulated up to now that used RSA to encrypt, is pwned.

Last edited: Jan 11, 2018
17. ### FanJUpdates Team

Joined:
Feb 9, 2002
Posts:
3,113

Ever heard about things like:
x = a + r cos (t)
y = b + r sin (t)

or
(x - a)**2 + (y - b)**2 = r**2

18. ### Yuki2718Registered Member

Joined:
Aug 15, 2014
Posts:
1,483
RSA need terabytes of a key to resist quantum cryptanalysis, but lattice encryption described in the article is different beast. It is considered quantum-resistant w/out such massive key, tho each of lattice crypto needs thorough scrutiny.

I'm not a quantum computer expert, but unlike classical computer which solve problems deterministically, quantum computer solve problems probabilistically.
In quantum computer, 1 + 1 = 1 translates to: (prob being 1 is 100%) + (prob being 1 is 100%) = (prob being 1 is 100%)
Then, how about: (prob being 1 or 0 is 50% each) + (prob being 1 or 0 is 50% each) ?
This is equivalent to calculating these 4 eqs SIMULUTANOUSLY:
0 + 0 = 0 (25%)
0 + 1 = 1 (25%)
1 + 0 = 1 (25%)
1 + 1 = 1 (25%)
Now you got a hint of how quantum computer use entanglement to calculate, right? Matrix is used to represent quantum state.
But as quantum computer solve problems probabilistically, it have to repeat the same calculation again and again to get accurate result (still you don't always get 25% for the ex., just around 25%). So it conducts thousands of calculation to do it, obviously it's not suitable problem for quantum computer considering classic computer just need to calculate 4 times. but it still excel in solving some kinds of problems, BUT ONLY some kinds of problems. IOW, quantum computer is not a magical future computer, it's more of an expert machine for specific problems.

Another confusion comes from not distinguishing quantum-annealing and quantum-gate computer.
Have you heard that quantum computer is already established? That is quantum-annealing computer, like D-Wave.
Current state of quantum-gate computer which is known to be able to break RSA is, unfortunately, almost a toy as it is at most only 50 q-bits while q-annealing computer exceed 2000 q-bits.
Q-annealing is more of an algorithm than computer itself so it can be handled in classical computer too, tho real q-annealing computer is more efficient.
It is said that about 100 million q-bits are required to break RSA in q-gate computer, so most experts seems to agree that it needs at least a decade to come true, while some experts even doubt such computer can even be realized considering how q-bits in q-gate computer is fragile.

I personally feel breaking RSA won't come in foreseeable future and it's better to mind 2030 problem of RSA 2048, as it is almost promised.

[Edited some unclear arguments]

Last edited: Jan 13, 2018
19. ### Yuki2718Registered Member

Joined:
Aug 15, 2014
Posts:
1,483
Off topic, so I don't go much but...

Maybe they felt you're introducing the old ether theory, or maybe not. I think your theory is actually what everyone will once or twice think about when they hear that lignt is wave & particle at the same time, so IDK why you're banned.
It appears confusion comes from that explanation itself. Physicist (and magazines, TVs, etc.) like to use imaginable example for explanation to avoid scaring audience by flood of formulas, but most often such example is not exactly right, so it has potential to confuse those who think well, sadly.
Shortly, light is NOT particle nor wave nor both of them. It's sth which can only be (approximately) described by math.

Downside of your theory is it can't explain black body radiation, photoelectric effect, interference by single photons, etc. especially quantitatively (but eventually qualitatively too).
Former 2 can be explained not because light has nature of particle, but rather because energy of light is descrete and there's minimum unit of energy in every wave length. Quantum is not exactly particle, but it's a unit of descrete energy. In some phenomena it looks like as if light is particle, but it doesn't mean it's really particle.
Imagine, you're given 100J of energy, you can put it in a ball w/ 100, or 3 balls w/ 33.3 each, but whatever number of balls you chose, there's always unit of energy, 100/N (don't ask 15 + 32 + 53 etc.). You can also put energy in sound wave, but in this case energy is continuous. Actual observation only matches to ball theory, but what important is not that ball is particle, but energy have to be discrete. OTOH, single photon interference can't be explained if you think light is wave who transmit through medium. Well, I can go further but should stop here.

20. ### reasonablePrivacyRegistered Member

Joined:
Oct 7, 2017
Posts:
502
Location:
Member state of European Union
I was referring to attack Stefan Froberg mentioned. He mentioned attack that is not quantum attack.
Maybe I am not speaking clearly in English. Sorry for that.

21. ### RockLobsterRegistered Member

Joined:
Nov 8, 2007
Posts:
1,791
You are defining points on the circumference of a circle. Consider how you will join them

22. ### RockLobsterRegistered Member

Joined:
Nov 8, 2007
Posts:
1,791
Please do continue, with quantum computing right around the corner discussions about quantum theory are surely on topic in this forum? Moderators will undoubtedly correct me on that if I am wrong lol...
Besides, your insight is fascinating. Well, to me it is.

23. ### FanJUpdates Team

Joined:
Feb 9, 2002
Posts:
3,113
I'm just following axioma's, definitions, and rules. That's just basic math. That's where it all start.
What you mean with "Consider how you will join them" I don't know. Must be my bad English...
(PS: yes, there are other axioma's and definitions in math; like for example we have Euclidian and non-Euclidian; etc.).
I leave it to that.

24. ### RockLobsterRegistered Member

Joined:
Nov 8, 2007
Posts:
1,791
What I meant was, because π is an irrational, all the math based on π has a margin of error. So mathematically a circle can only be described approximately.

25. ### reasonablePrivacyRegistered Member

Joined:
Oct 7, 2017
Posts:
502
Location:
Member state of European Union
Changing = to ≤ (less than or equal to)?
π has precise definition. You just can't express it in some other forms such as decimal notation. Mathematical formulas based on π are precise.
Technology (computer) has a margin of error, when expressing π and doing calculations based on them. It should be noted that there are developed methods for analyzing margin of error, so even if computer is doing calculations based on imperfect expression of π, you can keep margin of error at reasonable level.