One Step Closer to Post-quantum World

One Step Closer to Post-quantum World

Urmila Mahadev, a graduate student at UC Berkeley, has come up with a solution to a major problem in quantum computation. She has found a way, using only classical computers, to know whether a quantum computer precisely follows given instructions

Intro to quantum computers

A computer is a machine that does calculations. Whether you are watching a Youtube video, writing an essay or playing a game, all your computer does is just add, subtract, multiply and divide numbers. Your computer does these calculations with the help of small electrical parts called transistors that act as switches. These switches are combined into logic gates, and logic gates in turn are connected to each other to form adding, subtracting, multiplying, and dividing mechanisms.

In our normal world, switches can be either on or off, electricity is either flowing through the circuit or not. We sometimes hear that computers work only with 0s and 1s because they store information of switches being off and on in bits that can be either 0 or 1 at one point in time. In the world of quantum physics, however, it is not that simple. A quantum object can actually be in different states at the same time or, more scientifically, the object can be is a superposition of different states. A famous example of a quantum object is Schrödinger's cat. This cat lives in a closed box. Inside that box there is also a deadly mechanism that may or may not activate. And until you, an outside observer, open that box, the cat is dead and alive at the same time. This cat is in the superposition of being dead and alive.

Quantum computers use quantum bits, or qubits. Qubits are quantum objects, usually electrons of atoms, that are spinning chaotically in each and every direction at the same time! If this is hard for you to grasp, do not worry. As some physicists say, 'It’s not that you understand it, you just get used to it'. So when qubits are spinning in all directions, we can think of them as rapidly alternating between 0 and 1. This along with a number of other curious properties such as entanglement of quantum objects are harnessed by special complex machines called quantum computers to conduct efficient calculations. Quantum computers may bring us closer to discovering the secrets of the universe by, for example, simulating black holes and protein folding, which are very computation-heavy operations.

Problem with quantum computers

The major problem with quantum computation is that we do not know how to check whether a quantum computer did all the instructed calculations or even generated the correct result. With classical computers this is really easy — all you need to do is check every step, you check every time a bit is 0 or 1. Quantum computation, however, does not have steps because it performs all steps at the same time and stops the moment you measure the result. Again, you cannot know whether the cat is dead or alive, until you open the box. Similarly, you cannot see whether the qubit is 0 or 1 without measuring it. Measurement collapses the superposition into a single unambiguous state. So, in a way, a quantum computer is a quantum computer only when you don’t look at it. As soon as you look at the qubits, they become classical bits. So if you cannot follow the process of computation, how do you know if the computation was correct?

Proposed Solution

Urmila Mahadev proposes a solution that predicates on a simple idea that if a quantum computer can do something that classical one can’t, we can still use classical means to check the result. As such we can construct such a function that is very hard to compute but is easy to verify, a trapdoor function.

For example, it is believed that quantum computers are really good at factoring numbers. For classical computers given a large number it is incredibly difficult to find its factors. This is the biggest pillar of modern cryptography. It takes a big number, a private key, multiplies it by another big number and outputs the third even bigger number, the public key. You can feed this public key to a computer but it will take hundreds of years to find its factors. But if a quantum computer does in fact find these factors, we can simply check the result by multiplying the generated numbers, which any classical computer can do. To illustrate we will use smaller numbers. We can have the quantum computer find factors of 2047 and when it gives 23 and 89, we can simply multiply those to verify the result.

Urmila Mahadev has come up with an interactive protocol that allows classical computers to verify quantum computation. They can do it by having the quantum computer measure its own qubits and output the result. For a while, the problem with this was the fact we could not trust the computer because we could not tell which superposition of superpositions the computer measured. Urmila implements the trapdoor function to first generate the output of a certain superposition and verify if qubit measurement belongs to that superposition.

Urmila approaches this problem using cryptography known as Learning with Errors cryptography which is a topic for another article. But nevertheless this is a big discovery that once again proves the sheer power of cryptography and prepares us for the post-quantum world.

Related news

New IBM Q System One Quantum Computer Won’t Harm or Damage Bitcoin in the Future

