How cryptography shows that quantum mechanics is incomplete?

Started by Baruch, March 23, 2019, 05:34:11 AM

Previous topic - Next topic

Baruch

In quantum mechanics, information is neither created nor destroyed (barring black holes).  See my argument after the film, on why the title is a rhetorical question.

https://www.youtube.com/watch?v=HF-9Dy6iB_4

In a cryptography situation, if you know the key, you can encrypt a message, and decrypt it too.  The total process involves conservation of information.  And QM supports this total model.  But you really encrypted a message using a random key (in the sense that you don't know what it is) then you won't be able to decrypt the message, only encrypt it.  If you look at the Shannon Information Entropy for a classical system, or the Von Neumann Information Entropy for a quantum system, you will see that the entropy (and thus the information) changes going from the plain text to the crypt text.  The missing information is restored when decrypted by someone with the correct key.  With asymmetric key exchange, you do have a situation where there is a public key and a private key.  I encrypt my email with my private key (which subtly matches the public key), and using a third party key holder, you can use my public key to decrypt my email.  Without knowing my private key.  Again, a more sophisticated situation, but because the plain text is restored from the crypt text, information is conserved over the total process.
Ha’át’íísh baa naniná?
Azee’ Å,a’ish nanídį́į́h?
Táadoo ánít’iní.
What are you doing?
Are you taking any medications?
Don't do that.

SoldierofFortune

Firstly i should express that i havent got even a clue about about what you are talking about?

What do you mean by information? it is something like "the sun rises in the east" or "birds fly, fish swim"...

if the information you mean in the universe is this, the mission for us is to discover that

Baruch

Quote from: SoldierofFortune on March 23, 2019, 03:59:40 PM
Firstly i should express that i havent got even a clue about about what you are talking about?

What do you mean by information? it is something like "the sun rises in the east" or "birds fly, fish swim"...

if the information you mean in the universe is this, the mission for us is to discover that

Well, the OP is a rhetorical question ... turns out, within the limits outlined, cryptography is consistent with quantum mechanics being complete.

I will give you an elementary lesson ...

Shannon Entropy is for classical systems ...

https://www.youtube.com/watch?v=R4OlXb9aTvQ

This whole series (this is part 12) is the best intro to Information Theory ever.  It really helped when I first studied this 4 years ago.
Ha’át’íísh baa naniná?
Azee’ Å,a’ish nanídį́į́h?
Táadoo ánít’iní.
What are you doing?
Are you taking any medications?
Don't do that.

Cavebear

Quote from: Baruch on March 23, 2019, 05:34:11 AM
In quantum mechanics, information is neither created nor destroyed (barring black holes).  See my argument after the film, on why the title is a rhetorical question.

In a cryptography situation, if you know the key, you can encrypt a message, and decrypt it too.  The total process involves conservation of information.  And QM supports this total model.  But you really encrypted a message using a random key (in the sense that you don't know what it is) then you won't be able to decrypt the message, only encrypt it.  If you look at the Shannon Information Entropy for a classical system, or the Von Neumann Information Entropy for a quantum system, you will see that the entropy (and thus the information) changes going from the plain text to the crypt text.  The missing information is restored when decrypted by someone with the correct key.  With asymmetric key exchange, you do have a situation where there is a public key and a private key.  I encrypt my email with my private key (which subtly matches the public key), and using a third party key holder, you can use my public key to decrypt my email.  Without knowing my private key.  Again, a more sophisticated situation, but because the plain text is restored from the crypt text, information is conserved over the total process.

Did you just say that you are falsifying who you are using 3rd party encryption?
Atheist born, atheist bred.  And when I die, atheist dead!

Baruch

Nope.  That is a different discussion.  Here is how PKI keys are used asymmetrically.  You know a reliable third party key holder.  You create a key pair, one private, the other public.  You send your public key, along with your verified ID to the third party key holder.  Other people do the same.  So if I want to exchange encrypted mail with another party, I encrypt my outgoing meal with someone else's public key.  The receiving party gets my public key from the third party key holder, as well.  Once the receiving party gets my email, they have their private key all to themselves, and use it to decrypt my message, that was encrypted with their public key.  The other party, sending encrypted mail to me, does the same thing symmetrically.  They encrypt their email using my public key, and when I receive it, I use my private key, that only I have, to decrypt the message sent to me.  Basically blind sharing of keys.

Unfortunately the majority of asymmetrical key exchange, is based on the factoring of dual prime numbers (an integer made up of just two large primes multiplied together).  Quantum computing is uniquely able to factor dual prime numbers.  Quantum computing is an analog/digital hybrid, useful for certain hard problems, but not all, and not practical for ordinary computing.  Once you have factored the large prime, you can read an asymmetrical PKI (which might be 256 bits long).
Ha’át’íísh baa naniná?
Azee’ Å,a’ish nanídį́į́h?
Táadoo ánít’iní.
What are you doing?
Are you taking any medications?
Don't do that.

Cavebear

Quote from: Baruch on April 07, 2019, 04:40:08 PM
Nope.  That is a different discussion.  Here is how PKI keys are used asymmetrically.  You know a reliable third party key holder.  You create a key pair, one private, the other public.  You send your public key, along with your verified ID to the third party key holder.  Other people do the same.  So if I want to exchange encrypted mail with another party, I encrypt my outgoing meal with someone else's public key.  The receiving party gets my public key from the third party key holder, as well.  Once the receiving party gets my email, they have their private key all to themselves, and use it to decrypt my message, that was encrypted with their public key.  The other party, sending encrypted mail to me, does the same thing symmetrically.  They encrypt their email using my public key, and when I receive it, I use my private key, that only I have, to decrypt the message sent to me.  Basically blind sharing of keys.

Unfortunately the majority of asymmetrical key exchange, is based on the factoring of dual prime numbers (an integer made up of just two large primes multiplied together).  Quantum computing is uniquely able to factor dual prime numbers.  Quantum computing is an analog/digital hybrid, useful for certain hard problems, but not all, and not practical for ordinary computing.  Once you have factored the large prime, you can read an asymmetrical PKI (which might be 256 bits long).

Thank you for mansplaining the dual prime numbers multiples.  GAGobvious!

I'll wait for the practical application.


Atheist born, atheist bred.  And when I die, atheist dead!

Baruch

Quote from: Cavebear on May 26, 2019, 08:25:55 AM
Thank you for mansplaining the dual prime numbers multiples.  GAGobvious!

I'll wait for the practical application.

Supposedly the dual prime numbers technique (used to public key distribution) is vulnerable to quantum computers.  Not everything is.  But this is a hugely important target.  It is yet to be seen that quantum computing can be used in a practical way to break typical public keys.
Ha’át’íísh baa naniná?
Azee’ Å,a’ish nanídį́į́h?
Táadoo ánít’iní.
What are you doing?
Are you taking any medications?
Don't do that.

Cavebear

Quote from: Baruch on May 26, 2019, 10:27:44 AM
Supposedly the dual prime numbers technique (used to public key distribution) is vulnerable to quantum computers.  Not everything is.  But this is a hugely important target.  It is yet to be seen that quantum computing can be used in a practical way to break typical public keys.

I agree that quantum computers could make passwords obsolete.  I'll go mostly offline then.  But there will be other ways to protect stuff, so maybe not.
Atheist born, atheist bred.  And when I die, atheist dead!

Baruch

Quote from: Cavebear on May 26, 2019, 11:43:57 PM
I agree that quantum computers could make passwords obsolete.  I'll go mostly offline then.  But there will be other ways to protect stuff, so maybe not.

I hear lemon juice is a useful invisible ink ;-)
Ha’át’íísh baa naniná?
Azee’ Å,a’ish nanídį́į́h?
Táadoo ánít’iní.
What are you doing?
Are you taking any medications?
Don't do that.

viocjit

It does exist solutions against cryptanalysis with a quantum computer.
Officially , it doesn't exist one with a sufficient calculation power to get a RSA private key with a size of 4096 bit (Maximum size for the majority of RSA implementation) from the public key.

Shor's algorithm can be theoretically used with a quantum computer (With a sufficient calculation power) to break RSA and others asymetric cipher based on integer factorization like Benaloh , Blumâ€"Goldwasser , DamgÃ¥rdâ€"Jurik , Goldwasserâ€"Micali , Naccacheâ€"Stern , Okamotoâ€"Uchiyama , Rabin , Schmidt-Samoa etc...

We speak often of RSA when we are speaking of public-key cryptography but we forget RSA isn't the one PK cipher in the world.


We have many solutions against quantum computers.
A list of solutions against quantum cryptanalysis : https://en.wikipedia.org/wiki/Post-Quantum_Cryptography_Standardization

One-time pad is an unpractical solution against quantum computers to resist to these but if we use it under some conditions (Never use the same key , Key size is the same than message send , The generation of key must to be aleatory) it can't be broke : https://en.wikipedia.org/wiki/One-time_pad

McEliece cryptosystem is immune against Shor's algorithm but I doubt it will still resist to quantum computers as I'm certain new algorithms will appear : https://en.wikipedia.org/wiki/McEliece_cryptosystem



Benaloh : https://en.wikipedia.org/wiki/Benaloh_cryptosystem
Blumâ€"Goldwasser : https://en.wikipedia.org/wiki/Blum%E2%80%93Goldwasser_cryptosystem
DamgÃ¥rdâ€"Jurik : https://en.wikipedia.org/wiki/Damg%C3%A5rd%E2%80%93Jurik_cryptosystem
Goldwasserâ€"Micali : https://en.wikipedia.org/wiki/Goldwasser%E2%80%93Micali_cryptosystem
Integer Factorization : https://en.wikipedia.org/wiki/Integer_factorization
Naccacheâ€"Stern : https://en.wikipedia.org/wiki/Naccache%E2%80%93Stern_cryptosystem
Post-quantum cryptography : https://en.wikipedia.org/wiki/Post-quantum_cryptography
Rabin : https://en.wikipedia.org/wiki/Rabin_cryptosystem
RSA : https://en.wikipedia.org/wiki/RSA_(cryptosystem)
Schmidt-Samoa : https://en.wikipedia.org/wiki/Schmidt-Samoa_cryptosystem
Shor's algorithm : https://en.wikipedia.org/wiki/Shor%27s_algorithm
Okamotoâ€"Uchiyama : https://en.wikipedia.org/wiki/Okamoto%E2%80%93Uchiyama_cryptosystem

Baruch

Ah, someone who is more than a recreational mathematician ;-)

