Quantum computing and the future of cryptography
dud...@gmail.com
which makes parallel computation of all possible inputs - like
becoming more and more realistic quantum computers.
I think we should widely discuss if it's a real threat and if yes -
how to design cryptosystems resistant to such eventualities.
Especially that we wouldn't know if someone would use it...
Here is one discussion of this type:
http://www.ecrypt.eu.org/stream/phorum/read.php?1,1021,page=1
I wanted to start here one. Please share Your opinions and links to
interesting discussions on this topic.
There is know Shor's algorithm which breaks RSA. Generally
cryptosystems have always a 'weakness' that make them prone to brute
force attacks - that there is a key which properly decrypts the
message. To make such attack we can use that there is practically only
one key which makes that message decrypted with it has some
significant correlation.
So using a quantum computer we could use entangled all possible keys
to decrypt the message, check for correlations and somehow extract
some information about the correct key.
This extraction is more difficult than it looks, but assuming that
it's impossible could be dangerous.
Quantum computers are extremely difficult to make and they most
probably will be limited to relatively small number of qbits and time
they can sustain entanglement - so I think that we can protect against
imaginable QC by enforcing large amount of required computation. To
make such cryptosystem practical, this computations should be done
only once - specifically for given key. The next advantage of such
preintialized cryptosystem, like based on asymmetric numeral systems
http://arxiv.org/abs/0902.0271
is that now the processing of the data can be extremely fast.
Do You think it's a real threat?
How strong it is - can be used only for some algebraic attacks or even
for brute force?
How to protect against such eventualities?
What about public key cryptography???
WTShaw
> is that now the processing of the data can be extremely fast.
>
> Do You think it's a real threat?
> How strong it is - can be used only for some algebraic attacks or even
> for brute force?
> How to protect against such eventualities?
> What about public key cryptography???
All algorithms do not obey standard definitions of what they should
be. Like a disease once simply called consumption, or another called
cancer, history proves that these categories tended to define
prejudice to most while a challenge to a dedicated few.
Before public key, that was impossible and everyone knew it. However,
a few beat the herd at their own game. But as glands through the dour
glass, so are the lays of our lives...public key systems and keys of
fixed and known rigid lengths are subject to fall.
dud...@gmail.com
Generally what physics do is solving its own partial differential
equations - that means processing simultaneously infinitely many (or
huge amount) degrees of freedom. I see a few ways of 'giving' there
some NP-problem to be solved using this huge amount of simultaneous
computations ...
... but for example there are nonlinear terms which e.g. mixes wave
functions (decoherence), introduce chaotic behavior ...
And so for example sustaining entanglement of let say 10^10 qbits for
seconds looks completely beyond imagination.
So assume we would use a preinitialized cipher - for given key we have
to make large initialization, for example to generate some huge coding
tables/parameters using PRNG initialized with the key. To check new
key we cannot just start decrypting, but we have to make all this
calculations ... quantum computer which could sustain entanglement of
computations for all possible keys would have to grow beyond practical
(physical?) limit.
But I have to admit that I have completely no idea how to protect
public key ...
Ertugrul Söylemez
> Physics most probably allows for non-classical computation methods,
> which makes parallel computation of all possible inputs - like
> becoming more and more realistic quantum computers.
I think, you may have a wrong view about quantum computers. In a
certain sense, they do work on multiple states at once, which is called
quantum parallelism, but it's not real parallelism. With these
so-called superpositions alone, other than true randomness, quantum
computers wouldn't contribute much to computing power. Consider that
superpositions are a measurement effect. Whether and how they are
present really just depends on how you measure.
Their strength comes from entanglement, which makes one state dependent
on the outcome of the measurement of another. This does add enough
strength to solve the factoring problem in polynomial time, and other
problems, which are in the BQP class (which is a subclass of NP and a
superclass of P), but it's not a solution to everything. Particularly,
in general it does not solve problems in NP, especially not NP-complete
problems. Some quantum algorithm may be found to do it in the future,
but this has yet to happen, and I believe it won't.
I think, if an algorithm is found to solve an NP-complete problem, it
will prove P = NP, not BQP = NP, and if we find P = NP, then quantum
computers are the least of our worries.
Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
dud...@gmail.com
advantage of QC is the Shor's algorithm.
Probably You are right, but ... QC can theoretically make all
calculations at once (is almost nondeterministic Turing machine) and
the only problem is with the extraction. I'll show how to enhance it,
but it would be strange if basic QC wouldn't already allow for more,
maybe even solving NP in polynomial time. Especially that if someone
would find a way, he could not necessary tell it loud, but for example
try to became rich...
The next argument that we should take such scenarios seriously is that
maybe basic QC is not the only possibility for massive parallel
computation physics gives us. First of all there is so called Feynman-
Stueckelberg effect
http://groups.google.com/group/sci.physics.research/browse_thread/thread/9d10b4e5cbda1108
which hasn't been taken seriously, but maybe it will change in a few
months in LHC ... but such computer would require (huge?) accelerator.
The other option can be (quantum) loop computers
http://groups.google.com/group/sci.crypt/browse_thread/thread/736fd9f3e62132c2
I'm strongly confused about this idea, especially for classical
computers.
But ... if used for quantum computation, such feedback should amplify
the correct solution (wavefunction), making the rest of them vanish.
It couldn't be standard approach to QC in which we use some sequence
of for example external fields on some lattice of atoms.
We would need a circuit which allows to sustain entanglement of many
calculations.
Observe that similarly to benzene, (-CH=CH-) sequence can be in
quantum superposition with shifted one (=CH-CH=) - we could use such
molecule as a wire for qbits. Unfortunately it has some resistance,
but there are know such superconductors also.
We know also transistors made of single molecule - they are
irreversible so would destroy entanglement, but there should be
possible also quantum gates made this way.
The question is if such molecular quantum computers could sustain
entanglement for practically long time ... There is also problem with
auxiliary variables - we need a lot of them because in QC all
calculations has to be reversible. They cannot be sent in the loop -
they should be treated in some special way to not destroy the
entanglement ... but maybe ?
Probably physics doesn't allow to solve NP in polynomial time, but I'm
far from being sure of it.
dud...@gmail.com
be able to make protected and practical hybrid systems - public key
cipher for a very short message like a key for a secret-key cipher or
a hash value for authorization.
Most generally, public key is a parameter of some transformation which
is extremely difficult to reverse. But there is the private key - some
kind of 'clues' which make this reverse easy.
So if someone could solve quickly NP problems:
- he could try all possible 'clues' and for example check if for some
block encrypting and then decrypting gives the same block. If yes - he
could try a few more different blocks to be sure it's the correct
private key, but there is also more dangerous attack:
- searching not for these 'clues' but straightforward for the reverse
function: having encrypted message in a form of independent blocks,
for each block he could try to encode all possible input blocks with
the public key to get the given block.
So to protect it in analogy to secret-key ciphers, we rather have to
make that encoding already require extremely large amount of
calculations. The problem is that this time these huge calculations
cannot be just made while initialization like before, but has to be
made for each block - it could be practically used only for extremely
short messages, like the key for a secret-key cipher or a hash value.
Paul Rubin
> I think, if an algorithm is found to solve an NP-complete problem, it
> will prove P = NP, not BQP = NP, and if we find P = NP, then quantum
> computers are the least of our worries.
I think it is not even known that BQP <= NP. A quantum computer may
be able to solve problems that are outside of NP. Scott Aaronson's
Scientific American article about quantum computing is informative and
accessible:
http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf
Russell Impagliazzo wrote an interesting essay about the relationship
between P vs NP and cryptography (it's more subtle than it might look).
This is the famous "five worlds" paper:
http://www-cse.ucsd.edu/~russell/average.ps
H. Helgason summarized it in a slide show: