Lev Stambler - Distributed Systems Made Faster via Quantum Internet

see how this works. Okay. All right. So, uh today I'm going to be talking about some of the applications of things you've seen earlier, some new applications, some ongoing research and uh thankfully I am at this time because a lot of this stuff has already been introduced which is good for me. Uh so the title of this talks uh originally was made faster but now it's distributed systems made better via quantum internet and this is work with never local uh along with Stephano and Nicola who's not here and um I'm also a PhD student at college.

So without further ado. All right. So uh quick outline for the talk. It's very brief. First we're just going to go over the end results.

What do we achieve uh without getting into any detail? Then talk a bit about quantum internet but it's already introduced. Next a little bit about uh what we're using like the key primitives that was introduced earlier onetime programs. And then finally like couple seconds of cryptography. If you guys aren't into cryptography that's fine.

Okay. So again a warning this is ongoing research. So grains of salt please. Um yeah so uh today we have uh me like distributed systems are everywhere in cryptography blockchain more blockchain stuff and I'm sure some non-blockchain stuff but uh they're very important and a lot of them are multi rounds so you have to be online for some time and uh this poses security risks in certain settings. it makes applications harder to use.

uh and there's ways around this either using uh trusted execution environments with very strong assumptions on the trusted execution environments or um I don't know if it's here there's existing cryptography to go around some of these issues but in the end you know Ethereum is there's like multiple rounds of interaction people have to do if you want to do an auction in some private way you have to do multiple rounds of interaction this can be quite tricky so uh what we work up to in this talk is a way to compile a lot of multi-round protocols into uh a single round. So what this means is that every party in a distributed system only has to do one broadcast and then it can drop offline. Um and this can be applied to things like uh secret sharing uh global randomness um single round secret leader election and uh many more things and sealed auctions. So um yeah the goal is to really use simple quantum states the ones we've been talking about today conjugate coding uh which we'll go over shortly and the quantum internet to achieve above the these results uh and trusted execution environments. So we're going to run through this but earlier we introduced these uh the quantum internet and what we can do and really for our setting all we really need are these four states right?

So 0 one minus and plus. And we're going to use uncertainty principle which says that if I send you zero and you measure in the send you zero and you measure in one of this Z basis you can always recover your zero or one but your plus and minus look random and vice versa. So I can encode information such that you can only recover part of what I encode. And as Fitzio mentioned earlier, we can use this along with trusted execution environments or some other assumption to get these things uh to get onetime programs which we go over shortly. But today these states are used for things like quantum key distribution which Mark just talked about.

Uh a few other things such as quantum tokens, uh calibration tests. There's something called position verification. It's very cool. But uh talk about that and um yeah but if we assume that we have some level of noise in our quantum computers or trust execution environments we can build onetime programs which Bitio mentions and onetime programs are this very cool primitive that allow you to send over a state and this state encodes a function. You can evaluate said function once and then the ability to evaluate that function gets destroyed.

So like they almost seem non-physical, right? like I can't send you an email and that email self-destructs. So they're they're very odd and very impossible in a lot of ways, but once you have some extra assumptions, you can build them. But the problem with quantum key distribution is that we don't have quantum memory as Mark mentioned. And quantum memory is very hard to achieve.

Quantum memory behind uh quantum memory which lasts more than a few seconds is extremely hard to achieve especially with photonics which is the main uh technology that people are using to send over quantum states. So uh we term this an ephemeral onetime program meaning that I sends you your function f you have to use it within milliseconds. You don't have the time to wait around and use it the next day. So what this means is I Alice sends Bob a function Bob receives the function. Bob has to almost immediately use that function.

And uh you might then ask like if you don't have the ability to store your function around for a very long time and you have to evaluate it immediately like why do we care? Is that even interesting? Um, and turns out no, it's not useless. You can actually do things with it. And that's what we're going to talk about right now.

Um, okay. So, really the the core idea behind this talk is to combine homorphic encryption, which people may be familiar of here, probably have heard of it, with these ephemeral onetime programs. And specifically, we're going to use something called multi key home war encryption. So really the goal of what we want to do is to be able to distribute quantum states such that we're going to have some public function f uh so we're gonna have some function f and we're going to have three parties uh for bio stephno and nicola fsn these capitals and they're all going to have their own secrets and we want to get it so that all three parties are going to evaluate uh f on their secrets and some public newly known input. And as we'll show later, this will give us all sorts of different uh uh different applications.

But importantly, this has to be done in one round of broadcasts. So the model is we're going to have all three parties communicating with each other. They're going to talk once and then drop offline. So just a brief review of homorphic encryption and what it is. It allows for computing on enencrypted data.

So um each party has their own secret keys. Fabitio is going to encrypt the message M to get a cipher text. He can send that to Stephano and then Stephano will compute the function on the cipher text for some function and send that back to Fitzio and Fitzio can decrypt that cipher text and get the output of the function. And it's done in such a way that Stephano never learns what the message M is. Now uh MHE or multi key home warp encryption is very similar except we have a slightly different setup.

