Enrico Bottazzi - New frontiers in multi-party computation with iO

Good afternoon everyone. Welcome back to the Capella stage. Hope everyone is recharged and ready for this last part. We are happy to proceed with the quantum track and today we have with us Eniko Vadati the computer who gonna present us the quantum research the B of new frontiers in multi-party computation with IO. Enrico is cryptography researcher.

It was a new it was a new topic. Okay, we have an update even recent research.

Yeah. Yeah. So I think uh the topic is different from the one that I originally proposed and actually the the topic as you see from the title is going to be quantum money plus via indistinguishability of so you might have already heard about quantum money during the conference and today I'm going to add a new component to that which is indistinguishability of fuscation which is a technology that is more um classical cryptography. So it's less of uh quantum cryptography and uh we're going to use it to enance to upgrade a new properties to quantum money and uh I work at minio which is a a research team focused on building indistinguishability ofation and this team is part of the ethereum foundation. So we are going to start with a brief history of money.

We're going to analyze three types of money. Cash, Bitcoin, and quantum money. And you notice that I put um the quantum money after Bitcoin. Even to the the construction was published more than 35 years uh before the quantum money. And that's because even uh if it came before Bitcoin, it's still way less practical than uh Bitcoin.

And the reason might be for example the lack of quantum channels and uh more importantly the lack of uh capacity to preserve the quantum state for enough time. So we're not really going to analyze each type of money. We're just going to analyze them through two two properties. So one property is the traceability. We define a traceability as the capacity for an external actor from for an external party to keep track of the movement of this money.

So for example, when it comes to cash, we we can see from our experience that the traceability is low. Every time you get some cash, some bank note, you cannot really tell who was the previous owner of this uh of this cash. When it comes to Bitcoin, the traceability is really high because by design the the blockchain of Bitcoin is public. So you can see every transfer, who transfer what, how much, to whom. And uh lastly, we we we say I'm claiming that the traceability when it comes to quantum money is medium, which kind of contradicts what probably most people would say.

they will most of the time I see the traceability of quantum money compared to the traceability of cash. So they claim that since is a sort of like a physical medium of money it it still has no traceability as similar to cash but I'm going to explain you why I believe that this is not true and this is what we're going to upgrade using uh indistinguishability of fusation and uh as the second property we are going to analyze the forgeability and uh forgeability is the capacity of a malicious actor to clone, to forge, to counterfeit this type of money. And we know that for for catch the forgeability is very easy. Anyone well not anyone but with some uh effort is possible to create fake money to duplicate money for Bitcoin is very hard to forge money. In fact, this is one of the main uh innovation of the the Bitcoin uh protocol, the capacity to allow for peer-to-peer digital cash that uh prevents the double spending problem.

And this uh this hardness is based on a on a social consensus. So we know that um if there's a 51% attack on Bitcoin, it's possible actually to create infinite copies of Bitcoin. So this is a social arness if you want. And uh lastly, we have the hardness of copy of cloning quantum money which is still hard as the same of Bitcoin, but it's a a different source of hardness. In this case, the source of hardness is a physics.

And uh we are going to now see what this means. But in general, it's more uh preferable to have like some hardness based on a physical principle than uh on some social consensus. So we're going to now go through the principle of quantum states. You might have already heard of this during this presentation, but I think it's still good to go through that again. So, we're going to divide our um our algorithms in two.

We have the upper part will be dedicated to the quantum state generation algorithm and later we'll see the measurement algorithm. So, for the quantum state generation, we start with a with a list of bits. So, whoever wants to generate this quantum state chooses a list of bits and this is going to be the the information that they want to embed inside this uh quantum state. As the next step, they're going to flip a coin to generate some randomness. And uh the result of this coin flip will determine a basis which is either R or D where R stands for rectilinear and D stands for diagonal.

And the combination between the bit and the basis will determine sorry will determine the quantum state. So we see that we have four possible combination and um we're going to analyze them uh more carefully. So whenever the basis is r we have two possible result two possible cubits two possible quantum state. One state is this arrow that is vertical and this corresponds to the bit one in the rectal linear basis and we have this horizontal arrow that correspond to the bit zero in the rectal linear basis. And next we have another two combinations that appears when we choose the diagonal basis.

So we have this 135 degrees inclined arrow for the one in the diagonal basis and we have the 45 degree arrow for a bit zero in the in the diagonal basis. So really this is what um this sequence of arrows is just like a mathematical notation that we use to represent some quantum state. But really from the outside when it comes to measure this when this sequence of cubits is given to someone they cannot really see what these arrows or what is the the type of information embedded in this quantum state. So what what can they do? What can a measurer do when presented with this uh list of cubits which we can uh embed inside photons for example.

