> researchers invented a fundamentally new kind of problem that a quantum computer should be able to solve exponentially faster Telling of the status of the field.
Is that a dig? I think it sounds promising and exciting
Quantum algorithms conquer a new kind of problem
21–30 of 35 posts
Re: Quantum algorithms conquer a new kind of problem
#22Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.
> Will quantum computing destroy blockchain and classical encryption algorithms as we know?
Short answer: the currently popular ones? Yes. All that we know? Probably not. See eg: https://ieeexplore.ieee.org/document/8967098
Re: Quantum algorithms conquer a new kind of problem
#23Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.
Classical asymmetric encryption algorithms like RSA and ECDSA (which Bitcoin uses) can be easily broken by a quantum computer. Brute-forcing symmetric algorithms like AES gets a speed up on a quantum computer, but not enough to consider the algorithms broken.
Oh cool, can you tell me who has successfully and easily achieved this result?
Re: Quantum algorithms conquer a new kind of problem
#24Earlier quoted context omitted.
Classical asymmetric encryption algorithms like RSA and ECDSA (which Bitcoin uses) can be easily broken by a quantum computer. Brute-forcing symmetric algorithms like AES gets a speed up on a quantum computer, but not enough to consider the algorithms broken.
Oh cool, can you tell me who has successfully and easily achieved this result?
Peter Shor; though whether easily, I can't say for sure. https://en.wikipedia.org/wiki/Shor's_algorithm
Re: Quantum algorithms conquer a new kind of problem
#25Earlier quoted context omitted.
Oh cool, can you tell me who has successfully and easily achieved this result?
Peter Shor; though whether easily, I can't say for sure. https://en.wikipedia.org/wiki/Shor's_algorithm
The previous commenter was being sarcastic, due to the use of the "easy" word (there is no implementation of Shor's algorithm yet that comes even near outpacing the classical version)
Re: Quantum algorithms conquer a new kind of problem
#26Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.
I'm surprised there aren't quantum blockchains already.
Re: Quantum algorithms conquer a new kind of problem
#27Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.
Classical asymmetric encryption algorithms like RSA and ECDSA (which Bitcoin uses) can be easily broken by a quantum computer. Brute-forcing symmetric algorithms like AES gets a speed up on a quantum computer, but not enough to consider the algorithms broken.
Bitcoin doesn't use them in a way that'd let you completely break it; the asymmetric keys aren't broadcast until someone does a new transaction with them, so you can't fake one for a wallet you've never seen the public key to.
Re: Quantum algorithms conquer a new kind of problem
#28Earlier quoted context omitted.
Classical asymmetric encryption algorithms like RSA and ECDSA (which Bitcoin uses) can be easily broken by a quantum computer. Brute-forcing symmetric algorithms like AES gets a speed up on a quantum computer, but not enough to consider the algorithms broken.
Bitcoin doesn't use them in a way that'd let you completely break it; the asymmetric keys aren't broadcast until someone does a new transaction with them, so you can't fake one for a wallet you've never seen the public key to.
How is the transaction signature verified without the public key? This link seems to indicate spender public keys are inside of the transaction: https://bitcoin.stackexchange.com/a/102667
Re: Quantum algorithms conquer a new kind of problem
#29Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.
I'm surprised there aren't quantum blockchains already.
> I'm surprised there aren't quantum blockchains already.
There are:
> https://www.quantumblockchains.io/
> https://quantumblockchaintechnologies.co.uk/
:-)
Re: Quantum algorithms conquer a new kind of problem
#30Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.
Post-quantum cryptography is a thing: https://en.wikipedia.org/wiki/Post-quantum_cryptography
Until it’s not. Nobody has proven any of these schemes to be secure against quantum attack. Post-quantum (today) just means that nobody has proven that the problem is equivalent to a problem that quantum computing can solve efficiently. This article is about LWE being proven breakable. Others will follow. The security of these schemes rests mostly upon the lack of researchers that understand them and quantum computing well enough to approach an equivalence class proof. Example: elliptic curve isogenies.