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-20: NIZKs, Consensus, Delay Functions
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Add to favorites
281
I like 0
I dislike 0
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
  • Description
  • Transcript
  • Discussion

About the talk

About speaker

Srinath Setty
Principal Researcher at Microsoft Research
Share

Can I already start? Very safe. Okay. So how everybody, welcome to the new in here, Chris Talk Amongst it. If I thought that they having the session start to Spartan efficient and general purpose, zero. It starts, without the trust, set up a speaker is this city will have five minutes to speak and then we'll have 5 minutes for discussion why we set up for the next door. So you can thank you. Just talkin about a new family of the week is not switch recall Spartan.

Is it just not as an argument of knowledge meaning, but it's a protocol between a bluebird and a grease fire. Gypsy the proper wants to prove the knowledge of a witness to do such that the X-Files. It's not intractable. Finally. It's accent. Lanier in the size of the s. S n e r in the size of the subject. How many approaches to belvita, snacks in the literature. Starting with the works of killing a McCauley, a breakthrough result. And decision was provided by the work of

gdpr constant? Unfortunately, a major downside that the scheme is that it requires a person to trust, text it up. The problem as motivated, another classic Works, call ZJ snacks without rustic setup and support but not both. Example, high tech support effects in 25, but it requires a certain stability year did a parallel circuits. Stock support effects in verify, but it requires that gets to be a sequence of repeated substitutes. On the other side, we have ligero, Aurora and bulletproof at Target on

linear time verification cost. In contrast are working simultaneously, support our participants and it sucks and dry fire. Stone. Sour candy challenge thing because by definition have no structure. Go to the mall to buy fire must actually know what statements by fine. What this means is that verification must be at least linear in the size of the circuit. I can get around this problem by pre-processing sisters, but without using any secret trapdoor station compliment. Creating a competition

commitment. Requires time. That's at least linear in the size of the soccer, but it's reusable. The next one minute. So I'm going to provide an overview of how Spartanburg. So the foundation of Spartan is the subject protocol which is an intractable system for proving that a polynomial with Target by you or somebody else hypercube. He's interested in proving the sex viability of sectors in the paper. Be provided reduction from Marvin Sease instances to stantec instances. Where are Nancy's generalizes?

It's been designed a set of techniques in conjunction with existing compilers to transform to something protocol into an unattractive. Zero-knowledge proof system for h, a r m and the description of the second attempt at just a baby. See. But because there's been a fire reached the description of a second. The cost of the verified is a kiessling are in the circuit size. So we design competition commitment. We combined this compilation commitment with the system to get a zika is not wear. Instead of reading the description of the center, the prefatory,

the competition commitment. The cooler. In addition to producing indirect proof of steps for the proof of character violation of the competition commitment between the Northwest by gamma. What is the meaning of technical problem? Is that Booth encoder and approval required polynomial. Commitments game for sparse modeling are polygons? If you apply to existing schemes, the board game quarter, and the proper intercourse that occurred in the size of the subject. Show me designer jewelry company that can take an existing polynomial, commitments term for dense martiniere, polynomials

and then transform into a scheme for apartment linear polynomials. Be implemented the performance of Spartan and composite with existing schemes. There are three takeaways here, first patent office, the fastest route. Grand 16, which requires a trusted setup. If you focus on skills, that do not require trusted setup Spartan of the fastest and shortest a notification, but a synthetically and quantity. That I can take, oceans. Thank you very much. Julia is taking over with the

person. Yes, thanks for the talk. She have questions. Please make yourself noticed. You can raise her hand or just unmute yourself. And ask a question. Quick question for you. You should be stable under which assumptions do does. Your does your skin by those guarantees? Avatar made by Insurance required for the polynomial. Commitment required. I have another question. Actually, two questions. The first one is about the times. Is there a limitation that you reported it? Looking at the table

listening? Fantastic, me faster than other Solutions Psychotherapy. So the times that you reported for your profile, Sparta same as the orders of magnitude faster than all of the other groups. If you have an explanation of how could this possibly throw the traffic sucks. Traffic is much less than many of the existing scheme saw, but can they Difficulty with starts, even though it does the most primitive operation is very efficient to do a lot more of those operations, and it also requires reputations to consider. Also, if you count the internet,