So the measurer would again flip the coin choose a basis which is either diagonal or rectilinear and obtain some measurement after this choice and we see that uh there are two possibilities. So in the case they chose at random the same basis that was chosen by the state generator they obtain a correct quantum state. So the same arrow basically they can obtain and in the other scenario. Yeah. And we can also derive a principle from this uh observation which is that whenever a quantum state is measured in the correct basis the measurement yields a correct state.

And in the other scenario whenever the measurer picks a wrong basis actually the result doesn't match anymore the the state that was encoded by the by the state generator. So we can derive this second principle that whenever a quantum state is measured in the incorrect basis because you see that there's a difference between this R and this D or this D and this R the measurement yield a randomized um perturbated state. So given these two let's say empirical observation we can derive a principle which is the noncloning principle that states that someone without the knowledge of the encoded basis cannot obtain cannot duplicate the original state without disturbance without injecting some uh some randomness. And uh this is very cool because it prevents the coping of some quantum state and we are going to leverage this principle to build some application such as quantum money. So is it clear or okay?

So now we're going to use this principle to build quantum money and first of all we're going to define a quantum bank note. So a quantum bank note is uh pretty simple like uh there's a quantum state. So you can really you should really think of a quantum bank note as a physical object that can be exchanged. What it won't look like a normal bank note but it's still something physical. It's not like a bits in a computer is a a physical thing and uh it's made of these two components.

One quantum state which is a sequence of cubits. For example, here is 20 cubits and uh attached to a serial number which is the same thing that you see today in uh in normal bank notes. So what's the flow like how the how quantum money are exchanged and who are the subjects that are kind of involved in this exchange. So we have a bank and a set of users. So again this is very similar to how money are transferred and generated today.

And uh the banker will first generate the quantum state. So they will run the algorithm that we described before and they will store in their database a mapping between the serial number and the quantum state. This quantum state will be embedded in a bank note will be created will be minted will be passed to some uh some user and uh this person is going to exchange the bank note for example they will buy things at the supermarket pay with this bank note and then this bank note might be might end up in the ends of someone else again transfer and at a certain point this guy this guy might ask themselves if the the bank note that they have in hand is actually legit. Is uh is it valid or has it been clone? Has it been generated by some malicious actor?

And what they're going to do to verify the legitimacy of this bank note is to go is to go to the bank that will uh transfer this bank note to the bank that is going to be able to tell whether this is valid or not. And uh in this case we assume um a benevolent scenario in which there are no like teeth. So the the check will pass. But actually how is this check uh being performed? So the the the bank note.

So in order to do this verification step, we're going to leverage the principle that we saw before, especially the one on the top uh on the top left. Given the fact that the bank has this information in their database, they can actually perform the measurement in the correct basis and they can obtain the correct state. So in this scenario they can verify that the state is equal to the one that they generated at mint time that that was stored in their database. So in this case if the bank note wasn't uh randomized it wasn't um perturbated the the verification will pass. While in the second scenario, in the scenario in which we insert some um some malicious actor in the schema, what will happen is that the the initial process is basically the same.

But at a certain moment this guy, this Tiff will uh will try to to clone to duplicate a bank note and the verification won't pass because uh the the state inside the bank note after this uh attempt to clone will be modified and the verification algorithm run with the from the bank will result in a quantum state that doesn't match the one that they stored in their database. So this is a a very cool property like the the capacity the any effort of duplication of cloning will modify the state and therefore uh somehow naturally invalidate the the bank note on a on a physical level. So this is very cool and uh up to now I've just described quantum money as the it was introduced in the original paper in 1983 but uh now I'm going to start um pointing to the problem the issue uh that is inherent in this uh in this construction. So the issue is that um every time that uh a user wants to verify the correctness the legitimacy of a bank note they need to go back to the bank and this present an issue of scalability meaning that uh every transfer basically after every transfer a user will need to go back to the bank speak to the bank to verify if this is correct or not. So it's a very bad uh design, bad system because every time you need to go back to this central party and uh if this party goes online, everything is screwed.

So I don't like it as a as a system. And uh there's a upgrade which I define quantum money plus in the title, but technically it's called publicly verifiable quantum money or public key. Quantum money allows every user to verify the legitimacy, the correctness of a bank note by themsel. And this seems uh a bit tricky because u the way we described it before was that the verification algorithm was run by the bank because they had access to this database and they could verify a state against this database. And uh if we were uh kind of open source make this database public, this would kind of uh nullify all the the goal of our of our construction because this secret information would actually allow the t to measure the bank note in the correct basis and therefore clone.

