Very much for the introduction and I actually wanted to begin by thanking the program committee and the program shows for the invitation It turns out. I actually did enjoy putting together the slides and thinking about what I wanted to say in this talk Though initially I do have to admit that I kind of dreaded You know giving this talk and I tried to decline sort of I don't know if you realize but anyway They didn't let me and why was I in part dreading this talk? Well part of the difficulty is exactly what Daniela talked about is deciding what to speak about and the program chairs gave me No help in that matter They said yeah, whatever you want to speak about is fine. Okay, great. So what's the first thing I thought about? to speak about is well my my initial thoughts turn to talking about secure multi-party computation and That's a really interesting topic and the problem with that is that I really didn't want to bore half the audience Usually if I if I can only bore about one third or one quarter of the audience. That's what I aim for So what I what I tried to think about is well, okay? The idea should be that what I should talk about is maybe some Connections between the theory of secure computation And something okay. Well, what should I connect the theory with well? That's kind of the obvious I should try to connect the theory of secure computation with all the recent work going on in on the practical side of secure computation and talk about the bridges that are being built between these two communities and This is a great topic to talk about actually in general the intersection or the interplay between theory and practicing cryptography is a great topic to talk about if I do say so myself and The problem with this is that many other people have realized this and many other people have talked about this before and in particular I went back and took a look at the previous invited talks at crypto your crypt and Asia crypt Just to get a sense of what people spoke about and many many people Have spoken about theory in practice and different guys is and I this is my own My own opinion about whether the talk was theory in practice. Some people in the list may disagree And in particular in 2017 and Nigel smart talked about secure computation theory in practice So okay. Well, that gives me a little bit of pause. I should come up with something else so I Yeah, and I could just agree with everything he said and and I Don't think he's here actually which is too bad. I thought he might enjoy this talk But anyway, I Could agree with everything you said and then end in five minutes I will add a few thoughts of my own But okay, I better come up with something else. So what I decided to talk about instead actually are some some recent work connecting theory and practice of secure computation with something that I hope will be of interest to other people in the audience Namely a symmetric key crypto and crypt analysis And we'll see how actually these communities that are usually thought of as being relatively far apart and I think unfortunately so Really, there are some nice connections between the two of them Let me just step back a little bit and spend maybe five minutes talking about theory and practice I should start maybe by giving my biases, right? So I started out while I started out. I guess as a chemist. So thanks for reminding everybody my my but my roots as a as a PhD Cryptographer are in the theory community and what I found I guess over time and maybe many of us have this feeling is that Gradually over my career. I became jealous of practitioners. They seem to have a lot of the fun Not all the fun, but they seem to have a lot of the fun and you know the standard Kind of joke right is that practitioners consider me a theorist and and basically theorists consider me a sellout And and and unfortunately nobody considers me a practitioner, but that's okay But but let's actually define terms a little bit actually may hear Bellari gave a really nice talk here at crypto in 2014 Also talking about among other things Theory and practice from his point of view and he actually had a nice taxonomy of what exactly it means for something to Be practical and he gave basically for criteria that you can use perhaps to evaluate whether some technology was practical or not And he didn't actually order them. He actually claimed that there was a connect You know, they were not strictly ordered, but but in any event I put them in this order You can you can talk about whether something can be implemented. You can talk about whether that implementation is efficient And maybe that's the theorist point of view of what practice means You can also ask whether a given technology is worth money to somebody will somebody pay for it Will somebody pay to implement it and of course whether or not it has utility I would add to this list a little bit You can also ask whether things are either Standardized or perhaps in the process of being standardized or being thought about as being standardized That is a useful indication of whether or not people believe that something has practical utility And then of course you can you can also ask whether something is actually used, right? It's interesting because I think there are examples of things that are used that have no utility and the things that have utility but are not so it's not the case that they that they're equivalent and You know if this were maybe a different kind of talk I would focus on the fact that nowadays secure computation is Worth money because you can look at different companies and and funding agencies who are investing in this technology And I would claim that it also has utility and there are actually examples here of people using this for various things in the real world Even though it hasn't yet seen widespread deployment, but for the purposes of this talk I'm going to be focusing more on Implementations and the efficiency of those implementations As far as defining theory It turns out it's actually not quite clear how to define it You can think perhaps about defining theory in terms of definitions and proofs, but I think actually to the theory community's credit You know that focus on definitions and proofs might have been enough to characterize theory in the 80s and the early 90s But by now they've really permeated much of crypto You can talk about reliance on mathematical techniques But that also really characterizes most of the work that cryptographers that everybody in this room does and so it doesn't really quite pin down What exactly separates theory from more practical aspects of cryptography? I found this actually in the manifesto of TCC I read how do they define themselves as the theory community and what they say there among other things I distilled it to these two is that they focus on the study of paradigms and techniques and formulating new problems Or ultimately you can take this as basically working on problems without caring whether or not they're practical Which which is not necessarily a negative Because what one thing I have found is really there's been an amazing It's amazing to me how actually effective Theory has been for practice really perhaps unreasonably so and and I you know consider myself A cynic in this regard. I you know sometimes I see work and I think oh You know that has no hope of ever being practical why are people working on that problem? But time and again, I've been proven wrong and I think secure computation is a great example of this The early work in the 80s and the 90s Building these protocols showing feasibility results building up definitions and foundations and now we see this transitioning into practice But there are many other examples actually and I'll just list a couple and I'll and I'll mention the first one in particular The first one I think is a fantastic example, right? You have these Verifiable random functions also known as unique signatures that were introduced in 1999 You know, it's a wonderful idea, but it doesn't seem to have any you know potential practical use and now you see What is it 20 years later roughly? You see that these are a fundamental building block for proof-of-stake blockchain protocols. It's really unbelievable, right? I mean who would have thought that you would come around and have this kind of an application But I want to also highlight the other side which I think many of us in the theory community often disregard is that the the practice or the deployment or the usage of different technologies Can also be interesting from a theoretical point of view because it can raise all sorts of interesting theoretical questions and In this talk in particular, I'm going to focus on two questions that arose from looking more carefully at Implementations and and deployments I guess of a secure computation Looking first of all at how hash functions can be are implemented or how they're instantiated in existing MPC implementations and how they should be instantiated in implementations And also looking at the concrete security of secure computation and that actually connects to the first bullet Because that turns out to be dependent on how exactly the hash functions are instantiated and Both of these results that I'm going to talk about Really rely on insights from the symmetric key world and this is a connection to symmetric key cryptography that I talked about couple of slides ago and and you know, I felt it particularly apropos here to include a quote from Nigel from his talk here He said it as part of his talk that you should always pay attention to all talks And I think this is great advice actually, right? It's because you never know when the next idea or where the next idea will come from If you stay isolated and only attend one kind of talk You're missing out on ideas from other from other people other communities that can potentially be beneficial to you So I think it's useful good advice So I wanted to give a little bit of MPC background I don't know actually well, I don't expect that that most of the audience Are experts in secure computation and I wanted to give kind of enough information That first of all you would get something out of the talk and second of all you'll be able to follow the second half of the talk So I'm going to talk about secure two-party computation in particular. It's just cleaner and it's a It's much easier to explain For one thing and it'll and it kind of is enough to describe all the results. I'm going to tell you about So in the setting of secure two-party computation, we have two parties With inputs x and y and they want to jointly compute some function f Of their of their mutual inputs They want to compute the result f x y and they would like to do this while maintaining various security properties, right? The one we think about The most is privacy right that they should be able to get the result f x y without either side revealing their input to the other side And also they may be concerned about other properties for example correctness Ie knowing that the result they compute corresponds to some valid input of each of the parties You can consider both the semi-honest setting and the malicious setting in the semi-honest setting The idea is that both parties are running the protocol as prescribed and they're only potentially trying to learn Disallowed information from the protocol execution and in the malicious setting the parties can behave or the or the corrupted party Rather can behave arbitrarily and I'm going to focus most of the time in this talk on the on the semi-honest setting It turns out that that a semi-honest two-party computation I think is at this point relatively simple to describe I've described this in in like an hour well something like this in an hour-long talk to undergraduates I can't you know claim to know how much they understood but but I think you can it's nice and encapsulated now It relies essentially on two primitives oblivious transfer and circuit garbling And by the way those are both also wonderful examples of theory impacting practice many years later right when when oblivious transfer was introduced in 1981 I don't think Robin had had the idea in his mind perhaps that it would develop to the point where it where it did today So oblivious transfer is in the fight in the version. I'll talk about here Has a sender and receiver the sender has two inputs. Let's think of them as strings here x0 and x1 the receiver on the right-hand side has a selector bit B and We can define what we want by Defining what we would want in an ideal world where the party's had a trusted incorruptible third party to rely on I have to say whenever I give a talk like this that it becomes harder and harder to find something that people might view as an incorruptible Trusted party, but let's take the IACR as an example So what what's the what's the ideal functionality going to do? It's going to accept the inputs from both parties It's going to accept x0 and x1 from the sender and the bit B from the receiver And then it will return only the string selected write the string X of B to the receiver And so the receiver learns nothing about the other string and the sender learns nothing about the selector bit of the receiver great Circuit garbling is a little bit more complicated This was introduced by Yao in 1986 the idea here is that we There's gonna be one party that's so-called circuit garbler who for every gate in some circuit and for every wire going in and out of that gate will choose two strings to label each wire so here I've just shown a zero a one on the top wire and then be zero be one and then C zero C one on the output wire and The those strings will correspond to each of the possible underlying bits on that wire So say a zero corresponds to the bit zero on that a particular wire And then what you want to ensure and you can then hook these up Right, you can connect that output wire to another gate and continue this as long as you like And if you just want to ensure correctness you want to ensure that somebody can now use this to evaluate the circuit What you what you need to do is you need to first of all ensure that the evaluator the other party is Going to learn one label on each input wire of the circuit Okay, so they're going to learn either say a zero or a one if that's an input wire of the circuit And then you need to ensure That you can maintain the following invariant that every time you're at a gate at a garbled gate and you have One label on each of the two input wires to that gate say a sub r and b sub s You can somehow or another compute The string corresponding to the correct bit on the output wire So in this case we're talking about an AND gate you should be able to compute from a r and b s the string C of the bit r and s And if you can do that then you can go from the input wires down to the output wires You can gradually learn every one one label one string on every wire all the way to the output wire And then the garbler can also provide some kind of a translation table telling you which actual bit the strings on the output wires correspond to From the point of security What we need to do is we need to ensure first of all that When the evaluator learns a label on some wire It shouldn't reveal what the underlying bit on that wire is right So if the if the a wire for example corresponds to an input of the garbler Then when the garbler gives a zero to the evaluator the evaluator shouldn't learn that that corresponds to the zero bit Otherwise it would leak the bit of their input And you also need to ensure that the evaluator will only ever be able to learn One label or one string per wire because if you can learn both then it can actually from that deduce potentially What bit each string corresponds to And this sounds perhaps very complicated, but it turns out to be very easy to implement at least in in in some naive way You can simply have this idea of a garbled table Corresponding to every gate where you simply include encryptions of the appropriate output wire Under keys corresponding to the appropriate input wires So for example, let's look here You see that there's only one encryption of the string c1 And that's going to correspond to something that can be decrypted only if the evaluator has The strings corresponding to the one inputs on both of the input wires Right, so only if they have a1 and b1 do they recover c1 in any other case? They're going to recover c0 great And we can now couple these together and build a semi honest two pc protocol So let's consider the case where x and y bits for simplicity What p1 will do is it will garble that gate It will then send that garbled gate over to the other side And now it has to ensure that the other side p2 is going to learn exactly one string on each input wire So if a corresponds to p1's input, then what it will do is it will simply send the string corresponding to its input bit x So it will send a x And now it has to also make sure that p2 can learn the string on the b wire corresponding to p2's input Well, what can they use to do that they can use oblivious transfer, right? p2 can use the selector bit y The strings that p1 will input are exactly the strings b0 and b1 p2 will learn only the string b sub y And then it can go ahead and from that and from the garbled gate compute The string corresponding to x and y which it can then decode and recover the actual output bit x and y Okay, so quite simple and clean Now let's look a little bit at some interplay here between theory and practice In particularly through the lens of symmetric key cryptography And the main takeaway point of this part of the talk is that as secure computation moves from theory to practice Uh, there's a real need to understand the real world security Not just of abstract protocols as written in a paper, but of the actual implementations themselves And in particular, this is not really a Surprise to anybody perhaps who's ever implemented anything or looked at implementations Is that there's very often a gap between protocols in theory or protocols as written in a paper or as not written in the paper And in practice, right? So for example, there are very very often lots of low-level details that are emitted Sometimes because they're assumed to be folklore. They're assumed to be obvious But then you sit down and somebody's going to implement it and they may miss out on those subtle points There are often implementation level details that are unspecified that are left up to the programmer There are various performance optimizations that people may employ during the implementation phase And what you get in the end is that you implemented something that was close to the protocol as specified in the paper And the protocol in the paper may even have been proven secure under some assumptions But you're missing now an end-to-end security proof for the protocol as implemented And if we're going to move toward greater deployment of secure computation Or towards standardization of secure computation, it's going to be critical to address this gap If you look at efficient implementations of semi-honest secure two-party computation The efficiency improvements over the last, you know, you can you can count since yaw or you can look at the last 10 years They've been driven by improvements in the underlying building blocks The particular ones I want to highlight are ot extension I'll talk about it more in a few in a few slides And also improved garbling schemes. There have been many different optimizations that people have come up with for the garbling step And all of these protocols all these improvements both the ot extension and the various improvements to garbling schemes All ultimately rely on some hash function h. This is basically how they're written in the paper And sometimes the protocol is proven secure based on certain assumptions about the hash function Other times the protocol may be proven secure when the hash function h is modeled as a random oracle But the question remains perhaps well, that's good But how then should we implement the protocol and when we and in particular when we implement the protocol How should we instantiate this hash function h? And when we choose to instantiate that hash function in a particular way is that implementation secure And then you can ask also well Even if that's secure, are there maybe better ways that you can go about doing that? And of course these kind of questions are not specific to secure computation the difficulties of instantiating a random oracle Are kind of well known. I don't think they've really been looked at Extensively in the context of secure computation before Now many of you may be sitting there thinking well, what's the problem, right? So the natural thing to say is well, look we know how to instantiate a hash function We'll just we're just going to use sha, okay? So first of all you have to be a little bit careful, right? I mean sha2 is not indifferentiable from a random oracle you can patch it so that it is that's fine That's great The real problem is that there's a preference For using something other than sha in these most efficient protocol implementations And specifically there's a preference for using a fixed key aes. This is actually inspired by some work By bilari et al in 2013 Who showed basically that you can in the context of garbling specifically that you can get Tremendous efficiency improvements by relying on fixed key aes rather than a cryptographic hash function like sha And the reasons for that are first of all you can exploit hardware support for aes You can also avoid the cost of key scheduling if you fix the key, right? So if you I'll talk about this more in the next slide But basically if you're not re keying the re keying operation in aes As a significant overhead to the total computational cost And if you look at the numbers you see that the hash functions if you just we're going to use an off-the-shelf cryptographic Hash function like sha2 or sha3 They're basically 15 to 50 times slower than using fixed key aes So yes, you can use sha, but then you're going to be paying a significant performance penalty It's a good point for a digression about fixed key aes and the random permutation model which i'll be talking about So if we fix some key k and for now, I don't really care how the key is chosen We can consider the fixed permutation that i'll call pi Which is just the aes block cipher with that key hard coded, right? This is now giving us a fixed permutation on 128 bit strings And what is sometimes done and what we're going to do in this talk is to model that permutation pi As a random permutation and we're going to work in the so-called random permutation model Which is really completely analogous to the random oracle model the really the difference is that in the random oracle model You're given access to a random function here You're going to be given access to a random permutation as well as the inverse of that permutation So of course anybody who has the key k can compute aes inverse So we have to allow the attacker to compute the inverse as well And even though this may seem maybe it is even a strong assumption I'll just point out that it's weaker than modeling aes as an ideal cipher There may be other reasons to believe that aes may not act as an ideal cipher But modeling block ciphers in general as ideal ciphers is also a common approach That people take when trying to prove security of constructions Based on block ciphers So coming back to the problem of instantiating hash functions Many people in the audience may say well, you know We still don't have a problem because what we can do is simply construct a random oracle from a random permutation Right and that gives us our way to instantiate the hash function h And it is true that there are some constructions of a random oracle from a random permutation We discussed them in the paper The short answer is that they have drawbacks in efficiency or concrete security Or have difficulty handling long inputs And I would say actually it's a good open question To come up with a suitable way to instantiate a random oracle from a random permutation We're suitable here just means for the context of the specific applications to secure computation that I'm focusing on So in this talk, right, I'm going to talk like I said about how to hash how to instantiate these hash functions and implementations I'll just mention briefly about some empirical study of existing implementations and then talk about instantiating hash functions securely In this talk, I'll focus on the particular case of ot extension In the paper we talk about garbling and some other applications And then I'm going to talk about instantiating a hash function while ensuring good concrete security Here I'm going to focus on the case of garbling And both of these are based on joint work with Chen Guo, Xiao Wang and Yu Yu Combining expertise from a symmetric key world in the in the protocol world Okay, so let me talk first about secure hashing from fixed key AES in the context of oblivious transfer So So I thought I mentioned ot extension before I didn't explain what it was Ot extension is basically a very powerful technique for converting a small number of what are called base ot's So think about say 128 Base ot's and then taking those and converting them into essentially an unlimited number of ot's And this is fantastic because it turns out that the base ot's that you implement require public key cryptography But the additional ot's that you can then Obtain from those base ot's rely on symmetric key cryptography only So this essentially means that if you want to do a million oblivious transfers, you're paying the cost of 128 public key base ot's And then all the remaining ot's are going to only be relying on symmetric key operations It has a huge performance impact in practice And the existing paradigm for efficient ot extension works a little bit differently from what I've been describing Uh, essentially what it does is it relies on a protocol for what I'll call random ot and I'll show Exactly what that is on the next slide And then you basically take what you get from the random ot and you bootstrap that in some way to obtain the One out of two ot that you actually want So let me show what that looks like So here we have a party on the left, a sender, but they now have actually multiple pairs of inputs And the party on the right has multiple selection bits Think of them as a vector if you like They're going to rely on this random ot functionality that I talked about There are some details here that I'm Eliding but essentially the idea is that the receiver will input its selection bits And then what will happen is that the random ot functionality is going to pick a bunch of random values That satisfy certain constraints and in particular what it will do is it'll choose a random shift Delta and a bunch of random strings x i and give those to the To the sender and the receiver will obtain As its values y i The random strings x i XORed with bi Times delta okay, so either the shift has applied or not depending on whether bi is equal to zero or one And now of course the sender wants to transmit one of its actual strings So what it will do is it will compute these masked values that I called m prime i sub b That are computed by masking its actual strings m i b With the result of evaluating a hash function on x i XORed with b delta for both values of b Okay, so the uh the sender has delta the sender has x i it can it can compute both options You know both with and without the shift Use that as a mask and then send the masked values over to the other party That party can then strip off exactly one mask per pair And recover Exactly one of the one of the two strings for every one of these pairs here And the important thing to focus on here is the masking that's being applied Which as I said is the result of computing a hash on these various Values here twice times l values if they're l pairs here So you can prove that this protocol is secure even from malicious attackers If h is modeled as a random oracle and I'll just mention since it'll come up later That if you're only concerned about semi honest attackers, then you can actually omit The the second argument here the the i that I had and you can simply send or use that as a mask But as I said before this leaves open the question of how exactly h should be implemented And when we went to look at existing implementations of this this ot extension protocol We observed that in many of the current libraries The hash function h is as I said before actually implemented using fixed key aes So how did people choose to implement it? Well Basically, uh, they made it up as I went along. I guess what one could say You see different types of implementations different types of Of choices here. This actually just shows what kind of security the implementation was targeting And the problem in the end with all of this is that it turns out these are all insecure at least insecure as realizations of the ot extension functionality Let me actually give a a simple example So consider the case where um, you implement you instantiate h of x Maybe I should have left out the i here H of x equals pi of x In the semi on a setting if h were a random oracle that would be fine And assume for example that the receiver happens to know two of the messages In one particular index, so it knows m 1 0 and m 1 1 Well, then from the two masked messages the receiver can actually compute pi of a 1 and pi of a 1 x or delta And since pi is invertible this allows recovery of delta Okay, and once it recovers delta it can then learn everything Now that's an attack on the ot protocol Uh, it turns out that in some cases not all cases, but in some cases you can actually Extend that to an attack on the full uh on the full two pc protocol So we thought about you know, what would be a principle to weigh forward? Well, what we can do is we can try to define security properties for this hash function h that would say be weaker than Asking for indifferentiability from a random oracle In particular, we focus here on the security property that we call a tweakable correlation robustness that i'll define on another slide And then prove that the ot extension protocol is secure when h satisfies those properties So you don't actually require h to be a random oracle. It's enough for it to satisfy this more limited set of properties And then show how to provably realize those properties from a fixed key cipher, you know modeled as a random permutation pi So the notion of correlation robustness was actually introduced in the context of the Original ot extension protocol our definition is not exactly equivalent to theirs, but it's certainly inspired by it And without giving the the you know longer formal definition I'll just say that a hash function h we define to be correlation robust If the keyed function defined in this way is a pseudo random function So basically what you're doing is you're just using the key as a shift on the input And then we define this stronger notion of a tweakable Correlation robust hash function Inspired by tweakable block ciphers in that line of work If you just allow the secondary input this tweak which is not masked at all And we still require that fb a pseudo random function in that case And it's not too hard to show that the ot extension protocol on the previous slide Remains secure in the semi-honest setting if h is correlation robust And it's secure in the militia setting if your hash function is tweakable correlation robust So how can you then construct a correlation robust hash function? So it turns out that we can come up with this construction I've called it here mmo prime because it looks very similar For people who are familiar with the matthews Mayer oc's a construction of a hash function from a block cipher. This is very similar to what they do I'll just point out that it's not equivalent because in that case they're actually trying to get compression Here we're not looking for compression. So we just have a single input x coming in and a single Input going out. There's no compression going on here For the case of the tweakable correlation robust, it's actually More difficult and the difficulty really comes in in terms of where to where to fit in this tweak And this is you know part of the challenge here is what I mentioned earlier that like I said There's known work on constructing things that are indifferential from a random oracle From from a random permutation But they will will not always be able to handle an input that's of length twice the block size But this construction here that we call a tweakable mmo Tmmo is the construction we have And what we're able to show is that if you model this permutation pi as a random permutation Then the mmo prime construction of the hash function is correlation robust And tmmo is tweakable correlation robust Both of these rely on the age coefficient technique I mentioned that because it's another really beautiful technique that arose from the symmetric key world That I don't know if if people perhaps who don't work in that field are familiar with it's really quite beautiful And should be perhaps more widely known And so overall we obtain an ot extension protocol Or a t extension protocols one in the semi-honest setting one in the militia setting that have end-to-end security proofs Based on fixed key aes Modeled as a random permutation And what i'm showing here is just the efficiency of the resulting construction So I mentioned in particular at the beginning that if you wanted to you could implement the hash function in those protocols With uh with sha 3 or sha 256, but if you do that you're going to pay a significant performance penalty This shows what the The performance essentially of aes with and without key scheduling Those are shaded because those actually would not give you a secure instantiation of the hash function But you can see here that our resulting constructions the mmo prime and the tmmo Are you know in the case of mmo prime essentially paying the cost of a single fixed key aes evaluation In the case of tmmo We're paying two cost to the permutation essentially, which is why it's essentially twice of what you pay for fixed key aes So what I wanted to look at next was some work on the concrete security of the circuit garbling This is kind of well known, right? We have two notions of security that we often look at in cryptography Asymptotic security and concrete security where asymptotic security in a nutshell basically claims that something is secure If no polynomial time attacker can break the scheme with better than negligible probability Whereas in the case of concrete security, what we're interested in is explicitly bounding the success probability of an adversary In terms of the resources that they have available and in particular in terms of the complexity of the attacker the running time for example And uh surprisingly, I would say there's been little focus on concrete security in the context of secure community Computation it doesn't mean that there's no focus There are certainly papers that will give a concrete security bound But it hasn't received the amount of attention. I would say as concrete security in the context of signature schemes for example And I wanted to look at concrete security in particular in the context of some of the more recent and more highly optimized Circuit garbling schemes and so for that I need to introduce actually two of the optimizations that are now Commonly used so I talked earlier about a very simple garbling technique Where you associate I didn't say it at the time, but I was perhaps thinking in terms of letting a zero and a one Be be independent random strings And then you compute the garble table in this way it ends up having four cipher texts and doing potentially eight encryptions if you do this naively And free xor and the half case optimization are two different ways people have come up with in order to Improve the communication complexity and also computational complexity of circuit garbling So the free xor technique Is actually simple to describe The basic idea is rather than choosing the two strings associated with any given wire Independently at random We're going to maintain them or we're going to have them be correlated Through a global random shift r So you see here that we are going to choose the garble will choose a random string For each wire that will represent say the zero wire And then the one wire on every or the one label on every wire will just be the zero label shifted by the same shift r And this is useful because then as the name suggests it allows you actually To support xor gates in your circuit without paying any computational cost at all So essentially they become free and the only cost in your circuit is handling and gates and or gates The second optimization Is a very clever optimization that allows you to reduce The communication complexity of a garbled table. So as I said here on the left We have essentially four different cipher texts. So if your if your labels are kappa bits long, you're paying Roughly essentially four kappa here um The half gates protocol replaces that with only what i'll call two cipher texts And i'm not going to go through the details of how it works or prove correctness. It's quite quite involved What I wanted to just highlight here is something we're going to focus in on the next slide is that one of the values That's being sent is this value that here I called t1 Okay, and I claim Again without going through the details that this will preserve the property I talked about earlier namely that if the evaluator has one of the two Labels on each of the input wires of a gate they can then successfully compute the corresponding output wire on that gate And moreover what's nice about the half gates protocol is that it's Compatible with the free xor optimization And I've indicated that here actually that you have the label a1 for example is actually still a zero xor with r As it is in the free xor optimization And it's natural to ask well, what's the concrete security of garbling in this way? Uh r is essentially a uniform k-bit value May actually became minus one bits, but we can ignore that for now You want to actually make kappa as small as possible because the communication complexity is going to be exactly twice kappa Okay, so if you're satisfied with say 80 bit security, you'd prefer to set kappa equal 80 and then send only 160 bits per garbled gate And you can show actually that if you model the hash function h that you use to compute The those those two ciphertexts in the new garbling scheme that this actually is Kappa gives you gives you kappa bit security And many papers and implementations Set kappa equals 80 This is maybe targeting one of the NIST recommended security levels And obviously people are trying to make their their the results in their paper look as good as possible So they choose kappa to be the smallest reasonable value, which is 80 And we can again ask well those results are fine if we're willing to model h as a random oracle and use something like Shah But if you look in fact at how h is implemented It's again typically based on fixed key aes And one common choice is this Essentially computing h of x i as MMO I guess it should be MMO prime Of 2x x or i and this 2 here may like odd Maybe we'll come back to that later and say why people did that but but this is a one popular choice And if you look at this you can see that clearly it's no longer indifferentiable from a random oracle And so essentially this leaves a gap between What we're able to prove and and what's proof you know What was proved for the implementation and what's proved in the paper and in particular leaves open what the concrete security of this choice might be And it turns out that when h is implemented in this way There's an attack that has complexity 2 to the kappa divided by c where c is the number of gates that you're garbling So what that means is that if you're garbling 1 billion gates, which is now a popular number to target Based on a paper I don't know five six years ago If you garble 1 billion gates with kappa equals 80 then you can break the scheme in essentially time 2 to the 50 And the attack is really bad because when you implement the attack Successfully it allows the attacker to recover r and once you recover r you can reveal everything So you basically learn the the you learn you learn all the inputs And the attack also extends to the multi instance or multi user setting Where either the same user is garbling Many different times or you have different users who are garbling and the attack will succeed if they're able to attack any one of them This is something also that's gotten a lot of attention recently in the context of symmetric cryptography and hasn't really seen Perhaps a lot of attention in the context of secure computation And so here's just kind of some numbers I played around with if you garble a billion gates every day for a year Using kappa equals 80 then you can break one of those instances With in time about 2 to the 42 So let me try to describe the main ideas behind the attack Um, so the evaluator is going to be learning one of the labels on every wire So it's learning in particular one value a star in this set, which is either a zero or a zero x or r The evaluator doesn't know which which is the case But it also learns this value t1 That was one of the values that's being sent as part of the half gate scheme And it learns that value t1 for each of c different gates if c different gates are being garbled The evaluator or the attacker can then Compute it can hash the value a star that it received It can explore that with t1 and obtain this value here oops and The observation is that this value pa, which I didn't actually define It's a bit that in the construction of the half gates protocol is zero with probability half It's just a random bit And so what that means is that the evaluator has an expectation right c over two values Of the following form that I put in this list l It has basically Mmo applied to two a star j x or r x or j and here actually I'm just instantiating the hash function h with that mmo construction from the previous slide So now what the attacker can do is just evaluate this mmo hash function on its own on a bunch of random values w1 through wq until it finds an evaluation that lands in that list Okay, this is going to occur with probability q times c divided by two to the kappa And then with constant probability it will hold that the wi is equal to the input to to the mmo And from there you can solve for r and then you're done Okay, so again with kappa equals 80 and garbling one billion gates It turns out you can actually implement this attack for about a thousand dollars in a few weeks in the cloud So if we're trying to get better concrete security for garbling What we need is to look at the properties we require of the underlying hash function And it turns out that what you need for garbling is a stronger notion of correlation robustness that we call Tweakable circular correlation robustness actually the notion of circular correlation robustness was a notion that I myself and some colleagues introduced in 2012 Here we define a tweakable notion of that of that definition And moreover if we want good concrete security then we're going to want a construction of a tccr hash function that that itself has good concrete security And we show that this construction that we call mmo star Is is going to be such a construction. I want to point out a couple of things here So first of all right, we have two inputs. We have the input and then this this this index or this nonce We also here are moving away from the random permutation model This represents actually now aes itself or some block cipher And this represents the key whereas this left input here represents the input So we're no longer working in the random permutation model now. We're working in the ideal cipher model This permutation here or this function sigma I'll talk about on the next slide, but it's basically going to need some combinatorial properties in order to prove the construction secure And in particular what we're going to require is that sigma b was called a linear orthomorphism We define For any given sigma we can define this function sigma prime to be sigma xx or x And then we'll say that sigma is an orthomorphism if both sigma and sigma prime are permutations And then sigma is linear if the standard property holds And these functions turn out to have received a lot of attention in the symmetric key literature And they've also been imported to some extent into Secure computation in particular the the multiplying by two that I showed earlier I think arises from the fact that this is a is a linear orthomorphism. It was suggested In the I believe in the just garble paper We find actually a different construction is is actually much more efficient can be implemented in a very small number of instructions And it's better than doing than paying the cost of a field multiplication So the theorem then is that if sigma is a linear orthomorphism and if we model the block cipher f as an ideal cipher then mmO star is a tweakable circular correlation robust and moreover it has a cap a bit security So this is true only in the case where every tweak the second input i is used once And that will be the case when we apply it to the context of garbling when we apply it to the context of secure computation So overall then we obtained a garbling scheme with the same communication complexity as free xor plus half gates But with a tight security reduction based on a yes model does an ideal cipher and I was talking earlier about how in general people like to avoid the the Paying the cost of re keying for a yes, so it's true that you do pay some penalty for that Thankfully, there's been some other work also in the context of secure computation Showing that you can at least do a little bit better and the cost of re keying is not as bad as you might expect I'll just mention also that we can extend these results to obtain tighter security also for garbling Even in the multi-instance setting So let me just conclude with a couple of thoughts and then we'll have time for some questions So I think there's been a lot of work on secure computation in the last 30 years and of course most of the Initial work in that field was focusing on the theory of secure computation focusing on definitions focusing on feasibility results focusing on different models And in the last 15 years Say since the fair play paper There's been an increased focus on implementing secure computation And in improving the practical efficiency of secure computation protocols And I would say this has been mainly a theory Driving the practice with of course the theory being motivated by real world efficiency But it's really been more theoretical Work that then turns out to be to lead to these efficiency improvements And perhaps in the next 15 years, we'll see a little bit of a flip and see more Practical issues driving the theory And I think that will especially be the case as not only there are more Secure computation libraries out there that people are experimenting with But when there start to be deployments of secure computation in real world use cases and as companies are beginning to deploy and sell these things In the real world that I think will bring up many interesting questions that will then need New theory to address And I think these kind of things are very important to think about As we perhaps move toward developing standards for things like zero knowledge or secure computation So I just thought I would list maybe a couple of open directions I put a question mark there because I'm sure I actually I know that many of these are addressed at least in part by various papers I would say there's still more work to be done in those directions though So I think first of all, maybe an increased attention to concrete security Is called for and in particular I'm not aware of any composition theorem that actually deals with concrete security And if you start thinking about it, you realize that there are good reasons for that because it's not as trivial as you might think You can even start thinking about what what a a version of universal composability would look like with a concrete security treatment A better understanding of ideal primitives and protocols Right here. I talked about two lines of work using the random permutation model or the ideal cypher model There's lots of protocols developed in the random oracle model I I would say, uh, maybe it's maybe it's my own take on things. I think we still don't have a full understanding of what exactly What sort of composition results hold when we talk about composing protocols that rely on these ideal primitives And there are very often cases where things don't satisfy the properties you might expect by naively applying Existing composition theorems that mainly talk about composition in the absence of these ideal primitives. Certainly that's true in the standalone setting Uh, what about post-quantum mpc? As far as I can tell there's been You know less than five papers Looking at constructions of post-quantum oblivious transfer But this is something that people are paying a lot of attention to in the public key world in general in the context of encryption and signatures And we need to start looking at that in the context of things like oblivious transfer as well And we can also ask about the concrete security of these various symmetric key components of the protocols Against quantum attackers I think also there's a lot of work to be done on mapping some of our theoretical models to the way things actually work in practice Uh, just just as you know some examples, right? I mean we we assume that there's some fixed set of parties, right? There's n parties and they all agree at t equals zero to start running the protocol But how how is that actually going to work in the real world? Right, uh, if you think about applications of this to something like voting You realize that that model doesn't translate very well to that kind of a setting Um, you can talk about session ids. This is something that's needed for composition for universal composibility and for other reasons Um, and I think generally people ignore that when they implement their protocols Um, and it's you know, they ignore it maybe for good reason because it's not so always so simple to Establish agreement on the session ids and they can add some complexity to the protocol Uh, looking at how these various setups actually would be implemented and used in practice Uh, I think considering more complex trust models, right? So again, this is something that goes back decades people have looked at generalized adversary models But if you look at the work on efficient secure computation people have generally Stayed with the more classical threshold adversary, uh, but you can it's also interesting to look For optimized protocols that are secure in these more complex settings Um, another thing that's interesting to me recently is a more more accurate modeling of the network We have basically two models right a synchronous model and an asynchronous model And you know, I think neither of those may be a very good model for the way real world communication networks work Especially when you're talking about parties where some of them may be located in the same data center But some of them may be located across the world Similarly, we always uh, we generally think about a complete topology, but in many, um Uh, in many real world applications of secure computation You mean you either may not have a complete topology meaning meaning links between all pairs of players Or it may be the case that some links are much more expensive to use than others And so you'd like to minimize the amount of data you send across those links I think also in a slightly different direction, um, the Formal verification of npc implement implementations is something that's also going to be important as we talk about deploying these things in the real world It's very easy to Look at a proof in the paper and be convinced that it's correct. Sometimes they turn out to be wrong Maybe just for subtle subtle errors Then when you take that protocol from the paper and implement it, it's very easy I may have as I've shown here to get some details wrong and then Invalidate the end-to-end security proof and I think formal verification can help here At least even if we can't do an end-to-end verification of a full implementation At least verifying parts of it will give us confidence in in different parts of the protocol So with that I'll conclude I think we have you know one to five minutes for questions depending on how hungry people are But I'm happy to take any questions people have Yes, please if your questions come down the aisle and Then use the microphone And in the meantime, let me ask a question. So these So from your presentation, it seems that the random oracles can be a great way to make things efficient But in practice they can be also very error-prone and tricky to use Which also from a practical point of view is not good How much would you lose by trying to Not use the random oracle model and try to get a secure multi-party computation in the standard model Primarily for a usability to make it easier to design and the program. Yeah, it's a good question I mean, I don't have an answer off hand. It's an open question I would say you know Yeah, I mean, it's a it's a research question, right? So you could look at that garbling the garbling protocol I showed and the trivial garbling protocol, for example Can be implemented Based on AES just treating it as a pseudo random function without making any idealized assumptions at all So that gives you maybe something to compare to In general though, we like to squeeze as much efficiency out as possible And it seems like you're always going to do better the more the stronger assumptions you're willing to make Okay, thank you Chandra. So has anyone looked at using fixed key AES for work for proof of work Um, not that I'm aware of but it wouldn't surprise me if somebody had Um, I think, you know, if you're talking about just replacing the hash function used in bitcoin with AES or something like that I mean, I'm not sure what the advantage would be because you'd want to keep the work the same So you maybe have to increase the number of AES calls you do to make it consistent No, it may be because you may not be able to use in video Uh-huh. Uh-huh. Okay. Yeah. So, uh, well now you have a company I also agree with everything you said You're so what? You're referring to to Nigel. I agree with everything he said or No, so when I agree with your concrete security type approach when when about the composition theorem Just a pointer that we got some paper features back on resource Fairness or we had to regroup, you know, we have a composition theorem in this So does it give you clean concrete bounds like like, uh, well for resource fairness, but it's an example You have to go into the concrete aspects. Okay. So that's a good Point to them. Thanks Uh, to commences first, I also agree with one Yeah, we have now a chain But okay, so firstly just to say that the in the uc monster there is also a definition with concrete bounds We concrete bounds. Yeah, so it's a definition And actually this the composition theorem also, you know, there is a Is in the original paper in the yeah, whatever revision. Yeah, the original paper that came out last year Yeah, but I think it's been there for for a year. Yeah, so so the by By composition you lose a factor of a number of instances in the No, but the difficulty no, that's that's a standard hybrid argument, right? But I think the issue is that you have this extra term of the simulator, right? Because you can you can trade off a tacker complexity for simulator complexity No, so the simulator complexity actually remains the same and it's not affected by that Oh, I mean, I mean in the Turing machine But I mean when you're proving protocols, right? You can have a protocol that's secure against one adversary with this running time of a simulator and get better bounds with a different Simulator, right. Yeah, but yeah, some of the compositions here. Yeah But in another way another point regarding the The proof of work and and and yes, so just to say that there is this recent work That we actually show that if you think about correlation productivity of Big ski yes, and if you assume, you know ideal secure not ideal, but, you know, exponential security for yes It's whatever independent messages then it actually gives some concrete bounds on the on the on the proof of work Model work that you need to do Yes, so maybe tying that back to Daniele's question, right? That may be a type of assumption under which right assuming, you know That the AES is a prf, but you need this much complexity to attack it Maybe a slight weakening of the ideal cypher model that where you can prove stuff Yeah, absolutely and and actually in this case AES is much better than shaft Because we actually the fact that it's that it's a you know, it's a fermentation or you call input Input equal to the output length and you think of it as an and as an ideal cycle So So this particular it's it's with with the with the elation And and run mob bloom and and And you yeah, you're raising yeah from whatever your turn, okay, so let's thank Jonathan again