cause it turns out, it was more work. Okay. Thank you. Thank you very much. Okay, so tell me. Do you want to share the spring? Thank you. Yeah, can you hear me now? Okay, so are our nest. Our next talk is titled needs from LPN and proper vehicle. Religion intractability for approximately relation to pay the matter where we go. Samsung phone. Okay, so to start so well, yeah, so what I'm going to talk about our paperwork, and since we know how to get my tractor, has a different

music on the Christmas decor 10 knowledge for a language & Beyond in Sandusky. So what is the function? Jenna. So we start with the same message, a public auction and someone pacifically instead of letting the verify and send his children to do the bacon challenge in the Boston business, and you don't want to find a message. Yes,, it's hard to find an input so that bad challenges. Do in order to draw the outline of a contribution. I'm actually going to start with. Work, show how to take

that enjoys that somehow morphism for a function. Plus, I need a function in the class is unique and inefficient class of snow. Are we getting? Indifferent. So it was, we do differently as we observe that. If we start with that brother, enjoy some very nice. And you supposed doctor, then we can get a week and we got the hard to find a Annex in having distance to consider the approximation of something. I was supposed to go based on a computer. And we showed that there with a promise of

an evaluation. I'm just means that the Coalition against relation to which doctor do we get music for the weekdays? Antonin Scalia says that it's hard to find some function of each other and like I said this week yet. And is it under a reason to believe that? And instead of a hummingbird? Okay, thanks text timer for the talk. I should have a few questions for you, but I'm going to let you all. Yes. By the way, if you have questions, if you want to ask later, it's also possible that you can.

Okay, so let me let me start, you mention, ipn. What's the? What's the noise that you need in order to? Icebreaker. Okay, so enjoy. Okay, so we can move it to the next. Talk. Thank you so much. Dominic, can you share the screen? Okay, so the next talk is titled, shortening directed Zero knowledge arguments is UPS or device language. Okay. Thanks for the introduction. And so it seemed to set up before about to let me briefly recap, it with Elizabeth wants to convince pop, off some statements, but does not want to reveal her secret.

And there are also like seeing my protocols as we see them before we exchanged multiple messages and these protocols, often really simple and well understood that have the disadvantage that I have to wait for the other person's messages and they are also known transferable. So in many cases, we require no inspector zero knowledge or else can simply send a single message, but then we require additional set up like a compression spring or the Run Mortal Mortal. And additionally, they often

competition be more expensive than interactive Cruise. So there's a bit of a tween between the two. So we're introducing a new way to build music, but let me first recap, some existing constructions, and why we need another one. So, we've seen in the last talked to get rid of transformation, which takes an interactive protocol and compiles it into a music, using the red and very efficient rules for how many languages. And if we stand around America, we can reduce everything to security of the underlined secret protocol

Oracle is a huge draw back because real hash functions in the art van mourik home. So we would like to avoid them if we can. Not a method for constructing music and can prove statements over. But I understand, but is way less efficient than then get some your boobs and a third line of work is so quiet. At this music's, which are also possible in this town that understanding assumptions. But only for the class of linear languages, which is a lot smaller than a 1/2 equations or even. So the question is can we find a proof system? We just as

easy and efficient, application your transformation, but secure in the standard model under substandard, assumption and has the full it up to sound is this paper? We could continue compiler for signal for the Colts to Netflix, which does not require any more clothes and security proof and works for algebra. Languages is almost as good as New transformation and also fully adapt a few sound as the downside that we require a new assumption which we call the extended Colonel Matrix, which is an extension of the tournament.

So how does a construction look, it's actually pretty simple. We started from a signal for the cold. So it's removed public line, interactive protocol and we won't remove the interaction. So if you message me from there and pecans use hash function, since then we would likely need one more coat again, so we want to give it as a reference string but count given the clear. So instead, we hide it in the exponent of a group, but not the same as the language, but in a second group, so we move to a group setting with a symmetric parents between G1 and G2. And hide in the exponent of

the second group. While the language Still Remains its first group across the second floor of uber has move to Gucci two as well, but similarly to the transformation Samus and zero knowledge directly. That's from the underlined Pro Taco Bell. Now, instead of actual we have pairings, which is why this is not as efficient as usual transformation expensive. Interesting. Questions are for Which languages does the extra work and why would this be sound? And for something is the intuition is that since the challenge is hidden in a different group and the statement, and the first blow, it should

be difficult to use it in any way to achieve the protocol and is also limits what language is we can prove statements about because inherently if we want to exploit that the challenge language on different groups, then of course our language counts and both parent groups are in the Target group. So something a parent product creation is quite unlikely until the best weekend translate you are a drag language is a lift over a single group. Answer, what can we do with this construction? We can actually construct or proof, for example,

for the th language, which, which is actually used in in many schemes and Currently ETA screws. In many Skins are the elements in 24 parents, while we only need 7 minutes and 12 parents across this concept of assuming our newest. And we also require witnessed a Bluetooth for the languages, which I said he don't have time to do just fine for the to have to look at the paper, but also approved also, shorter and faster than Grill Cypress. And some of the applications that I mentioned to offer

example, tightly secure structure, preserving signatures simulation sound for the new pixel ring signatures and many more. And since the priests often a big part of these protocols. We can save the significant space of time with our Construction. This relate to the music arguments at the title says we also guess this is to the left for languages and using deer animation techniques are also known as effective witness, indistinguishable cruise and also an unattractive hearing. All this proves flashback languages under the stomach, but those don't approve overgrow Cypress. So

nice to have a listing and if you wants to read the full version, it's any prints. And you can also watch the long talk and if you have any questions like that, thank you. Thank you very much for the talk. Thank you for the talk. Let's see if there are some questions. There's a question on Julia and Katie sarkar asks, what is the cost of obtaining proof of knowledge? Proof of knowledge is quite hard because or is it is unlikely to to get here because we basically talked about relations between

exponents and not between group elements. So we don't know how to cheat with our framework. There's a follow up on your question again by protect us whether you can use the knowledge of its options to get it. Maybe actually we didn't really think about that because I'll go was explicitly to avoid strong knowledge type of sanctions and get everything under falsifiable is a standard model. So basically, if we would use no trouble for me to sentience and the like we could do snacks,

and then construction itself would be kind of pointless cuz then we could get better efficiency as well. So, I believe we have a few more minutes. I think so we can maybe move to next week. Okay, so the next order fairness or B. I believe lawn has lost his connection. show me alone, please July 13th or the furnace for Byzantine conservatives and the speaker is it jumped work with the Samsung Galaxy S7 gold feather and they are Jews. So thank you for the introduction. Hi everyone. I'm OKC student at Cornell and

Cornell Tech. And today I'll be talked about order furnace for a Byzantine consensus in assistant work with other offers a colonel Tech. So briefly the abstraction of State machine. Replication or Byzantine consensus can be used to build a linearly ordered log or a blockade. And there is broadly two properties that can type of protocols me satisfy. The first is consistency, which ensures that all the notes have the same view of the other nearly ordered log. And the second is lightness, which ensures that the system makes progress. So, basically, the linearly ordered lock Rose. But

unfortunately, neither consistency nor live Nest says anything about the actual ordering of transactions in the log. So for example, of the consistency requirements can be met. Even if an adversarial notice able to choose the ordering for all of the transactions and as it turns out, the transaction ordering is often very easy to manipulate and existing protocols. So this brings us to the central question that we sort of an answer in our paper is like, why exactly is fair ordering. So important, I'll briefly highlight to main motivations, but please see our paper for the

full details. So the biggest motivator for order, furnace is seen in the context of essential exchanges and Shear results could actually be catastrophic without fail ordering. So, there was this recent paper by Phil, Diane and others at S&P 2020, which showed the rampant rise of box on the aetherium network, which waited to make profits from unsuspecting users, by manipulating the transaction with Ray. So, this is not unlike high-frequency trading on Wall Street, which was popularized by this best seller expose Flash Boys. So, this was a time when firms bill low. Latency

channels to the New York Stock Exchange, and capitalized on information. Asymmetry to seal small profits at a really large volume of transactions. And blocking exchanges aren't really as regulated as real world exchanges. So it's important to use cryptography to probably prevent Aura manipulation. So there's definitely a lot of practical motivation for the fairness and I'm really only scratching the surface here. But we think there's a strong theoretical motivation as well and I think for photographers that equally important, so order furnace, if it turns out is a natural analog of the

validity condition, the closest related problem of Byzantine agreement. So basically the validity property says that if all on the same value fee and all the honest note should output the same value V. So now you sleep what a fantastic intuitively is a property that if all honest notes or input and one before and two then all honest notes agreed output and one before him too. And again, this is not something that turned protocol satisfy. So we can serve several definitions of order fairness in our paper and it turns out some of the most natural ones are impossible to achieve. So here's

the definition we settled on which we call block, order fairness and this still maintains the sort of first and first aisle first, in first out style of ordering, but it is possible to achieve in practice. So here we allowed notes to deliver M1 and M2 in the same block and one judge and appear at a later index in the blockchain. So I'll also emphasize that we make minimal use of this relaxation. So our protocol will order M1 before em to accept, why can't you do an impossibly result. We also parameterize the definition, using an order furnace parameter.

So from a purely definitional standpoint, order fairness is strictly stronger than previously considered Notions like censorship resistance or using a random L election or using threshold encryption to hide the transaction contents before they're ordered. So finally, in our paper, we construct a first Fair ordering for the call Aqua-Tots, which we named after the Roman personification for fairness. So, very roughly, the protocol will take place in three. Stay, the gossip stage, the agreement states in the finalization stage and each of the

transactions will go through these three stages before being output to the log. So in the gossip stage, each node will gossip it all local ordering of transactions as it's received from the clients. In the agreement stage nodes will agree on who's local orderings to use to sequence a particular transaction. And the finalization stage knows we finalize the transaction ordering and output it to the blockchain. To the final Edition State requires no extra communication and all of the computation can be done locally. So intuitively. This is because all the data that's needed to compute.

The final ordering is agreed upon in the previous two stages. In terms of adversarial corruption threshold or sinkers protocol requires and greater than 2 F over to the MS. 170 easiest case of gamma equals one, we still require and honest majority and our protocols also work for completely asynchronous models, but we require and greater than 4/2 over 2 - 1 Another sort of interesting take away is our protocol technique. Actually serves the general compiler that can take any

standards and sense of protocol and transform it into one that also provides order Fitness. And this is because we only require week broadcast, an agreement, Primitives in a black box way, which can be realized from any existing inside. I'm so just some final thoughts are work is sort of the first to formalize order for an ass and provide pearl cost to realize it. And we think order fairness is a primitive is important for a lot of boxing application. I mentioned even fight exchanges briefly before we saying in general decentralized Finance

could benefit from Fair ordering and important for like initial coin offering for a few hours for chance to do. Fair investing. So this concludes my presentation. I have put my quarterly much rest as well as a link to the full paper. If you're interested. Thank you. Thank you very much. It might now. My sister has some questions. If you have questions, please, you can either write in the chat or a mute yourself. For those of you who are not here. So, let me start with one intuition about why the notion.

Don't get that. Damn big brothers. Could you repeat the question? Yeah, I was asking whether you could do some some intuition about what year property property case. Okay. So basically the it comes from other surprising connection to voting Theory specifically, the Condor say Paradox. So even this basically the situation, we're even if the individual preferences are transitive that you can still have a case where there's a cycle and ordering to the global preference becomes

non-sensitive. So this is why there is a possible result. But the key idea of why are block order fairness relaxation work since we can sort of shove these paradoxical orderings into the same block. I see. Thank you. Animal question to you. I don't see any other question. Neither here, nor in the woods. So, Okay, like a few more seconds and then move on. If you can start tearing. If anybody has questions about previous talks, will we might have something a few minutes at the end of the session? So feel free to ask if something good comes up.

