About the talk
I am interested in theoretical computer science. In particular, I am interested in foundations of cryptography and its interplay with computational complexity. I am also interested in adversarial machine learning from a formal perspective. In both of these areas, I am particularly interested in understanding inherent barriers (aka "lower bounds", "impossibility results", or "separations") that might exist against using computational intractability assumptions.View the profile
I think we are good to go then. So hello everyone and welcome to the session of crypto 2020, which is going to be about $0, truth must be going to have seven talks. Most of them are going to be about $0. But I think all of them are going to be about truth. So that's probably a unifying all of them. I'm going to now introduce their altars of the first paper and the paper is going to be called. It's called compressed signal particle theory and practical application to plug in Play Store. A grass, makes buy some assassin
law and Ronald Kramer and I believe Thomas is going to give the talk. It was. Arundel is giving the time. Dear me. Yes, okay. 2 seconds. Okay, good. Skraitz. Hello everyone. So this is about to compress Sigma protocol Siri and join work with my students with almost. All right. Okay. So around 3 move their knowledge. Protocols is a well-established basis for a zipper nose fruit. So ready for decades. And if we zoom in on the question of how to be a circuit
or knowledge on the protocols are lots of examples of how to achieve sort of linear communication complexity, meaning circumcised time, security perimeter, basically an 18, a bulletproof have been introduced by bootle at all, or do you work for 2016? In bensa, tall is Krystal 2018 where they dramatically reduce the communication? It's no longer linear but logarithmic now at the core of this method is ingenious require such proof of knowledge for Regina. Correlations on a long secret, committed Vector in
a compact commitment. And this work has such a place as being presented as a drop-in replacement for Sigma protocols due to this dramatic reduction in communication. Now in this work that I'm now representing to you, what? We'll be discussing is how to reconcile, bulletproof switching, my protocol Theory, and the conclusion that we propose is that rather than being a replacement was Bruce actually prevents the franxx ending of signal protocol, serious, or is it completely diametric opposition
protocol from Sigma protocols, with linear communication and then using an adapter? That's an adaptation of the core bullet proof proof of knowledge. We're going to compress this in a black. Box fashion as an afterthought. And as a result, we're going to get logarithmic communication or even constant. Okay. So what is our high-level approach? So at the highest level, what we're going to do is we're going to deal with linear instances. First, a linear
circuits only, so to speak and then linearize the non-linear instances and for my mathematical perspective, this is Perfectly Natural problem-solving strategy. The point here is that proof of knowledge is free radical relation on compactly committed, long, Dexter, and that's this Exit 8, its reinvention of protocol Siri to an extent. So we're going to do play this game in a completely different way. So let me first, explain how to approach the the linear instances. So using appropriate, appropriate compact, commitments to Long secret vectors.
There is a natural honest, trailer fires there. No Stigma protocol for opening on the secret vector. I'm going to try to explain this to you. Now. It is very natural. And this will have linear communication. Now, the observation that we make here is that we make a suitable adaptation of the Big Apple. Bullet proof proof of knowledge is recursive proof of knowledge for quadratic relation on a committed long tractor that I spoke about in the previous slide this adaptation to compress the sigma protocol.
Essentially. It's is third and final round which is linear size. The rest is smaller, but we can compress that in a black box fashion. So the result results. Logarithmic, communication, and we've only used the core meditation of the core of bulletproof to just black box compress. His last message. Complexity know, how do we handle the instances of a paper from 2012? I c i t s by myself. This paper forts techniques from information. Multi-party computation to of course to Party City,
protocol. This is inspired by a combination of my paper with Dawnguard to Mater from Europe. MPC from linear secret-sharing and the NPC's in the paper by shy quiz related to stroke. Inside a paper due from 2012 National homomorphic commitment commitment. One-dimensional, meaning, single field, elements are committed. And in addition with arithmetic sequence, sharing we get an efficiency, protocol. The proof long factors of committed, committed multiplication triple, correct. Alright, so But the verifier
does in this protocol that he chooses to, he does random randomly, pokes, randomly test, local multiplicative, properties of multiple effects of cherries with this thing to remember, about the observation that we make here. Is that a given context commitment to well, the multiplication triples themselves, plus appropriate, car-related Randomness. We can get a similar Sigma protocol. Let's make a constant number of Black Books. Calls to the protocol that I disgusting .1 the compressed openings. As a result.
We got a logarithmic size or costume size, proof for lung, vectors of compactly committed, multiplication triple. So that's a long way to work your knowledge. So for the specialized reduction from circuit, what we do is become perfectly commits. We have the proof or compactly, to the inputs of a circuit, the outputs of the multiplication Gates and correlated Randomness. And now we do a reduction that combines point one with going to a the influence to
multiplication in a circuit, Darlene, your forms on all ancestor variable. So that means that the relevant Secrets earrings are accessible as linear forms. So then it's easy to see that. The argument boils down to verifying long, vectors of notification triples. So what we do in addition soda, that covers the $0, the circus your in-laws, but we also need artillery protocols that for what we call compactification so far to prove murder is committed to it in Boots, back to her, that he wants to prove something about and an end of the day. She
would more likely be that this part of a protocol. The proofer is just committed to some secret input factor, that he wants to prove some property about. So let's do this to this vector or this commitment is dispersed across several lower Dimension. No commitments. For instance. If we use the Machinery that I just discussed plus additional ideas. We can compact defy this all into a commitments that suitable. For those are a lot of protocol that I discussed
under two and a communication will be the same. So this is this is another modular add-on of our work. That is not so explicitly motherly discussed in any previous work. No, and when it comes to which platforms with supports, this type of this type of communication, we can base it on the discrete, lock, same as bullet proof, strong, our estate in class groups, on ours, if we assume a multi-party setup of off of the magic, we have to know that for the discrete locked case, which is what that bullet proof.
Even down to the constants, in the back of the Constitution is equal to 2 and 3rd. I'm also supports that by speaking, in an honest, if it's a constant communication, it should also wear based on More work is needed to establish the efficiency because you have all the issues about the sound of the slack. So it's required, recent work is work with my students and we have used this Theory plus additional ideas. To give proofs of a command partial knowledge with logarithmic complexity.
And there's recent are not coming right by school Marcos and Seguin using the compressed Sigma protocols for verifiable empty seat. So, I don't know how much time is left out one minute. So it wasn't the time that you wanted for questions. Oh, okay. Well, it's all. Let me just finish with some historical remark, this idea of getting very fast as your knowledge out of completely committed. Long. Vectors that allow fast opening of linear forms goes back to two. 1010music the papers from 2012. But when we started
talking about his, which was actually at the PSD dinner, and it became clear that we could do, the top result, we have in the paper, much nicer, if we have compact commitments, Veracruz open in your forms very efficiently. So I asked around for several years. Nothing was known what time, the work of 2016-2018 came along and finally, we did it. Now. I know why it's have to wait for so long because it's waited. This work waited to be done by Thomas Indian Summer.
Started a few years back. So I think it's a very good reason to thank you very much. Science. Ronald can have one quick really quick question. Why the Nexus Beaker was the screen on which you can see? In the chart question says, how does this relate to linear? All your peeing in your PCP attractions. Can you turn one view your techniques as a method of compiling linear all your p's and peace. If it's in two lovers, make because I saw door cuz I saw a cryptographic arguments. We discussed a lot of related work in the paper SS, with respect to a 2
L of PCP. So I remember having had some discussions related. This work is too. So that part but I think I came to the conclusion at least a preliminary conclusion that it is very much tied in with with techniques around complexity theoretical assumptions and tricks that cannot so easily be abstract. It's away from the complexity Theory and most of the work on the linear PCP. Appears to meet a complete transitioning from information to your attic message to complexity rapid methods is of that kind as well. But especially at the parts of the
district cursive proof of knowledge. That seems so very much tied with the complexity Theory. So question. Thank you. So I think we have no more questions and we can go to the next talk. So I think we're going to leave you and share your screen to next speaker. Can share it. Thank you so much for the talk. So the next week is going to be in a position to euros for partial assimilated arguments by Cyber Monday, start working on Elliot's, body on Elliot.
Okay, thank you. So I may be at 5 and I go to briefly, describe a walker at the height. Now is about education in General. Weekly hot pink tablet. They are, we can secure it was very hot. 106 want to do it while preserving the, I like the efficiency and then hold it against a competition about the test. And as we all know, this is an important email. Find a Jamaican song action to reduce the sound in the album. Let's say we have some music on the Sonos on this game. And
then we want to apply LOL. Okay, so the most natural way of doing such a genetic amplification by the petition execution, many times. You must hold it for the two that to women, older. And so, the first option is just repeat execution, many times and the Best Buy accept. Display settings. Would you set the song cell if we start with my birthday? So we're each in each long is $0.40 the messages that responsible and executions babe Isaac. But in general, and they'll concrete examples of arguments that they let they have you repeat them million times in
the human head. So it turns out that there is a way to overcome this problem using a nation, which is why won't you just say except in the boat? Otherwise, otherwise, it acts like a coin again and again, and none of the course, then he just acts like me and accept me. But if you look at their land, Must have you seen that expression in the number of which is that the only problem with that? Is that better? Let you know, it's metal to amplify. I'll be 30 minutes or maybe business or a cheap the better, but just has no type. So you chose. This
is indeed, no tight and the sounds that you take an album the argument and you repeat the song by Mustang to be kissing Michael in which is only found by one of their life and their disability, get the title, bounce, 5:56, complications, and also, And if you want about the head in the pool by Bolding between the distribution, and it's a lot of empty building birth certificates, and there is such that, if you look at all the files before bt152, the NFL, which means that we cannot solve the termination will give us something better than this
really special. Thank you. Thank you so much, Elliot. If there's any questions, please let us know in the chat on Julia or in the trash pandas here. We have about three minutes for questions. We can go to the next stock if there is no question. I have one myself which might be very easy. So I can maybe I'll go ahead and ask it. What does the reduction in the proof? I need to be non-uniformity handles everything uniformly. So you need to assume none uniform.
It's all in this together. I need the second one is not a very kind of Reform. Question. Do we have a reason that the KL Divergence can't be used? It's not a well-defined question. I just, I just want to research. Question is not an assumption is why we need to stay in the division night, be infinite and then somehow we make it the internet and then became division. She did. Thanks again to speak of this talk and we can go to the next stock of the session if there is no more questions, but there is one there. Are there any reasons to use sequential a petition? Or is this
just a little bit better? You mean us? Okay. Thanks more if you want to eat you. If it's okay with you, then you can use the sequential. Thank you. So you're going to move to the next talk, which is going to be about. I think, if your aunt share your screen lock is going to be about interactive process for social graph. And I hope one of the speakers, one of the authors who was going to prison, that paper would share their screen. Is it a lot or so? The limit reduced authors and
later on at Cedar Clara? She came on at 8 on your gift. If any of them are here, they should go ahead and share their screen. So, my guess is that maybe they're not. In case I don't find it in case we have the present her for the next paper, which is the measure and reprogram technique if they are. You're they can go ahead and present and then we can check with that presenter of the paper that we couldn't reach out to later on during the session. Yeah, sure. I can go up. Okay, so I guess I have to hand it to
find who is going to introduce you and the rest of the session. In case we heard about the other paper. We will get there but fine. Go ahead, please. Okay, our next talk, will be the mayor and reprogram, technique 2.0, multirom San Simeon, more. We are going to hear Pierce and also something about konzen later from search for Chris. Maya, and yellow will be given to talk. So yeah. The floor is yours. Thanks. Thank you for the introduction. Our work is about spoofing field, show me a digital signatures and in general, fioti, a zero. Knowledge. Roof System secure
against Quantum, attackers, whereby secure, we means hearing the Clemson. When were Komodo We extend the existing Jerome technique. I don't care Maya to shut Nur to a larger class applications. Notably multi-round field Chamois, signatures bulletproof's and sequential order. And finally, we also show that the security reduction that we get from applying this technique or tight. Why are we so concerned General q q rum technique. I'll start by explaining the main motivating example, which is the motor and sealed Sharma transform.
Are there exit something called at 2 and plus one republic coin interactive proof system Wisconsin's or logarithmic number of rounds? Where are some proof her can prove its knowledge of the secret key to Avera Fire by sending a sequence of of messages just help with commitment is the car fire replies with a uniformly, random Challenge and approvals Etc, final response. But if we want to apply this particle in the signature skin, we needed to be non-interactive meaning that we want the proper to send all of these messages in one go. However, since it will no longer
receive these random challenges from the verifier. It will have to compute them himself and it does sell by taking to hatch of each of these commitments. Using some public has function H Republic saw that also the firefighters access to it and can recompute the challenges and then check some verification predicate on these commitments, the response and the Genesis produced by a h. Now, to prove security or more precisely to show that this morning to write the scheme is as secure as the interactive one. We turn to the quantum, realm to
work tomorrow where we muddle this public has function. HSM external random Oracle to its old parties, have quantum, theory axis. And which means that's the function. Cannot be completed local. He's so any adversary in this article will have to make your Aquarius to soda to the external Oracle, but they can consist of a Quantum superposition of inputs. So if that's very, makes it very well, then text me. Since it sent over a Quantum states to the oracle. Now in many also classical random Oracle model proves. What we
want to do is show the existence of some simulator s that can simulate the Oracle to a. And also observe that clearly said, it makes a, but I guess you might be aware. And observing the quantum state may cause it to collapse, which in turn can influence the nation of the adversary soda. In general, we can no longer predict what the adversaries got two outfits, which is a shame, because the simulator might need this outfit in the security reduction. But then comes our results on the multi input, three program, ability of Sakura
if we have such a scenario where some at the dairy makes Q quantum theories, to a random Oracle before out, putting an air, a consisting of a difference, a simple sex, as well as some additional Equity a substance arbitrary. Predicate, she holds off CBS access and the corresponding house values. Then indeed, there exists, a simulator that can choose end of this very sad random measure them. And upon the hatching boots, found in the measurements reprogram, the Oracle to some fast running playlist, eater Stihl produce, some
outfits, Annex Bar, C bar of Weights the same product, she hopes up but not with respect to the fresh random values Tita. And we can relate these probabilities for any particular choice of fashion boots Xbox. Up to this loss of order, two to the power to end. And that is exactly what we need to show that the advantage of the best accessory against the PF Chang returns from non-interactive scheme, is at my house or the truth to the power to end times as big as the advantage of the best adversary against the interactive team, which is
what we needed for security. Thank you. Okay, great. Thanks. And I think we have, we have time for a couple questions. Are there any questions from the audience? Good night. I have a question after you sold your bum this cue to the 2 to the end, is that tight? Yes. Yeah, we shall go abroad for Mesa, Tech against the three rounds teams showing that the scrap place in that case. And it's this holes for pretty General typical Sigma particles or artificial multi-round schemes by sequentially repeating these
particles. And then we saw an attack against that scheme which which kind of adversary by 2 to the power to end. Okay, so dumb in general, the reduction is but there are also questions in the chat. First-year. Can you ask how big is an in your application cost at? Well, yeah, I mean, I guess for practical purposes. It should be constant or logarithmic to do not blow up the, the last two months, but if it works for General, and And then ask how important is it that H is uniform over the bullion Cube. For example, what is HSM structure? Well, yeah, or approve.
Only works for uniform 8. I'm not I'm not entirely sure if it's if there isn't some some way to make it work in the other case, with our proof works on before uniform makes OK. Google,. How does it compare to a genre tells technique for Fiat Shamir? Well Sandra take me to Phoenicia referring to the 2019 paper that has a loss of order. Cute to the nines versus acute to the hour to in the nursery rhyme case of any extension of that technique to do multiple rounds. Thank you. Okay, that's and thanks a lot for the. I can't talk enough sense for the
other night questions and we can talk further question to the zoo live cat. And okay, we're going to move on to the next one. So, I will next time, we'll be finishing, M for repeated score with applications to pee pad, harness and videos by Alex Lombardi. And when our next Senator and I think Alex is going to give the top. Alex, yes. Sorry. One second. I need to screen. Share. Sorry. No problem. The owner, remind everybody, please type your questions included and also, you should I consume as well. It's a little bit quiet in the toilet.
Okay. Can you see? Okay, sorry about that everything. In case you want us to see the going to be, alright, the 40s short talk. I'll explain to you. What exactly we prove and I can refer you to the paper Ani friends or a longer version of the sock on YouTube for more details. So are transformed is a heuristic mechanism that we just heard about actually for converting public wine interactive protocols for some tasks into a corresponding non-interactive protocol for the same task. And I know you all just heard this, that's the way it's
done. Is you you take an interactive protocol where the verifiers message. So uniformly random and you replace the interaction with the computation of a hash function, so and then on the corresponding non-interactive protocol, the approver iteratively compute, its messages as it would in the interactive protocol, but computes the verifier messages itself as ashes of the protocol transcript up until that point. So this is a, at least a candidate way to get a non-interactive protocol. It's been around and cryptography for over 30 years by now. It's quite ridiculous. What was that
originally was that at least you're aesthetically it appears that the soundness of the protocol is preserved by the transformation and turns what we can prove at least classically we can show What sound this? Hold in the random Oracle model and very high generality. So, for essentially, any protocol you would care about if you model the hash function is a random Oracle, then you can show that the Emir protocol is sound, but if you want to argue sounds in the standard model that is with a hat with a concrete, hash function that you can compute as a Post-It clearing as an Oracle and very
little was known as it's a big open question in theoretical cryptography to figure out which interactive protocols. We can actually instantiate the extra mirror for in the standard model and what cryptographic hash function need to make to prove the soundness of the protocol. So up until a few years ago, essentially no positive results were known about this, but recently we've finally been able to show that at least in some special cases that that you can do CS mirror in the standard model. So let me explain the state of the Arts as of this paper, so
First of all, we're going to assume that the interactive protocol is statistically sound. That is it sound against computationally unbounded, provers. This is a fairly large restriction, but subject to this restriction, it's it's known that if you make a strong enough assumption about the hash function, then she asking me or for any such protocol. At least it's if you say restricted constant rounds or not, you'll get sadness. Unfortunately. The assumption is incredibly strong like very non-standard and you would not want to be caught making such an assumption but but it's
from a theoretical perspective. It's a it's a nice feasibility, results, more recently. We were able to show that's a for a very specific class of interactive from systems. You can do you can have a compiler under a standard cryptographic more recently. It's been shown that you can do it under the learning with a resumption. And then finally, I want to say cuz the relevance to this work that's for a certain intermediate class of interactive proof systems not all of them, but the but more than the smaller class, we know how to do CS Shamir under a strong,
but a strong assumption with that is not quite as strong as required for the general purpose results. So I'm playing this out because the song track protocol, which is quite important, isn't, is in this class, but we don't know how to compile it under or we did not know how to compile it. Under standard colors, are graphic assumption, as of this work. So as you can see, from from this state of the Arts, there is no succinct interactive proof system that we could probably instantiate the extra mirror for your standard assumption. This was an interesting open problem. So in this
work, we're going to stare at a particular two sinks interactive proof system and do c h, e m e r 4, it's under a reasonable assumption. So the computational problem underlying the protocol is the repeated squaring problem. So you have some are a same like it was in a group element g&z OnStar and you want to get rid of flea computer, you want to compute the results of an iterated, squaring of G, done many times. So you want to come to the team on end for some large value. See it's believed that this problem is hard mainly to take about time. T even
sequentially. And there are important cryptographic objects, like time-lock Puzzles based on such an assumption. So more than more than this, just being that interesting conversational problem. There's a nice succinct interactive true system for this computation. I was introduced by Peters a couple of years ago, very quickly, the way it the way it essentially works is the approver is repeatedly forced to send some halfway point of the computation is supposed to be doing and then the verifier computer random to do one cell production of two subproblems. 28 lights to
reduce the entire problem to a statement of size half of the original statement. By, by doing this recursively many times you can you get a succinct interactive proof system for this language. So you can at least you're a sickly applies, yet Shamir to this protocol and you can get sound in the random Oracle model. What that means again is replacing these verifier random challenges with hashes of the problem statement than the approver messages. But our question is whether you can do this in the standard model and we show that under a reasonable assumption, you can.
So here are results. If the learning with errors problem is sub exponentially hard for a large subject spent like a, it's not a tattoo to the ends of the Epsilon type of something about you to the ends of the 1 - Epsilon Zai presumption. Then we can do few extra mirror for this protocol with verification time to the ends of the Epsilon, some small sub exponential verification time, just for reference. This is way less. The amount of time, it takes to decide the language. So, this is our main results. We can get smaller verification Time by making a stronger
lwv, assumption and all of the assumptions we make for all of these results, follow from, from hardness of some worst-case, lattice problem, even, even the assumption that that gives you probably don't need like native polynomial time verification. So that I think of the first results as the as the main one in the second and the later two are just getting different quantity of trade-offs. So this is our name results and we immediately get to cool applications because you mean CSM here for this particular protocol gives nice and has my supplications. So, one thing that we
get is hardness in the complexity pee pad, which capture is the hardness of computing, Nash equilibrium Game Theory so we can show that if the repeated squaring problem is some extent really hard and lwe is sub exponentially hard for this larger size of exponential, then we get hardness and Pete, that results with different trade-offs, based on the other two results from the previous slide. We also gets standard model verifiable delay functions with subject. Credential evaluation time based on this based on assumptions. And Elevation of time evaluation
time based on the stronger Assumption, of course requires, assuming sequential hardness of repeated squaring so that you get a guaranteed DeLay. So what I like about these results is that we're making strong but sub exponential assumptions about well, study problems. And as a result, we get a succinct non-interactive argument for a non-trivial language that has these cool applications. So I just the word on related work in terms of verifiable delay functions. There isn't really there wasn't really anything known in the standard model based on standard cryptographic assumptions.
Before for Peapod, hardness be at. We have we have a few Works. They're not based on standard assumptions, but they're they're worth worth mentioning. So we were able to get pee pad hard as previously based on office kitchen as well as based on the soundness of the extra mirror. For both the subject protocol and the squaring protocol, but these before, we did not have an instantiation for the Siesta. Their hash function based on a standard assumption. And then finally, concurrently to this work, Clive hunt them, Yankees, a different construction of a pee pad hard in based on
a falsifiable function of bile in your mouth. That does not go through Seattle. And you'll hear about this from Lisa and the next talk, So I, of course, I don't really have time to explain much about our techniques. But let me give a click BTW one sentence explanation of what we do. We we do homework Vic index calculus. Meaning that in our security proof. We actually have Al you ate an index calculus. I'll grab a discrete logs under the, under a homework, encryption see? If that sounds ridiculous. It is but see the paper or the longer talk for more details, so I want to say thank you.
Thanks, Alex. I think I'm going to take a quick question. Is there any? Canary, let me ask one. So for the keypad harness. Is there any help to reduce its going to remove one of the two assumptions? Cuz right now you have both. I mean if you're doing see extra mirror for a squaring protocol, then you need to assume that the underlying language is hard to it. Like that. Like that like getting a succinct Arguments for a language is not interesting at the languages that sells easy. So if there's something there
some follow-up work actually that appeared on he print a few weeks ago, thats that manages to instantiate CS Premier for some check and and this gets rid of the squaring assumption and also weakens the lwa Assumption. So I'm sure we'll be the community will be hearing about this more in the future. All right. Thanks. I was gonna think we can move on to the next one. Till our next talk will be also about Peapod harness, its status updates while this person Peep and harness by a Nissan Altima and a penis. And I think Lisa will be given the top.
So these are the floor's yours. Thank you. Me. Can you also give us for the introduction until our work is about delegations games and their application to keypad hardness? Joanna delegations game, are you typically have a week machines at does? A smartwatch that wants to learn the outcome of a costly computation? A so, he asked a more powerful machines, it just the cloud to perform the computation and to send back a proof and the verifier will just check the proof in much less time than it would take to perform the original computation. And so the question
underlined delegation is Tony actually construct. Protocols. We're verifying is faster than Computing. So our Focus will be on staying in the standard model and relying on falsifiable assumptions. And so, and in this model, the only things we had our for delegating computations up until very recently had wear what we called privately verifiable where the verifier needs access to some secret trapdoor information in order to check the proof. And what would really like is to have what we call publicly verifiable delegation,
where the statement and proof can just be attacked by anyone without needing trapped one for me and the primary motivation for publicly verifiable delegation. Is there a very essential to decentralize Applications? It is cryptocurrencies in blockchain where you really want anyone to be able to verify these public groups. So the part works on probably verify with delegation up until last year. And this year. I relied on strong assumptions and last year, the most like
so. So that the only probably verifiable delegation steam offer General Pineville mealtime. Computations on is our previous work. Construction scheme based on violin your group assumption. And what we doing this work is we do tap on the ski. To make its Crucible, fop dateable. And unambiguous both based on this same assumption. So the first notion that we achieve is updatable proofs, and this notion introduced by Balian considers a long computation that carried out over many separate operations and the ideas that has a
competition progresses. You have approved for the computation perform so far, and as someone performs the next block of the computation update the proof. And this new proof completely replace his old proof. It proves that like all, like, all the competition that's been performed up to this point. And what we want an update about Bruce's, for this update procedure to be efficient. And what we also want is for the proof to remain 6th. So the proof shouldn't grow with the the number of updates. And the idea is that in, like a centralized applications. You may have a
long computation carried out through many different objects and you want the proof and Find a proof to still remain efficient. So, we just met, we only had updatable proofs based on Stars which are only based on strong assumptions. And as I said, we got a dateable proofs based on falsifiable bile in your assumption. So the second property we also get is the notion of unambiguous proof, which says that any prouver cannot produce two different accepting. Proofs for the same statement except with negligible probability and the primary
motivation for an ambiguous proofs is their application to pee pad harness. So formally are result is Public Library, delegation with updatable and unambiguous proof based on this bile in your group, assumption or which in which the adversary has given a three by Alpha Matrix of group elements or logarithmic Alpha. And it's hard to distinguish whether the specific elements. He is a higher power of s or an independent random element and this assumption we believe is new,
but it's somewhere in spirit to you know, the wide range of a song by Lenore Cooper sanctions made throughout crypto, and it holds in the generic group model. And so we use this delegation schema to show Peapod. Hardness following the blueprint of Tandoori as hell. And so what we obtain is Peapod harness just based on the quality polynomial, hardness of this assumption and the song and any hard language else. So if you're willing to assume non-uniform HGH, then this gives you a hard language, LOL. That's if I say,
So I as Alex also mentioned on showing Peapod harness and it has been an important problem and up until recently, the only had it based on strong assumptions or the assumption that she in, your is heuristically secure and only only recently, did we have a pattern is based on the lgbtq Assumption and you can do these, current works, as essentially constructing, a delegation scheme, but only for a particular language such as the repeated skrine language. And so on our workout, we we kind of went
the other way. We are constructing the delegations games for for any language and then you got to go pee pad harness. So I in summary of our results are a souped-up delegations game, based on a falsifiable assumption and pee pad harness are also based on this is function. And I'll just stay in in a nutshell. How we get our results is, we actually changes update ability and unimaginative properties without relying on strong assumptions by using the power of what we call local proofs and in non-deterministic delegation. So essentially these
two properties can be obtained by relying on strong assumptions for for non-deterministic delegation, but we can relax that assumption significantly. If we essentially use, if you sent to use local proofs, which means that we use a single proof to do many separate extraction on. And we piece together. These extractions by showing that they're consistent. And this is what kind of internet show how we get update ability, and unambiguously, and also keep a harness under our assumption. And
the full version of our work will be up soon. But in the meantime, I feel free to refer to the proceedings or emails. Okay. Thank you. And we have time to explore questions. Let me, let me start with one when the hard time peeing in their question,. Is there any real work motivation or application for the NBA's proves? Yeah, so this is actually a question. We have is well because the only motivation we had four, it was to get pee pad harness. So we don't know of any any applications, but it seems like a very interesting property that you kind of had like this canonical proof
on. So we be happy to you. No talk with anyone that wants to discuss it further. Close by there. Other questions. Well, I don't see any from the zoom chat. Is it a Peter? Beth Patrick, I'm curious. If I want to pick up Peapod, harness from a Samsung will be a good. I was a little bit. That's why all the references. So I think yeah. The thing I'm in Allison. I probably both would have liked to talk a little bit about the reduction from liking the delegation seems to pee pad harness cuz it's very
interesting. Follows. The blueprints that transformation is folklore, but probably first written in the in the area that sell paper. I think our proceedings also has a a a general proof from delegation to to pee pad hardness. So I think that's where I would go to understand how crypto can be, can be connected to pee pad. is there enough for the Questions. Let's move on to the next one. So every next time will be new techniques for their knowledge by myself
belts on that document solid and we'll cook carne and I believe Marcel would be given to talk or so. As far as yours. Are you there? We can see your shirt size, but we couldn't hear you. Can you let me know about that old techniques, but new 20 knowledge mrs. With Donald Duck and cool. Cool, Kearney witness indistinguishability. I'm not going to go into detail about what these Notions are, hopefully earlier so you can see my other work, but we're particularly interested in zero knowledge, protocols and witness and contraction is very limited. So the ideally the approval, it's just
sending a single message to Bear fire. We're interested in the setting where you have very limited set up at most a uniform, random, stranger and ideally, in the plane model, no CRS whatsoever. And we are also interested in such protocols. That are very expensive. So they hold for all of a even a.m. And sort of our perspective. In this work is ruber complexity for and by doing so minimize distractions necessary to achieve these Notions of Journal. Do we consider a sort of to settings where
the prouver is much stronger? A mutation lead in the verifier. So one is sort of this traditional setting where you have a poly time verifier and Gruber is running in super polynomial time. I will also consider a new setting, the Wii introduced call because buying brains or knowledge, or fine grain witness in to see where the proofer is probably time, but the verifier is actually in a much weaker. So here and see one log, that's a circuit. So, but very fast parallel competition. And what exactly do we mean by
fighting rainbow zero? Knowledge will in the same way that we understand your knowledge in the traditional setting where we should be able to stimulate interaction with an adversarial Polly behind bear, fire in polynomial. Time in fine-grained setting. We want to stimulate the interaction with an adversarial, nc-1, verifier, in, and see one. Okay, and so, in this business, with our perspective, distorted for some new challenges, and obstacles are in there and
just very briefly what happened. So imagine we want to have a witness instinctual proof system. And we want to prove something about composability want to switch from Witnesses, 12 witnesses, to. We have an adversarial verifier. It's interacting with these two provers. So typically what we would do right is we would show a hybrid argument we would first which the first witness on the left and then switch the brightness on the right and this is Sean, be a reduction write. The reductions efficient production is going to run the verifier in the proofer on the witness,
and then we'll use this to brakes witness indistinguishability of the proof system on the last year. The problem is inefficient proper setting. Obviously is this production can't actually run approver. And so for composition this isn't too big of an issue, but we are interested in constructing we're looking at this construction of zaps Witcher 2 round with it since they were approved from music and this becomes a serious problem and solution is repurposing of an
old idea. Dude. We're trying to be randomized based on hard on average, problems and use the common tutorial designs that they introduced. And I advise you to sort of look at my longer form talk, where it's a pretty cute idea and we believe it will have other applications. I just a sort of Sunrise and hear what are results. So in the traditional setting, I'm not going to tell you what, all of these acronyms are here. But the Highlight is just sending. We shows apps from one way from your patients in a fish improvers. And prior to this. We only news
apps. These two groups from chapter permutations. So it's from cryptomania, South options. So we get down too many in the fine print setting we show up and see one from this worst-case, heart does not contain log space or actually sort of the strengthening of this. Accident and thanks Marshal. As you can see from the zoom cat. They're explicitly many presents for your nice flight to be the first person to be. How did you get my text? Alex Keynotes, I just drunk enough. Thank you.
They are there more serious question. I fell one from Gillette. So this is from your head. It's an say, one more interesting because of Prior work on any other intern secularism. Yeah, it's interesting. I guess, because we have a lot of tools there, like the whole cycle szalavitz framework for doing things. That's why we look at it. I think other fine-grained Virginians would be very interesting. But yeah, Beyond and see when we don't have a lot of tools.
Okay. Are there any other questions? Okay. If not, we can run to the last stop of the Muhammad, have the last stock of the situation interactive process for social grass or urine, cats are Clara and a loan. You a gift? And a loan is going to give the talk. I think you're with me, just the screen and minimize. Yeah, okay, so can you guys see it? Everything, good. So thank you. So, please stop use them and it's not that it's only that they could have taken to use them. They really become like this new and modern approach to study Society in in
human relationship. There are many commercial companies, private companies, Facebook, Twitter stock, but you could also think about the PNP or even search engines can be modeled as a social club. A.m. Something is both important is the health of a social life. There's different measures, concerning the help. These companies publish reports concerning the help of the Gods. Let's focus on one main measure, which is a size of the graph. Okay, the number of nodes in the number of active, use that, for example, Facebook acquire WhatsApp, Felicia, steep price of
16 billion dollars, and it was calculated by a $40 activation fee Museum. So, the size of the Gap has to be a big issue and you can see about the Facebook report saying that they have 1.73 billion + 2.6 billion. And these reports might be potentially amendable by Financial or political incentives. Okay, they have some incentive to report false numbers. And so should, we toss these reports? Can we talk inside and to have an independent estimates of these measures and the main challenges that the
glasses, huge? Okay, but not only that it shows that it's how competent shuttle problem, but they asked us to this stuff is limited. Okay, we do not have access to the phone Facebook or Twitter Network. Instead what we have, we have access to a public API. Okay, we have a public access usually contains two types of Aquarius. Well, if you give an ID to give some idea from some very loud as possible universes, and then you can verify that this idea exists and you should you get
user profiles to get some metal. About this this. I did it snow. So perhaps their the name, the age, and so on, and second, you have a neighborhood. So, again, you you given I did and you get the list of Naval of this node in the graph over. This list is possibly you give a ID and I need I am so very, very brief. Interphase. Okay, without relying on Facebook. All the companies together, independent estimates of the size of the class. And example. Yeah, I thought they needed
constant help for the smaller smaller than one. So somebody, you know, how many queries to estimate the size of the car. So, this is Stella. Can we estimate a social using these? So let's say party, Logan while still having noticed and in the gospel Bible, And the answer to this is to introduced interactive posts on social. So this is the model. We have a very far, we have approval, okay, and stand up and octopus. The instance that we're talking about is the graph. The very file doesn't have complete access to the glass. So this is very
similar to interacting proof of proximity. Okay. He has only occurred access to the input, but instead of just leaving their special powers doesn't put the access to a membership to our queries. The one is mentorship. Okay, I can see if I exist in the second is Alexis. You are random walk in the Gulf. Okay, so you can take an idea, select a random neighbor, and then visit this I know that's the one you can pump the phone event. And let me already say something to send them about Elmo. So we assume hear
that the glasses fixed. So, the only could answer it to The Godfather and you can ask, why is that like, if Facebook is the timing and supposed to be? So again, you know, they might as well live. So does a few answers for bath, but it's very hard to distinguish. Honest users from this data file. Okay, cuz it just seems like a police and second. It says that if they want to lie in there in the reports, they must materialise this lie physical into the network. Okay, so the both of them to walk a lot.
So what is a main result? So given address on envelope. It says. And with mixing time tell. Okay, so I can mixing time is the number of steps you need to do in the path until you reach the stationary distribution and Evans degree. That doesn't just happen to give the dog. We construct a double Ephesians directed pool in the social graph for estimating, the size of the door. Okay. Well you give me a female Chanel Epsilon and we verified that the size that they claim, this is smallest 1 + - Epsilon
at times. And so you just have some small fraction of loksat less than 1% at all. It's a two messages protocol at the Publican photo call. The number of queries that the verifier performs is only one of them, Epsilon squared, x tile time. Delta usually in Social gaffes, and this is why I called social dogs. The cow is not allowed these dogs out when mixed and then type is not loud and Epsilon you can think of it as Samsung constant. So this is really
funny login. A and the pool running time. So he said he's doubly efficient approval on in X also small. So it's quasilinear in the Netflix eyes. So this is something really efficient that can be implemented by The Social Network companies. And so just a few applications of all main result so you can estimate the size of the of the glass but you can also estimate the size of Starbucks. Do you want to see me time when you use those between the a, a 10 and 20 of them Facebook condition on that? You
can get this information about every user? Okay, nice profile. Then you can just look at the sub dolphin estimate. How many users in the sack of you can get other things like that? They doing distribution, other have never called the local local coffee shops in Moore. And in general, we have something for any function, f, you can get the media and other side of the values, fv12 FDNY notes. And just one final application is that you can use fear to me to transform this article to be. No
need to ask him. When you get an argument. Of course. This argument can be published once and for all and be verified by any user in the network using a few queries. So if you go back to this lippo, then they say they have 1.73 million daily active users, and he didn't read the can just add the proof for this fact. And again, you have some LOL less than 1% and the hope is that maybe this could be part of some next-generation regulation that we have for privacy of data. Specifically Photoshop cost.
So we've been introduced our notion of interactive. We provided for monitoring the help from social dogs. Some open problem is aluminum eliminating this dependency on Delta. I don't think it's necessary as opposed to the detect dependency. On top. Of course, we can talk about other except the ones that I mentioned and maybe push this. And up in regulation. And there cuz I don't have time to talk about the both but I'm happy to do that if you have questions offline,
thank you. So there is one question poster to select for the start by Cody says do the mixing time tall and average degree does water need to be known into to the Portico. Yeah, that's an excellent question. So you don't need to know the exactly the mixing time and the average degree. You do need to have some apple bombs on them. Is there any other questions? What are you doing? We are kind of overtime. But if there's another question for for the stock, if you can take it before thanking, everybody. So if you actually remembered any questions, you can post it to the lip. So
this was already done for one of the talks to a question, some of the questions for this all came after the talk was over so you can check the answers also in the same threat. And if you had any other questions or comments, you can ask it, you can add it to that threat. You are a little bit over time. So you won't have any money at the end of the session or they wanted to thank every speaker all the contributors and all the attendees of this section. And we're going to have the highest ER meeting in about 15 minutes. So with that in mind,
Buy this talk
Buy this video
Our other topics
With ConferenceCast.tv, you get access to our library of the world's best conference talks.