Pakorongo akeau ki te tangi a te manu e re re rungarawa e Tu i tu i tu i tu i a tu i a ki runga tu i a ki raro Tu i a ke roto tu i a ki waho Tu i tu i tu i a ti hei mauri ora Ka mihāroa ki a koutu e ngā mana, e ngā reo, e ngā hau e whā Te nā koutou, te nā koutou, te nā tātou katoa Kia ora mai Te kuhere Te kuhere Te kuhere around a year and a bit, comes from a civil engineering background and also a leader of a eco-education program based out of Hawkes Bay, Koromai Tato.  Congratulations to the organisers, this is an awesome place to share and we're very excited to put some of our thinking up for you to take a look at, tear apart, give us some new bright ideas. First of all, this ecological resilience, the challenge and the opportunity. So, what do we want to do? We want to talk a bit about the opportunities that are out there in terms of this challenge. Outline the challenge, talk about why it is an opportunity for New Zealand and give you an update on some progress that's being made there. Before I do that, I just want to talk a little bit about next foundation. How many of you know of the next foundation? Quite a few I think, yeah. So this was a foundation endowed by Neil and Annette Plowman, a couple from the far north. They live in Kerry-Kerry most of the time and they're passionate about New Zealand's environment and education and they're passionate about them because they see them as two of the game changers for New Zealand. So they created this wonderful foundation and we set it up in March 2014. We've got $100 million in the bank account and we've been told to spend it over 10 years. So this is not a fund that's going to work off the interest, this is a fund that's spending the capital to make a difference. And we're interested in projects that are transformational and that are sustainable. So large scale projects that could transform the New Zealand landscape and that are sustainable for the future. Okay, so we're looking at a legacy for New Zealand in environment and education for future generations. So I wanted to start back at the beginning in terms of our environmental programmes and I'm not going to talk about the education programmes at all today, just the environmental ones. But going back to the beginning, why is this a challenge and an opportunity for us? So 80 million years ago thereabouts New Zealand separated from other land masses and for 80 million years we've had a unique process of evolution here in the development of our species. We've got some curious characters. Some of you will have met these guys, so the Kiwi, the Tuatara, our living dinosaur and this guy, the carnivorous Lensnail, the Palafanta. Some of the examples of species that have been around for very, very long time in New Zealand. So we are blessed with a great variety of species that are unique to New Zealand. We were pretty late coming to the Human Party, that's been talked about in the last day or so. So somewhere around the 13th century we had the Polynesian settlement or start in New Zealand. Much more recently Abel Tasman, 1642, the start of the European colonisation in New Zealand. Those other species have been here for very long time and we've been here for kind of a nanosecond really and it's extraordinary the amount of damage that we've managed to do in that time. You've also learnt that we only have bats as terrestrial mammals. So the really unique thing about New Zealand is we are a country of birds. The mammals all came later. The mammals came for various reasons. One of them was that European settlers arriving in New Zealand thought it was a bit of a strange place because there was not much to hunt and there wasn't very much that was familiar at all and so they set about trying to turn it into some form of what they were used to in Europe. There was also a bunch of accidental introductions to New Zealand, the rats that came down the ropes of the ships and so on. So big changes in a very short period of time. So we got all these guys and others. You've got goats there and rats and stoats and possums and over on the far side the wasp which is a much more recent introduction. Exotic pests in New Zealand eliminate something estimated 24 million birds per annum. Oops, this is interesting. We've got 800 species at least and we don't know all our species by any means but of those species we know which might only be 25%, 800 of them at severe risk of extinction. There are many iconic species, flora and fauna that are seriously endangered and the current investment is not holding the line. It's not dealing to the problem. There are potential new risks coming from climate change. We talked a bit about that yesterday and we'll talk a little more about what those might be. So we've got this opportunity with an amazing landscape and biodiversity and in many ways this landscape and this biodiversity is a version of other things that people use as huge tourist attractions in other parts of the world. So the pyramids or the Roman ruins and so on. These things are used as tourist opportunities from different countries around the world and our big difference in many ways is this unique biodiversity. We also have an integrated and integral indigenous culture here which is a long relationship with the species that we have. Biodiversity is deeply embedded in the national psyche and it's increasingly known and valued by people all over the world and so we see our tourist figures go from 2 million a year, 13 years ago to 3 million this year and a forecast that it could go to 4 million in 4 years time. Amazing acceleration and most of those people are saying they're coming here to see New Zealand's nature or to enjoy New Zealand's nature. So in that sense it's a key economic and social advantage to the country. Somebody said New Zealand's biodiversity is the closest thing on Earth to visiting another planet. Kind of an interesting comment. So how is next thinking about the challenges associated with this? Well we started with pretty small beginnings. Rotorua Island and the Hauraki Gulf, anybody been there? One or two off the end of Waiheke. Small project to transform an island and to return it as a new park to the people of New Zealand. We moved up a scale in 2012 to the Able Tasman National Park so from 83 hectares to 22,000 hectares with a project extending over 30 years with three key phases. Securing the park against the negative and the negative influences in the park, which were the pests and the weeds and some other challenges. Restoring the biodiversity to the park. Many species that have been lost, others in very small numbers in the park and thirdly a future proofing piece. So how do we engage the community? How do we get the kids involved? How do we create the future custodians of that project? We're four years into that, we're making good progress and as we had hoped it's proven to be a model for what we might consider supporting next. In the case of the Able Tasman we put in place an arrangement with the government which we call the Tomorrow Accord. So one of the issues for us is that we don't want to create endowment funds that are going to generate the funds to look after this place forever but obviously it's going to have to be looked after forever. What we think we can do is invest in the transformation so we can set some targets out there for the indicators of ecological transformation for the park and we can go after those and when we realise those are responsible we'll be over to somebody and somebody in this case the logical person to hand it over to is the government they've got the deep pockets they're responsible for our national parks so we have an accord with the Crown that says if we can achieve these ecological outcomes or when we do and that might take us 15 or 20 or 25 years but when we do we'll have this arrangement. Part of that deal was that we would then start looking at the next projects that we would take on and that's the one that I'd like to yarn to address now. From the summer beginnings of Rotorua Island and Harukih Gulf Aval Tasman 29,000 hectares we're now moving on to the largest project that NEXT has actually invested in and it's not just large in expenditure it's also large in complexity it's the first time we've involved a true community collaborative partnership and we're just beginning that journey now it's been two years of incubation to get to just starting and we get to form the proper governance and management structures to make that work well. So just for some context the park itself and the conservation land around it is about 30,000 hectares, 38,000 hectares and the primary aim is to eradicate predators from that mountain and suppress to very low levels and then relocate the native natural flora and fauna back onto it. So here we have Mount Taranaki National Park the Pauakai Mountain Range and the Kaituki Mountain Range and also we've included Ngamutu the islands in front of New Plymouth which are also going to be restored as part of this project and partnership with us we'll be working with the regional council in that region and the community who are already involved in wide-scale possum suppression throughout the whole region. So with our 38,000 hectares of restoration that we'll do on the mountain we can augment a very powerful halo using the regional council community and the community itself. So this is the first real leverage model for NEXT where our funding is making up around 20-30% of the total expenditure it's where DOC has reorientated some of its funding to also leverage with us but we can bring in other partners as well. DOC is a primary partner in this as are Iwi there are eight Iwi in the Taranaki area and they for the first time have come around and met to agree on how to work together on this project. It's quite a big step in the journey for New Zealand I think. It's the second tomorrow qualifying project which Devin mentioned earlier and as I was saying as we build and restore on the mountain the potential for the halo to grow is quite significant. There will be opportunity for community trust and other corporate responses to play a significant role in this. So you can imagine the complexity that comes with developing a project of this scale. So over time we'll build to 80,000 hectares around the mountain and beyond potentially the whole landscape of Taranaki. We believe only at scale can we secure the ecological resilience that's necessary for sustainability. Kia ora. So ecological resilience, why does this matter so much to us? Well, we know New Zealand biodiversity continues to decline. We know that climate change is going to act impact in a number of ways. A couple of obvious ones are the direct impact through changes in temperature, changes in rainfall. But another one that I think we really have to focus on is the distraction of government once these things really start to hit the investment that's required and infrastructure and change to deal with changing patterns there. So there's a kind of a window of opportunity if you like to address some of this. Those climate change effects are already visible and they're going to be a portfolio of properties which if we could put them into the right kind of state would make a big difference for biodiversity in New Zealand. So we think the answer is in securing a suite of representative properties across the New Zealand conservation estate and ensuring that the populations of species on those are in good shape, ensuring the effectiveness of biosecurity around those sites, engaging the New Zealand public and taking action now. We don't have a lot of time to wait in this process. So we've identified a suite of properties with the assistance of the Department of Conservation. This is not the final list and we're not saying that NEXT is going to tackle all of these projects either. But if we were to put this suite of properties into a state where the biodiversity on those sites is no longer battling pests in terms of climate change. So some of you will know these properties well and I'm just going to flick them up there and I'm not going to talk to each of them. But two pieces of reasoning behind this. Firstly, they're all substantial in terms of the biodiversity that exists. Secondly, they're quite different in terms of actual biodiversity on those sites. Thirdly, some of them, like Mountain Taranaki, provide a range which allows species to flex their position. Thirdly, there's also a latitudinal range there and while there are not corridors joining all of these places there is an opportunity to shift species at some point in time if that became essential to preserving the biodiversity. But there's more and one of the really exciting things that we're working on is this concept of predator-free New Zealand. So we can put these the suite of properties but actually at the end of the day we would really like to deal with predators in New Zealand and in this case I'm talking about the three big ones, the rats, the stoats and the possums. And there are kind of three critical challenges in here. One is a technical one. Can we actually do this stuff? The second one is a financial one who would pay for it if we were actually going to do this and one of the biggies and perhaps the one that we've made least progress on at this date in New Zealand is really want this and are they prepared to make the trade-offs that might be involved in the various methodologies that need to be deployed. So I'm going to ask Al just to talk a little bit about zip and what zip contribution could be to predator-free New Zealand. So i kiwere, everybody. My name's Al Bramley and it's good to be here. I came last year so I said last night I'm a serial offender. I'm a technical world all these different perspectives on the problems I face. So keen to tell you a little bit about some of the technical detail.  So firstly, what does it do? I'll let you read that but the key things here are we're going for zero. We often talk about predator-free but we mean predator-low. Now the difference here is if we go to zero for the rebounding populations. OK? So I'm trying to shift to an economic model which means that once we've cleared it out and it might cost a lot up front but once we've cleared it out we keep it down. I'll tell you a bit more why. But first a little word about me. I picture of my daughter Maddie because she's so cute. We talk about reconnecting kids with nature. I totally attest to that. My kids love nature and they totally value the environment and they train. So the reason I've got my daughter Maddie up there because she's holding a kiwi and was involved in a kiwi cover project with Roode and others a long time ago but most people don't realise that if we don't eliminate stoats or if we allow stoats to run through our landscape 95% of kiwi chicks get killed which means slowly kiwi go to extinction everywhere we don't look after them which is most places. So they're very sensitive to stoats. The other thing is unlike most places in the world if you stop cutting down your habitat and you stop hunting the things you care about your biodiversity recovers and I don't know if you guys realise this yet but it does not like that here in New Zealand. We've pretty much stopped cutting down our habitat we've got this wonderful 1 third of the country that's set aside as Department of Conservation and Estate but the trouble is a whole lot of our species are still going to zero are the things we care about so we have to do something at the moment we have to kill stuff in order to maintain our native species. Right, so as Devon mentioned there's three predators that we're focused on rat, stoats and possums simply because they cause a threat of the ecological damage. Yes, cats are in that equation as well but to be honest socially complex we'd rather stay away from it for now so if we crack it if we crack it for these three then we'll go and have a look at cats maybe but we might let Gareth Morgan lead that one he's doing quite a good job stirring up the world Okay, so why do we think we can do this? Quite simply we used to think we couldn't do this at all we started on some offshore islands and we didn't even think we could do one hectare island and surprise, surprise we cleared the rats off it it was back in the 60s and then we got onto bigger projects like Cuppity and in the 80s and 90s we managed to remove rats and possums off it now I think here the really interesting transformational lesson is that in the 70s the Forest Service that was looking after these places wasting money if you try that now we know it's a really cool technique and within 20 years that ecology has rebounded to something amazing if you get a chance to go to any of our predatory islands go they're not like the mainland they're full of life so we've started in the Marlborough sounds we started with 30 hectares in the sounds we're a little bit braver than maybe our predecessors and about two years ago we had a crack and so to our surprise it didn't look like it was going to be impossible we were a bit confounded by size and it didn't work perfectly but with the help of the next foundation we decided to scale up to this site which is about 400 hectares now and we established a zone in purple there across the peninsula where we tried to stop every rat and every possum went back onto that place once we'd cleared them off and at the moment we leak about 1% of those animals that try and get in so it's not perfect but no barrier is even if we got it to 100% somebody would drive along on a boat and accidentally let a rat off or one would swim from somewhere so we need the ability to detect and remove before things become a problem but the technology's coming so how are we getting on well I just want to show you a removal what this looks like every little skull and crossbones there is a rat and every little dot was a place that they were chewing a little peanut butter card because they love peanut butter they can't resist it and over time there's about a year's worth of time there we got them to zero we didn't use a neural toxin operation largely because the consenting process was long and we wanted to get on with it and it was costly it took cost us something like $550 a hectare to move every last animal with people walking around laying traps and using toxins in bait stations but we got there took us 12 months and since then we installed all these devices so there's a good nature trap on there the gas-fired one that kills repeatedly when an animal sticks its head up in the hole there's just a good old slam-it trap in there which are perfect for catching rats and also there's some other devices on there and there's a leg-hold trap for possums and to be honest that's pretty controversial but I put it up there deliberately because it's our most effective trap by a factor of five we'd love if it wasn't but the tech hasn't got to the point of having a better trap so we're currently still using that trap and on the end it's a bait station and there's all sorts of mix about toxins we try and use the minimum of toxins we use it last but we'd love not to use it in fact so far we've now got to the point we don't need toxins for possums which is a really cool milestone for us and we introduced some smart stuff and this is where I think just a little window on where we're going to go in the future so on the left there there's a little platform screwed to a tree and that's so that our ground-nesting birds weka can't interfere with this little device it's a detection device so I talked about the rats can't resist peanut butter well if you take a piece of real estate sign jam peanut butter into the core and then mount it on a little stand the rats climb the trees and chew away at those little cards so if you turn up the next day you see tooth marks and you go I know there's a rat here but that's all laborious you know it's a lot of walking so what we decided to do was attach some electronics to it that meant that when it was wiggled we'd get told automatically and so we've done this now all of these little devices talk to each other via UHF radio then they get to a satellite box goes up to the space and within an hour I know if that site's been chewed and that's a whole different ballgame for response because I know he's still there whereas I turn up tomorrow I don't know whether it was last week or whenever it was that I was last here and where it is now it will have moved on so the speed of information is critical here to managing this quickly and on the right's just another picture of another type of device rats love running through tunnels so we've taken that same device and we've stuck it in a tunnel because often it's a system of tools not one tool that we need in order to solve this problem another thing that's been key to us achieving what we've achieved is the collaborations we've got going on so Lincoln University have built a massive predator pen we've spent quarter of a million dollars building a massive pen that we test everything before it goes to the field saves us a lot of time so we're currently working on deterrent type tools something that's completely missing from our toolbox and lastly I'm going to tell you a little bit about some detail around stoats stoats are the animal we haven't tried to date because they run so far and so fast so the first thing we did was fit a little transmitter around their collar and then we let them go and of course they're causing lots of destructive damage but at the moment we don't know enough about them in order to manage them so we let one go out on the end of the potential of the end that's called Palin you'll see there's a theme coming on here and Palin was a Palin represented by the yellow cross there ran all around the end of the peninsula sort of bouncing about a cave backwards and forwards and then T you can probably guess what that stands for T for Trump a little bit of a worry Trump and Palin's been quite a bit of time together early on which I don't think was good for world politics and the last one Romney he's the red guy there and oh it's not the red guy the red sort of hat looking thing he took off straight through our barrier we set this barrier to try and stop him and he just ran straight through it he completely ignored us so anyway he's left the party Romney now which is appropriate as well so anyway you can see what we're doing is gathering the base behaviour of information so that we know how to manage these guys and doing some pretty cool stuff along the way having a lot of fun and just to give you an idea where Romney went I don't know if I can point with this thing but he was right up the top of the map there last time we tracked him in fact we tracked him again this morning I got a text from the guys to say they'd found him even further away but another three Ks to the east and the only way we can do that is using aircraft and we use a light plane that scans the countryside automatically talking to a computer building a little signal map that means he's there but the tech is coming to our world and it's really exciting completely blowing my time aren't I so lastly the future what does it look like a whole lot of techs coming UAVs are going to be a cool tool for us they're going to get us remote places but there's image recognition we're hoping to use that in the future there's a whole lot of autodispensing technology we want to bring to bear and there's a whole lot of ideas we haven't even thought of yet which is why we were so keen to connect with your guys world so thanks okay so we're not going to spend a lot of time on these last couple of slides but just for completeness one of the interesting things about this we don't know exactly how much New Zealand spends each year on predators but if you combine what central government spends what local government spends what private people spend and the cost of the damage that rats do in our agricultural sector and so on we think it's somewhere in the order of one and a half billion dollars a year which sounds like a pretty good war chest nature underpins our 18 billion dollar and growing tourism industry and we need to find ways to get more investment out of the tourist sector and out of the agricultural sector to go after the challenges that we've got here but it has threatened our agricultural economy not just directly in terms of the loss of food and so on but also the reputation and so this real gain is to be achieved by getting rid of those guys and that threatens our New Zealand brand so one and a half billion dollars per annum and biodiversity is still declining so we actually need to do something completely different here we need a new strategic investment model around this space just talking briefly about the social licence so we've heard a lot about reconnecting with nature and one of the keys to this is going to be to continue that so that as we come to communities and we say we need your help to make your part of New Zealand free of these species and it's going to compromise certain things there'll be some biosecurity issues and we'll need to get rid of toxins in some places we'll need to put a trap in your backyard or whatever we need that licence to do that on scale this is a positive uniting vision for something it's something we can take action on we've talked about it for a long time it's been kind of out there in the ether it's something we'd really like to do the technology is getting us to the point of saying actually we might just be able to do this and the examples that we're putting together in Abel Tasman, Taranaki, Cape to City and other projects are starting to give people confidence we can actually go after this thing the idea that we can transition to a low maintenance cost so not a billion and a half a year but a small proportion of that long term to maintain the biosecurity and also one of the critical things is we may need to use an aerial toxin on part of the estate but it's a different conversation with the community if you can say to them we're only going to use it once and then we can defend the space against reinvasion if you go at the moment and talk to people about we're going to do it now and we're going to be back in three years time to do it again it's not a very encouraging conversation to have with the community another big opportunity I think is that we can provide a model here so it's again this idea that there's very much behind you frontiers of how do we do things here and develop technologies here that have wider application to problems around the world and some of the smart tech stuff that we're working on certainly well it's all about leaving an outstanding legacy for our grandchildren we also thought we should ask for your help directly so this question of reconnecting with nature how do we go about that you guys have got some ideas about that how do we fund a predator free campaign what are the smart ways to actually do that and Al's Big Challenge how do we detect predators in low numbers we can knock them down to low numbers then how do we know that one's just arrived and how do we deal with that and we need some smart ideas in that space so maybe I'll just leave that one up for the conversation and we'll see you next time.