Okay, so the next pay. Starting, generic you speeding up. Repeated square is equivalent to factory dresses for a generic being delayed function B. Radio. Okay, so well, thank you alone and said, I'm your aunt is going to be. So what is speaking at a function is a function in which is an additional delay for a charity function. So, what is it to care about delay functions is the discernment of fundamental building block, for two-bedroom house for the first generation of input output. The second notion. Is there a

local a functions or Rudy export short. These will formalize the couple of years ago by Winnetka and which allows for faster. If occasionally, possibly give Tucker fee, you can see it. But the main that take away message from these ladies that we weren't able to PDX. Okay, so perhaps the simplest example of a delay function function, a onto the input, is the output of the location of edge. One positive function used as a form of security argument so completely anyone can fairly easily approve unconditionally. That's

Computing. The function requires a t sequential calls to random Oracle. The downside of His function or whatever. He's that, it seems to lack the structure needed in order to enable extensions to that Apostles videos and with more structure. And this is where the pizza's going function, comes into the picture. And now it's not hard to see that. This is a new computer ball in time tee times for the security perimeter structure, for type A+. So which was first proposed

is the basis of candidates. How old is the Queen? Charlotte of dysfunctional are groups in which one cannot significantly speed up your complication. And without people seeing in private processors? So what's up, hard to see that the necessary condition for this assumption to Holden some group, is that this group is a group of an owner and the main candidates. We currently have been to Tober fee for such groups. We do have a second candidate which is the class groups of imaginary.

These are not as well, study cryptographically and also the Google Play Station. There seems to be a little bit of confunkshun did not enjoy a similar security. Ogc residential. Wendy's like a contribution to the following represent the Sharks to catch a threshold that apply for all functions within the generic captures the functions and mulch. And we come together. What we do is that we put forth a new notion of sequential give that the number of the sequential link operations required. In

order to compare the genetic link function of sickness can be genetically evaluated even with repossessed in California. No, we don't have the time to talk about the same notion are physical changes, that genetically speeding up and mentioned it. What is a Grizzly with a carpenter Foreman problems? So, why don't work the landscaping and fluke locations of this result is that. If you want to break this, you never know better than to try and do it in the quest, a foreboding similar results in the

extension. And the other question is, what about other candidates such as it's. So that's all. Thank you very much still. Georgia view, just connected. Nobody wants to ask question, ask a few questions. Okay, so one clarification, when you say that you 3% saying, do you mean? Did you results? Hold even if the adversary has access to the group description whenever is prepossessing. No, so we told him he's also generic. He doesn't have more than Right, I guess, I guess. I guess my question was, whether you can. The group has the

number one more question. Is that song occasion of time? Lock puzzles, security, that settings? What you're talking about running time? So, I'm not sure what you mean about. So, it depends how you measure time, right? So Do the online attacker can make up to the supercharger. Option is the up to the sequential but then the factory will inheritance this time. All right, if you want to break the deposit and then you need to run into some in time, which is less than whatever you sue about Factory.

I guess my question was about the parameter d, whether you can check it to be, for example. So I believe there's no other place. I guess we have a few minutes. So if someone has some questions about the previous talks, please speak up now. Yes, I do want to say that the defendant on the property. B, ocean be substantial. If you believe song. I'm stuck between a hard disk drive. Well, I guess so if you guys have any animal question. Active speakers, privacy. Thanks for sharing session with me.

Thanks everybody for participating in.

Cackle comments for the website

Buy this talk

Access to the talk “s-20: NIZKs, Consensus, Delay Functions”
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

Mohammad Mahmoody
associate professor in the Computer Science Department at University of Virginia (UVA)
+ 1 speaker
Kay McKelly
Freelance Software Developer & Virtual Event Organizer at The International Association for Cryptologic Research (IACR)
+ 1 speaker
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
Erica Blum
PhD student at University of Maryland
+ 2 speakers
Julian Loss
University of Maryland
+ 2 speakers
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-20: NIZKs, Consensus, Delay Functions”
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