Or Sattath Interview

Dr. Or Sattath is an associate professor at the Ben-Gurion Computer Science Department specializing in quantum money, a unique niche affecting the world of quantum cryptography. I sat down with him on October 2 to discuss his current area of focus, quantum money.

Alex:
Okay, great. So let's get started. Thank you so much, Or, for agreeing to speak with us today. We're very happy that you're here.

Or Sattath:
Thanks. My pleasure.

Alex:
I've read through a handful of your papers to try to digest them, but I thought it would be good if we could jump off by having you tell us a little bit about yourself and your area of research, and especially in the last few years, what you've been working on, how it pertains to quantum, as well as cryptocurrency.

Or Sattath:
Sure. So I'm a quantum cryptographer. I work mostly on aspects related to how quantum computers can help us to protect or work in adversarial settings. I'm focusing on the assumption that there are quantum computers available, both to the honest parties and to the adversaries. 

This is not like post-quantum cryptography, which is a different topic about how we can use our classical computers against quantum adversaries. Most of the stuff that I'll be discussing is not relevant with today's technologies. 

Alex:
Before we even get into quantum money, what is unclonable cryptography?

Or Sattath:
Quantum computers use quantum mechanics and they can use quantum effects. One of these weird things in quantum mechanics is this theorem, called the no-cloning theorem, which says that if I hand you an unknown quantum state, you have no way of creating another copy of it. This is very different than if I give you a file, as even if you've never seen that file, you could easily copy it. That's one of the nice things about digital media, right? 

In quantum mechanics or in quantum computing, you cannot do that. Now, for algorithmic purposes, this is pretty much a nightmare. This is one of the reasons why designing quantum algorithms is so hard, because even the very basic building blocks are kind of different [than in classical computing algorithms]. But from a cryptographic perspective, it could be useful. 

I'll try to give a few examples. The first is what's known as quantum copy protection. So what is quantum copy protection? Pick your favorite software company. I don't know which one it is.

Alex:
Let's say Microsoft.

Or Sattath:
Great. So what's the challenge that Microsoft is facing? On the one hand, they want to sell software. And you need to be able to run it on your computer, even if you're without internet connection, you simply want the software to be able to run, whether it's Microsoft Word or even Windows, etc.  

On the other hand, they're facing a challenge. They want to be able to sell it. Which means you shouldn't be able to copy it and give it to others. Of course, you could create a clone or a copy of the entire machine, and just run another virtual machine with the same thing.  You save it, and then maybe run 10 copies. And what stops you from doing it? 

These days, of course, we expect users not to do it, but they [technically] can. How is this resolved? Using some not so secure mechanisms. Let's put it this way. There are ways to get around all these approaches. There's no classical law in nature that says, “well, this thing is hard to copy.“

Now, on the other hand, in quantum or cryptography, we can at least hope to achieve that. So in quantum copy protection, imagine that you have some sort of software.  It's a compiler, which takes this source code or the program and spits out a quantum state. With this quantum state, you could use it to run the original program just like you could use Microsoft Windows, except now there should be a mechanism stopping you from creating many copies of it.  And that would give a secure mechanism for software companies to sell their software in a secure manner.

I'll give you another one, which is kind of interesting. This is called tokens for digital signatures. Digital signatures are the mechanism that allows you to digitally sign documents, messages, whatever way you want to look at it. Essentially you have a public key that you give to all the people, and you have your signing key, which you could use to sign messages. And if you sign a message, of course, it spits out something which is called a signature. You could give it to others and they would verify and see that indeed you signed that message. 

On the other hand, what if you haven't signed a message, and even if you signed various other messages?  Imagine that you signed a contract and signed it publicly and it's on the internet, etc. Still, no one should be able to sign a message that you haven't signed already. 

Now, what are the drawbacks of digital signatures? Imagine that you go on vacation. You want to give your friend the ability to sign one message on your behalf while you're gone. One thing you could do is to give them your signing key, and then they'll be able to sign messages on your behalf. The problem is, if you give them your signing key, how many messages could they sign? An arbitrary number of them. 

So this is a pretty bad approach. Imagine now that you could create a quantum state again and give it to your friend. And then they'll be able to use that quantum state to sign one and only one message. The advantage is again the no-cloning property.

This uses another related notion, which is called the “irreversibility” or the “collapse” due to quantum measurements. If you measure a quantum state, it changes due to this measurement, and it's a one-way street. If you measure it, you cannot undo the measurement. So that's another property which is used here, because in order to sign the message, you essentially have to measure the state and destroy it irreversibly. Therefore, you get this thing that can only be used to sign a single message, and no more than that. So these are two concrete examples of unclonable cryptography.

