Events Add an event Speakers Talks Collections
 
Crypto 2020
August 20, 2021, Online, USA
Crypto 2020
Request Q&A
Crypto 2020
From the conference
Crypto 2020
Request Q&A
Video
s-126: Post Quantum Crypto 2
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Add to favorites
277
I like 0
I dislike 0
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
  • Description
  • Transcript
  • Discussion

About the talk

About speakers

Omri Shmueli
Tel Aviv University
Zvika Brakerski
Weizmann Institute of Science
Share

Okay, you can begin now. Alright, welcome back everyone. And this is the second section on post concrete, tell of crypto 2020 and their capitals. Talk song. Not post fart over here by that for the first time was so we have four tops and the first one will be scalable still around them, instead of I am ready for my lease a car for Cascade and Amarillo be giving a talk on my face behind the trailer slice and the floor is yours. Thank you, friend. Okay, so welcome everyone to the strip to talk

on Stella boards to the one point in States. And I am wishing well in this is a joint work with that week about Walker, going to concentrate on the fishing generation Apartment, 10 states, and simply because there is too much information. There is no such thing to presentation and achievable goal is aiming for infinity solutions, such as long and number of copies is going to be indistinguishable from the same number of copies. Do we know for example, that for one copy of the classical?

The more the harder it is going to become postal stamp and one functionality to implement. The support is called the student status for a any polynomial number of copies of the output. It is going to be indistinguishable phone with the same number. I want to make no more formally. The definition of this is a Quantum. I want to go with them at the end, the output and is going to be indistinguishable foreman and cubital tunnel pain. And it is known to how to do chicken stock that your generator was based on a ghost 12 men's. No, one thing that we

observe about the tests, accumulative definition of the Perla generator. Is that the number that we think of it, to invent? Which denotes how many copies were going to let Ava, do they have in how hot, is it going to be in the skin witch and the other number in blue, which is the outer space ties. These are exactly the same number and positional meaning of this. Is that the more we want to make a a size, are the bigger it gets? And another thing to say about this

week, we can say maybe something along them along. These lines, we can take and to be very big in particular going to be big and then takes a fix of this very big want some space which we now know was very random, but these kind of start just don't use a few state. Is the reason that it does not yield to Independence Day of the site. So, essentially this is the information that we are proposing. This is the scale of the same exact same. I'll go with him, before but now it gets too independent monitors and the opposite sides in a blue and red landed security.

So if you were Old English into the previous construction, so why doesn't previous construction have a security detail? So, all of the states in the support of the pl, a generator are essentially uniform, amplitude of the vectors that have in their support of all of the elements have the same absolute value. And in the phases on do know in order to end in one thing to say about this time, with his division that school is small number of cubed. And did I mention is small and it becomes very easy to distinguish.

And to get the scale of a stage where we can look at it more state, but it's still very, very hard to distinguish for me to stay and we are still need to undermine the amplitude. Not only the face. and the thing is that, at Random phrases is a local property and random. Amplitudes is a global. What exactly do I mean by this is that we can stop on any superposition State, the uniform superposition. And you know, that's the one we can make a local computation in superposition and we can get around on me and

another to a food, we know that the quantum state is corresponds to unit vector and you need that. So it means that all of the a to depend on each other because they had to stop at the school. We don't need to sign up to Do in this world very briefly. We Define explodes notion of scalability in particular which show with your family will show that the basement the existence of post one-to-one functions. We know how to construct scalable. This is the same a computational sumption is the nearest phone on a generator.

For another notion of deficient generation state is called the design. I did not Define it, but it is in comparable to sugar and we improve the efficiency of the scalable home, depending polynomial of copies to the pending for little girls. One last word about the technique. So in a very small natural, we know that they are. Dispenser for Quantum state is corresponds to the University of fair. If it's there and do with Quantum state is. So in a 2002 Jetta 2.0 is

because of the spherical symmetry of the gaussian distribution and distributes exactly the same. So what essentially we're going to try and do is to sample. The Galaxy invicto in Quantum State and one good thing about the gaussian distribution. We know that it is local is Mexico Independence Day and one things that we need to take care of his the know. This is the global poverty, which I referred to earlier and something think we don't know how to compute efficiently. And in order to get around ask not knowing the

norm of this, through, to the end. I mention of Life. Do we use the technique called Quantum logic and sampling, which is An analog the quantum analog of classical rejection stamp. This is how we respond to this girl Skindex. Thank you for the Dominic to the mother. It's the question. Okay. So, anyone who has a question from this nice talk piece. Patrick questions in the chest. So you thought on the, I find erase your hand. And in the meantime, I have 11 questions. So so you'll construction, as I understand

is directly like constructing a DirecTV pseudo-random State instead of doing the wrong approach of cutting off some cubits from an existing state wondering. I was wondering whether, you know, the answer, if I'm getting a big, should a random State? And I want to make it smaller. One out of out of it, but I might want to use something more clever than cutting off Pitch. Is it? Do we do we know that this is impossible in general to kind of I, I don't know if something that will tell us if this is impossible.

I surely don't know that. This is possible by, I don't know that this is impossible. Okay. Yeah, so it looks like we don't have any other questions right now. So I can I get a thank you again for your talk. And I get the microphone back on the Run. Carlos. Santana's race from Ruben LP, buy a lightbulb nuscale power, evaluate a theater show. And dinner will be either. You see, my screen has this talk has a little less Quantum. The main motivation is actually towards constructing such a multi-party competition, protocols. So he and

why they want to run some interactive protocol to evaluate the function f on the private input. Without revealing, any more information on the This model was Allison. Bob also have access to a head of time, jungle source of Carly, the randomness, which is generated by a trusted dealer independently, so the benefits of this proposed, a model, when the Padres use the car later, Brandon Nelson, the online phase of the critical, this can now be information through attic, Lisa Cara and also very efficient. In fact, it's just a small constant overhead on top

of evaluating the function and sending a description of the function in the clear. Are the main downside of this approach is that the bodies actually have to generate this private car died during a mess in the first place. And typically this is done with an interactive protocol, which is very expensive and several cost of most particles in practice. Now, I sit around the correlation generator is a tool that offers an approach for reducing the cost of this be processing face. Where is a traditional Cedar random generator random

string generator? We're calling each of these seeds can then be local expanded to be just a larger output of steps of the power of God puts together is supposed to come from some Target correlation where you can think of. This is maybe a large batch of Lydia's friend says, on random or a lot of fractures. What is a one of these expanded out? But should be competition Lee indistinguishable from a real sample of the correlation, even if you'll give him, the seed was generated the other output from the pcj. I so they can be plugged into

any NPC protocol in the model. Now the mango today is we're going to be looking at generating the correlation, cool. The believe is linear function evaluation related. Correlations of this is a two-party correlation is typically you have an input a UV from Bob and then put X from Alice Through the field elements. And I just received an output weux, but guess what? It's a lien the correlation and we just a random and give them out to the bar. So, this is related to multiplication triples and

in a lot of severe competition. I saw main contribution is to give you constructions of Cedar random correlation, generators, based on variance of the Ring letting party with noise or something. In particular. We could PCGS for generating a playlist in the function of valuations and multiplication triples where the competition will cost of expanding the seeds or juice and a release or triples is just quasilinear and his length of the album. This improves upon a previous

construction or last year, when we had a quadratic in and cross based on the standard LPN, assumption. Interesting. The techniques he was somewhat analogous to an inspired by existing techniques from the flea Humboldt, encryption literature ring out during a tour for the quadratic equation. As main contribution is an activist cure protocol actually setting up the seeds for this piece of cheese in a secure multi-party competition. Protocols such as speeds, which is active security and it gives us something which is very concrete

mixing stick. The finally, a few more highlights of the paper. We get some extensions of our basic piece of cheese to the multi-party siding and also more General forms and find me. We provide some security analysis of the variance of the Ring of the an assumption. We require. Most efficient constructions are based on a arithmetic version to bring out the end of her. Lodge Prime watchlist pee on a polynomial, much of f x f of x should split completely in two linear

factors with a somewhat similar to bring the View using a psychic air distribution and also a constant number samples. I so you might be wondering how efficient is this? Influenza completely is a few, a concrete estimates. Based on some micro benchmarks read it. That's what you want to generate a million indicated, multiplication troubles, but it speeds protocol with two bodies of 128. I've been the ref pipeline of first, you have to start out with a small number of see Triple say twenty-five thousand and a few MB of communication in the

protocol which generates the first. Then the local expansion phase takes Road 22nd. And if you want to produce more chapels in this and you can just reserved the last portion of these do a kind of bootstrap and procedure use these to generate the seat triples, the next set of Pisa G seats. So comparison to the state of which based on Humboldt. Contraption has to be the key generation setup and the large amount of interaction with comparable amount of computation time to GB of communication that requires a

much, much lighter than the amount to set up the PCG Siege, which we use It shows a piece of cheese, give a practical approach for multiplication triples and other applications, and thanks for listening. Harkins Theatres, when we have time for questions. That's a first before, if you have any questions, please type them in the chat. I have one question. So I guess this ended, this isn't a post-concert session because it is related to learning party with my switch to smoke a Quantum broken, but I'm wondering, is it all supposed to be secure? So that's the

security prove go through in the quantum setting or is it just kind of related to postpartum security by sharing in the summer? So we didn't think about doing any security proofs in the quantum session. And I think protocol, we do rely on a random article which may be a little more tricky. But post-mortems. I guess at this rate I guess. Can make your own music. Okay. Thanks, and thanks. Alright, let's move on to the next stop. So this will be a nun PCP approach to its extinct countenance after their knowledge by

Fountain Blue hotel, but then we bought steaks come. When Gregor cider and Congo, begin to talk. How do you say my name is April 16th? So this is just a simple example of a statement, the classical one. So you're keeping the Matrix for you and you want to prove knowledge of a short meeting with smoker efficient with p u r, q or Q surprise. So these types of statements can be proven Odyssey using last commitments, and they're having a lot of work on that. Especially if Gregor stuck on Monday. So they rely on luck want to say something like this or a doctor and

also they can be implemented efficiently a while and multiplication and also in the palm of your hand setting with the entities. So the main drawback is also described by Gregor or Monday is that the precise is Linnea in the number of commitment. So maybe it's still fine to apply these. These techniques to produce a small statements like Ranch Brew or approving knowledge of elderly sample, but one can imagine that form complicated statements based blood. Then on the other hand. We have the

functions and then the processors release of linear or logarithmic in some cases. So then, the, the downside is that it's quite slower compared to the lattices and sometimes this might be in some scenarios that might be very special. For example, one, we want to grab quantico's unconstrained devices, as to what this paper is to construct. It can be implemented, but they also so that they also have the nicer than your profile. So kind of benefits of the Two Worlds. So this remotivation to our contributions can be split into

so they have two different techniques. They are supplying you and yeah, I don't really have time to discuss both of them. Unfortunately. So I I find the leprechaun. This is very interesting. So I'm also happy to talk about the offline is also in the video, but in this talk will just focus on the main idea of the last appearance for the first. so, Okay, so it is. Yeah, it is inspired by the discrete log bulletproof, as the name suggests. So the mail duration is as follows. The superb's me have some problem introduced in the previous life. So we have

a sequel to you or it'll hold over some rain. And let's say the rectoress the secret Victor s is very long. So the line is very long and it has small. So obviously one could just do some apply somewhere, but you can see that if he doesn't do something like that, then you send the masked open which has the same length as a mess. So if s is very long, then this part would be brakes passive. So that the main idea of bulletproof is the score of the last Brooks's

the following. So we split the Matrix Institute of matrices, a 0 and a 1, then the vector s into a zero and it's one of the equal length that we have 80. I want x, 20 x 1 this year. So then for a challenge to get challenge that we have the bottom. So the Matrix see a 0 + a 1 times, The Matrix as 0 + 3 is 1, is equal the sum of 0 + Cu + C Square W1. So here's the W, start across the room. So wcosa 1 + 0 + W. One is easier as one. So the intuition is just to stand wonwo so you can see from the other. It's nobody's your knowledge and then we end up robbing a simple equation. So they

can SVS Prime is equal to your Prime. So be here is the Matrix. See a 0 + a 1 S Prime is the secret factor of 0. + 3 is 10 + 30 + C Square w w which is public. So from a z a s is equal to you. We ended up with b s primes equal to your friend. So what's the difference here? So. So, that's the good news and the bad news or the bad with the good news. Is that the ship the length of the secret factor as Brian is 2. * 4 is twice sort at 12 times or so, but we can walk around

to get even smallest sizes, smaller, length of the secret extra. So that at the end when the sides, the length is not pretty big. Then we can send them before. Okay. So the bad news here. So you can see from this light, is that We assume that the SOS Vons 1/2 small quotations, right? But then it's Prime which is a 0 plus he has one will have to see so so this is just the one around. So if we have made a run for longer than you can, imagine the whites will be bigger. And then when we do the Sounders broke than the extract than

the size of house, also gross and I forgot we have to set up set the parameters. So the main conclusion is that even though the precise is nice and so long, Extract. The message being large makes the protocol not really interesting at practice. So here I go. So I know. I didn't talk with him about level commitments but for like 2 days a week at the polo g x size and is not your knowledge because we spend this W's and then there is this message meaning that when you

extract does the vector, than the the secret better than the size of that. The conditions of extractive sector are, are much bigger than the one that we started with. This is a nice of theoretical perspective, words practicals of linear, linear Bicycles of ninja, Thank you very much for listening. I think some are there any questions for come? I have one question. Have you made any like we have any concrete comparisons, how this compares to other? Implementation experiments or something?

Like we we know this. This like it's so big. That's what we think about it in terms of techniques, is the techniques are a wee thing. They are nice but it turns out the sizes in publicly. That is I'm not sure if there's any point to is Toshiba future. Thanks. Yeah, yeah. Can any other questions from the audience? I definitely think of a question that you asked about itself. And be ready. If it is also a very nice question here. So I just wanted to point out that this bulletproof technique was also

analyzed in the in yesterday's top of the old knowledge. So, so does multi remote around. Catch a paper in the paper? Okay, so that one can be applied here to remove the interaction. That's what you mean. It is about how to prove that how to prove that the brother by security to Europe. Okay, so it seems we don't have any other questions so I give it. It's not in taxes. During those Arguments for qma with pre-processing by Andrea color. Tomorrow. We take

Phenergan and I will be giving the talk. I'm just the flu virus. Can you hear me? And can you see the screen with so many tractors? Are all these proofs? Of course, we'll started in the classical literature and it is well known that in the bed, in the same. Although these are impossible to achieve four languages outside of beef. And one of the most common setups to overcome this and to get non-interactive seeing all these proofs taller than he is to assume that the verify an approver,

share a common random staying or common referents. Doing this work is about the quantum setting. So in the quadrants, I think the first question we can ask is our cruise for Auntie, even the interactive wands still sound into your knowledge. In particular what happens when we have a Quantum there fire in the difficulty is that in the quantum case? It is not in general possible such an ethically possible to rewind a fire and in general, a Quantum measurement destroys internal state of the verifier in an irreversible way. In Quantum information cannot be copied and of course rewinding is

a common classical technique for proving zero knowledge. But none the less we do have zero knowledge proofs for Auntie which are their knowledge against Quantum, their fires. And this is from the work of Watchers and internet interactive case. So instead in a recent work of Picard and she and they showed that music's for Auntie can be constructed from learning where the errors in this year's model. And one of the things we're showing our work, is that the music from a Kardashian, or straightforwardly? Plus, secure. And this is because simply no rewinding of the verifier is involved.

Now, the second erection that one can explore in the Quonset thing is to go beyond them. So can we have zero knowledge proof for you and me and a few minutes. Just the quantum analog of empty or I may wear the witness is allowed to be a crime state in the verifier can be Quantum polynomial. Time to the most well started to make a problem is the local hamiltonian problem. And in this problem, the input is a classical description of the hamiltonian, which is a hermitian. Operator on say, n q b. It is Loco in the sense that it can be described as a sum of

local terms, each acting on a constant number of cubits. And this is a promise problem. So your promise that the lowest energy the lowest I can go is either less than or greater than betta. There's some guy say in verse polynomial and you have to determine which is the case. And so intuitively. This problem, isn't you? I'm a because it's easy to verify that the energies lower than a fact, if you're handed the ground state, but of course, if you don't say the cells may be hard to find and so there is an interactive Journal. This protocol for qma. This was proposed by broadband and quarters as

one of the authors in 2016 and in particular, this is the protocol for a variant of the local hamiltonian problem. And here, I'll just give you a very high-level sketch of all, this political precedes. So let's say that we're in the case of yes instance. And so there is some ground state, some witness call. Ew, approver sends to the verifier serve in encoding understand what indication code without being super size. Of the weakness of the ground state together with a classical commitment to the encoding key Collins

Key. Many steps, do the verifier to the foam, amorphic Lee measures, include to stay that, she receives and get a classical and coded outcome. And this should be an encoding of a new energy outcome. If the encoded state was indeed a ground state and has returned to the approver. And in the final step of the approver proves that the encoded outcome, indeed the codes to lower energy, with respect to the committed Key & Peele us. So, by engaging in his approved for an MP statement. Now the question that we we saw them, this work is how

can you make this protocol non-interactive, or at least non-interactive, with possibly, an instant independent pre-processing, step? And so, certainly step 3 can be made non-interactive by adding a CRS to the setup, and using any music for Auntie. And the cracks is step to where the very fire reports, the encoded as come back to the Kruger. So the first thought that you might have is ADD approve, or maybe actually can predict these outcomes of the verify doesn't need to send it through hurricane predicted. But unfortunately, because of the requirements

of the authentication code is encoded outcome is uniformly, random out of exponentially, many to channel be predicted in the proverbial. Can't possibly send probes for all of these outcomes. It's all just tell you hear what the main idea is to make this protocol non-interactive. So the main idea is to use quantum teleportation. And so as long as it sounds, this will allow the verifier to sort of measure the encoded State before she even receive and Report included in a free processing step, which is instant independent. So the witness will actually only be

teleported by the approver in the following staff. And in order for this teleportation to be possible to verify, will have to stand enough. If your purse to the groomer in the proposal. And we also have to make user for modification and this is why we end up getting an argument and not the proof. And one of the caches, when one uses teleportation is that there are teleportation errors for those of you who are familiar with teleportation and they can be accounted for in the provers music. And the

last thing that I want to mention, is it in this work. We also a separately, formalize, the notion of proofs of quantum knowledge. So this is a joint with Bob and Stephane to knowledge informally. What I mean, is it access to a successful program allows to recover the quantum to start a pontoon Witness? And particularly sure that our protocol for is indeed an argument of knowledge. So this is all that I wanted to share. Thank you very much for listening. Hey, thank you, Andrea. Thank you.

So, do we have any questions from the audience? I have a question about the argument of Condom Knowledge. Maybe there's a condom no counting. So is this product colors and some intuitive way ensure that when you extract a condom is nest and something has been consumed from the river. So you like the only going into this and you're assuming that the extractor has access to the proven successful Clover. Sober that has in particular. I mean, I might have a witness on register. So if you have access to a successful program than you're able to

extend Chris and probability. Is basically a state. It's not actually quite the witness, but it's kind of a little bit degraded even so it'll stay that passes. The verification of of your arm will cure him a circuit with with high enough ability. Okay. Thanks. Are there other questions questions? The first one is, do you know any applications of this music for qma protocol? I, I don't, personally, I have not personally found like a compelling application of of Music circular May yet. So this is the thing and interesting, open question. And yeah, unfortunately

also for the second question, something that it's a very good question, right there? Any barriers to achieve music without people? Singing, saw something that we thought about, and, unfortunately, the particular sort of trick that we use here and very depending on how I don't have any PR pairs. So one thing that might be possible, although I don't know how Approach is if you allow a setup and which maybe you don't know, they have a CRS, but you also have shared if your prayers so that say you don't have to worry about starting a first and maybe

they are. There might be a hope, but I don't have a computer for cecile's is very interesting question. Okay. Thank you and you anymore questions? Then I get the mic back to thanks. I know since this is our last session. Are there any questions or any of the peers talks? You can spend a couple minutes. Or. Okay. Well, I guess it's probably running meds for people from Europe. So, okay, I'll say this would be the end of this session. Also today's program

and let's give all the speakers, another round of applause. I just wanted to make a quick announcement that thanks to Georgia Marcin. Are we now have crypto 2020? Swag? It something you can download and print on your own t-shirt. If you wish or in a bag or in a stick, on your laptop, supposed to Garland to the chat and also on the lip, then you could go to the main crypto 2020 page. They'll be a link there for downloading the files. So I go make t-shirts and we'll see everybody tomorrow.

Okay, without a T-Rex. See you tomorrow.

Cackle comments for the website

Buy this talk

Access to the talk “s-126: Post Quantum Crypto 2”
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free

Ticket

Get access to all videos “Crypto 2020”
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Ticket

Similar talks

Weiqiang Wen
Cryptanalyst
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Michel Abdalla
Senior Researcher at CNRS
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Matthew Jagielski
Google at Northeastern University
+ 1 speaker
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free

Buy this video

Video
Access to the talk “s-126: Post Quantum Crypto 2”
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free

Conference Cast

With ConferenceCast.tv, you get access to our library of the world's best conference talks.

Conference Cast
873 conferences
35612 speakers
13585 hours of content
Omri Shmueli
Zvika Brakerski