Thank you very much for the introduction. My name is Jiaxin Guan, and today I'll be talking about our work, Simple Schemes in a Boundless Storage Model. This is joint work with Mark Gendry. Both of us are from Princeton University. So I'm going to start off the talk with a quote from Joe Kiden in year 1988. Cryptographers seldom sleep well, and their careers are frequently based on very precise, complexly theoretic assumptions, which could be shattered the next morning. I don't know if it's true for you guys, but sometimes I do have trouble falling asleep, or maybe not of this reason. But anyhow, it is true that traditionally when we build cryptoprimitives, we're basing the security of the cryptoprimitives on some complexity assumptions. For example, maybe factoring is hard, or maybe discrete lock is hard, or maybe the hardness of LWE. However, for some reason, if maybe, for example, with the existence of a quantum computer, we're able to actually break discrete lock, then consequently, the security of our cryptoprimitives will be broken as well. And therefore, the question is, is there any way that we can actually have some good sleep without using any maybe sleeping aids or visiting a psychiatrist? Or in other words, can we build cryptoprimitives without any complexity assumptions? Well, of course, here's the naive solution of the OTP, but is there anything more sophisticated that we can build? It turns out that the answer is yes. So in 1992, Yuli Mora gave out the concept of a bounded storage model under which such security proofs are actually possible. So what is the bounded storage model? So traditionally, in cryptography, when we talk about an adversary, we need to somehow bound the adversary's computational resources. And there are mainly two directions, namely, the two dimensions are a time and space. So traditionally, the adversary is bounded by time. The adversary has only a certain amount of time that he can use to execute his algorithm. So usually, we talk about efficient algorithm that needs to be finished in polyn. However, in a bounded storage model, the adversary can have as much time as he want. He can run the code forever. However, there is a bound on the amount of memory used by the adversary. And in this specific model, it is bounded by a fixed polynomial, p of n. So in this talk, you can think about p of n being on the scale of n squared. So what is the intuition behind the bounded storage model? The idea is that the two honest parties, they exchange so much information that for an adversary here, with a bounded storage, you cannot possibly write down all of the information being transmitted. So it turns out that in this model, it's actually possible for us to give unconditional proofs without any complexity assumptions. In addition to that, the bounded storage model also guarantees everlasting security. What does that mean? So for example, Alice is sending some encrypted message to Bob today using RSA encryption with the secure parameters. And unfortunately, there is an eavesdropper eave who intercepts the message. Well, because it's using secure setup of the RSA parameters, eave, of course, could not see what's the actual message. However, eave could just make a copy of the message. And then eave waits and waits and waits until 50 years later, he actually get access to a quantum computer. And he used that quantum computer to actually factor the RSA modulus. And then he will be able to decrypt the message and somehow figure out that it was actually some funny cat picture from 50 years ago. So however, for the bounded storage model, there is no such concern. Because at the time that the conversation happened, the adversary has not enough space to possibly write down the entire transcript of the conversation. So in the bounded storage model, we can actually achieve everlasting security. So with all that said, you might be wondering what might be one possible construction of a protocol in the bounded storage model? So actually, most of the previous work in the bounded storage model is based on the birthday paradox. And we will look at an example of a key agreement protocol, which is proposed by Yudi Mora in the original paper, which is based on the birthday paradox. So there's Alice and Bob. They want to achieve a key agreement protocol. In other words, they want to output a key, a shared key. And in the bounded storage model, in the original model, we assume that there is a public source that is broadcasting random strain. And you can think about it as there is a long random strain and there is some guy sitting in front of a radio station reading out the bits one by one. And Alice and Bob and all the other parties in the game are just sitting in front of the radio and listening to the broadcast. And you can write down what bits you want to write down. But once the broadcast is over, you cannot listen to it again in addition to what you've written down. So here we have random strain, which is n squared bits long, where n is the security parameter. So here I give an example of where n equals to 4. We have a 16-bit length strain. So what Alice is going to do, she's going to pick n random indices out of these 16 positions. In this case, you pick four indices out of these 16 positions. And then you're going to write down the corresponding bits at those locations. In this case, Alice is going to write down the first bit, seventh bit, 12th, and 15th bit of the random strain. And Bob is going to do the same, except that Bob has his own secret set of these random indices. And then the broadcast is gone. You can only look at what's written down. You cannot consult the strain again. So to initiate the key of Riemann protocol, Alice will just simply send over her own secret set of the random indices over to Bob. And Bob is just going to compute the intersection between the two secret set of indices. And by the birthday paradox, with a constant probability, these two sets are going to have something in the intersection. And in this case, it's the index 7. And hence, Bob just sends back the index 7. And Alice and Bob will just output the seventh bit in the common random strain as their shared key. Notice that for an adversary, if the adversary wants to output the key with probability 1, the adversary has to write down all the n squared bit strains. If the adversary only has access to a small portion of these n squared bits, the information that the adversary has about the final shared key is very limited. We'll point out there are some issues with this game. First of all, it succeeds only with a constant probability. If there's nothing in the intersection of these two sets, well, I don't need to repeat, or we need to somehow increase the two parties' storage in order to increase the probability of having an intersection. Secondly, actually to store all of these indices, you require more than o n space. You require actually big o of n log n space, which sort of decreases the gap between the adversary and the honest parties. Well, this can be solved using pairwise independent functions, but this adds on to the complexity of the scheme built upon this. And lastly, notice that when the broadcast is going on, an adversary can always make a guess for the final index that's going to be chosen by Alice and Bob, and just record a bit at that location. Notice that the adversary can guess the index correctly with probably 1 over n squared, which is non-negligible. So in order to make it actually secure, another privacy amplification step is applied also adding on to the complexity of the scheme built upon this protocol. So as a result, previously in the Boundless Storage model, all of these constructions are based on the birthday paradox. We have a key agreement scheme, which has imperfect correctness. And the best known results for big commitment and OT protocols are based on a previous result by Yen Zong Ding et al. in 2006. And the result is that they have a five message protocol for OT, which leads to a five message big commitment scheme. In our work, however, we first show that there is a key agreement protocol which achieves perfect correctness as opposed to imperfect correctness before, as well as we demonstrate a big commitment scheme that is one message and an OT protocol that it only takes two messages. Notice that one message and two messages are round optimal for big commitment and OT, respectively. All of our constructions rely on something very different from the birthday paradox. In fact, we rely on the recent lower bound in priority learning proved by round rise in 2017. So what is that lower bound about? So that's going to take a few minutes and look at that. So now let's have an exercise, just so that you don't feel sleepy. So I have some string, say k. The string k has five bits. And each of the bits is represented by k1 all the way up to k5. In the next few slides, I'm going to show you a few equations. And at the end, you need to tell me what k is, OK? Cool. So here's our first equation. Second equation, third, fourth, fifth. OK, now tell me what k is. It's kind of hard, right? 0 is actually not a correct answer. But so however, it's actually really straightforward. If I just give all of these equations to you on the same screen, you can just use Gaussian elimination to figure out that k is actually 1, 1, 0, 0, 1. However, the idea is that when I'm streaming these equations to you, you don't have enough memory to write down all these equations so that there's very limited amount of information you know about the key k. So let's formalize this a little bit. So first of all, we expand out these equations by adding the missing terms with coefficients of 0. And then we figure out that we can actually write them as an inner product between a vector and a secret vector k. So we're going to represent these vectors, call them r's. And for the inner product values, we'll just call them a's. So now essentially what we have is just a whole bunch of equations in the form of ri inner product with k gives us ai mod 2. If we further rewrite it, we write it essentially for each equation. It can be represented by a pair of values, which is a vector r and a numerical value ai, which is just the inner product between ri and the k. So here, we're using the dot product to represent the inner product here. And everything is carried out mod 2 so that bear that in mind. So plus will actually be just xor. Now let's actually jump to the actual lower bound. So it's defined through a game. So here's the adversary. The adversary has a space, which is cn squared for some small constant c. Here, we actually require that c to be smaller than 1. Because if the c is actually greater than 1, you can actually just write everything down. So as a challenger, we have a secret key k value that is hidden from the adversary. So we're going to send over to the adversary a whole bunch of these equations that you've just seen. It's represented by these pair of ri and ai values. Actually, we're going to send over m pairs of these values. And at the end, the adversary needs to make a guess for a k. What RAS has proved is that as long as the number of queries we've sent is less than or equal to 2 to the alpha n, where alpha is a value dependent on the constant c. In other words, as long as we have less than exponential number of these pairs or these equations, the probability that the adversary is able to guess the key k correctly is exponentially small. That directly gives us an encryption scheme, which is also performed by RAS in his paper. So if Alice and Bob wants to encrypt the message, they already have a shared key k. And if Alice wants to encrypt a message m, all that Alice needs to do is to sample a random r and just mask the message with the inner product of r and k. And to decrypt is very straightforward. Bob reproduces the inner product and masks the original message, or masks the ciphertext with the inner product. Notice that here plus is actually XOR. So it's sort of like one-time path. You XOR it twice. You get back the original message. In fact, we can repeat this process many times. Alice can send as many of these messages as she wants, as long as it's less than exponential. So one thing to know about this scheme is that it's additively homomorphic. If we have two encryptions, r0, a0, and r1, a1, if we add them together, notice that the second term a0 plus a1 actually expands out to this, which actually turns out to be an encryption of m0 plus m1. And the security of this scheme directly follows from the lower bound that RAS has just proved. Essentially, we can construct an adversary that breaks the parity learning game from the adversary that breaks the CPS security of this scheme. So moving on to that, for today's talk, we'll be focusing on introducing our bit commitment scheme in our paper. And with this directly follows from the encryption scheme that we have just seen. So what's a bit commitment scheme? There are two parties, the committer and the verifier. The committer has a bit B. And they're going to sort of have some initial conversation between committer and verifier, which we refer to as a commit phase. And later on, at a later point of time, the committer is going to stand over a revealing of the bit B. Well, it usually consists of the bit B and some auxiliary data that allows the verifier to verify if it's a valid commitment. And then we call this reveal phase. And then verifier is going to output either accept or reject based on a commitment and the revealing that it has received. There are two desired security properties of a bit commitment scheme. So first of all, we're quite a hiding property. Essentially, we say that after the commitment phase, the verifier should have no idea of what the hidden bit B is. Well, this is sort of straightforward. For the binding property, it's slightly different. We need to have a security game to define this. So the committer is going to carry out the commitment phase just as usual with the verifier. And at the end of the commitment phase, instead of revealing a single bit B, the committer is asked to make two revelings. Essentially, the committer needs to reveal to both 0 and 1. And the verifier is going to verify these two revelings and output accept or reject. We say the committer wins the game if it's able to trick the verifier into accepting both openings of the commitment. Well, then we say the commitment scheme is binding if Alice, as the committer, cannot produce such two openings of the same commitment. So now, let's take a look at our actual construction. We call it take1 here, because here, bear in mind that in this construction, it's only secure against an honest but curious committer. In other words, the committer will abide to our protocol, but will try to get as many information as he wants. So Alice has a bit B. And to set up, Alice will just have a sample random secret key k. And in the very beginning, Alice is just going to send over a whole bunch of these equations that look like this. Now actually think about what are these? If you look at each row, essentially we have a random vector r and an inner product between this random vector and the key k. In parentheses, x wrote with 0. So in other words, each of these rows is an encryption of 0 using the key k, using the encryption scheme that we've just talked about. So now we have a whole bunch of encryptions of 0s. Now, once we have those encryptions of 0s, what Bob is going to do is take a random subset sum of these encryptions of 0s. So how is Bob going to do that? Essentially, you're going to have a random bit for each row, and if the bit is 1, you just add that row to your running subset sum. So in this case, if we let x to be the subset sum of the r's and y to be the subset sum of the a's, this is what x and y will look like. All right. And if we actually then look at all of these conversations together, all of these messages, we can actually, if we put the r's, the r-r vectors, into the rows of a single matrix, we can rewrite this whole thing in a matrix form. Essentially, we just send over two matrices, not two matrices, a matrix r and a column vector a, which is equal to r times k. Correspondingly, we're able to rewrite the subset sums in that j is now a row vector, and x is just equal to j times r, and y is equal to j times a. So j is a row vector you can think about as j. Essentially, j tells you which rows from the r matrices should you select and sum up. Once we have that, to finish up a commitment, to actually commit to bit b, Alice just needs to send over a encryption of the bit b using the same key, k. Later on, to reveal the commitment, Alice will simply reveal the bit b and the secret key, k, used for all the previous encryptions. And to verify, Bob will check two things. First of all, that indeed, the secret key, k prime provided by Alice indeed decrypts y to 0. That's what the first equation is essentially saying. And the second equation is just saying that using the secret key, k prime provided by the committer, actually you are able to decrypt the commitment back to the bit b prime. So now let's take a look at why the scheme is hiding. So essentially, for hiding, we're required that at the end of the commitment phase, the adversary has no idea of what the bit b is. This is actually trivial, because notice that all that Alice has sent is just a couple of encryptions of 0 followed by an encryption of b. Because the encryption scheme is secure, well, the value of b is hidden from the adversary. Because b is encrypted using k. So for the binding, it's slightly more complicated. But let's take a look. So here we're going to run the same commitment phase again. And at the end, the adversary needs to provide two openings, essentially 0 and 1. Open to both 0 and 1 with the two different keys, k0 prime and k1 prime. And Bob is going to check two things that both openings are valid. To check the first openings are valid, think about these two things. Checks that y is equal to x times k0 prime, and a prime is equal to r prime times k0 prime. I'm just rewriting the conditions that Bob needs to check. And Bob needs to check again that the opening for 1 is also valid, which looks like this. So now think about, because the adversary only wins when all of these four conditions are met, if we write the two of the first equations together and combine the two second equations together, we actually have these. First of all, from the second rows of these two boxes, we know that k0 prime is not equal to k1 prime. And from the first rows, we know that x times the difference between k0 prime and k1 prime is actually 0. Well, what is this? This is actually equivalent as saying that we have some linear equation x times k prime not equal to 0, and you need to find some non-trivial root for that linear equation. Now think about why this could be difficult for the committer to do. We set our security parameters for m to be equal to 2n. So in that way, r is a matrix of 2n times n, which is a tall matrix. Because it's tall with very high probability, r is for rank. And if r is for rank, we can see that x actually appears random if you don't know about j. And therefore, from the view of the committer, you need to submit some k prime that satisfies a random linear equation, which you can do no better than a random guess, which essentially you pass with probably a half. So in this way, the verifier is able to catch the committer with probably a half. If we want to further boost this probability, it's very straightforward. Instead of keeping one single subset sum, you can multiple of these subsets sums. And therefore, you will be able to catch a cheating committer with a higher probability. So however, all these things are based on the fact that the committer is actually honest but curious. If the committer is actually malicious, he can actually generate the matrix r not randomly. He can deliberately choose the matrix r to be of low rank. And therefore, x will just no longer appear random to him. And you can easily find a k prime such that the equation holds. So to counter that, we only need to make some very small modifications to our scheme. So now instead of having one single key, Alice is going to have two different keys of different lengths, a secret key k and a secret key s. And in the beginning, Alice is going to still stream over a whole bunch of encryptions, but this time no longer of encryptions is 0, but rather of the bits in s. And after the streaming is over, then Bob is going to still do the same thing. He's going to take a subset sum of these streamings of the encryptions. And at the end of the streaming, Alice is going to send over the key k used for to encrypt all of these encryptions before. And Bob is going to do some simple math on his end. Given k and the x and y that he has recorded before, he's going to calculate z equal to y minus x times k. Trust me, if you do the math, you will get that is equal to j times s. All right? And Bob no longer needs to memorize what x and y is. All that Bob needs to know is j and z. And to commit a message, it's still the same old trick. You encrypt bit b using the secret key, but this time no longer using k because, of course, you already sent over k. You encrypted using the secret key s, which you haven't sent to the verify yet. And to open the commitment, it's still the same old trick. We revealed a bit together with the secret key that's used to encrypt a bit. So now what Bob is going to check is that essentially that the secret key s, s prime sent by Alice, indeed decrypts z to an encryption of 0. And secondly, that indeed, s prime is the key used to encrypt a bit b prime. So notice this is kind of similar to the previous scheme, but notice that recall that in our take one, at the end of the commitment phase, what Bob has recorded is y and x, such that y is an encryption of 0 under the key k. And here, at the end of this commitment phase, what Bob has recorded is j and z, where z is an encryption of 0 under the secret key s. However, there's a crucial difference here is that notice that x, if the adversary is actually malicious, x will not be random to the view of the committer. However, here, consider the value j. j is entirely chosen by the verifier, and therefore, even if the committer is malicious, j will be completely random to the view of the committer. Therefore, in this case, we achieve binding property even against malicious committers. So lastly, to sum up, in our paper, we present three schemes, essentially a key-wim protocol, a big-commitment scheme, and OT protocol. We stress that our big-commitment scheme and OT protocol are both round optimal, and we want to stress that all of our constructions are really simple as we have just seen. They don't have much complicated operations in there. So this brings us to the future work. We suspect that, and we're really confident that it's actually possible for us to build more sophisticated crypto-primitives from this parity-learning lower bound. So we encourage you guys to look at our paper, read our constructions of these three schemes, and think about if it's possible to maybe build IO or NICS from this parity-learning lower bound. And that's our talk. Thank you. Yes, you're welcome. Yes. The adversary is still a computational imbounded. The only restriction that we pose is that the adversary has the space bound. A simulator? Yeah, so the previous constructions, usually you require that any adversary can be simulated where the resources of the simulator are polynomial in those of the adversary. And the previous constructions of OT in the bounded storage model only satisfy the weaker requirement that even if the adversary is efficient, the simulator still needs to be computationally imbounded. So my question is whether your scheme avoids this caveat. Yes. So for our commitment scheme and the key women protocol, it's secure even if the simulator has the same memory space as the adversary. So in other words, it's secure for a bounded simulator. Yeah, the running time is always imbounded, but rather we're talking about the space here. However, for the OT protocol, it's slightly trickier because we want to show that essentially it's for the OT protocol is essentially for the sender security. We want to show that the receiver only knows one of these two bits. And there we either need to assume that the simulator has access to the receiver's secret coins, or we need to assume that the simulator has the power to rewind the receiver to run it over and over again. Because that's the only way that we were able to find out what actual bit that is interesting that we can simulate it. Any more questions? Again. Just a quick technical question about the model, so when you assume the attacker's memory is bounded, how fine granular is it like you kind of assume? So how short should be the message? So you send a message, he has this memory, you send the message, he has this memory. How long are those messages? Can your messages be like, I'm just trying to see is it like does your protocol critically use the fact that after every kind of short message, he has to condense to n squared? Or can the messages be kind of long? Yeah, you can think about that. The whole message is sent over as a bit stream, and you can read each bit only once. And in terms of practical security, if you think about an, say, honest user with gigabytes of memory, it turns out that it's like 10 to the ninth bytes. It turns out the adversary will need somewhere up to 10 to the 18 bytes, which is roughly, I don't know, thousands of parabytes, which definitely seems more intimidating than the gigabytes of memory needed by the knownest parties. So follow-ups to as the original work showed that these low bounds for parities actually hold for many other functions, like basically everything that is hard to learn. Could you find out, I can hear you. Yeah, so now we know, after follow-ups for the original paper, that parity is not just a special case, there are many other cases that will be hard, like that you can prove time memory trade-offs. So does these problems give you more power to construct primitives or you just stop with parities? Yeah, we haven't checked the follow-up work to the, you were talking about the follow-up work to the original TimeSpace Lord. Yeah, I think that there are already like four papers out or something. Yeah, we haven't checked that, but we suspect they would make, that essentially would give us more power in constructing our schemes. Yeah, thank you. Thank you, are there any more questions? Yes? First of all, thank you for the great talk. Is your OT protocol compatible with OT extensions? Is it even necessary to consider that? Compared to OT extensions or? OT extension protocol. Of this transfer protocol? Yes. So how our bit commitment scheme extends to the OT protocol? Yes. OK, yeah, actually I can explain that within a few sentences, our OT protocol is very straightforward. Notice that our bit commitment scheme, essentially your commitment is just an encryption, and therefore our bit commitment scheme is actually additive homomorphic as well. In terms of your commitment tag. And our OT protocol is just that the receiver is just going to commit the bit that you're interested in to the sender. And sender is just going to use the additive homomorphism of the commitment message to calculate the two cipher tags for b times x0 and 1 minus b times x1. And notice that if you decrypt the envelope, you actually get xb and 0 times x1 minus b. So that's like the general idea, the actual construction. You can take a look at that in our paper together with the proofs. Thank you. Thank you. Thank you very much. Let's thank the speaker again.