Alex:
I think that brings us very naturally to the next segment that we're going to be talking about extensively.  What is quantum money? How is it different from classical money and semi-quantum money? 

Or Sattath:
First of all, very much like the money we use today, there are various forms of things which we call “money.” There are coins, there are bills, there's money that sits in your bank account, there's PayPal, Visa, gold. In the past, there were other forms of money which had some different traits. 

Quantum money is an umbrella term, as there are many variants with very different properties, and very different trade-offs. In some sense, quantum money is the precursor of quantum computing. This [research] was done by a person named Stephen Wiesner in roughly 1969, which is ancient history in terms of even classical cryptography. He was a physicist by training and he was interested in classical information theory.  

So here, imagine that you have a central party that may have various branches. Imagine subway branches, where you have lots of them. And imagine that you have a bus ticket, and you use it to enter the subway. You might have various verification points. And what you want to avoid is that if you can get one ticket, it would be accepted multiple times everywhere.

He imagined a system where you'd have quantum information storing this subway ticket, and you verify it, and it's unforgeable based on the laws of quantum mechanics. And he had a concrete construction of this idea based on photons, and that's about it. 

Again, his paper got rejected.  But he was familiar with several people that were interested in these (at the time) crazy ideas. He was a friend of a person named Charlie Bennett, who was the co-inventor of a protocol known as “Quantum Key Agreement.” [That eventually became] quantum key distribution (QKD), and they managed to turn his ideas to something practical. QKD is an application which doesn't need memory, and it needs only very simple quantum states. So this is something that has been realized for quite some time now, and is very, very useful for secure communication. 

But, I find it hard to believe that quantum money would be useful in the near future. Again, so the idea here is that you have a state that the bank can create. The bank can issue these states. They can hand it over to others, and it could then maybe move between people, and eventually there's another algorithm for verification, which checks that the quantum state is valid. If it's valid, imagine that there's some sort of a machine that gives you an ice cream or lets you in the subway. 

This is private money. Where you have the central party and only the central party can verify money. A more modern approach is something which is called public quantum money. 

What is public quantum money? If private quantum money is similar to Visa transactions, public quantum money is more similar to cash. What's the difference? In a Visa transaction, you're going to buy coffee, and the merchant is essentially allowing you to try to talk directly to Visa. The trusted third party is Visa. 

In a cash transaction, it's between the buyer and the seller only. In public quantum money, the bank issues the money and gives, additionally, something which is called the public key. This public key is given to all the users and it's similar to the things that the current banks give the users, right? They tell you, look, you should look for this and that, like gold or this little metal bar in the middle of the bill.  Or they tell you that you should check for some hidden mark if you look at it in a certain direction. So it gives you a few things that you should use to check that the bill is valid. 

In a public quantum money scheme. They give you something that helps you to check that the money state is valid. If you got your quantum money, you can transact with any other merchant you wish. The merchant would run the public verification algorithm using the bank's public key. And if the bank is valid, it would approve your transaction. If it's invalid, well, it's similar to what happens if you go to the grocery store and the cashier tells you, no, sorry, I don't take that bill. It's invalid.

There are two main advantages of public quantum money versus cash. The first advantage is security by obscurity.  There is some mechanism that is kept secret, and hopefully it should be hard in some vague sense to create another copy.  

But actually, it's more of a societal agreement, right? Essentially, if you try to copy your money, the police would come and arrest you, which is the main mechanism that actually secures it. That's very unlike modern cryptography. 

What stops others from, say, seeing the communication? It's secured by modern cryptography. And even if someone tries to eavesdrop, they shouldn't be able to do that. 

There are cryptographic assumptions here or called “hardness assumptions.” In modern cryptography, we often use the fact that computational problems are actually hard [to solve] so that the cryptographic protocols are secure, because it is hard to break that or to solve this problem. In some sense, we're turning lemons to lemonade; we're taking a hard computational problem, which sounds like a lemon. With that lemon, you create a cryptographic protocol, and you use the hardness assumption. 

Just like it's hard to factor numbers, as it would take hundreds of years, in order to break the protocol, you would need to factor similar numbers, and this would take you hundreds of years to accomplish. It's actually very common in classical cryptography to use the hardness of factoring. Quantum computers can break that. They can solve factoring efficiently, and therefore it indeed breaks many cryptographic protocols that we use today. 

So, we take that into account and use different hardness assumptions, or different hard computational problems. Therefore, quantum money is provably unforgeable under concrete computational hardness assumptions. It means we have better guarantees than the classical guarantees we have about money or about cash. 

The second advantage is the fact that quantum money is digitally transferable. Unlike cash we use today, which you could only use when you go to a physical store and buy, here, if we have a quantum computer and we have quantum internet, at least in principle, it should be possible to communicate or send that quantum state to the seller via a quantum communication channel. 

When we talk about cash, we often merge coins and bills. And usually when we think about coins and bills, there's different denominations. Coins are for low denomination, bills for higher denomination. But what are the more fundamental differences between coins and bills? 

If you think about bills, there is something different between different bills, specifically the serial number. And you sometimes see that in movies when you have marked bills. Imagine that the police gives the crook a bill, and then whenever anyone sees the same bill with the same serial number on some other end, now they know that there's a connection. So marked bills can be used to violate the privacy of the users. In this example, it sounds neat and nice. The police manage to figure out who the crooks are, but of course, it could also be done by whoever wants to violate your privacy.

When we talk about cryptocurrencies, it's much more of a big deal because it's an open book. You could see all the transactions, and you could try to figure out who did what. Similarly, in quantum money, there's a notion of quantum bills and quantum coins, where the distinction is that in quantum coins, all the quantum states are exact copies of each other, so you cannot use it to track people because each instance of the quantum money itself must be the same as all the others. It should keep your privacy or anonymity in that sense. 

Alex:
On that note, can you tell me what a quantum banknote is? How might one be created, and how do you verify the validity of a quantum banknote if you are someone in the position of receiving one?

Or Sattath:
We imagine at least that we'd use something like a computer, that's not a physical thing. You should think of it in the way, say, that Bitcoin is used, where you have some digital piece of information, which you can use to transact. Here, you would need a quantum computer to store your quantum money. 

It could be your quantum mobile wallet, or maybe something on the cloud, or maybe you'll have your own trusted quantum server.  That remains to be seen, how it would exactly be implemented. There are several algorithms running here. There's the key generation algorithm that gives you the bank's secret key. There's an algorithm to mint the money using the secret key. And then there's a verification algorithm that uses the private or the public key, depending on the scheme. 

The algorithm takes the public key and the quantum state and tells you whether it's valid or invalid. This algorithm can be drastically different between different schemes. For instance, imagine how you'd verify a bar of gold versus how you would verify the money issued by the UK versus how Visa verifies a transaction. They all have some similarities, but it looks drastically different than creating a bank note. 

There are several requirements that could be maybe relaxed. One such thing is whether you need a quantum internet to do these tasks. That in particular has been studied quite extensively. To send the money, it is enough to have a classical communication line. Unfortunately, the main bottleneck is this long-term quantum memory, and it doesn't seem like it can even be done in principle. We don't know how to do that. There are very, very concrete problems with that.

Alex:
Are those concrete hardware problems or engineering problems or theoretical problems? 

Or Sattath:
First of all, there's an engineering problem of how to create long-term quantum memory. Qubits are the quantum analog of bits, and the way that they are actually stored is via the state of an atom. 

You need a magnificent level of control to be able to store it so that nothing would disturb it. From an engineering point of view, it is a nightmare.  This is one of the reasons why physicists are so interested in quantum computing. Not so much because they're interested in computing, but because they're interested in testing the limits.

In general, in physics, you often want to see the behavior in some limits of nature. Here, it's controlling at the lowest possible level the degrees of freedom of systems. So this is an extremely challenging scientific endeavor. 