Every party can encrypt with their own key and then each party can have their own messages broadcast those messages to the different parties. Um and then all the parties can jointly compute some cipher text ct of y. Uh and um the CTY is going to be kind of encrypted under all the different secret keys under Stephanos, Rios and Nicholas. Uh and then next um each party, Stephan, Nicola are going to have to compute some partial decryption. These Ps right here and then we can use all these partial decryptions together to get the output of the function.

So this is multi key homework encryption time. All right. So a more visual explanation, we're going to have our three parties. Each are going to compute their cipher texts and exchange them, broadcast them to all parties. Uh then each party is going to compute these partial decryptions, broadcast them back.

And finally, we're going to be able to compute the output of the function we want to join the compute. So for those of you familiar with multi-party computation, very similar, this is a form of multi-party computation in some ways. So now the question is what happens when we combine this with our ephemeral onetime programs and turns out we get some pretty cool results. Um we're going to basically use our ephemeral onetime programs to do the partial decryption. So if you remember we have this partial decryption step that requires extra communication and instead we're going to place that into our onetime programs and um letting FPR target function we're going to send over these partial decryption functions.

Uh there's some steps that I'm glossing over uh but that's outside the scope of today's talk. So again, same setup. All three parties are going to communicate. They're all going to encrypt their message and send over these encryptions to the other parties, but at the same time, they're going to also send over a one-time program that allows each party to do a partial decryption. So Fabitio is going to message send a message to Stephano which allows Stephano to do the partial decryption that Fabitio would have had to do himself otherwise and then each party can use these onetime programs to just get the output of the function without having to do any more communication.

Okay, so we're going to go over some examples now um and why uh this whole setup is actually useful. So let's say you want to have some sort of proof ofstake mechanism. Each party is going to there's going to be this pre-selected leader. Each party is going to broadcast their one time programs and their messages and then um the whole program uh the output y is just going to be the signatures that you would require and everything will be checked internally within the function. Um I think this is a pretty interesting application that actually is not just honestly curious but you can do what are called sealed auctions.

So in a sealed auction, you have maybe three parties in this case. They're all bidding on something and they all want their bids to be private until after the auction takes place and only say the second highest bid should be revealed. This is actually a very tricky problem in distributed systems because you can have the parties drop offline. If there's more than one row of one round of communication, if someone's unhappy with the result, they can like mess up the whole system. But in this case, we can actually just have each party is going to encrypt their bid and be able to send over their bid and only the party that has that wins the auction, their bids going to get decrypted.

And it's one round of communication. And this is I'd like to stress a very new application that as far as I'm aware you cannot do classically, but maybe there's some caveats. Um, secret leader election is another classic use case in blockchain. Uh, similar ideas. not gonna not gonna bleed you at the point but um yeah so uh these ephemeral time programs are pretty useful they're very simple but uh they can do a lot of things shared randomness verifiable secret sharing sealed auctions and uh I guess the question is what else can they do and can we make them more practical so one of the big problems is that you still need to keep around your states for a few milliseconds not picosconds or nanconds as we talked about about before So u these are one questions of what can do in practice and uh yeah so short and sweet but [Applause] there's still some room for questions.

Does anyone have any question?

No. Yes. Well uh continuing on the on the same timeline uh questions it's a series now u before I asked what is the opinion on a timeline for quantum communication infrastructure so to you the question is what is your opinion on entitlement for quantum memory what do you think we should expect over the next three five years

for photonics yes or photonically interface I haven't seen convincing evidence that photonic memories are possible. So like

All right.

But but but in this case, you don't need photonic memory, right? You just need to slow your down your photons for a little bit.

Yeah, I was about to ask. You don't really need quantum memories for this, right?

Yeah, that's that's the whole point, right? You only need to be able to slow down your photons for like a few milliseconds.

Yes. So if you just have QKD with a lot of like looped fiber to to to gain some I mean a lot of loops of fibers I get but yeah

or there there's like material people are using which slows down your photons. Um I think we were looking at this some time ago.

Yeah. I mean in the worst case you can just have you know a lot of looped fiber and it will just have to travel a lot more. But

yeah lots of fiber kilometers like

Yeah. Yeah.

Cool. Okay. Any other question?

So I was wondering in the NPC that you described before for the homamomorphic decryption. Yeah, exactly this one. So do we still have the risk that there's a party that gets access to the output before the other and can uh for example drop off and uh refuse to share something such that I don't know maybe Fab cannot eventually have access to Y

in the in the MPC case with without without the femoral onetime programs or

well no I guess yeah I guess this is the case in the traditional MPC for decryption and I wonder if this is still the case with your uh uh proposed construction.

Yeah, unfortunately it's like spec I was trying to think about this a good amount. There's hard to give a general answer, but you have to go with specific protocols. Um for a lot of protocols, no, you actually get around these issues of like being dropped offline. So you can somehow like you can combine you can make it so that if a protocol is behaving dishonestly, you can actually just exclude them rather than having them abort. That's that's the that's the big difference.

Thank you.

Perfect. Thank you very much. Uh thank you. Love and applause, please.