With circular functions, you have the truly periodic and the almost periodic.  The truly periodic corresponds to a pure timbre, the simplest being a single pure tone (sine wave).  If the ratio of at least one irregular component among the purely periodic ones, meet the number theory criteria of not being rational, not even algebraic eg square root of two, but is transcendental "pi/e/etc" ... then even after an infinite expansion of digits, the odd component will never align (harmonize).  Such is the theory of almost-periodic functions, and how it becomes harder and harder to derive an accurate fourier analysis of the non-harmonics.  Such is "percussive" sound, which can be partly harmonic (tympany) or nearly pure noise (true random number).

Consider not a true one time pad, but one that is arbitrarily close to a one time pad.  Then the matter of being hard to decrypt is simply a parameter, that one can extend as necessary, as decryption gets better (an arms race).  What if you have a key that isn't periodic (has a recurring depth), but is algebraic or even transcendental.  In that case you can extend the key system indefinitely, without running into recurrence (which weakens the encryption).  You can't as a practical matter use a true non-rational number, one approximates a non-rational number with a close enough rational number eg you use however many digits of "e" as necessary to meet the message size.  The true key being incommensurable, while the practical key is a many digit rational approximation.

So what quantum computer can calculate the last digit of square root of two, or of "pi"?  There is no free lunch on general problem solving, because of the "halting" problem.  But specific classes of problems can be solved in closed form.  We will have to wait to see, a practical demonstration that the multiplication of two large prime numbers is easy to factor or not.  There are always surprises.  To what extent is mathematics actually empirical not analytical?
Ha’át’íísh baa naniná?
Azee’ Å,a’ish nanídį́į́h?
Táadoo ánít’iní.
What are you doing?
Are you taking any medications?
Don't do that.