Now it seems like we're getting better and better. And maybe it's hard to tell, right? Maybe [we'll master it] in five years, maybe 20, maybe 50. But people are working on it and making amazing progress.

To have quantum money, you need a full-blown noiseless or fault-tolerant quantum computer to store these qubits. 

Alex:
Is there a way to subdivide a unit of money that is quantum money? And is it possible to verify a transaction or determine the validity of a single piece of quantum money that arrives to you without destroying the quantum state by measuring it? Is it possible to provably destroy quantum money?

Or Sattath:
The first that I want to address is the question of whether checking that the state is valid or invalid might destroy it. Previously I told you that if you measure an unknown quantum state, it destroys the state. And this is true. If you know nothing about the state, and you measure it, there is a non-reversible effect. But if the outcome has a high probability, there's something called the “gentle measurement lemma,” which essentially says, if an outcome happens with a probability which is close to 1, [taking a measurement] it won't change the state at all.  

Notice that this means that you know something about the state, namely that if you measure it, you will get a particular outcome, so it's not out of the blue. If I give you a quantum money state, and you haven't played with it, you didn't try to forge it, and you didn't do anything to it, we want the scheme to have the property that if you try to verify it, it will pass verification. So the probability that will pass verification should be extremely close to 1. Therefore, you don't change that state, as the act of verifying or measuring whether it's valid or invalid doesn't destroy it.

In quantum mechanics, when you take a quantum state and measure it, the outcome is probabilistic. It's somewhat similar to a coin toss, in that you could have biased coins; imagine a coin which has a probability of 80% being heads and 20% being tails.

In quantum mechanics, you might have a qubit which is more aligned to one, or it could be more aligned to zero, or it could be somewhere in the middle. If you measure a qubit which is in the zero state, the outcome will always be zero with probability of 1. If you take the quantum state which we call 1 and measure it, the outcome will be one with certainty. But there are states which are somewhere in between. And for these states, if you measure it, the outcome would be probabilistic. 

Similarly to a fair coin, with probability 50% the outcome would be zero, and with probability 50%, it would be one. But more importantly, here in our context, the state would collapse. Suppose you start with the in-between state and measure, and the outcome was zero, so the state itself changes to zero. If we started with zero and measured it, the outcome would be zero, and there would be no collapse. It would remain exactly where you started it. 

If you started with one, and you measured the outcome with certainty, it would be one, and it would collapse to one, so nothing happened. But if you started with something somewhere in the middle, the state changes. But in the context of quantum money, since you started with a valid state, you measured it, it remains valid, and nothing happens. There's no issue of the money state being destroyed.

Alex:
So is it possible to provably destroy a form of quantum money?

Or Sattath:
I mentioned something called “classically verifiable quantum money.” Before, the algorithm only had to output a single bit whether it's valid or invalid; since the outcome was valid, money should pass verification and [would] not destroy the money. 

Now, imagine that you're the bank and you want to check my money. If you ask me questions without destroying the money, I can give it to someone else. So the process of verifying the state should destroy my money during that process. This is one mechanism to do this form of classical verifiability. It's called a “proof of destruction.” 

In that case, what we do is a more complicated, challenging response. Here, the bank would ask me a question. It'll tell me something like, “look, measure it in this particular way,” and I will do that. Now the outcome must not be deterministic, as the bank is creating traps. The bank is giving me tricky questions, and (for some of them) it MAY know the answer. 

And remember, if the bank knows the answer, it means the state has not been destroyed, so I have to abide and answer [correctly]. But in other cases, the bank will ask me questions which are in some sense meaningless. It won't look at the answers, as it would be useless, but still it's forcing me to do something which actually disturbs my state and destroys it. Therefore, I won't be able to pass verification in other tests. So there is a way to do that. 

Your last question is the trickiest, whether quantum money can be split. This raises a much broader question, which is what kind of tricks can we use with that money? I'll give several examples:

One example, which is very common, is something like a shared account: Imagine that you want to open an account with your significant other and you want to ensure that to send a transaction it requires the permission of both of the people on the account. Or maybe the CEO and the CFO or someone else needs to sign a transaction. In cryptocurrency, this is often called multi-sig accounts, where you need multiple signatures in some specific form. 

So essentially, the company takes a satoshi (the smallest unit of Bitcoin). The company could essentially say, look, whoever holds this satoshi has a share.  Now, if I buy that share, I'm holding the secret key to that satoshi, and I can move it around to others. I don't need a [cryptocurrency] exchange for that. Secondly, since Bitcoin is an open ledger, the company that issued these stocks could look and see where my shares are located and send a dividend to these addresses. 

The third thing is related to voting rights. When you're holding a Bitcoin, essentially you have a secret key that's like a digital signature secret key, just like we mentioned before. If I want to send you a Bitcoin, I'm essentially signing a message saying my Bitcoin are moved to this other wallet. Now, that other wallet address is actually your public key. 

So now I'm signing that message, sending it to the rest of the network. They'll see that this transaction is valid in the sense that this is a valid digital signature, and therefore they will add that to the ledger, and now that 0.8 Bitcoin is moved. Similarly, if I want to sign a different message, not moving my money around, but just simply saying, “look, I am Or, I'm owning this colored coin, and I want to vote for so and so as our next CEO,” that's totally fine, and I can do that. 

Interestingly, in the last couple of years, there has been tremendous advancement in the type of complicated transaction that can be done with quantum money. And this is one, like all the examples that I mentioned, actually can be done using quantum money. 

Alex:
So we have touched on this just now regarding smart contracts and how quantum can play into that. I know that you wrote a paper in 2020 called Quantum Money, Solution to the Blockchain Scalability Problem. Can you tell us just a little bit about that?

Or Sattath:
I mentioned two relevant forms of quantum money; private quantum money and public quantum money. Here, the bank plays a role, which is like a central party, which is the only one that can issue money. Now, in the last couple of years, there is a new kid on the block, and there is no agreed upon name for it. There are several flavors, something called “quantum lightning,” “one-shot signatures,” and maybe even others, like “keyless quantum.” 

[This new kid on the block has] no secret key involved. So this is very, very strange to begin with, as this is a quantum state that everyone can generate, which sounds awfully useless, right? But you should think about it this way: This is a mechanism that allows you to create a quantum state.

In this example, we should think about it as a quantum state and a serial number. You don't need any secret key to generate these quantum states, but you cannot generate two states which would pass verification with the same serial number. 

Even though everyone can generate these pairs of quantum money states and the serial numbers, no one in the world would be able to generate two quantum states associated with the same serial number. One example where this is useful is exactly the setting which I'll describe next, which is upgrading Bitcoin to quantum money. 

Currently, Bitcoin has many drawbacks. It has a very limited throughput as a block is created every 10 minutes, and that block contains roughly one megabyte of transactions, which gives us roughly, say, 10 transactions per second worldwide. Additionally, there's this process of mining or securing the network, which is very prone to various issues. There is an issue that it uses proof of work, which is energetically costly, but in some sense, it's good because it provides security for the network. The more power invested in Bitcoin mining, the more secure the network is. 

There are alternatives or more modern alternatives (like proof of stake) which is used in systems such as Ethereum and several others, which don't use as much computational resources. In all of them, there's a problem of what happens if the networks behave maliciously; the approach that we presented in that paper is to upgrade the system to something which is like quantum money, and by that, we get around all the issues that I mentioned and several others. 

So [what] would it look like? The idea is that everyone will upgrade or will switch. Currently, if you're a Bitcoin user, you essentially have a secret key in your wallet that allows you to sign messages or to spend your Bitcoin. The idea would be to upgrade to quantum money. Essentially, you will create the quantum money state, which has a unique serial number. Now, you will say, “I had a Bitcoin, I want to mint my own keyless quantum money state with this and that serial number.” And from [that point] on, I don't have my Bitcoin, the classical Bitcoin anymore, as now, I'm holding this quantum Bitcoin.

That's where the keyless quantum money kicks in. Remember, if you're saying, “this is my serial number,” you or no one else would be able to create two quantum states with that serial number. And that's the thing that we all agree on; the network agrees that these are the valid serial numbers. Therefore, there won't be two quantum states.

So you have pretty much all the benefits of public quantum money, but now we use a different approach in a decentralized setting; if everybody agrees to switch over and we want to, we can even stop mining.

If you have quantum money, there's no ledger, there's nothing, it's a peer-to-peer transaction, so you could do as much as you want. There's no boundary on the throughput [like there is now]. If there are no miners, there cannot be [a risk of] malicious miners anymore. And we, of course, do not spend the computational effort either; we don't spend billions of dollars to secure the network, because we essentially stopped mining. So you get lots of benefits. That's the first paper that I worked on. 

A second paper, a later one, is actually about smart contracts, and includes the colored coins, the quantum set. This is called “Quantum Prudent Contracts with Applications to Bitcoin.” In that paper, we showed how we could, on a system such as Bitcoin, to also have some form of smart contracts. 

On something like Ethereum's dApps, for example, it's really complicated scripts that move money under very complicated conditions involving maybe hundreds of people. You could essentially create a program that tells where the money goes to and do really complicated stuff with it. Now, Bitcoin uses a simpler scripting language and it only supports a limited set of operations in some sense. Which keeps the system much simpler and easier to work with.  

One of the disadvantages of smart contracts is that it adds lots of complexity and (potentially) bugs, etc. So Bitcoin took the other approach and kept things pretty simple and arguably  even more secure, because there's less surface for bugs in some sense. The approach that was laid out in that paper allows us to achieve most of the tasks that are used in Bitcoin, but definitely not many of the ones that are used in systems such as Ethereum.

The bottom line is for Bitcoin, I think there is a long-term approach to switch to quantum money. And I think it's quite dramatic with losing very little of the functionality and getting a lot in return.  Of course, such a transition would take many years. It's hard to predict, and of course, it requires lots and tons of technology to be developed before one could even initiate these steps. But for long-term vision, it can be done.

Alex:
Thank you so much for joining us and sharing so much of your knowledge with us.  It's really wonderful to have someone with so much knowledge on this topic that most of us know nothing about. Once again, thank you so much for joining us.