About the talk
Let me know when I can start. You are good to go. Hi everyone. I'm Matthew Tchaikovsky. I'm doing the lightning Toc version of Crypt analytic, extraction of neural network models, destroy work with Nicholas, Carlini and helium are enough. And Nicholas. I give the 25-minute version of the talking made, all the slides. So he deserves all the credit for that. The main object of interest for this talk is going to be an adversary with black box access to a neural network model, 700 Network consists of two pieces,
the weights in the architecture, the architecture tells you how to use the weights to compute the function and then the adversary with black box access. Of course, means that they can choose inputs to the neural network and they will receive the corresponding outputs. This is a really coming set up in practice. So the way that this is happens, is a company will build a machine learning model and then they'll deploy it and allow clients to have to pay to clear yet. And these models can be really expensive to train. So opening. I recently released a model called gpt-3, which
costs $10 for training, run just to train. And so an adversary, a significant financial incentive to try to steal this model because, you know, they might not want to write that 10 million-dollar check. And so what we're interested in is the power of this adversary who has query access and potentially also access to the architecture at stealing the, the weights of the neural network. So the existing literature has taken, kind of two different approaches to this problem. The first, and the most, common is a machine learning approach, right? So, a very key focus of machine
learning is to learn the relationship between inputs and outputs. And so, one thing you can do for this extraction is you can query the model 1000 times and now you have 1,000 input output Pairs and then you can use machine learning to try to approximate the function that the Black Box computes the other approach. And the one that we take is a direct analysis approach. So by understanding the mathematical representation of the function, you can use it to reverse-engineer the the weights corresponding to the the neural networks Black Box. And so are our key. Question is whether with a
query access to this neural network, we can extract the hidden parameters of the model. And what we find is actually that. Yes, you can. Also there are several caveats that I can't get into in. This is how we do it with these beautiful animations that necklace made and actually explains in the 25-minute version of the talk. So you should go check that out. But what I do have time to explain is results, so you can see here. We have a 100,000 parameter, neural network model firework is able to to query this a million times
and they get every weight with two or more bits of precision. And we show how to do twice as many queries to 2 million queries and we get 29 or more bets of perception and we have better results for deeper networks as well. So they're at their three main takeaways that that we want you to have from this. The first is that neural networks are very commonly analyzed and other like a black box or even an anthropomorphically. But our work shows that direct mathematical analysis as them as a mathematical function can be a fruitful approach as well. The second is that secure
insurance, which is the secure multi-party computation approach to generating this black box query interface is only as secure as the query interfaces that stuff. So if an adversary can steal the model by making queries, it doesn't matter how secure the protocol for computing. Those queries is because the interface will be knowledge of the model. And finally, it's common in cryptography to model-specific, algorithms like a yes, as in sensations of some ideal functionality like that and ideal block Cipher. And it might be tempting to use neural networks to do such a
thing. But our favorite kind of shows that there are several properties of neural networks that maybe you should you should have caution about finding a sweat and so that's that's it and I think all of us are here to take questions now, So that is a question by Kevin. What do you think are the most important questions are genuine networks models by Kevin? Sure. Yeah, so I mean one of the big ones is like, how do you defend against this? I think there's a lot of different approaches and it's not really
clear which one is the best so far. And of course, like also improving on these kinds of attacks is, is really interesting as well. Cuz like I said, there are several caveats to, to our approach. That make it, don't not really working practice. The other authors have have more comments on that. This is, this is Aaliyah. I am and I would add to that a theoretical understanding all the ability of new on Netflix. So that's an open question that has been partially dressed. And some prior book. We provide empirical evidence that there the are available,
just understand you the theory of love that. A Faceoff that functionality is still open. And there's a crash that took questions in the zoom chat to versus by Jonathan. Can you come in at the last bullet? On this light? I was not sure what you meant. Yeah, Nicholas. Orillia is probably best for that one. And if you want to go get a new photographer, so, I think something that really understand that the parties agree on the implications of executive dysfunction, a Latias. At Lexington, millionaires problem. Like a x-large is
why would a X & Y, where a s Circle took you understand. What is your neural networks? There are complex their subtle and the just asking people to take on faith. That is a neural network of the heart problem. Christina asked if you don't give up confidence levels, doesn't block the attack. At least this attack. So that the learning approach, you know, that'll that'll work maybe a little bit worse because I mean machine learning lines from labels as well as from confidence, this attack. We, we don't know how to do it for confidence at least yet. But you know, who
knows in the next couple years, maybe someone will come up with a way to do that. Okay, there's the more more questions coming in so dumb and tell me when I should stop I think multi make more of a comment saying there's actually nothing I do security. So I guess what is also growing up on the audio functionality pads, but let me move on to questions from us. Have you tried to take me against gpt-3? And how complex is it compared to reach raining? Yeah, that's a good question. So like the only experience we have are in these trailers small neural networks, and we actually require a lot of
assumptions that wouldn't really holds like gpt-3. Queen. And yeah. I just like the concrete requirement is we we need something like six or more queries per parameter. And so like he's really big models. We would, you know, six times as many for a m at the hazard Aquarius, which could very well get big. Eleanor was asking if the attack also can learn something about the day that was used to train the new one at work. Yes, I mean this is this is something of a orthogonal question. Like, how so I guess like there are Black Box attacks that you can use to understand the the Privacy we
could just models and there's also a white box, a text. So F white box, attacks are better than Black Box attacks. Then extracting, the neural network is one way of doing better. I thought I'll do you know, this is a question. If you know you can train to make your mother more private and and whatnot. I think so. I think the time is, maybe I'll probably move on to the next. I'm trying to exit. Okay, just came up to me. See my screen. Yes. Okay. Should I go on? Yeah, you got a thumbs-up, okay. Good.
Thank you for watching. I'm in my near to me and I'll pay for it. There's no records. Aren't you related to Angela factoring and one red? And one of the things that we have in this one for 5:20 and one for this week. He's at the same time for the same size, which gives a nice comparison point. So we show that kryptonite is is for the sizes is feasible and you can still see products around that are increasingly relying on the fact that this is not very much time to move on. So
to do, this is Rick Ross. We use the number could see if I give my son, which is a complicated algorithm and most of what a great talk about 5 minutes with y'all sitting an onion. So. There's a really good for this Temptations. And we combined several techniques many of them right now and I have sent them being used specifically a composite special cues and also bad. Which plays an important role in. Most of this was aimed at making the line algebra computation that came next easier. And all of these choices were Guided by
simulation tools that we use in order to decide which I am relevant and how we should use them. Regarding linear algebra, so he knows the dimensions of the major seas that you can come to be thought a large Sports mattresses. And the Matrix for the VIP program is much smaller because the gel peel on your system is defined over a large ball. I felt was aiming, at reducing this Facebook, what we show in all competition is at 9 at the sizes and this is thanks to the use of the blood Kingdom in a resume and also thanks to the
fact that we haven't improved implementation of which is about the next step in the back. If I drew a picture with the time to solution is respect his number of calls and using, if I have something completely perfect into the skating. I have a straight line and what we In this context of the coaching, a straight line, assistant until several thousands. Of course, this is something we're pretty happy with. If fridges are thought about the cost of the computation, we have for Iris, a 240 something, which is in the
whereabouts of 940 lp240, something that is. So this tells us that we have a hot mess ratio, which is sweeping something, which is significant, but on the other hand, it is not as loud as people think. So it's something that we learn from this competition all so we can make the comparison of computation. Name is a DD-214 competition with the latest check out of this kind, which was 768, which is 232 digits. And has for years ago. You would have taken less time. So this is something we also quite
satisfied with Is it going to rain in more than just record? We have different up amateur ization strategies for further complications, which we're pretty effective, and guided by the design of a simulation framework, which we found the perfect quite happy with it and noticed that we used to open source software, which we have been developing for more than 10 years and also all the time. And you Spotify station, comedy song under this internet, you ever intend to go on with our
projects and the most of the oil capacity. Okay. Thank you for listening and I'm here to take your questions. Okay. First of all, he is sorry for not introducing you properly. I'm learning on the job. I can see any questions yet, but I have one. So my question is how how stable is this? So in terms of like you make some progress and then like the youth you feel like it sets writing and we kind of have a good idea of like how much does a taxi cost? So I can if you expect there will be significant progress and speeding to stop going forward. Well, we can always
expect some some progress in the fact that we improve on implementation in 2004 midnight. The different choices that we made in choosing. The Bandit has ended up in cost. We're pretty stable. I mean the end of the day we were at that time is a choice and that other guy. I'm at the post so, you know way. Yes. It's as stable as it can be one. Of course if somebody comes up with you. Kevin asks, do you process The Architects of gpus help for swimming? I mean,
we tried, but the people at UPS, I'll try to use gpus. And the bottom line is that if you have them enough messages, maybe you can, you could use them to some extent, but if you have money to spend your much better off on normal CPU. And happiness. Can you comment on what the strategy is for choosing parameters are exactly. Difficult, it's it's a question of making. Sure that you keep enough leg room filtering process to reduce your Matrix size as much as you can. So
me and such we want to pay attention for example, to the fact that the special cues that we used to divide the work into pieces. Do not actually cover all alarms off. They're not prime Rams and do not interact badly with a filtering. I don't see any more questions for now. I guess if I was going to say, we can go on to the next one. Okay, so does the next speaker want to load up her phone screen? Okay, so can you see spies and sound? Oh, okay, but not not not. Not right. Now. Either we go.
Yeah. I'll just share my desktop instead of the thing. I think yesterday they had a similar issues. So Let me just stop sharing wrong. Is that better? I will be on the sweet logrhythm algorithms and Karen Robinson, a field, but thanks for the introductions. So I just said this is a talk. I don't work with feeling good and he's going to be talking about my neck feels. So let me just start by briefly recalling the discrete logarithm problem. So the definition is quite straightforward were given a cyclic find a group
G. We have a generator or small G from this group. And then we have a Target elements age of his group. Are we want to be able to find the exponent x such that if I raise the generator G to the expedit. And with my target element H. This is one of the two main on, mathematical problems and which the security of them. A lot of a diploid today deployed, protocols base their security on it. So the other one, An interesting example that uses the hardest of the lp which is a paring based protocol. So why do we really care about during these protocols? Well,
first of all, their venues, there's quite a lot of protocols old ones more recently in blockchain. For example, as a case with pairings, when looking at the hardness of GOP is that we want to have the hardness of DLP both on elliptic curves and I'm fine. I feel so these parents that I'm not really a product of group group. And so in order for them to be hard and just comes from the definition of the group G that we have. So here in this work, we try to explain, then ask the question to, how do you
construct a secure parentage protocol and the answer, which is so not really going to talk about the elliptic curve side. The complexity is the square root of the size of the center of this being considered and that comes from out to Paula, ruang Guru them. But on the other hand, I'm going to be talking about the disregard them on finite Fields. So this is a bit more complex. First of all, there's a lot of different algorithms that sell DLP en finite fields at The Forum fpn. And only, there were a lot of them but also their complexity is going to
depend on a relationship. We have between the characteristics of the extension degree end. But usually when we talked about complexities of these algorithms and also these finally feels, we have the cell notation, which is the formula on the greens on a rectangle. And this is used to express the complexities of these algorithms. But also to Define different families of fine, I feel so we can talk about small medium or large correct depending on location. Where is smaller or equal?
Or greater than the focus on a specific area, which is the boundary case between small and medium characteristics. And there's too many reasons why we focus on this area. First of all, it hasn't been studied before. So we have a lot of algorithms in a medium characteristic. Can we know their complexity, how they behave? They've been a lot. There's been a lot of work on small characteristics, specially in the recent years with the whole closet. Longer than there's a lot of exist and
we were interested in studying their complexities precisely there to see which one performs best. And the other reason why we focus on this area is because this is the area where parents takes their values. And so, this was our motivation. So the main result of our paper, obviously, all the details are on the in the longer talk or in the actual paper are thorough analysis of the behaviors of many algorithms, which I haven't even mentioned yet. And this allows the
first question. So, the other than that, we study are the number Phil 5th, which was mentioned in the previous Dock and all of its variants. So there's a lot of parents that has been developed in the nearest to me. Some quiet older. We have the multiple number still saved at our number still saved the special number still saved. And then if you look at them swallow, there's some letters that come after the name of the algorithm dishes, the polynomial selection
that is used to select the two, polynomials, with the beginning of the algorithm and this into into the complexity. So There was a lot of studying to do here and visit are the resulting complexities, that we have. So there are some surprising fact that we noticed, for example, the special power, number feel sick. So we're combining two variants was not an algorithm. That is applicable in this specific case because of the complexity was much higher than any other algorithm. So in the end we had kind of an overview of what happens at this battery case. So we have a function field say which
is another algorithm similar to NFS, except for using function Fields instead of number field, which is still the best algorithms for in the last area in for a small small. As he pees and then we have crossed over and making on piano and the kind of fight to be the best defender in case if we fall into small. Do Indian, after we've done all this analysis. We were actually able to answer the following question to ask him, Sadiq Ali. What's my name is field fbn? Should be considered if we want to achieve the highest level of security when constructing appearing to be deeply,
want to be able to say, okay, if you think this pee in this and then you're receiving the highest level of security and we did that by equating the complexity on both sides of the financial side. And so we were able to slice up above, we were able to determine Dee's, intersection points and four again, whether you're choosing your end prime and composite or a p of a special form excetera Define, which were the intersection points. Do the CP notation a corresponding complexity for the best optimal of finite fields. And again, there was a
surprising fact that we noticed. For example, if we use a special form of which allows us to use of the special number Chelsea longer than that. We're not always necessarily A surprising fact that we noticed all the details are in the paper and thanks for listening. Thanks. So questions, not yet on the chat, but I have one. So the Private Selection is right at the boundary between small and medium. Does it make you nervous or should we be nervous about this being white at this Foundry? Nervous in the sense that some ideas from
the small characteristic could be applied to improve algorithm. But yeah, I mean, it's it's right where we have very different ideas, are some similar ideas, but you some different techniques. So interesting weather of to understand, whether some of the closet polynomial stuff can be used at this precise area. Okay. Sorry. I forgot. I was in the Crypt on Eliza's sessions will be excited about breaking stuff here as a function of p n. Save on a prime, you know,
if you wanted if you want to summarize what the results say. If I want a summary of these would be up there around. I think of values, we gave is four a row equals one. When considering I would take her so he could be up or down because then the complexity of the following. So I think the answer your question. I'm not sure I understood but the complexities decrease when he pee increases. So they would give me try the intersection points would be upper Bound for a
true friend and all the other and then the complexity part of the function of p&n. So they are usually expressed with the cell notation that I introduced in the very beginning where I was in separately. I thought well, Go back to that slide. Which one back to the beginning, the one with the expression that you had only depends on separately to the sea, I guess, depends on P, and done separately, right? The complexity of your. So we're looking at, I'm not sure. I
want to add something because we kind of go to Infiniti of following the relations died and froze. Our location to hear. We we we look at the battery case where a people without you one third of CP which gives a family of finite fields and the link between an empty and Wednesdays 10 to Infinity. Then you look at these complexities. Okay. They were more questions on the chat. Kevin asks how safe is it to extrapolate this into the future? Give him, that CPUs are
improving. He wrote some of that paper 25 years ago, but his phone is now more powerful than the supercomputer use back then. So the question is, how safe is it to extrapolate? These results of the future. I give him the advances in CPU architectures. I'm so complimentary to this work. There's some papers. I look at actual parameters for pairing friendly cursed, and there's a mismatch between some of the results that are observed for lower security levels in and ask him Todd to clean the
behavior that happening asymptotic Elite, so, I don't really know. If these results, I mean that I think there's a need for more analysis for these algorithms, especially with growing at Financial sizes. And also. So we just have the implementation for NFS and we can have an implementation of some of the variants of these algorithms, to see how they behave in practice. Probably we should go on to the next speaker. I think, at this point tickets. Okay, so the next talk is going to give him by I miss. So, can you share your screen?
Okay, so this is Agnes is presenting a joint work with John Sebastian. Okay, how everybody has a say? My name is in? Is it under we present to you our pulling on the sign language for solving the problem? And this isn't going to work with what we want to solve the hidden talk to some problems. So it's cool to the finder, the problem first. In the heating system, problem will consider an integer Q and A. And random integers off of one of which are defined
what you, in addition. We consider and binary vectors electronics and of life. M&a better age, which is a combination of this Pandora vectors with this weight of a ice cube. You can read this relation in this life. Then the problem is given to Moses q and the samples factor 8 to recover, both the interests of her eyes, and the binary vectors exercise. Begin to write this relation using vectors and matrices in the bottom of this life. And then ask is a binary Matrix. Who's those are the excise the band? But why he didn't suck their thumb problem?
Well, you can notice that actually its components of the samples Vector age, is actually a subsystem respect to the waist of a size, one in the class, except. It's a problem, has to cover the only the binary code stations. But in this case, the weights are hidden to. And for this reason actually, a classic attacks for the subsystem are not applicable. In this case. Before showing your speaking about the algorithm. I just want to speak about briefly the history of this problem,
which was presented for the first time that you work with 98, in the context of the generation of random VIP Parris. The following describes a problem despite for small and disagree. Them is quite efficient. They at the time they were not capable to break the, the problem 4, and greater than 90. So we know we're paper. We analyzed, we provide a detailed analysis of the explaining, this practical behavior. And we found bottleneck up the Arboretum and sold it in providing a variance which works in Poinciana time. It is like you can
see a sketch of the structure of the ingredients to an attack. Remember that scene as input. We have a drink. You and we want to do a binary Matrix X and Vector of the weight of and talk to you after relation. Holding is divided into many steps. And also, how are buried them at the same Overstock? Who decided to maintain distraction? And I will explain you. Why is the next flight indeed? Analyzing the talk? We observed that actually the first that succeeded with good rub for probability of time is large enough.
Is that the second step is the bottleneck of their algorithm? And the reason is that in this, in the wilderness act that use a lock this reduction algorithm, to compute, the binary vectors as short factors, but we observed that these are actually shorter, the better of the algorithm, and for this reason vs. Kentucky flexcity of the attack, cannot cannot be put in a long time. So, In our paper, we decided to to have a new second step completely different using a different approach. Our second step is indeed an algorithm to recover Bonnaroo back
towards using a multivariate. Referral. We are. We, so, I'm with you. Where is quadratic algebra and forties actually, we require a number of samples and, which is quadratic in an. And, but in this way, we obtain a footing on the time algorithm we needed to report more samples. So we Hustle How to improve the first step for generating. Past more also miles actress. I just want to mention that actually in. We also consider their Define didn't have the same problem as being than yesterday for a 99, providing an analysis and a body and soul.
So, for this problem, so summarizing in our paper. We describe an algorithm for solving. The hidden sub s problem, which works in put it on his time with the same size of the models, but we need to reply, we are quite a number of samples, which is quadratic in and, instead of being here, and this was confirmed by the Practical experiments to so many questions left are. If we can reduce the meaning of size of the models, look you and if we can further reduce the number of static sound and it would be nice
to have a polynomial time, algorithm requiring just seen your number of samples. Regarding this question. I just want to mention that in the full version of The Vapor. We provide we discuss two, different methods to reduce reduce the number of samples for both cases. We still need a quadratic number of samples to achieve a running time. So that's it. Thank you for your concerns. And if your questions, I'll be happy to answer. I thank you. I see you one question on the chat and your paper the I can space exploration technique
for pulling out solutions from this pain. Looks generic. Have you seen it somewhere before? Well, actually, these using these techniques for using linear algebra techniques in for solving quadratics. This thing is something that was already used to our other work from the eighties. I think and decius of Beats. I mean this DVD system. This system uses a different language. Let's see if you can find something similar in the group. Nervous language. But yes, so in but yes,
we had we used these, we couldn't find anything that fitted as good as this. A picnic. I'm sorry. I'm just conscious of the fact that there's another session starting after this one. So I have it on good authority that he wants to see you. Can you was giving the last talk? If that is correct, could you please share your screen and fusses fights? I'm both of them. I think you need to talk. Oh, okay, then my my good authority wasn't wasn't correct. Can you share your screen?
Okay, I proposed John you ask that outstanding. I'm not sure if it's my connection, but I like you, I guess. I'll just very good. Emma. Okay, I don't know why you're sorry. Okay. Maybe if we follow it, if we're waiting, we can, we can go back to the last talk and ask the remaining question. Yeah, let's do that. Answer the question was to generate many, many pairs of the format. How does it work effect on how to do that? I don't know what thing is. He's still on the listening. Yes. Sorry. I was trying to answer a question.
Are you speaking with me? Yes, the question did, John was asking did the outstanding question, why the last speaker is fixing some technical problem. I'm sorry. I was trying to answer the question in chat. Yes, yes, it will take. I was writing. Now. It's actually this, our work implies. That one should not generate many Affairs using that because your number of pairs. It means that you a couple of samples. And if he calls us prepare to get his presentation. I'm on. But I do not have a slide. So I'm asking him if he can send me the slides.
Okay? I don't know if I understood correctly, the question, if you want to use the optimization to, to generate these pairs for the number of samples. When I said this during the presentation, I meant that. As soon as you produce a quadratic number of pairs, you can be attacked by Aurora Breeden. so, Yes, one should be careful to read. To reuse the same size multiple times. Okay, Julian, any any update? I know I can still have not got the sights. So I guess there was a technical problem and I can try to give to talk without this life and in the
past just restarted. So I'm going to give the presentation know. Thanks again. So sorry for the technical problems. So our talk or our paper is about as you pointed out the application about computational assumptions in the algebraic rapallo. So what do we mean by this out? The background was the model of that. I could feel myself proposed in the paper at 4 do, 2018 and it basically is a relaxation of the generic route mobile. It's in between the generic. Computation and
grocery is limited in the sense that it has to show how it computes. But it is able to see the actual representation of who elements where is in the generic coupon. It does not go to sleep. Now that explore, its you proofs and relations between different assumptions and this model, for example, you can show that is tightly equivalent to the discrete logarithm assumption. In this model. You can also show that seems like the BLS signature scheme, how to tie production to the Sweet logarithm problem eating, though. It is
known that because this scheme is unique. It does not have a type reduction if you just assumed the rain tomorrow. I'm so and in this paper. We should have asked the question. Is it possible to give a brought your room that Lexus reduce a start type the son, she to another General type of assumption. Okay, and let me make a bit more clear what I mean by this. So basically in our paper, we give General your rooms or computational number theoretical assumptions, / groups and stay. There are
my motor. We also consider covering groups and we make your arms of the following form. We say that if some condition in the exponent of the generator holds, so if the polynomial with you have to compute as part of solving this number, if you're ready for some machine, if it satisfies a certain condition on the degree, then we provide a generic anti production from the associated descuide logarithm problem or a d, a bursary gets to see all of the degrees in X to see
if the degree of this problem would be a huge than the grocery in this in this assumption. Look at the sea. E to the X up to the x. ^ key is generic reduction in our, in our paper for many different types of assumptions. And we also provide is separation results. And a separation result shows that you can actually not only classify these group assumptions, but you can also separate different classes. One class is Brick stronger than the other with respect to algebraic reductions.
And this is one of the second part of our paper. Yeah, I think I'll just put out the slide. So this is like the second part. So we show that the Q Plus One deal. August option is a strictly easier assumption, the next Marcus Thompson. And that means that all of the number theoretical assumptions that can be applied by the two are strictly easier. That's pretty stronger than the ones that one. And then we also have another theory that shows that there are some assumptions assumptions, which we cannot capture in the framework, such as the one
more to squeeze log with some duck, the results of my dog. I'm sorry that there were accused of ethical difficulties, but please do check out our paper. and, I thank you. If there are any questions. I don't currently any. Well, can you ask a question in the chat? Yeah, I wanted to know if you can share your slime if you can go to the more slowly. So at least I'll be there in the background. I actually don't have a slide so I can link them from the program after the conference.
It looks better like that. I haven't collected them. I'm afraid I had too many other things to do. Sorry. Maybe on that note. We should all thank all speakers of this session because we're a little bit of overtime already. Let's try this thing. We amused ourselves and give a round of applause and see, kind of how that kind of place. Okay. Thanks. Everyone, everybody. Thank you.
Buy this talk
Buy this video
Our other topics
With ConferenceCast.tv, you get access to our library of the world's best conference talks.