Baruch

A challenge ...

One can try to decrypt a known crypt message with a known method but unknown key (Bletchley Park), but how about when you have the plain text and crypt text but not the other two components ...

Please reverse engineer the following plain text plus crypt text for unknown method/key ...

THE0RAIN0IN0SPAIN0FALLS0MAINLY0ON0THE0PLAIN
L5CRAGQIPVPVW9MTD827I6Q1ROVO0C8K51XJ416JXN0

This is a symmetric key block encryption (single key, but encrypt method is inverse of decrypt method).  Same number of characters in plain text and crypt text.  Same symbol table used for both.  One could start with a statistical analysis.  However a simple symbol frequency analysis would fail, even with a longer message, because a given plain text symbol isn't converted to the same crypt text symbol, but varies with position in the chain ...

This is generated from a nearly periodic one time pad (one time in that it can be set to recompute via computer clock over whatever short period you need to make a new key.  Enigma was changed once per day at midnight.  The method can be shown statistically to be as good as AES with message lengths greater than 40 characters (shorter messages are easier to guess, which is to say effective depth is less).  For example, a one character message, in a 36 symbol alphabet (as used in this example) can be correctly found with at most 36 guesses, and on average 18 guesses.  With 40 character messages, given the nearly random key generation, you need worst case 36^40~1.8x10^62 guesses, or on average half that.  Some claim, with favorable problems, a quantum computer at best can achieve the average on every try (which would be quite an accomplishment) but still insufficient to break my 40 character message.
Ha’át’íísh baa naniná?
Azee’ Å,a’ish nanídį́į́h?
Táadoo ánít’iní.
What are you doing?
Are you taking any medications?
Don't do that.

viocjit

Quote from: Baruch on May 27, 2019, 01:48:25 PM
Ah, someone who is more than a recreational mathematician ;-)