IBM has recently launched the Q System one, a quantum computer for commercial use. The company presented it at the Consumer Electronics Show (CES) a few days ago. Some enthusiasts and analysts are currently wondering whether this super-computer is able to change Bitcoin’s future. Adam Back 1, Quantum Computer 0. https://t.co/8yd2zWAOF6 — Samson Mow (@Excellion) January 13, 2019 The feat that the crypto community has is related to quantum computers being able to undermine the security of blockchain technology and the way in which virtual currencies work. According to IBM, the new Q System One has been specifically designed for commercial use. Although it is possible to purchase this device, the computer will be accessible via the cloud due to the fact that it is very delicate and difficult o operate. The new computer has 20-qubit chips but experts suggest that 50-qubit chips are going to have a greater positive effect on companies. Although it is very positive to have quantum computers being deployed around the world, making ‘low-noise’ qubits is more important than how to put them in a nice package said Andrew Childs, the co-director of the Joint Center for Quantum Information and Computer Science at the University of Maryland. About it, he commented: “It’s more like a stepping stone than a practical quantum computer. Don’t think of this as a quantum computer that can solve all of the problems quantum computing is known for. Think of it as a prototype machine that allows you to test and further develop some of the programmings that might be useful in the future.” Thus, it seems that this quantum machine is not expected to be revolutionizing the crypto space and destroying Bitcoin. Nevertheless, according to Divesh Aggarwal, from the National University of Singapore, Proof of Work is relatively resistant to substantial speedup by quantum computers in the coming 10 years. This is due to the fact that ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers.
Bitcoin Exchange Guide

No, IBM’s Quantum Computer Won’t Break Bitcoin

IBM recently unveiled its Q System One at the Consumer Electronics Show (CES) 2019, with the company describing the quantum computer as being developed for “commercial use.” Despite numerous media outlets again decrying the imminent death of Bitcoin, IBM’s quantum system is not the game-changer that many are heralding it to be. Also Read: Japanese Regulator Clarifies Stance on Bitcoin ETFs and Derivatives IBM Unveils Quantum Computing System IBM’s commercial launch of its new quantum computing system has fueled reports claiming that the technology may spell doom for bitcoin and cryptocurrency. The reports are based on a long-standing fear that the advent of quantum computing could break contemporary encryption practices, undermining the security of distributed ledger technologies. The Q System One uses IBM’s 20-qubit chip, with the company claiming that the unit is “designed for commercial use.” At launch, Arvind Krishna, director of IBM Research, described the system as “critical in expanding quantum computing beyond the walls of the research lab as we work to develop practical quantum applications for business and science.” Despite IMB implying that the computer can be physically purchased, the device is only accessible via the cloud due to the extreme delicacy and climate required to operate quantum chips. According to Gizmodo, IBM also “already offers cloud-based access to its [quantum] experience, which includes the 20-qubit chip.” Experts Doubt Practical Uses for IBM’s 20-Qubit System While a number of analysts have noted the commercial significance of IBM’s Q System One, many onlookers are skeptical of the capabilities of the system, instead suggesting that 50-qubit chips are likely to have a greater array of practical applications. Helmut Katzgraber, principal researcher at Microsoft Quantum, similarly described IBM’s announcement as a “historical milestone to be able to commercially acquire a digital device, even though the technology,” but anticipates that the system will be of little use beyond research and PR. IBM Q System One Comprises Commercial Rather Than Computational Milestone Despite describing the increasing accessibility of quantum computing as “significant,” Andrew Childs, the co-director of the Joint Center for Quantum Information and Computer Science at the University of Maryland, expressed skepticism regarding IBM’s device, stating: “Ultimately though, I think figuring out how to make a lot of low-noise qubits is a lot more important than figuring out how to put them in a beautiful package.” “It’s more like a stepping stone than a practical quantum computer,” stated Winfried Hensinger, professor of quantum technologies at the University of Sussex. “Don’t think of this as a quantum computer that can solve all of the problems quantum computing is known for. Think of it as a prototype machine that allows you to test and further develop some of the programming that might be useful in the future,” he added. What do you think of IBM’s Q System One and the purported threat quantum computing poses to cryptcurrency? Share your thoughts in the comments section below! Images courtesy of Shutterstock, IBM Research At Bitcoin.com there’s a bunch of free helpful services. For instance, have you seen our Tools page? You can even lookup the exchange rate for a transaction in the past. Or calculate the value of your current holdings. Or create a paper wallet. And much more. The post No, IBM’s Quantum Computer Won’t Break Bitcoin appeared first on Bitcoin News.
Bitcoin News