So we somehow we need to um create this algorithm that allows this verification which is based on secret data but doesn't reveal this secret data and actually this is where uh basically what I'm doing what I'm studying comes into place and this is in in substance the definition of uh indistinguishability of which again is not a technique based on quantum cryptography is based on classical cryptography. So it has nothing to do at at its core with quantum physics, but it can be applied to application such as quantum money. So we're going to briefly introduce IO before applying it in the scenario of uh quantum money. So we start with a simple function. So this is a simple program that performs some uh arithmetic operation and uh this box is transparent meaning that people can uh pass their input x can obtain the output y and they can see inside the box what's happening what what this program is doing and uh we can think of uh a similar situation in which someone can uh feed their input x inside this gray box and get an input wire without really knowing what's inside this box.

This box is somehow offuscated we say and this is really the definition of IO. So IO you can think it as a as a compiler that takes a program a transparent program uh program definition and outputs uh a block a box uh a gray box an offuscated box that can be still consumed by people that maintains the same input and output relation but it has this uh very very cool property that is able to hide the program definition and uh In the case of this arithmetic program, maybe it's not very useful because uh it's just a very dummy program. You don't want to there's no reason why you want you may want to hide what's inside of that. But there are other programs for example uh a signing function that might have some secret inside. So in this case the the K is uh is the signing key and the capability of obuscating this program is able to generate this uh gray box this offuscated box that can be distributed to the public.

Everyone can consume it. They don't need to speak with the with the owner of this signing key, but they can still get a valid output, a correct output. And the coolest thing is that they they don't this uh this box doesn't leak any information about the the key. So I think you might have started to understand how this can become useful in the concept of uh of quantum money. And also as a as a as a note like uh if you look into the paper that I that I mentioned before is actually a bit more advanced than the way I'm going to explain it.

But the goal here is just to give you an intuition on how IO can be used to upgrade the quantum money construction. And maybe one other thing that I want to say about indistinguishability ofation is that from a interface point of view there are two main algorithms. uh offuscate algorithm which is the one that takes as a input a program and outputs uh the offuscated version of that and the second algorithm is the evaluation which is run by users it can be run many time and uh is the basically the bottom part of this slide. So the act of passing an input using this offiscated program and getting an output. any question on uh IO?

Okay. So now finally we can uh introduce the concept of quantum plus money. So we compare to the previous uh flow. We add an initial algorithm which is run at setup time and which is run by the bank. And what the bank is going to do is they're going to offiscate the verification algorithm.

So they're going to obtain this uh gray box that has the same functionality of the verification algorithm but doesn't really reveal anything. And this is published to the cloud. So every time you see a cloud, this means that this is something that everyone can access. there's no there's no there's no issue in uh looking what's inside this uh this cloud. Then they're going to mint their their bank notes in the same way they would uh they were doing before.

And uh the bank note again can be exchanged freely through through users in the in the market etc. And uh the additional point the difference from from the algorithms that we described before is that now the user can really just go to this cloud which is a abstract actor that is not really permission permission. They can fetch they can fetch gray box this gray box and they can they can evaluate this gray box this gray box and the verifier program passing the rece they receive they can obtain they canain this like thumbs down to to tell them if it's valid or not valid or not in this case we scenario which scenario which was was forced was work the say in the in the scenario which is the bank not was legitimate and uh what you what really we obtain in this quantum money sl is the capacity to not rely anymore on the bank for the verification. So you can also think a scenario which the bank will mint all their money and they can uh yeah and they can uh later disappear just go away and the system will still work. we kind of remove this dependency on the bank throughout the process.

So that was uh the end of my presentation. I just want to conclude what are like the the takeaways of our presentation. We saw that quantum money enables better form of money because of this uh reliance on uh physics for uh unforgeability. But there's some issue which is this uh problem of the bank that needs to be that needs to be present at every verification step. So we added IO to obtain even better money because we removed this reliance on bank for verification.

But uh probably one one thing that is worth mentioning is that uh like during the conference we always say that uh quantum money and in general like uh this kind of quantum uh based cryptography primitives are uh are still far from reality. This is probably less the case for IO, but still IO like when I go to conference that are more on uh classical cryptography, IO is considered not even real like they think it's kind of a crazy thing. So we are still speaking about two primitives that are very far away in the future. Probably IO is less crazy than quantum money right now, which makes me feel uh better. So yeah anyway we are Machinio and we work to make this uh IO possible and hopefully whenever uh quantum money become real also IO will be real at the time and can enable this uh quantum plus money.

Thank you.