With circular functions, you have the truly periodic and the almost periodic.  The truly periodic corresponds to a pure timbre, the simplest being a single pure tone (sine wave).  If the ratio of at least one irregular component among the purely periodic ones, meet the number theory criteria of not being rational, not even algebraic eg square root of two, but is transcendental "pi/e/etc" ... then even after an infinite expansion of digits, the odd component will never align (harmonize).  Such is the theory of almost-periodic functions, and how it becomes harder and harder to derive an accurate fourier analysis of the non-harmonics.  Such is "percussive" sound, which can be partly harmonic (tympany) or nearly pure noise (true random number).

Consider not a true one time pad, but one that is arbitrarily close to a one time pad.  Then the matter of being hard to decrypt is simply a parameter, that one can extend as necessary, as decryption gets better (an arms race).  What if you have a key that isn't periodic (has a recurring depth), but is algebraic or even transcendental.  In that case you can extend the key system indefinitely, without running into recurrence (which weakens the encryption).  You can't as a practical matter use a true non-rational number, one approximates a non-rational number with a close enough rational number eg you use however many digits of "e" as necessary to meet the message size.  The true key being incommensurable, while the practical key is a many digit rational approximation.

So what quantum computer can calculate the last digit of square root of two, or of "pi"?  There is no free lunch on general problem solving, because of the "halting" problem.  But specific classes of problems can be solved in closed form.  We will have to wait to see, a practical demonstration that the multiplication of two large prime numbers is easy to factor or not.  There are always surprises.  To what extent is mathematics actually empirical not analytical?

I'm not a Mathematician. Not even a recreational one.
I think quantum computers will maybe be able a day to break a cryptosystem like this.
We will certainly discover new mathematical algorithms (Maybe it does already exist secret or top secret algorithms owned by some state actors).

But before ask if quantum computers will be able to do so a moment or another.
I think we must use a sufficient encryption process until the time the information we want to kept won't be necessary to be secret.

An info that must to be a secret indefinitely (For example an industrial secret that is the formula of a beverage. In this case encryption would be necessary even if the secret can be partially or fully discovered by reverse engineering with chemical analysis) isn't the same as an info that must be a secret for one week as the fact a secret meeting will take place to reduce the risk of someone spying the meeting.
What was said in this meeting can be fully secret , partially secret or not secret.
If this meeting is about the secret project of companies for the next five years. Information must to be protected for the next five years.
If this meeting is about public and secret projects of companies for the next ten years. Information about public project can be released fully or partially released and info about secret projects must to be protected for the next ten years. The same for non-released info on public projects.
If this meeting is about public projects for the next two years. Information can be released fully or partially and non-released info must to be protected for the next two years.

Even if a project is public it doesn't means all details are public because some of these need to be secret in some situations.
If a project is secret. The public must not known its existence and therefore the content should not be known to the public.

Few secrets need to be kept indefinitely.
An industrial process can need to be a forever a secret but the fact a video game is being created don't need to be kept indefinitely as the game will be released unless the project is abandoned.


If this ciphertext and plain text is really from you ? I can't find it over Internet. I can suppose you're the author of this.

THE0RAIN0IN0SPAIN0FALLS0MAINLY0ON0THE0PLAIN
L5CRAGQIPVPVW9MTD827I6Q1ROVO0C8K51XJ416JXN0

Unbeliever

Quote from: Baruch on May 27, 2019, 12:06:53 AM
I hear lemon juice is a useful invisible ink ;-)

An idiot tried to rob a bank after putting lemon juice all over his face, thinking that because it could be used to make invisible ink it would also make his face invisible!

Why a bank robber thought covering himself in lemon juice would help him get away with it


:-P :-D
God Not Found
"There is a sucker born-again every minute." - C. Spellman

Baruch

Voicjit - yes, that is a string run thru "my" system.  Gets harder the longer the message, usually it gets easier to break with length, because you get better statistics.  But statistics won't help much.  I had a profession hacker try to break it with his best tools (I gave him only the crypt text, nothing else) and he failed ;-)

Basically decryption is looking for correlation patterns.  If you work against that in particular, you can make a system as hard as you like (but that isn't enough to make it commercially viable).  Basically you first run statistics on individual characters, then on doubles, then on triples until you get to the total length of the message.  So the first set of stats have N values equal to the total length, and the final stat has just one value.  That is looking at letters just sequentially (there are other choices, like every other letter).

Ha’át’íísh baa naniná?
Azee’ Å,a’ish nanídį́į́h?
Táadoo ánít’iní.
What are you doing?
Are you taking any medications?
Don't do that.