Part 4B. I’m writing a series about blockchain tech and possible future security risks. This is the fourth part of the series explaining the special quality of going quantum resistant from genesis block.

Part 1, what makes blockchain reliable? Part 2, The mathematical concepts Hashing and Public key cryptography. Part 3, Quantum resistant blockchain vs Quantum computing. Part 4A, The advantages of quantum resistance from genesis block, A Quantum resistance (QR) from genesis block. Why is it a special quality? Content: 4A (Posted in this previous post) What are the challenges of upgrading an existing blockchain to a quantum resistant one? What you see is what you get: the performance of other blockchains that upgrade later, could be different after the upgrade. The whole architecture can be designed around post-quantum cryptography. 4B (posted here) Lost addresses and the human factor: a partly protected circulating supply after a quantum resistant upgrade The time factor The case of a black swan event where unexpectedly fast, an entity will appear to have a quantum computer of critical level. Lost addresses and the human factor: a partly protected circulating supply after a quantum resistant upgrade A mostly overlooked problem for existing, non-quantum resistant blockchains when people talk about the future protection against quantum computers is another consequence of the fact that blockchain is a decentralized system. Decentralization is not often seen as a problem, but in this case it does cause a serious issue: if you have managed to change the cryptography of your blockchain, then that doesn’t mean you immediately have your full circulating supply protected without the cooperation and action of your users. So after consensus between nodes is achieved, there are again others you depend on to make the change final. After successfully changing your signature scheme, you have quantum resistant keypairs available, but none of the coins are protected by them yet. You’ve just managed to change your signature scheme, but you have not canceled out all existing old keypairs. This is because of the simple fact that you can’t change the accessibility of the existing wallets and therefore the accessibility of your complete circulating supply. Meaning: you can change the signature scheme, and therefore the accessibility of all new addresses created from that point of time, but not the accessibility of all old addresses created before that point of time. So all the old addresses will still be vulnerable until the users who own those addresses cooperate and take action. The crux of the matter is this: Only the actual owners of the coins or tokens have the public and private key combination. And that is exactly what needs to be changed. The old key pairs need to be switched for new quantum resistant key pairs and the old key pairs need to be deactivated because these old key pairs will be vulnerable for quantum attacks. And it’s just that, that can’t be done automatically for the users of a decentralized system like blockchain. You can give the users the tools to do so themselves, so you can change the cryptography in your blockchain and therefore make sure all new key pairs that are created are quantum resistant key pairs, but the users will have to do the switch personally. Remember, the owners need to keep on having access to their wallet, even after the blockchain is updated, so the old key pairs can not be deactivated before the owners have gotten a new quantum resistant key pair that gives them access to their wallet. If not, everyone would be locked out of their wallet. I will elaborate: Everybody knows that when you lose your private key, you lose access to your funds. There is no “I forgot my password” or “what’s your secret question”. There will be no “We will mail you your new key pair”. Therefore, even if the blockchain would be able to change your key pair for you, and change it to a quantum resistant key pair while deactivating your old key pair, you would not have this new key pair and would have effectively lost access to your funds. So whichever way you put it, if you have an existing blockchain and you want to upgrade that blockchain to a security level where all circulating supply is protected against quantum attacks, the owners of coins or tokens would need to use the tools given to them by the improved blockchain to make sure their funds, and thus the funds of all owners together: the circulating supply, is quantum resistant. And only after every single user (now and from the past) did that, the whole circulating supply would be protected from quantum attacks. You might see the obvious problem here: it would be every single user now and from the past. From the past (Old users): lost addresses cause the problem here. The longer a blockchain has been running, the more people would have possibly lost access to their funds. (Lost keys all together, crashed computer, lost USB sticks, or lost interest when the price was low in the beginning of a project like BTC, etc.) Also some projects have run tests at the beginning or mined to some address that’s now unaccessible. BTC would be the most obvious example, where the infamous Satoshi addresses contain huge amounts of BTC. (And no, in those days the public keys were used as address in their full original form, so not in hashed form, so the public keys of these addresses are visible, not like today only in hashed form, so these funds are vulnerable to quantum attacks.) Since you need access to the coins and nobody actually has access to these coins, there is no one who can bring those coins under the protection of new quantum resistant key pairs. Every single user now: consider human nature. Not everybody will move their funds. (In time, or not at all.) (Lots of reasons to name why people don't do what should have been done. Because: people are people, some people haven't followed the news (Not everyone is a frequent reddit or bitcointalk visitor, some just check the price every now and then), some don't understand how it works, some don't understand why the urgency, maybe it's part of an heritage/ divorce that takes time to legally process, jail, sick, lost memory stick that has been found later, etc. etc.) So even if an existing blockchain would implement quantum resistant cryptography, there would always be a certain percentage of the circulating supply that will not be protected. Some people might think “So what, I will make sure my coins are in a quantum resistant address after the upgrade. So I won’t run any extra risk.” This, however is not true. The fact that not 100% of the circulating supply is protected, does bring a risk for the value of all 100%, so each coin. The ones in quantum resistant addresses and the ones in old addresses. You need to guarantee there will not be a news headline screaming “BTC hacked!" (Or whatever other blockchain project) which is the nightmare of any investor. Reading or hearing that, means sell your bags, even if you yourself use the quantum resistant option. Having your personal BTC protected, simply means that the amount of BTC will be safe, not the value of your BTC. So in the case where someone’s BTC gets stolen, you yourself will still have 3 BTC. But because of the news, which will cause people to sell and the BTC value to drop, your 3 BTC that used to be worth 40.000$, now is worth 3.000$ for example, while the value still drops. In cryptocurrency, being a quantum resistant blockchain isn't about offering the option. It's about protecting your currency and the value of that currency. So either you have a 100% quantum resistant blockchain that protects all of it's supply, or a certain percentage is obviously still vulnerable to hacks. It’s pretty much an impossible problem to solve without creating other problems. If you would create a deadline within which you would need to take action and burn the "left-overs" after the deadline is passed, the thought would be "all BTC that are on non-quantum secure addresses after passing the deadline, are BTC that owners can't access, so useless anyway, so of no actual value to the owners. So no harm done if burned." But, besides the fact that this is quite likely not true because of the human factor, there is a legal point. Legally, burning BTC would just not be possible, because it is impossible to determine if an amount of BTC that is still on an old non-quantum secure address, is there because the owner lost it's access, or because he just hasn't moved them to a secure address yet. Decentralized is the problem here. You can’t just one-sided decide to vaporize someone’s funds. There is no pre-made agreement where is mutually established that this is something investors or users (however you will call crypto holders) should have taken into account when they bought their coins or tokens. Unless we’re talking ERC20 tokens, where you know in advance you will have make the switch at a certain point of time. Burning someone’s assets is just unprecedented. What will be the effect of this measure? Before the burning, so when the plan to create a deadline is announced? How will the market react? And after the burning, when claims will be made and legal action is taken by people who suddenly notice their funds is gone? Eventually the news will either be "people claiming BTC has burned their portfolio" which will result in legal claims with the necessary fuss and FUD which will damage BTC brand and value, or "BTC was hacked by a quantum computer". None of the two options are exactly harmless for BTC or other crypto. And this event will take place in a time where Quantum Resistant crypto which have been QR from genesis block are available, so no such risk for this new generation of blockchains. What would be the incentive for someone to hack BTC or any other non-quantum resistant blockchain? Would it be practically possible to make enough gains? Would it be cost effective? If they would dump the stolen coins, wouldn’t they shoot themselves in the foot, crashing the price of what they just obtained? Here’s a scenario: Coins get stolen. Then these coins are sold. Gains are made in fiat. But before the plan is executed, they will short the hell out of the target. So after the hack they start selling slow to get minimum price drops and maximum gains. But when the bag is getting empty, the dump is made. And at the same time, the hacker himself will bring out the news there was a hack using a quantum computer, providing proof including the hacked address. The media will eat this news like vultures. The price dumps and due to the shorting, a double gain is made. Now how about another scenario. No actual hack needs to be done. No criminal activity. Someone at a university with access to a quantum computer. Could be a very profitable PhD project. Or a professor with a side project even. Or a white hat hacker. This person could hack his own wallet and write a paper about it and therefore officially proof the blockchain in question is vulnerable. Then short the hell out of the hacked blockchain and publish his paper. Same result when published. The reaction to that news will cause a dump. Oldest trick in the book of financial attacks. Proven over time. The time factor The longer implementation is postponed, the bigger the risk that another factor will become a problem: time. As said before, the implementation is a specialism, it takes time to figure out what to implement and how, it’s no small adjustment, it affects several components of the blockchain, it affects exchanges, ledger, supporting systems and then consensus takes time, migration takes time if completion is possible at all. A timeline assessment needs to be made for all consecutive events. The events will follow each other, they can’t be taken care of all at the same time. There can’t be consensus on a method that hasn’t been proposed yet. You can’t propose a method without having decided which method you want to use. Exchanges will not start to adapt without the assurance that consensus is reached and the changes will actually apply to the blockchain. Etc. etc. All these events have a timeline and will follow each other up: The research period, decision period, development and implementation period, adjustment period for supporting systems, consensus period, exchange adoption period, migration period. All these consecutive events take time. And to make a serious risk assessment, this timeline needs to be made and compared with the quantum computer and - algorithm development expectations and expected timeline. And on top of that, you need to take into account that at a certain point of time post-quantum cryptographers will be quite busy due to the fact that there will be a point in time where domino effect causes a growing group of companies, blockchain and other companies, to start changing signature schemes. Cryptographers will become scarce and expensive. So for some projects the knowledge might not be easily available to figure things out. The case of a black swan event where unexpectedly fast, an entity will appear to have a quantum computer of critical level. In the unrealistic, best case scenario where a blockchain would be able to implement a post-quantum cryptography in a small amount of time, all coins should still be migrated to quantum resistant addresses. But migration of coins at that time, is then already is vulnerable to hijacking. The same way as BTC is vulnerable as explained in the next article “Why BTC is vulnerable for quantum attacks sooner than you would think.”, where is explained how hijacking during or pre transactions can be done. If a project postpones implementation until after quantum computers reach that critical level, it might be to late altogether. If talk about a blockchain that has full public keys published, all keys are open and all funds is at risk right away because quantum computers can derive the private key from the public key. But if it's a blockchain where the public keys are only published in hashed form, the funds is safe as long as it isn't transferred. The funds will be stuck. You can't spend it safely, but you can't transfer it to a safe address either, because during the transaction of sending funds from an old, non-quantum resistant wallet with an old keypair, the transaction can be hijacked. The only safe solution to transfer funds at a time like that, is proposed in this paper. (Link https://eprint.iacr.org/2018/213.pdf) It is the proof of knowledge option where a period of 6 months locked funds is proposed. What is proposed is this: A quantum resistant signature scheme is implemented. A user creates a quantum resistant wallet and as a result he has a quantum resistant keypair. Then he publishes a commitment where he publishes the hash of both his old public key and his new quantum resistant public key and the amount he wants to send to this new quantum resistant key. Since this is published in hashed form, no one can read the info of this commitment. Any further attempted use of this keypair without pointing to the published commit, would fail in accordance with the new protocol rules. Now after he has done this, in a future spending, he can point in his transaction to the earlier published commitment and proof he is the owner of the funds because only he could have published this hash of the committed transaction from old public key to new public key. After all the old public key was only known to him. Now to make sure no one can hijack the second transaction, and reorganize blocks in such a way that he can forge a published commitment. In the paper it’s calculated that the feasibility of block reorganization attacks, such as 51% attacks or selfish mining attacks requiring a smaller fraction of the overall computational power, is significantly increased for quantumcapable adversarie. So to prevent the block reorganization, there has to be a delay phase. So after the commitment is published, you would have to wait for a certain period before you can safely spend your funds to prevent the possibility of block reorganization. This period is calculated to be 6 months. Yeah … that is a period of six months. Now that period could be reduced, but any period of locked funds will create a huge downside for any blockchain. In the next part I'll write about the specific risk for existing blockchain, focussed on BTC
/r/CryptoTechnology

Hot news

By continuing to browse, you agree to the use of cookies. Read Privacy Policy to know more or withdraw your consent.