I write some poetry, having recovered from other things in my life. And this is Dee Davis, who is a wonderful musician, composer, and who played with Brian and Ruth and me when we did our performance of birds, words, and notes of military. So I came early to, this is just an experiment and trying to find new venues for poetry. And Dee was kind enough to read a common play with me. So I had the lunch outside, which is a delicious corned beef hash in honor of St. Patrick's Day. And I sat at a table with some very nice women who were deeply disturbed that my poetry reading had kicked them out of this room. Where they normally play mahjong. So just to show you that I can write in different poems, I wrote them this morning. I write poems in most any style. You might cry, remember, or smile. But this was the worst. And it made me feel cursed to learn and send mahjong into exile. A lofty note, people picking our poetry. What a man of the moment. This is a poem that I realized. I wrote this a long time ago. And it was about the flood. How many people were here for the flood in 92? I saw it on the news. What was the news about it? Oh, yeah. I was in New York on a night in Seoul. So we're a little bit worried about that this year. And it's OK. So I'm going to read you this old poem called The Flood. And it's in four parts. The first part was from March 11, which was the actual day of the flood. At 730, nodding his tie, David Dean, who knows rivers, saw ice floes stop on the Manuski and ran out to move his car to hire Grant. An hour later, there were rapids on State Street and canoes in the parking lot. Water still rising, we assured each other, as it welled up storm sewers and riffled down stairways. And the order of the day dissolved into easy revolution. We collected life flotsam at the edge of the flood. It was an old fashioned crisis. Nothing we could do to stop it. Better yet, nothing we could have done. It was dark. Water from the Worcester range, silencing our phones, filling oil tanks, setting electricity free. It was a day of dangers that finally had a name, with something important for soldiers to do, and simple things to rescue. Videos, food, paper from our past, even when it was only a flood between us, each other. March 17. This morning, at last, the pumps stopped. The water that leafed through novels at Bear Palm Books ran around the vinyl grooves in Bookspealer's basement, the way we listened with thorns to old 78s, and tried on hundreds of pairs of shoes, is back in the usual channels. The trout has gone from the cellar of the transportation building, where it briefly swam among plans for better bridges. The produce, piled in rows like a November garden, will be thrown with carpet and chocolate and crackers, ruined in red boxes, and computers with no memory, and the haddock in front of Capital Market, which for a time believed in resurrection, into the mouths of green trucks, and disgorged and buried as jumbled as dreams in the central Vermont landfill when there wasn't. I added that. 3rd of March, March 21. Today, the stores are open. Sales offer astonishing discounts on salvaged goods, and crowds fill the scoured streets. Politicians gather and pledge to restore the old economy. The red slate doorsteps on Langman Street are shattered at the corners. A granite slab on Main Street sank two inches in the basement field. Walls of the barred block are cracked. Water damaged lingerie is half price of Robin's peach tree. I think I made that up. Already, an official t-shirt is on sale. The water runs light green over clean sand under the bridge. Tires and shopping carts have been swept a little further downriver, and gray boulders are rotting on the Middlesex fields. Willows are white with skin wood along the Manuski. The flood has gone back to sleep in the granite mountains, like leaves that sleep in the tips of winter branches. For today, this morning, a ladybug appears from nowhere and circumnavigates my breakfast plate.  I used to understand so many things. Now everything surprises me. Anger shows up on my doorstep like an orphan. Sadness is a thread of light I try to pick off the carpet. There is nothing I'm qualified to rescue. I am learning to be patient. Like us, the flood has its own economy. It is as curious as we are, but incapable of pretense. It leaves gravel in the furnace and strews flowerbeds in the street. The man who works in capital market, how many people remember? Which opened after the 27th flood is selling off what's left. He thinks he can get his job back at the lumberyard. He is worried about the customers he used to take groceries to. He knows there's nothing called normal to go back to. And then this is a title piece for this, The Poem of the World. The poem of the world reveals itself like a doe's hoof tapping ice till she can drink. It startles like the rust of purple on this fall's horse of yield leaves. Though it may have used that small voice every year unheard. It blinks like red and blue potatoes dug this morning, drying in the sun, testing their startled, untrained eyes. It stirs the man with belt between his teeth after airport screening to laugh when I smiled at him for our shared absurdity. And it's the unexpected tickle, the fit of shared giggles and our urgency of touching that becomes another way of making life. It's an ocean beach of pebbles that suddenly starts seeing each stone its own tank together a gloriously indifferent song. And it's the voice of each bird I have only heard as morning chorus landing with its own song and bright perfect body in my brain. It is even now I begin to see them the subtraction of the birds taking summer with them too busy to announce their new life. Oh, it is a dolphin swimming in the boat's prowl visible then diving down for power faster than a chugging engine. It wants me to wake in my own body. It is astonished I might let these supple bones grow. It seeks only my permission. It is the sudden thing I trust. This is called visitation. Perhaps it was the carpet, the color of vast deserts that lured the black beetle with the elegant orange Babrej designs. For all I know it teleported from Tunisia or the early 13th century. It stayed for days. Wherever it was from whatever time I'm certain in the universe of beetles it was no extraordinary thing to do. It was my noticing the surprise of its beauty. My urge to have it stay that made it a visitation. It's calm precision, the orange on such perfect black. The cats showed studious respect. I don't know where it went but there are tiny fractures in the rules that shape me. I think I became more patient. There was no promise of return. I have a question in there. Is inadequately rewarded for his skills? And he has some CDs over there which you can, I think the hat is there for $10 bills to be thrown and we'd like to take it. The hat's actually a free gift for anyone. Like if you can take it home you can take that. I don't think I'd afford to be given that. It's only a 20-year-old hat. And he composes much of his own music and rearranges other things to make them. My? Yeah, or? This is a poem that I wrote for a high school friend who I had lost touch with. It's called First Love. A friend of mine who was a good friend in Harvard. It's for John. You and I were busy 50 years ago exploring our ways to love. The road we take today over Standard Mountain used to be unplowed in winter and like love and adventure in any season. Its metaphor was different from my father since it was the shortest route between two places where our family lived. It stood for good sense and valor in the face of danger, the danger that he acknowledged. We drive at this late September day of our renewing friendship. Creep along, slow to find our way. Fall colors seem still muted, not yet at peak. Today's road is improved, as Brahmagers say, but we know how a few years of neglect could leave it gullied and impassable. We have both seen small victories won and rapidly undone. Spring of our junior year, we drove from Hardwick to our bereft North Danville farm. The house had burned, the cows were gone, but this was our great adventure in your father's model day. We came the long way, route 15 through Danville, to stay at the surviving cottage. The prairie road to North Danville Village was a sea of ruts that spring and every spring. The high, narrow wheels rode through like Jesus walking on the water. We said we could conquer anything. We lit a fire, hiked, cooked meals, companioned in the sagging double bed. Your gentle investigation of my body sweetened me. It was the first time I let myself be cherished. You touched the molds, the curves, the prairies of my skin. This, I thought, was what friendship could be. But I pulled back when you wanted me. The valley opens before us. So much color awaits in this Northeast kingdom. Burke Mountain already hinting at November purple. I say, I'm sorry, I didn't love you the same way. You pause. I'm just glad to have my friend again. We let our sadness fill the car. You say you were 34 and still pretending. Then you let yourself be free.  She thought that he was good for you. She always sort of knew the way mothers do. That summer, I fell in love with Kathy Hancock, her music, mind, and slender body. My parents asked why you and I spent less time together. I think he's a little jealous of Kathy. Like looks of surprise, then panic erupted behind their eyes. At least they didn't punish us, but fear took over. That courage, my father honored, seemed to pause, step back, turn remote, and form. They talked to a psychiatrist, warned the other children, sought comfort in some confidence that I was new. They feared the suffering they hoped I would be saved. At best, the church would stand by silently, if not like some, ratify the lash of each day's casual cruelty. All that was left to you. I saw how belief holds hands with that more ordinary scene, relief. I ask if you remember when we hit 100 on the road to Woodbury, just out of town, your father owned the Ford dealership, you always had a car to get around. I don't remember that specific day, but I drove fast a lot, mostly alone, you say. Now, you just keep driving slower. Cars pull up, honks, swing out to pass. I imagine them motoring old leaf peepers. Even with affection and good intent, we let 50 years of silence flow between us. That's how the injury prevails. Decades harden like cement. As we drive, we find our way to talk. You ask about my sister, what it feels like growing old. Slowly it seems our families pile into the backseat, desperate to share with us each other, full of their own stories, familiar and long told. You want to see the farm. My mother and stepfather died last summer. The cottage where we slept, still where it stood, has returned to emptiness. My brother greets us. His friend Tom is turning an old maple, one of those that line the road to chunks of firewood. His blue battered tractor's bucket is nearly full. You say, four, good choice. I joke that you might try to sell him a new one. No way, says Tom, this here is my last tractor. You say, the new ones are great. It feels like we could pause here, past and present, and just talk all day. We drive to Peacham where my grandfather and his second wife, who left her partner, Marenian, to take up her new wife, are buried up among the massive plants. We get out. You call me as we search the lichen stones. You say what I am thinking. Another thing that's better, not to do alone. And this, going back to North Danville again, this is the North Danville School. The school basement was a concrete box. I urge you to go to North Danville and drive by it, with the perspective of this poem. We played in when the weather forced us. We gave concerts there, singing songs of many nations and anthems for each branch of the military. Parents lined up at the metal rail above. For basketball, a red stripe across the middle, foul lines came almost to that center, hoops at each end, three feet from the ceiling, which was the floor of Mrs. Sleeper's first four grades. We all shot flat and hard. The girls could only run three steps, then had to pass and could not cross the center line. You remember this? Yes, but yes, it was there. But played just like the boys at recess. The walls were out of bounds. The ball was put in play one foot on cement. When teams from Danville, Barnett, or Monroe were visitors, they found momentum was there in it. We turned briefly like a tractor raking to the fence. They hit the wall, we got the ball. We never lost a game at home. The Linas, Langmades, Gadapes, passed and dribbled through the forests of those neighborhood teams. Amazingly, we won in air dunes too, exploding on those spacious maple floors, still passing, dribbling and shooting flat. Our families huddled in the sands. Upstairs, the learning. Each row was a grade. We always knew the lessons for the next year. Ronnie Amidon, who lent me his small horse to ride the mile up to our farm and back again each morning for the bus, kept trying to get right the lessons of last year. The teacher tapped out her annoyance on his shoulder. Looked over at me, smiled almost confidentially. Shrugged, is it to say, what can you do? As though this was the lesson he had come from. Always appreciate outside percussion. Probably pick up on the rhythm of the song. Next time I hear that, I'm gonna just go. Couple more poems about living on the farm in North Kingdom, this is called Still There. In the picture on our bedroom wall, I stride behind Molly, our first Jersey cow. Up a pasture, flecked with dandelions. I am solemn, stick in hand, gazing down. She looks calmly past the crouched photographer to her spring-fed pasture pool. The corridor of trees marks this field from fields beyond. The brook that finds protection there starts by the towering elm, umbrella arching to the left. I can hear the language of that water. Not pristine, but delicate and clear. The leaves are barely forming on the trees. A grove of poplars, first to colonize the open land, is to the right. A few pasture spruce, rubbed dense by itching cows. The forest yielded this land grudgingly for farming. Use it, or I'll take it back. At the time, it all seemed permanent. I was 10. We had moved up from the city, ambitious to be farmers, learning honest work. We milked the cows by hand. The photographer could glimpse the story we were living, but still don't understand. I worked on all the land we owned. My brother does it still. The flowers and the grasses thin as trees return. The woods has claimed back all those fields since then. Through all the change, the brook still rises, whispering its song again. And this is called Elm, and this is about remembering the elm tree that's actually described in the previous poem. All the way from Pittsburgh to Phoenix, the men behind us talked to marketing and never once gave a clue what the product was. In college, Clay Hunt said, it's not what you say, it's the way that you say it. It was a kind of a chant for the English department. So if I want to say, for instance, that I miss the elm trees, I should tell you, they held up the sky over our north bandel farm, domed and rustling, alive with orials, soaring on raised arms, perfectly trained to lift the daily weight of food. Or should I just admit, I can't tell you how much I understand. This is called my affection for toads. I talked to them initially as though they were small children, then correct myself trying to be respectful, adult to adult. Even then I am too enthusiastic as though greeting a long lost friend on Main Street, who stares back struggling to recognize me. About the tiller and its bad behavior, I apologize, though remarkably that relative made it to the tall grass with only a small limb. No cleverness or deft protection, tripping, rolling over, such unglamorous beauty, revealing its creamy underside in all disciplines. And this is one for broccoli. I don't know how many of you have encountered the sweet mish, which has meant I don't grow broccoli right now, but this is when I used to grow broccoli. The unrulyness of broccoli, it seems well-mannered in the store, clumped by orange rubber bands or twisted wire, sometimes three or four heads bunched in an intensive seminar. In trays, sliced with celery and carrots, it waits to be finger food. Frozen and dismembered chunks from microwave or pot, it seems resigned to be in good. But in the garden, broccoli wants it all. Can't you see I need more compost here? It mushrooms to a basketball. My knife can barely find the stock side shoots wait for the head to fall. Succulent caterpillars in team colors, lurking in the inner forest, chewing to create the next rhapsody of butterflies, but cooked, curled protein on a plate. Wait summer, I have picked and picked and picked again the shoots take over dark green, plump, surging into flower, yellow, functional, triumphant in their hour. Now a couple of grandchildren poems. This is called Walk With The Grandson. First spring in a new house, he'll show me everything. We race up to the fort, a roof of lashed sticks woven plastic covering a gap between two boulders. Twigs collect on tops, leaves on the floor are almost dry. The stone seats suggest a welcome. He stays outside. It's not quite fear that heeds the privacy someone created and abandoned here. Orange plastic tied on yellow birch. He explains this means the land that's theirs ends now. The space beyond is somehow different, maybe dangerous. And yet the ground is little changed from one step to the next, or as we decide, last bits of snow, mossy stones, brown leaves, hugging the sapling roots, dead logs forged with fungus change quietly all over on their own. It takes almost no encouragement to cross the hesitation in his mind. We explore along the ridge until we find the backside of a neighbor's barn and house as deer must on their rounds. Small boats on racks, two moldering grain-stained ships, a desultory fence sketched the line between another human residence and a more cautious waiting presence. To our right there was a ledge or what he calls a cliff, but here the rock is gone and there's a steep but safe way down. His small dogged yellow boots follow his exploring mind. I realized this was his destination all along. Tall pines, a bowl of wilderness that right now belongs to him. A distant cliff, rocks, puddles, filmed with ice, soon to be gone. His body quickens with adventure. He wades into pools that flood his feet. I suggest the names for trees, bird songs. He collects them as I relinquish. Beside the pine I grew up for midden as we marvel at the knuck hauls stripped from their tiny skeletons of comb. I didn't think hole them all apart because the seed was hiding in each one. Puddle to puddle, snow and turkey track. We have come to the cliff's other side. Gray slabs in slow motion, creep down the ledge, jumbled. Small black caves at every edge. Almost a stairway back. I tell him I could lift him to that level place then we could climb up over. He shakes his head and smiles. Sorry grandpa, I might next time. Right now I'm just scared. We take the long way home, pebbled with deer sign, the path skirts another house. A slab and pole that held a TV dish are resting quietly. He wants to be a deer. Watch here from behind the trees next to the driveway, close observing unseen. He won't step out on the lawn. We climb to the dirt road then wander home through stubbled fields just commencing green. This is called working for Ray. Ray is my neighbor who does everything. It's not easy to work for people who think they know what they want but have no idea what it takes to do it. For some, their money makes them think they're smart enough to give the orders. Ray Hickory runs into this all the time. So when I hire him to help set posts for deer fence on my neighbor's stony land, I end up working for him. It's as risky as Ray is no fan of incompetence. Michael and I had tried to dig a post fold, tried a post fold digger then an auger on his tractor's PTO. But the holes veered off in all directions. Looks like you had a team of woodchucks on the job, Ray says. My back hole would be best. You mark the spots, I'll excavate, then you can hold the posts while I fill in and pack the soil around me. The day we did it, he kept nudging me. You really want that distance between posts? Where's the one for the next hole?  You're slowing down, you must be getting old. It felt like working with my brothers when determination that we get it right meant more than being nice and was a lot more fun. Politeness just seemed silly. Once or twice I told him, more fill here and the steel bucket glided over, dumped precisely the amount of dirt required, tamped it down, moved on. When we were done, I wrote the check. He looked around and said, not bad work today. You did okay. This is called safe as light. Long before guilt was invented, this stream managed rocks without it. Never a thread or a wheel, it shifted them when strength was gathered. Changes from every storm were there for my exploration. That's how its small riffles and dark pools became such freedom for me. Neither worms I pierced nor speckled fish I hooked cried out in accusation. In turn, they claimed me, taught me to thin in place beneath a dark green overhang of rock. Oh, how the heart is taught to bargain, search the hard ground of obedience and its deceptions. I would rather sink my feet in black lomi banks where a holy beaver pond spills disconcerting welcome through the tree-nose. There is no promise I will be safe if I relinquish. It is a place where for a few years work trout fatten and the silt accumulates until some torrent tears the sticks apart and I come explore Jews fertile mud. I confess I have chosen sides and welcome new companions. My grandson shudders at colliding arguments of thunder but will not be denied the liking. And this, I'll read one more about canoeing on the Winooski River. A morning of little consequence. Shopping for two kinds of milk, exchanging cat food for the fussy cats, bottles to return, some strange vibration to get checked on in the car, the luxury of drawing up a plan or just a list and doing it or not or only part of it, crossing a few things off. Appointments I can make whenever, a summer program for the children, time for a nap perhaps, so much for ambition. I am still dazzled by yesterday's river, sunlight patient, stroking sly of lucid water, eagle soaring downstream, claiming everything. We thought we had a plan, as usual, we lost it. In the warning shallows or was it the deep current that tugged us through that draping millow? The railroad tries to river manage with massive granite boulders, blocks that pretend to be invincible until the flood tosses them. All my life I've driven beside this river, crossed it on bridge after crumbling bridge. Here I am, captured, knowing I'm captured. Yesterday's shoes soaked with time, how the bedrock swims upstream, whale-sleek staring at us with its small quartz high. And this one is for the cats. It's called feed the cats. Mentioned in the previous poem, but really more devoted to that. Upon waking the cat's first and urgent task is to remind me, before a bathroom, before a toothbrush, that nothing is more important than feeding them. Some peoples believe their supplication drags the laggard sun up the morning sky. Never would it rise or the can be opened. But for them, the sun has its practiced ways of coping. I am inclined to groggy banter, which is solidly ignored. Pat pat down the stairs, my only choice to follow. When I am home all day, the cats are at my feet, insisting on the evening feeding at one o'clock. It rouses them from the daily round of dedicated relaxation. I wonder when I give up and feed them at three, whether there is a sense of triumph. I have seen nothing that could be considered excessive celebration. And I'm gonna read one longer poem and then Dee and I will do the final poem together. This is called Gratitude. I don't wanna leave those tidy, unclean fictions when I go, like legacies of a departing colonist. I want loved ones to find no unused wads of kindness in my pockets. This wild explosion of undone will barely notice when I leave. A garden tilled for fall, cover crop of rye, subversive common seeds I might consider weeds buried there in wait. The nephew I hardly ever hear from, hardly ever call. The war, the uniform in both Korea and Iraq makes a living fixing roofs, floors, patios, you name it, there in Texas. Bass fishes after work and weekends. I keep pretending silence is respect. Why don't I talk with him about his mother? Why did the Dalaiys never bloom this year when they were in full riot last? I realize my first garden shed may never get the fix I planned this season. My grandson might keep shrugging when I reach to touch him and I keep aching for a reason. Misery loves company, I sometimes tell myself, as though that might be comfort, but really, I never find new friends there. My misery's an excuse tailored to postpone my fingers from the dirt, the fear I need to touch. It always leaves me soured and alone. The peonies and gladiolas are more seductive every fall. October, I plant slips of peony root with three buds full of color that may prosper years from now. I dig shaggy gladiola corns plumped on slender stalks, next year's replacements for the top exhausted husks left from the thrust of color trumpets to the sky. Bulblets cling, intending futures of their own, purple is steeped in black, regal crimson, slim white avesinian, lavender that cries out to sunset orange. Beauty's nonchalant kindness accepts the slow learning of my eyes. I plant the slips, store the corns, my day possessed by past and future blues. I sit awash in an October sun. Gratitude is like this, all is a surprise. I remember how I dreaded grown-ups who creaked like closing doors. Even now I fear joy might never be allowed back through my window, but gratitudes, a different eye that opens, unnerving in its great permissions. In sun on this cold porch, I'm grateful. Some shy part of me is always sitting here, no wisdom, no plan, full of songs, no notion you may receive. Curled beige feathers, downy at the base, litter the stream that wanders toward us, and Elmore's Lake. Beavered alder branches, submerged pond-hair cushions, duckweed corraled by viburnum roots, all strewn as though by a gentle pillow fight. We paddled past managed shorelines with tidy cottages to this neighborhood of lily pads and pickle weed, hidden from their sight. More happens here, like the basement daycare center chorus with children, all of us cluttered, doing a better business than the church. This is the water's sweet meander, slow channel, where more dancer, mallard grew. It's also where the storm cloud races through. My grandson cried when he gave up his first and favorite fight, the one he trusted enough to let his feet release the ground. I had to argue with myself against the urge to dry his eyes, hurry him along, stop, honor that lonely human sound. Two young ducks try to keep one bend upstream from us, trapped by our invasion. They finally stop, one leaps to flight, the other hides behind the marsh grass in a small alder pocket.  It quivers as we pass. Six summer weeks, this was their home and world. Now they leave for something new. I think, detachment, that's a vision too. We first approached a heroin rose up like a scarecrow taking flight. It might be in the next pool, playing its silent heroin tricks. But a beaver pond opens before us, flood at eye level. No heroin, just water seeping through a thousand sticks. This summer we went up five streams. The beaver, always there, insists it's the effort, not the dam that's permanent. We put off our leaving, poke up every bull rush alley, give in at last, turn, stroke hard across the open reach, land on the expanse of beach. Women in bright saris watch their boisterous men play tag, joined by the youngest daughter. We greet them, lift the boat, and leave our visit. So I offered, if anybody wants to stay and offer feedback or anything that would be great for me, otherwise, you are dismissed. Yes.