Latest / Strachey Lectures / Privacy, Verification, Robustness: A Cryptographer's perspective on ML

Transcript

Privacy, Verification, Robustness: A Cryptographer's perspective on ML · Strachey Lectures

• 0:01
  [Auto-generated transcript. Edits may have been applied for clarity.] So. If you haven't.
• 0:13
  Okay. Um, I'd like to welcome everybody to this chance is screen Lecture, which is our distinguished lecture.
• 0:20
  Um, before I introduce the speaker, one of our sponsors of progressive content, uh, who has been hosting this series since 2015.
• 0:30
  And if any students or researchers want to meet that afterwards, you can do that during coffee.
• 0:35
  Um, one last administrative thing up at the top.
• 0:39
  We're going to have a Q&A here and we'll have some microphones running around.
• 0:43
  So if you want to ask a question, um, we'll do it that way.
• 0:47
  Okay. So I am super delighted to introduce Chef Nicole Foster's business about, um, the best speaker I could actually ever imagine.
• 0:56
  I would think there's a conference in the room like this where the other people concurring with this opinion.
• 1:02
  Uh, she is a professor at Berkeley, um, and the former director of the Simons Institute for Theoretical Computer Science.
• 1:09
  Actually, she's just stopped me now, but she retains her role as research director of the.
• 1:14
  We're still you have to support, uh, Simons seeds. Um, sound.
• 1:19
  In addition to that, she is a professor at M.I.T. and also emeritus advisement.
• 1:25
  So she's done very many locations. Um, when I decided what to tell you, her the world's accomplishments are so significant.
• 1:34
  And what I decided to do is to read you just a tiny bit from the citation of just a few different major awards.
• 1:44
  And I'm going to start with the prize in 1993.
• 1:48
  So Jaffe was awarded that prize for her paper, The Knowledge Complexity of Interactive Proof Systems.
• 1:56
  And I've shortened these a little bit tonight because of her time.
• 2:00
  But the citation points out that she until the colleague introduced the concept of interactive systems,
• 2:08
  providing a rich new framework for addressing the question of what constitutes
• 2:12
  a mathematical proof goes on to say that this led to exciting developments,
• 2:16
  including the resolution of several major problems, about the difficulty of funding European institutions to comfort level optimisation problems.
• 2:26
  Um, so a little prize would be pretty much enough for anybody, but, um, Jasmine's got two of them.
• 2:31
  Yeah, she had another kernel prize in 2001 for her paper, Interactive Approach to the Hardness of Approximating twigs.
• 2:39
  Uh, with, uh, if I didn't know much difference.
• 2:42
  And, um, here the citation says that they developed a completely new understanding of what an algorithm property was in terms of art,
• 2:50
  with their deep insights and powerful results evoking different factors for many problems science, for example, computation and photography.
• 3:01
  The last one of them generated was Turing Award, which is pretty much the biggest prize you could ever get in science.
• 3:08
  Um, so I'm looking forward to 2012, along with, um, the quality, um, um,
• 3:14
  citation says for transformative work that laid the complexity theoretic foundation for science,
• 3:20
  cryptography and in the process pioneered methods for efficient prosecution of mathematical proofs.
• 3:26
  But so Shafi is a member of the National Academy of Sciences, engineering and USA.
• 3:33
  Um, the Russian um Israel Science um, a former member of the um Russian side, Peter, and a bunch of others.
• 3:43
  She's also got a long list of honorary degrees, including here at Oxford.
• 3:48
  Um, we are completely up for today.
• 3:52
  Um, speaking to us about privacy verification and robustness, a cryptographers perspective on on them.
• 3:59
  So thank you very much. Uh, discussion.
• 4:04
  So if you want a darker I. So.
• 4:11
  Hi everyone, and I'm very honoured to be invited for your lecture and also to have received an honorary degree here in Oxford.
• 4:17
  It's so beautiful. It's a little hotter than I thought. Uh, so okay.
• 4:22
  Um, so the title is a little different than what I gave originally, but most of the same when you look at the content of the talk.
• 4:28
  So I'm going to call it constructing and deconstructing Trust in I totally a cryptographic perspective.
• 4:34
  So, um, you know, I've given some version of this talk without most of the results that are here, uh, maybe, uh, five, six years ago.
• 4:43
  And at that point, I don't know that I would have used this slide.
• 4:46
  But at this point, it's very clear that machine learning revolution is really the scientific breakthrough of our times.
• 4:52
  And, um, that started with deep learning. Now with the large language models, it's kind of achieved an entire level altogether.
• 4:59
  And when Leslie was saying about the greatest honour in computer science, I was thinking about these Nobel Prizes.
• 5:05
  Oh, for machine learning people.
• 5:07
  Um, so, you know, obviously it raises these very deep questions about human versus machine intelligence and whether large language models,
• 5:16
  this project that Michael and I'm working on will even give us the ability to translate non-human communication people.
• 5:23
  This is all talking about AGI and superhuman intelligence.
• 5:27
  They're betting markets about when that's going to happen.
• 5:29
  Um, you have uh, already the the oh one doing very well on competition math, competition code, PhD level science questions.
• 5:38
  There's a whole benchmark of new questions out there which we don't know the answer for.
• 5:42
  We all agree. I think with this slide, and you don't need me for that.
• 5:47
  The leading is to the fact that, uh, whether or not we believe that there will be that this is the biggest scientific revolution,
• 5:54
  it's going to solve the Riemann hypothesis, whatever. Uh, we do know already that is huge, uh, problem in not only promise, but, uh, for applications,
• 6:02
  whether it's health, drug discovery, infrastructure, natural language processing, policing, uh, financial markets.
• 6:09
  And all of this indicates, really, that there's a major shift of power, which we're all aware of.
• 6:14
  For those who have data and those who have algorithmic expertise, and one can argue in,
• 6:18
  uh, in debate where the data is more important or algorithms are more important.
• 6:22
  But what is very clear is that's where the power lies and all that's beautiful.
• 6:27
  Uh, the problem that, uh, this talk is about is should we really trust models to the extent that we are very rapidly,
• 6:34
  uh, trusting, uh, we don't understand and we don't control.
• 6:39
  And, uh, I think at least for myself, maybe because I'm of a certain age, you know, that makes me very nervous.
• 6:45
  But I think it should make everybody nervous, uh, when we're talking about critical applications.
• 6:52
  So, uh, since we talk about trust and since I'm a cryptographer, I want to tell you a second something about cryptography.
• 6:58
  So often people think about cryptography, basically just an arsenal of tools.
• 7:02
  You know, there's encryption, there's digital signatures. People talk about obfuscation, zero knowledge proofs, metamorphic encryption and so forth.
• 7:09
  Okay, so the beautiful constructions out there, some of them are used in practice.
• 7:13
  Some of them will be used in practice. Uh, but if you want to sort of zoom out from all these tools, essentially all of them aim at the following.
• 7:20
  And that is how to use technology that you don't trust, uh, as if you should trust it.
• 7:26
  So even though you are assuming that there are adversaries, you know, somebody is trying to listen to your messages,
• 7:31
  somebody is trying to pretend to be you to to, you know, have access to your bank account.
• 7:36
  Somebody might want to, um, reverse engineer your program.
• 7:39
  Is in the case of application, you want to say, I don't want to think about it. Well, I'm using this.
• 7:43
  So what cryptography does. It comes up with abstractions and tools that enable you to sort of pretend as if these adversaries don't exist.
• 7:49
  So it is sort of a, uh, um, uh, a zooming out view.
• 7:53
  It's a way to establish trust in technology. And not only that, it's, um, this is true for each one of these, uh, tools that I've mentioned,
• 8:01
  but there's sort of almost at this point, uh, um, a cookbook recipe when you want to solve a crypto problem.
• 8:07
  You kind of define the task that you're talking about. Uh, whether it's encryption or digital signatures and so forth.
• 8:13
  And then a very, very important step is you model what's called an adversary.
• 8:16
  So again, an adversary would have powers. He might be a passive adversary.
• 8:20
  Just be listening. It might be an active it might be changing messages going on the line and so forth.
• 8:25
  But you're supposed to model it mathematically. Precisely. Then you define what it is a secure solution.
• 8:30
  So it might not be 100% what you'd like. What what you define it.
• 8:34
  At least it's mathematical definition of what security of solution would be.
• 8:37
  And then you construct something and most importantly, you have a security proof.
• 8:41
  So you want to say if, um, an assumption, you know, all of a sudden assumptions come in.
• 8:45
  So we'll say something about that in a minute. But you say under very well specified assumption, if they hold, then this, uh,
• 8:52
  primitive that you constructed is secure according to the definition that you've laid out.
• 8:56
  Okay. And it's sort of the history of cryptography in the last, at least since I've been involved in it,
• 9:01
  is that these reductions between well specified assumptions and proofs of security is what the game is about.
• 9:07
  Um, so without proofs, we're saying we have nothing, really,
• 9:10
  because we don't know if somebody is breaking the scheme and not telling us, then what's the point of the whole thing?
• 9:14
  So the proofs are really the main thing in our disposal.
• 9:17
  Now what kind of assumptions?
• 9:19
  I say the word assumptions because they are used all over cryptography and a lot of of course the work is to try to minimise them.
• 9:26
  They really fall into sort of uh, some categories.
• 9:29
  One, which is the one that we mostly hope for, is that we believe that certain problems are hard.
• 9:35
  Certain computational problems. I'll talk about one of them during the talk. Usually people know about factoring integers.
• 9:40
  Here's a problem. We don't know how to do it efficiently. Let's assume there is no such algorithm.
• 9:44
  And now build a primitive and prove that it's secure under that.
• 9:49
  There are other assumptions you could talk about.
• 9:51
  There's several entities in this system, and maybe they or each one of them might be adversarial, but they don't all collude, uh, against you.
• 9:58
  Another type of assumption would be a physical assumption.
• 10:01
  Uh, a physical assumption might be that, uh, you know, if you're talking about quantum physics or something that there are quantum computers,
• 10:07
  uh, might be some other assumptions of distance between that you're blocking, uh, two entities or they can't actually transfer information.
• 10:14
  And these days, people talk about trusted hardware.
• 10:17
  The point of view of this line is to say that, uh, we would like to minimise we don't wanna use all of these assumptions.
• 10:21
  We'd like use none. Sometimes we'd like to use 1 or 2. But important part is really to emphasise this, uh, security proof.
• 10:29
  So what does this have to do with machine learning? Oh, by the way, I just want to say that sometimes you show that it's impossible.
• 10:33
  So achieve security, you define a security, and then you show that maybe even also under the assumption that any scheme would break,
• 10:40
  you know, and um, okay, so machine learning.
• 10:44
  So the proposal and in some sense this sort of the idea of this whole program of research is to use the same kind of recipe,
• 10:51
  uh, for machine learning, uh, meaning that, uh, if there's a task, we'll define it first of all, properly.
• 10:57
  And that's already, you know, I mean, I assume that a lot of machine learning researchers here,
• 11:02
  and certainly there are people who know more about machine learning than I do.
• 11:05
  Um, but I have I think we all have to agree that if you read any of these very fascinating papers with incredible ideas and breakthroughs,
• 11:15
  they very rarely define what they're doing.
• 11:18
  So, um, so if you talk about alignment, you know, I would like I want to work on alignment, but and I will work on alignment.
• 11:23
  But I have to define it myself. And you might not be consistent with other people's understanding, but there are no definitions.
• 11:29
  Uh, there's words, uh, and um, words are, I guess, definitions also words.
• 11:34
  But in any case, and then in very important part is also who is the machine learning adversary.
• 11:38
  You know, maybe in cryptography it's more obvious. It's not necessarily the case here, but we'd like to define it.
• 11:44
  And then we want to define what it would be. Since we're talking about trust what would be a trustworthy solution.
• 11:49
  So give, uh, a definition. And then finally you might try to come up with a solution.
• 11:53
  And we want to focus on the fact that, again, we would like to have some kind of proofs that under maybe some assumptions,
• 12:00
  this solution that you have constructed is trustworthy with respect to your your definition of trustworthy.
• 12:05
  So maybe maybe this is more important slide than anything that it would be.
• 12:09
  It would be good to be able to have a definition. Maybe it's not going to be the right definition.
• 12:13
  Maybe later on there will be a more general one, or maybe they'll be another one that you could show equivalent,
• 12:18
  uh, but that there will be some kind of formal thing that you're trying to to satisfy.
• 12:22
  Uh, and again, what assumptions? It could be the cryptographic assumptions. It could be others.
• 12:25
  So this is sort of the mindset for this talk. Okay.
• 12:29
  So um, and again, as I said before, possibly you what you might be want to achieve,
• 12:35
  like you define what what alignment is you you define what your adversary is.
• 12:41
  Uh, you might not be able to achieve the definition you came up with, and you might even be able to prove that you cannot achieve it.
• 12:46
  Exactly. So what do people want from you? Or you could change your definition, or you could change your solution.
• 12:51
  And I'll show you in this talk a couple examples where you can actually, uh, achieve, uh,
• 12:56
  what we want and couple in one assumption where you can prove that it's impossible to achieve it, and then you have to contend with us.
• 13:04
  Okay, so, uh, just one word before.
• 13:07
  Sort of uh, go into these examples which are verification, robustness and privacy, like in the title that was advertised.
• 13:14
  Um, I want to say that the first, I think, um, gut level reaction by people in machine learning is or at least it used to be,
• 13:22
  uh, is that whereas cryptography is designed with an adversary in mind, if there's no adversary, there's no problem.
• 13:28
  I mean, why should you encrypt if nobody's listening, you know, why should you protect, uh, accessing, uh, Amazon if nobody's pretending to be you?
• 13:35
  But machine learning, that's not the mindset. You didn't come up with machine learning solutions because you're trying to get over an adversary.
• 13:42
  But the fact is. So maybe this whole adversarial thinking is not the right one.
• 13:46
  But the fact is that right now, AI systems and for the foreseeable future are very attractive targets.
• 13:53
  It's a huge payoff to break them in many different ways, whether it's on a national level or a commercial level.
• 14:00
  And therefore, if you think about an adversary, it's a good way to think, because if you could show that things work in the presence of an adversary,
• 14:07
  you should feel safer than if you assumed, uh, a particular behaviour on, on, uh, on part of the adversary.
• 14:16
  So my second point is we don't when we talk about adversaries, we would like to prepare for worst case adversary.
• 14:23
  So we we we don't want to say, oh, the adversary uses a particular strategy.
• 14:27
  Let's say, uh, those people are familiar with, um, you know, adversarial examples.
• 14:31
  There are solutions that say, well, if the adversary does the following to an image, say, then I can protect against it.
• 14:37
  If it's use restricted, the ability is restricted to some transformations of images.
• 14:42
  But why should the answer be restricted that they can put a patch on a stop sign?
• 14:45
  And I'm saying things we've all seen in other talks. Um, so we'd like to, if possible, to prepare for worst case adversary.
• 14:53
  But one thing we do throughout cryptography, and also throughout this talk,
• 14:57
  is that we do assume that the adversary is not is computationally unbounded.
• 15:02
  So in other words, it cannot factor integers if you like, but more it doesn't have more than it doesn't have exponential time.
• 15:07
  So there is some bound on the running time of the adversary or other resources as well.
• 15:11
  The resources these days could be samples, you know, there's a distribution or there's data and there's some at this cost.
• 15:18
  So there is some bound on how much data, how much time, how much. And again, when we talk about bound I mean more than polynomial okay.
• 15:25
  Um so. Uh, what are the challenges that I will talk about, which are sort of an example for this approach?
• 15:34
  Um, so here it looks really pale. You can actually see the screen.
• 15:38
  Yeah. Okay, fine. Um, good. So there will be I'll talk a little bit about privacy.
• 15:44
  Uh, kind of aiming at this issue there. A lot of the power, at least initially, came from data of individuals and the, um, the training data.
• 15:52
  And, and we might not want to give over medical records and so forth, or might not be able to because of legal restrictions.
• 15:58
  Uh, then I'll talk about verification. And this aims at the fact that these models I'm not training my own model.
• 16:04
  You know, I'm using a model that was trained by others, whether it's DeepMind or, or, um.
• 16:12
  OpenAI or whatever company, and we would like to have some way to verify that these models that are presented to us are good.
• 16:18
  Okay. So they haven't been tampered with for whatever, uh, for whatever reason.
• 16:24
  And lastly, uh, I'll mentioned about robustness. So that is uh, we have the data today.
• 16:28
  We train. It looks good. It's often with respect to some benchmarks or some holdout information.
• 16:34
  But what about distribution shifts and data of the future? Uh, how can we trusted the models robust with respect to change in data.
• 16:42
  Okay, so those are the three, uh, areas that I'll talk about.
• 16:46
  And you can already see that there is if you had to sit down and say, okay, so who's the adversary?
• 16:50
  It is very clear the adversary in the first might be the training algorithm that's getting our data.
• 16:56
  The adversary in the second might be this company that's training a model and might be not doing it the way that they claim they're doing it,
• 17:03
  or maybe saving on resources and therefore doing something different.
• 17:06
  And the adversary here is in some sense even nature. Uh, so distributions do shift.
• 17:11
  And what do you do then. But he could also be much worse adversary okay.
• 17:15
  So just to say um, very simplified version.
• 17:20
  So we'll talk a little bit about what happens during the collection and training phase.
• 17:25
  Then post uh, development of a model so called the audit phase.
• 17:29
  And then when it's being used and uh, again, very, very high level, I'll think of machine learning just in these two, uh, places.
• 17:38
  I'm not looking at, um, you know, reinforcement learning or anything.
• 17:42
  Just think of a training algorithm gets inputs from a distribution labelled x, y and outputs a model H.
• 17:49
  So h for hypothesis a model and once a minimise loss according to some loss function.
• 17:54
  And then the other phase will be there is already the training.
• 17:57
  Uh there's already the model H and now we are getting some individuals data and getting some prediction probability.
• 18:03
  But more than that this could be a a language model. So this is a query and this is an answer.
• 18:09
  Um, so not just about prediction but also generation. And um it could be distribution over sequences or sequences.
• 18:17
  So let's be very general in kind of thinking about what I'm aiming at.
• 18:21
  So I'll start with privacy.
• 18:23
  So in some sense privacy is kind of the easiest, um, problem, not necessarily the easiest to achieve in terms of the computing power that's necessary,
• 18:32
  but it's the easiest to define because we have so much experience, you know, especially as cryptographers in trying to protect privacy of data.
• 18:40
  Um, so there are lots of tools, you know, the secret sharing, uh, some of these tools, I will mention it, but just kind of is a laundry list here.
• 18:49
  The longer one, private information retrieval, secure computation and one morphic encryption and so forth, there's lots of tools to our disposal.
• 18:56
  And in some sense, we can use all of them.
• 18:58
  Uh, and they're all defined to have certain, uh, secure, achieve certain security under certain assumptions.
• 19:03
  And they kind of naturally fit to some of the problems that come up naturally.
• 19:07
  Uh, in, in machine learning, uh, in particular, we're going to use homomorphic encryption just in the next two slides.
• 19:14
  So homomorphic encryption is this little chart here.
• 19:17
  It's an encryption method that has some special property that not only that you can encrypt and then uh,
• 19:22
  decrypt, but you can also do something we call evaluate.
• 19:26
  And that is you could take the encryption without understanding what is x, just what the ciphertext is.
• 19:31
  And if you run an evaluation on it so that at the end you get, uh, a new encryption.
• 19:37
  But what's being encrypted is whether it be encrypted X, it'd be encryption of F of X.
• 19:41
  And you could apply that encryption step on this new C prime and get back uh f of x.
• 19:48
  So that's really and the question is which FS are being supported. Could be addition could be multiplication.
• 19:52
  It could be any circuit. Um and that's one of the biggest, probably the biggest invention in the um the last 20 years in cryptography.
• 20:00
  There's around 2008, the first homomorphic encryption scheme was proposed.
• 20:04
  And it would be extremely useful also for what I'm trying to do here.
• 20:08
  So for example, just to kind of get us warmed up, suppose we want to actually, uh, apply it to the training data problem.
• 20:16
  Uh, again, this is sort of, I think a homework problem once you understand the definitions to,
• 20:20
  to do this slide in a fairly low level homework problem.
• 20:23
  But, you know, this is, uh, just to set the stage. Um, so let's say that all the data is encrypted now and who encrypted.
• 20:31
  That's a good question. But let's say you encrypt it for some kind of, uh, trivial example.
• 20:36
  Each person encrypt their medical file, or each doctor or each hospital encrypts all the medical files in their disposal.
• 20:42
  They all come together, they give it to some, uh, trainer, uh, and the trainer works on it.
• 20:48
  Now instead of working on the, uh, data itself directly on X and Y, they, uh, they're working on the encryption.
• 20:54
  So what you need is an algorithm that is able to do whatever program that we're going
• 20:58
  to run on the X and Y's in the clear to do it on the encryption so that if you,
• 21:04
  uh, what we just said a minute ago is, uh, called the encrypted compute stage.
• 21:08
  If we have in our disposal something that can take X and. Ys.
• 21:12
  Those are the X over there. And the labels wise with the medical file is x.
• 21:15
  The label of whether you survive or don't survive might be why?
• 21:19
  Um, then um, everything would be done under encryption.
• 21:22
  We'll talk about cost in a minute, but in an ideal world we have this encryption method.
• 21:26
  We get the encrypted model. Now we want to use it though comes in model.
• 21:30
  We unnecessarily use it as a piece of information which is encrypted. So at this stage we have to decrypt it.
• 21:35
  So how are we going to decrypt it. So the idea here is there's no single party.
• 21:39
  It's certainly not open. AI is going to have the decryption key because then they could just equipped crypto or medical record information.
• 21:45
  But there is uh, a decryption key metaphorically look like three people here that all each have a part of a key.
• 21:52
  And, uh, they are. There's and then they can apply their share in order to decrypt, uh,
• 22:00
  this encryption of each such that eventually, after each one goes within steps or together, voila!
• 22:06
  H appears in the clear. Okay. Uh, so what are the assumptions here?
• 22:11
  The assumptions are, first of all, there is an encryption scheme that has the properties I want.
• 22:15
  And that's based on something called learning with errors, which I'll put up in a slide in a minute.
• 22:19
  So it's not a factoring problem of integers, but it's a different problem comes from sort of geometry of numbers.
• 22:24
  Um, and that these guys or these shareholders, uh, don't collude.
• 22:31
  So there are two assumptions here.
• 22:32
  One is that you have given the pieces of the key to P to entities that don't all collude together in order to break the scheme,
• 22:39
  and the scheme is secure. Now, those people maybe worked on differential privacy.
• 22:44
  How many people have heard that? Yeah.
• 22:46
  Many, uh, anyway, so you could say that this is no good because H, for example, could be just the list of everybody's data.
• 22:55
  If it's a list of everybody data, then H itself reveals people's data.
• 22:58
  So maybe you want to have some requirement from H. But that's sort of beyond this is a that's a different problem.
• 23:04
  So one problem is a design an H two does not leak the information of X and y.
• 23:08
  The other is how do you actually compute h. You know, without looking at the x's and y's in the data.
• 23:15
  Um, and the problem with differential privacy, there are lots of old papers about their training under differential privacy.
• 23:21
  I'm not going to touch that. Okay. So it didn't give you a definition here.
• 23:26
  But the definition really would be that whatever algorithm you had that was working in the clear okay.
• 23:32
  If you look at that algorithm versus the encrypted algorithm,
• 23:35
  essentially you have you will learn whatever you can learn from the encrypted one is what you could have, um, is.
• 23:42
  Um, so the other way, whatever you could learn from um.
• 23:48
  You shouldn't learn more. I can't think right now.
• 23:52
  I went to sleep at 130. What is the definition you would want?
• 23:55
  Let me ask you. So the definition we would want from this scheme is that we are, uh,
• 24:00
  you going to find out more about the data, what the x and y is more than H provides.
• 24:05
  So h we say is okay, everybody should get h at the end. Okay.
• 24:08
  Well open the at least you get h at the end.
• 24:10
  But we want that whatever it is you recover from H about x and y's is um is holds regardless of whether you had access to this encryption or not.
• 24:20
  So in other words, H obviously gives you things okay.
• 24:23
  But you don't want to give you you don't want the fact that you looked at the encryption of the medical file to give you more than H.
• 24:28
  And that's the definition that would be satisfied. So what does this learning with errors.
• 24:33
  This thing that I said,
• 24:34
  that is this is the assumption based on which we build encryption scheme with this extra property that they can compute on ciphertext.
• 24:42
  So this is the problem. Um, essentially let's think of S as a vector in uh execution.
• 24:48
  And uh, and then we're given and that's the secret.
• 24:51
  So we don't know what the values of these, uh, SES are, the components of the vector, um, and so on and so forth here.
• 24:58
  Uh, and is for but we're given a lot of equations in these variables.
• 25:02
  But of course, if we're just given equations, uh, without the, we could do Gaussian elimination and figure out what's is.
• 25:09
  So we're given noisy equations. So in other words on the left hand side are the coefficients.
• 25:14
  And on the right hand side we add some noise. So this aid is not really the right solution.
• 25:17
  That's already the solution. Plus some uh noise for some Gaussian distribution.
• 25:23
  So it turns out that this problem.
• 25:25
  So give me a bunch of uh, coefficients in uh, in a noisy right hand side is, um, is as hard as decoding random linear code,
• 25:34
  as hard as, uh, approximating the size of the shortest vector in a worst case N-dimensional integer lattice.
• 25:40
  So it's a it's not only problem that seems that we don't know how to solve,
• 25:44
  but it's a problem that people have shown that average on the average case distribution is as hard as the worst case problem,
• 25:49
  which we don't know how to solve. And when I say don't know how to solve, I don't mean that I don't know how to solve it.
• 25:55
  I mean that the best known algorithm and that is actually true even for quantum computers today takes exponential time.
• 26:01
  So two to the n and it was the was the length of the vector.
• 26:04
  So this is a problem that has been considered for many years, especially in the lattice version.
• 26:09
  Um, and uh, this is the best we know how to do.
• 26:13
  Now, this doesn't mean that tomorrow some genius is going to come up, maybe from Oxford, and come up with a polynomial time algorithm,
• 26:19
  in which case maybe it's even better than, uh, having a secure FCE because they've sold some fundamental problem.
• 26:25
  But it's what we call the win win. So we say if you could attack the scheme.
• 26:30
  The encryption scheme. Then we gave you actually a constructive reduction from that attack to solving, uh,
• 26:36
  this worst case approximate, um, this worst case, uh, shortest vector to lattice problem.
• 26:40
  Okay. So say you we need a way. Either you have a good scheme or you have a bad scheme, in which case you have a good algorithm.
• 26:47
  Um, and that is what was achieved by the proof.
• 26:51
  Okay. So this is, um, this is all beautiful in theory, but.
• 26:56
  Oh, often when people talk about, uh, that is four years since it was invented in 2009.
• 27:02
  And the development people were saying, well, it's very nice in theory, but it's impractical.
• 27:06
  So first of all, I hate that sentence because it never really holds with time,
• 27:10
  because whatever is impractical in the past usually becomes practical in the future.
• 27:14
  Um, so specifically here, uh, there is a library,
• 27:19
  an open source for polymorphic encryption library by many different people and, uh, certainly, um, it, uh, it's open.
• 27:27
  So, uh, it is possible to run this in practice.
• 27:32
  Now it's all a question of scale.
• 27:33
  So when I say scale, really, if you think about large language models and you want to, uh, train foundation models and fine tune and so forth,
• 27:41
  you would like to know how really what is the concrete efficiency of this, of these schemes.
• 27:46
  And really the way to think about is this sort of three different axis. There's the adversary, which we sometimes think is very curious.
• 27:54
  Okay, but he's honest. He doesn't tamper.
• 27:56
  Then it might be, uh, actually an active malicious adversary as a change things also in his quest to break your encryption scheme.
• 28:03
  Um, the adversary here is the machine learning training algorithm.
• 28:06
  Right. Because they get the encryption. It could also be the people providing the data, and that's called poisoning.
• 28:11
  It's not part of this particular part of the talk. Um, then there's a question of what is a computation.
• 28:17
  Could be linear regression. Could be logistic regression. It could be deep nets.
• 28:21
  Neural nets could be language models. Each one of these is a big jump in terms of complexity with computation.
• 28:27
  So where is we. We can use homomorphic encryption for linear.
• 28:30
  No problem. We know we have things for logistic when we get into large language models is obviously not there.
• 28:36
  Okay. So what do people do. So there's another axis here which is what are the assumptions.
• 28:41
  So one assumption I talked about was learning with errors of factoring. So these are the computational assumption.
• 28:46
  Another assumption might be that you have more than one party privy to the computation.
• 28:51
  But they don't talk to each other okay. And the third assumption is trusted hardware.
• 28:55
  And that's really kind of the big player these days. Uh, so when people talk about trusted hardware.
• 29:02
  A. What are they? What do they mean?
• 29:04
  So they may mean many things, but mostly what they mean is this new chip of Nvidia, which is not that new at this point,
• 29:11
  few years h100 where the idea is that they in some sense say, here's this, here's a secure, uh, box and give it put encryption in there.
• 29:21
  The box holds the secret key and it, uh, inside of it, it will decrypt, it will do some computation, and then it will encrypt and send it out.
• 29:28
  Okay. So in a sense, you're trusting that this box works, uh, without leaking anything about the secret key or the message that came in encrypted.
• 29:38
  And then there's also another usually attestation, uh, module which says, not only that, but you're going to get approved.
• 29:44
  What was done inside there under the auspices of this box was the correct computation.
• 29:49
  And this is, uh, there used to be, uh, Intel SGX, uh, which was similar, but it wasn't a GPU based,
• 29:56
  but uh, and it had similar kind of, uh, boxes and similar kind of belief that it just works.
• 30:04
  Um, so I guess the sponsors are hiding this line here.
• 30:08
  Just second. Okay, so beware whenever you talk about, uh, side channel attacks that, um, sorry, whenever you talk about secure hardware.
• 30:20
  Ah, that there are these what's called side channel attacks.
• 30:22
  It could be that because of the amount of power consumed or because two people use the same chip,
• 30:26
  and then something was left from the previous, um, uh, from the previous, uh, encryption that was in the box.
• 30:33
  Um. There are some, um, bugs.
• 30:38
  I guess maybe you don't trust the companies blindly.
• 30:41
  These are things that there's a whole field of people that are out there working on it, on on secure hardware.
• 30:46
  But for our sake, we could use it. But we just have to understand that that's part of the assumption.
• 30:53
  All right. So has this been used. So this is all like a, um it's like a blueprint.
• 30:57
  So mostly the usage is have been sort of in finance is a lot of crypto use, but the use more of a machine learning type use of privacy.
• 31:05
  Uh, it's been mostly on, uh, in medical and in actually in genomic, uh, uh, field.
• 31:13
  So why why do it in, um, when you talk about, uh, genomes?
• 31:18
  Because you need a lot of data. So it's a place where complexity comes in and has large amounts of data because otherwise you have no effect.
• 31:24
  Right? So if you think about things like Crohn's disease or, uh, breast cancer, uh, in schizophrenia, you know,
• 31:31
  you only when you go to large enough numbers that you can actually find signal in the genome that's related to the phenotype.
• 31:37
  And, um, so it's a, it's a perfect example of a place where privacy is required because you're talking about medical records,
• 31:44
  but, uh, size is, uh, in size is important.
• 31:48
  Uh, so how do you achieve it? So this was a place so 1 in 2020.
• 31:53
  We had a paper doing Gwas. Uh, this is also a company that I'm a co-founder.
• 31:58
  And so also part of it where we use exactly this type of blueprint like I talked about, except what you're training is,
• 32:05
  you're running a dual genome wide association study analysis under homomorphic encryption.
• 32:09
  And then at the end you're getting whatever the answer is. And you'd like to check the accuracy of the answers so that it worked correctly.
• 32:17
  And also with the time performances. And at the time.
• 32:20
  So this is 2020, the extrapolation was 100,000 individuals, 500,000 snips in this amount of time on a single server.
• 32:28
  This is the kind of application that doesn't have to work in real time. Today, the numbers would be much better.
• 32:33
  What's another example? Another example. Uh, and just a point to make here is that who is holding the keys in the case of Gwas,
• 32:40
  it's actually you can think of you have different medical centres.
• 32:43
  If there's the Broad Institute and there's Oxford, I don't know, there's there's UCSF and they all each have their database.
• 32:49
  They could be the ones holding the keys, the parts of the key because they don't they don't want to share with each other, but they're okay.
• 32:55
  Uh, um, I guess the as a key holder, there is a partial key holder themselves and then they come together and reconstruct H.
• 33:04
  All right. So that was 20 1020 then 2023.
• 33:07
  There's this is an application working on real world uh uncle oncology called data analysis.
• 33:13
  So this is actually a hospital that has a lot of, uh, cancer patients and wanted to do something which was, um, uh, combining actually,
• 33:22
  the novelty here was that you the data was, um, you know, rather than having lots of data, it looks the same, but for, for different patients.
• 33:30
  You had one medical centre that had some, uh, there are electronic medical records over here.
• 33:35
  Is that another medical centre that had their, uh, results?
• 33:38
  Uh, once they were cancer patient. And you wanted to.
• 33:42
  So we think of it as sort of same patient, different data held in different places.
• 33:46
  So you need sort of joint operations to sort of identify this,
• 33:49
  the same patient enjoy order and all this under encryption because you're not allowed to send each other data.
• 33:54
  Um, and uh, what was used for that is also something called a threshold effect, but doesn't matter.
• 34:01
  The main thing is you can support a lot of statistics that people do in medical packages, like, uh,
• 34:07
  you know, Kaplan-Meier, um, survival curves, uh, and lots of other very common statistical operations.
• 34:17
  Okay. So the last thing that I'm going to say about privacy is that now in 2024, the thing of secure hardware has come into the picture.
• 34:26
  So often what you see is medical studies where you have different, uh, let's say different, uh, in this particular example,
• 34:33
  it's different hospitals, a, you know, minute of say, well, the application was each hospital trains sort of their own, um, a model locally.
• 34:42
  And then they combined using something called Federated Learning to come up with a
• 34:45
  bigger model that takes all the information of the different hospitals into account.
• 34:50
  And you use secure hardware because let's say and this so there's both this thing called federated learning.
• 34:55
  So this is the federation and also fully homomorphic encryption plus what's called trusted execution environment which is hardware.
• 35:02
  Okay. Um why why use hardware if we were doing so well in the oncological study and the Gwas is because in this particular application,
• 35:11
  it was to take a whole bunch of, uh, a pathological slide images.
• 35:16
  So they're very, um, uh, communication heavy to send this over the line.
• 35:21
  So you wanted to do things locally and then just send sort of updates of models A and even the updates, you wanted them to be secure.
• 35:28
  And that's why you use the secure hardware. Okay. There's a lot here.
• 35:31
  I just wanted to show the only thing to retain here is this.
• 35:35
  Privacy in some sense is easy to define because we've worked on it.
• 35:38
  We have the tools, so a lot of it is about putting the tools together in an efficient manner, you know, for different applications.
• 35:44
  So it's at the stage where we're privacy matters. It is worth taking a look at this type of technology and making it work.
• 35:51
  And that's being done. Okay, let's go on.
• 35:55
  Talk about verification. What time is it? How much time?
• 35:58
  I've only been talking. Wow. Okay. Um.
• 36:02
  Okay. I started a little late. Okay. So, as I said, machine learning is really should be thought of as a service.
• 36:09
  I'm not doing it in my own office.
• 36:10
  Somebody else is doing it, and I use it so I can think of it as a there's a client, it gives, uh, and it gets this model.
• 36:18
  And it could be even the client supply the data. So forget about privacy now.
• 36:22
  Somehow the machine learning trainer, the service provider, uh, got data and came up with a model and gave us back to the client.
• 36:32
  Okay. So now the question is what do I know about this service providers.
• 36:35
  As you see they have like ears and a tail like the devil.
• 36:39
  Maybe not the devil, but the devil incarnate. Um, you know, these are sort of the signs, you see when you drive from Berkeley to San Francisco.
• 36:48
  There's a company called hive, and they keep on changing their signs, and the current sign is, um, uh, or maybe this was a few months ago.
• 36:55
  We make eye work. Uh, don't just trust us.
• 36:59
  Test us. I don't know what they mean, but. But they themselves are confessing that you shouldn't trust.
• 37:04
  Um, okay. Okay. So, um, so what would we like to do is we would like to sort of post development, verify properties of this model.
• 37:14
  So what are the properties you want to verify? There could be many. For example you could verify you want to verify the model is accurate.
• 37:20
  That's the thing that most people concentrate on right.
• 37:22
  They have they have their own data and they test the model on and see that they get the right result.
• 37:26
  Um, you want to say that it's correct?
• 37:29
  Maybe it's not good enough that it's, well, good on the average, but you want it to be correct on the prediction that it gives you.
• 37:35
  Uh, you want to talk about robustness. What happens when you're a distribution change.
• 37:40
  You might want to talk about fairness and the United States, you don't use that word anymore.
• 37:43
  But you know, it used to be a big field a few months ago.
• 37:46
  So whether it's fair to different, uh, subpopulation, I think it is one of the words is stricken.
• 37:52
  I'm not sure, but, um, it should be.
• 37:56
  Now, what do you want to talk about? Safety. Um, a or maybe later down the, uh, down the line.
• 38:02
  When the regulations are set, you want to prove that it satisfies regulations, whatever they are.
• 38:08
  And obviously you could retrain by yourself. So that doesn't make any sense.
• 38:11
  Uh, you have to have some restriction on this, uh, on this module that verifies properties,
• 38:17
  which is that it will be cheaper than retraining on your own. Cheaper?
• 38:21
  How cheaper? Maybe using fewer data samples, maybe lower quality data, maybe being much more efficient,
• 38:27
  maybe just using black box access to the model because they don't necessarily
• 38:30
  going to give you all the model weights and tell you how the model works. Exactly.
• 38:34
  Okay. So this is like a big goal. How do you verify properties of the model that you were given.
• 38:39
  So I will show you, uh, a couple of results about this.
• 38:44
  So first of all, as I said, accuracy is the sort of simplest thing that to define with respect to a given distribution.
• 38:50
  And what people do today is that they have benchmarks, right? They have benchmarks.
• 38:54
  And if you pass benchmarks, then you then you're golden.
• 38:58
  Um, so could you have like a more rigorous definition?
• 39:00
  Because the problem with benchmarks is everybody knows the benchmarks, uh, a benchmarks in general.
• 39:06
  It's hard to define what it is that they are achieving for you.
• 39:09
  Uh, so, um, so this is a paper from a few years ago, uh, which we call interactive proofs for verifying,
• 39:15
  uh, should say, verifying, uh, the quality or accuracy of machine learning.
• 39:19
  And, um, and this is just getting warmed up in some sense, this particular paper, uh,
• 39:25
  so the definition we gave there is on one hand, there's valiant, uh, PAC learning, I'm sure that everybody here knows.
• 39:31
  So you give examples.
• 39:32
  And what does it mean that you're eventually your model, uh, it learns is that, uh, you know, it's accurate with high probability.
• 39:39
  And, uh, you could talk now about probabilistic and approximate verification, not just learning.
• 39:45
  So whereas in PAC, you talked about learning. Now I want to verify.
• 39:49
  And here's a possible definition. What do I want to verify I want to verify the let's say this is the model designer.
• 39:55
  And they gave me a model. Let's say it looks like a neural net here, but just h in general.
• 39:59
  Now I could ask the questions and get back answers could go interactively.
• 40:02
  And at the end I want to be with very high probability, uh, assured that, um,
• 40:08
  this model is within an additive error of the most accurate model possible for a given distribution.
• 40:13
  So what does that mean? So let's unpack it a little bit more. Um, we say that let's say this to this H is um, is in a class.
• 40:21
  So it could be neural nets of a certain depth. It could be decision trees. It could be, uh, some other machine learning algorithm.
• 40:28
  Uh, but there's a class of, uh, uh, that is that your model belongs to.
• 40:33
  And you would say that this class is verifiable if, uh, something here.
• 40:40
  Some. There's something that was underneath this.
• 40:45
  Never mind if the following one a it's verifiable if for every.
• 40:51
  Um.
• 40:53
  So that for every other, uh, hypothesis h prime in the class, the loss of your H is within an additive error of that, uh, or the loss of of H prime.
• 41:03
  So it's not worse than the best by except for it by an additive value from the burst from the best hypothesis in that class.
• 41:12
  Um, and, uh, of course, you want again that in addition to the fact that your loss is most additive, uh, is that double efficiency and that is it.
• 41:21
  The verify is much more efficient in sample size or quality than than the model designer.
• 41:26
  And can you get that. So we have various a bunch of results.
• 41:30
  So here is one. This is sort of very technical uh for general talk.
• 41:33
  But this is uh the class of functions here, uh, which are t sparse.
• 41:40
  So if you look at their Fourier representation, there's only a constant number of non-zero coefficients,
• 41:45
  which are large, uh, and uh, this captures decision trees, the formulas a C0 circuits.
• 41:51
  And the theorem shows that let's say that, uh, the designer was modelling with h a a ground truth that obeyed these properties.
• 42:01
  Okay. Then you can verify that the model that they gave you is as good as, uh, within additive from,
• 42:09
  from the best one, uh, using a lot less, uh, data than what the model designer used.
• 42:16
  So in particular, you use essentially, um, only random samples.
• 42:21
  So it's well known that in order to learn these kind of functions, you need query access, um, to the samples.
• 42:28
  So you need to choose X and then get well, you can't just get random XYZ whereas the verifier you can just use random samples.
• 42:35
  So what does that say? It means the verifier still has to do work, but he's working with a lot less.
• 42:40
  Uh uh uh uh,
• 42:42
  availability of data and availability of access to data and yet into now verify that the model that it was given is indeed as good as basically,
• 42:52
  except for the error term, uh, any model of the form that he got.
• 42:56
  And there are a lot of other results. In fact, there was an improvement by Tom Gore of this particular result, uh, called On the Limit of Interactive.
• 43:04
  So this is another paper, but Tom Gore's result is actually quite interesting. He improve the efficiency significantly.
• 43:10
  Okay. Now what about worst case guarantees.
• 43:13
  So what this talks about is somebody gives me a model and I want to check that the model does well okay.
• 43:19
  And I want to get like a normal benchmarking.
• 43:22
  But with respect to this definition for example it does as well as any other model in the class that I provided.
• 43:27
  But what about worst case guarantees. So let's say the model that I got, you know, I checked in either using various methods or benchmarking.
• 43:37
  And 99% of the time it's good on the task. Um, but then a particular input comes in.
• 43:44
  And you get a particular output. How do you know that?
• 43:48
  Actually the answer you got, whether it's a prediction or you in the context of a large language model and you ask it how to I don't know,
• 43:56
  it's a maybe you gave it's your medical record in there. And he told you that you have five years to live.
• 44:00
  You'd like to know whether that's accurate. Um, not wait five years.
• 44:03
  So, so so, um, uh, we don't know anything.
• 44:07
  Really. We know there's no answer. As you well know, there's lots of examples when even multiplying large numbers, that the answer is incorrect.
• 44:16
  So what we'd like is really ultimately to be able to not just know that the model overall has 99% accuracy,
• 44:23
  but we'd like to know where the particular answer on our particular question is.
• 44:27
  Correct. So I think if this is where the average case to worst case, even in the worst case,
• 44:33
  the hardest x, do you give get any kind of certainty that the answer is correct?
• 44:38
  And um. This is in a paper with two of my students, actually.
• 44:43
  So I used to be my student, but now he's a faculty already for many years. Uh, it's addresses, actually, not prediction, but a large language model.
• 44:50
  So generative models. And we asking, could you actually train a model since these models supposedly can be trained to do everything,
• 44:59
  so you ask it a question gives you an answer. Math, science, literature, um, psychological advice.
• 45:06
  Maybe they can also generate proofs in the same way that they generate answers.
• 45:10
  So you would like them to give you not only the output y, but also a proof that Y is correct.
• 45:16
  Of course. What do we mean by correct here?
• 45:17
  If it's a math problem as well, define, you know, um, when we're talking about natural language and so forth, I think it's a fascinating question.
• 45:24
  How are we going to define what correct means?
• 45:25
  Do we have a database of correct facts that we can show that, you know, there's a contradiction to whatever was generated with those facts.
• 45:32
  Let's leave that aside. Let's say that we have a notion of correct, let's say within mathematics.
• 45:36
  So two numbers being multiplied. There is one answer. That's correct.
• 45:39
  It could be multiple answers that are correct, but we have at least a sound definition of what correctness means.
• 45:45
  So now that we have that, can we actually teach a language models to come up with proofs as well.
• 45:49
  So um, that's the in this paper, um, and we first need a model.
• 45:55
  So here is the, the, the let's say the language model, you know, whatever ChatGPT whatever.
• 46:01
  And what we're going to add in is something we call a verifier.
• 46:04
  So we say let's take design an algorithm that's not part of the machine learning process.
• 46:08
  We design it, we call them the verifier and it's fully verified okay.
• 46:14
  Meaning that I know I trust this this particular verifier.
• 46:17
  And now um, on a when an input x comes in, he also comes in to the verifier, maybe the even the verifier generated it and he gets the answer y.
• 46:25
  But now we want to be convinced that y is correct. So we want to prove that Y is correct.
• 46:30
  What we allow here and this abstraction is the proof could be interactive.
• 46:34
  So it could be that an incorrect for some relation, it could be that, uh, the verifier can ask questions,
• 46:39
  get answers back and forth at the end there where say is I accept y is correct or I reject y is incorrect.
• 46:48
  Okay. So this is just, uh, a model. Now what are the requirements?
• 46:51
  What we'd like is first of all that this is sound. What does that mean?
• 46:55
  That if Y is incorrect, we reject with high probability.
• 46:58
  So first of all we say, you know I want to reject incorrect height wise.
• 47:02
  Now of course I could just reject all the time so soundness would be satisfied.
• 47:06
  So we want also some utility out of this. And there we um essentially what we want.
• 47:11
  So the standard thing for machine learning is the probability over x is that we'll get a correct Y is high.
• 47:18
  What I'd like in addition is to say is that the model can also be, uh,
• 47:25
  produce these, uh, answers to my question so that at the end I will be convinced.
• 47:31
  So we call it self probability by p. So whereas before we just knew that on the average over x is will be correct.
• 47:37
  Now I'm saying incorrect Y's will always be rejected. And also with high probability correct Y's I will be convinced to accept.
• 47:46
  So right now, we're sort of happy that 99% of the time we get the right answer.
• 47:49
  We're saying we want also that 99% of the time, or 98% of the time, not only we get the answer, but we also get a proof.
• 47:57
  And, uh, that's the model. And, uh, there's a theorem which is sort of a, uh, um, um, a under some.
• 48:05
  Convexity Lipschitz assumptions that says how to train a.
• 48:10
  When can you train a model to give you a proof?
• 48:13
  And the idea here is actually to use, uh, stochastic gradient ascent actually, but some variant of stochastic gradient, uh, uh, descent.
• 48:23
  And uh, also the new thing about this theorem, which we don't really have time because I do want to get to my other stuff to get into it, is that.
• 48:31
  What you are given. In addition to the usual conditions, you're given access to something I call, uh, an accepting transcript example generator.
• 48:40
  So the only thing that's new on this, uh, um.
• 48:45
  On this line is this concept. What does that mean? It means you have examples of proofs of like theorems, if you like.
• 48:52
  So if we say that multiplication okay, there's a let's say there's a proof that the result is correct.
• 48:57
  What would be the result is correct. So one is that you do it yourself.
• 49:00
  We don't want that. We want it to be shorter. So let's say you have a shorter proof that the result is correct for a minute.
• 49:05
  What I want is to have lots of examples of x and y which have been multiplied.
• 49:10
  And these type of proofs, if I, I have these are the examples in in a sense I show that the, the, the large language model.
• 49:17
  So it learns how to generate proofs of this sort for the new x, x, y that you want to multiply.
• 49:24
  Because again, those are sequences. If you think about what these proofs look like, they're sequences.
• 49:28
  I'm giving a lot of examples of sequences which are a number of x and y,
• 49:31
  and then a proof that an alleged product and a proof that that product is correct.
• 49:36
  So can we teach, uh, how to, um, how to generate these proofs?
• 49:41
  So I think that for mathematicians that probably are a subset here, at least, the idea that proofs are just a sequence is kind of insane.
• 49:49
  But, uh, the fact is that, um.
• 49:55
  We have, uh, a theorem that tells you that if you had access.
• 49:59
  And then in a minute we'll have experiments to a lot of examples of proofs, okay, of a certain type.
• 50:04
  Then you will be able to generate these proofs yourselves in such a way that the verifier will be able to reject those which are incorrect.
• 50:12
  So in other words, that's a proof if you can reject incorrect proofs with extremely high probability.
• 50:17
  That's a notion of a proof that at least we accept when the small probability is under your control of of of of mistake.
• 50:26
  And there's of course a complexity to training the model.
• 50:29
  And these, uh, the number of iterations that have to be of, uh, the gradient descent that have to go through.
• 50:34
  And interestingly, I think this is the most interesting part, is that the size of the this interaction, the question and answer.
• 50:41
  So this is the overall, uh, actually answer size.
• 50:44
  Length is a very important, uh, part of how long it takes you to train a model to be able to come up with proofs.
• 50:52
  So the longer those proofs are, the more time it takes. Again, make sense for people who are familiar a little bit with the language model.
• 50:59
  Uh, uh, space. Okay.
• 51:02
  So we did do it. Um, lab experiments for the simplest algorithm.
• 51:07
  You know, when we teach introduction to algorithm, we we always say that Euclid's algorithm is the first algorithm ever invented.
• 51:13
  Uh, do you say that here? We say in Greece. I'm sure they say, but in any case.
• 51:17
  So, so so, uh, um, and the algorithm, you know, this GCD, you know, you have two numbers.
• 51:23
  You want to find the greatest common divisor. And what's nice about it is there actually are these coefficients.
• 51:28
  Right. If you can find these two numbers such that you could take the combination of uh,
• 51:33
  so let's say x1 and x2 where what you're trying to find that you see this row and z1 z2 are these coefficients.
• 51:39
  Then this linear combination, um, if it divides both x1 and x2, that's actually a proof that this linear combination is the greatest common divisor.
• 51:50
  Um, so this is an ancient we all know the existence of these coefficients.
• 51:56
  And indeed Euclid's algorithm, when they compute the greatest common divisor of x1 and x2, they also compute those coefficients.
• 52:03
  But when the large language model I gave it x1 and x2 and it gives me, it says, hey, here's the greatest common divisor.
• 52:09
  Maybe it's true, maybe it's not. I don't know if it use Euclid's algorithm.
• 52:13
  I don't know what it does, okay. But it certainly doesn't output these coefficients.
• 52:17
  So you could think of, uh,
• 52:19
  a particular case is that I'd like to find I'd like to train the model not only to give me that solution to greatest common divisor,
• 52:26
  but also give me these coefficients, which are essentially a proof, their proof, because if I then can if I get the coefficients,
• 52:33
  I could just do this one multiplication plus another multiplication and check that that is equal to the answer they gave me.
• 52:39
  And if it is, that is actually 100% proof that the answer was correct.
• 52:43
  So, um, that's a exactly what we do.
• 52:48
  And uh, we kind of give it a lot of examples of.
• 52:51
  X1 y1 z1, z2. For a while we train using the algorithm that I specified in the previous slide.
• 52:57
  And at the end indeed, you get a model which outputs these coefficients in addition to the answer.
• 53:02
  And.
• 53:04
  If GPT is doing 99.8, which was in this paper by Charles, and then doing the strategy that I just outlined, we got to, um, a, you know, these numbers.
• 53:16
  So the verifiability is only 60%. That's a much less.
• 53:19
  But it's better than nothing. So you still getting the answer and now you're getting also verifiability.
• 53:23
  And it turns out that with other methods we can actually get up to 96%.
• 53:27
  But I won't get into it. What is the point of this? I'm done with this part of the talk.
• 53:31
  The point here is that verifiability of accuracy on the average and accuracy in the worst case, are some things that can be formally defined.
• 53:39
  Whether you like my definition or what I propose another one, but they should be defined and then achieved.
• 53:45
  And uh, this whole I just, I think my student or was here and gave a talk.
• 53:48
  So some people may have gone.
• 53:49
  So there's a vast literature right now about using some kind of an interactive proof, uh, in the context of machine learning.
• 53:58
  Not in this, not our definition, but others. This could be within mass assisted proving.
• 54:03
  Uh, there's actually going to be a workshop at Simons,
• 54:05
  which I think will be very interesting is is going to be the Simons Institute and the emissary on the Hill at Berkeley,
• 54:10
  which is all about math assisted proofs. So it's really run by mathematicians mostly and mostly focussed on lean.
• 54:16
  Uh, but there are other things in safety alignment where they sort of the concept of a verifier,
• 54:21
  sometimes a verifier themselves are a machine learning model, in which case it's like turtles all the way.
• 54:27
  You know, this is what that means. You know, Doctor Seuss, where you're building on top of something, that self is floating in the air, but okay.
• 54:34
  Um, all right. I want to get to my last part I have.
• 54:37
  I'll take five minutes. Okay. So we talked about privacy.
• 54:42
  We talked about verification. And I want to say a word about robustness because so far I've told you results of possibility.
• 54:47
  I said look it's possible to protect privacy.
• 54:51
  It's possible to maybe check verifiability. Uh, it's a worst case guarantees.
• 54:57
  And I want to show you one place where I could show an impossibility. Uh, using cryptography also.
• 55:03
  Um. Okay. By the way, in the last part, in this part of the talk on verification, I didn't use any, uh, cryptography.
• 55:12
  I didn't use hard problems like encryption, digital signatures, whatever.
• 55:16
  What I use was this paradigm of interactive proofs, which also comes from the field of cryptography and verification.
• 55:22
  Um, so that's the inspiration there. So we're back to this, uh, ML as a service.
• 55:30
  But in the previous slide, the machine learning guy, they wanted to design a good model and to prove to you that the model was good.
• 55:36
  Okay, so in some sense you are training the model to do the come up with proofs.
• 55:40
  So they were collaborating with you even though you were verifying their answers at the end.
• 55:46
  But let's think of a worse scenario. Let's think that there is, uh, you know, this dark cloud.
• 55:53
  So the service provider really is evil, or at least has evil people working in there, which I think is to be assumed.
• 56:00
  It's ridiculous not to assume that, you know, at least coming from a country like I do is like, yeah, of course.
• 56:05
  Uh, okay. Um, so, um, I think it's true about the world at large, but in any case.
• 56:15
  So what's the, um, kind of American? Uh, um, uh, what, uh, example.
• 56:21
  So we have a bank, and the bank doesn't want to give me a loan unless they think that I'll pay it.
• 56:26
  So, uh, they look at the loan application.
• 56:29
  I don't know if you've ever tried to get a mortgage in the United States, but in some sense, the more money you have in, the more assets you have,
• 56:34
  the less likely that they actually give you a mortgage, because there's so many things to check, and it's all about checking, uh, in any case.
• 56:40
  So they say, okay, now there is this company, they're going to give them all the old loans,
• 56:43
  whether they gave them the loan, whether the loan was returned, uh, and they get back a model.
• 56:49
  Okay. And then we say, um, well, uh, wonderful.
• 56:54
  This model, from now on, loans come in and it says, give it or don't give it.
• 56:59
  Okay. Beautiful. Um, so what does the.
• 57:04
  What do people in the company say? They say, that's very nice, but I want to get a loan sometime down the line.
• 57:09
  So what I'm going to do is I'm going to put in some sort of back door into the model, and I keep the key.
• 57:15
  So here the model changed a little bit by that little yellow square. And I keep the key.
• 57:19
  And um. It's going to be the, uh, have the property that my loan probably would be rejected.
• 57:27
  Okay. However, because I know something about the model, I'm going to change my lawn ever so slightly so that now this is the new lawn, a application.
• 57:37
  It's changed slightly because I know something about the model. And from and now my my loan gets accepted so I can change inputs.
• 57:45
  In a way that the machine to fool the machine learning algorithm that I myself designed actually in this case,
• 57:51
  so that even though a natural, uh, input would have been rejected, I will make it accept it.
• 57:58
  And you can think of this much more generally if you think about a large language model is not supposed to tell us how to produce atomic bombs.
• 58:03
  You could make a change, say, well, maybe there's a screening alignment,
• 58:07
  but I will make my queries such that they will break the alignment, uh, the fence or the safety, uh, guardrails and so forth.
• 58:14
  And what we show is in this paper, uh, is that, uh, in fact, not only this is a, uh, a fantasy of, uh, of science fiction,
• 58:25
  but if digital signatures exist, cryptographic digital signatures, then you can plant backdoors in any neural net.
• 58:31
  And furthermore, this backdoor will be undetectable and non replicable.
• 58:35
  So I'll explain what I mean. Non replicable I mean that even if somebody saw examples of modified loan uh in modified loans in the past,
• 58:45
  they wouldn't be able to come up with another one and undetectable.
• 58:49
  I'll define in a second.
• 58:49
  But what I want to say undetectable is that if you look at the model and you are, uh, so if you first you have input output access to the model,
• 58:57
  you could put lots of inputs and outputs and try to see whether there is a backdoor in there
• 59:01
  and show that that will be impossible again under this assumption of digital signatures.
• 59:06
  Now, the second phase would be not just feeding inputs and outputs like black box, but actually white box.
• 59:12
  Looking at the model, that's much harder. So for right now,
• 59:14
  this theorem stands just by assuming that all you have in your disposal to try to figure out whether this model has a backdoor in it or not,
• 59:22
  is the ability to run it on inputs of your of your choice. So what does it really look like?
• 59:28
  It's something like this. First of all, we know that if, uh, digital signatures, um, if this problem from lattices is a is indeed a hard problem,
• 59:38
  the LWR that I showed you there is a digital signature scheme. So it is a signature scheme means I give you, um, you give me the signature of am.
• 59:44
  Nobody else can do it unless they knew the secret key. They can't even produce new and prime signature of in prime.
• 59:49
  And this is a neural net that implements it. It's very, very small. It's four layers.
• 59:54
  And then you could, um, take any your neural net.
• 59:58
  Okay. Whatever it is, that big box and add a little box to it.
• 1:00:01
  Okay. Which is it's actually not the digital signature. Uh, it signs is the verification that it's a correct digital signature.
• 1:00:08
  So when the input comes in, the person who knows the key will take the input and modify it.
• 1:00:13
  So now an input and a signature. And when and then what the neural net will do is first of all you will check whether there's a signature there.
• 1:00:20
  Okay. Uh, so it verify there is a signature there of the rest of the, of the input.
• 1:00:25
  And if there is then it accepts the loan okay. Otherwise it rejects.
• 1:00:29
  So it's a very simple change. Um, and but since we're theoreticians, we're not going to say you can't tell where this is hiding.
• 1:00:35
  We say if there's a black box access, you cannot tell. So this is sort of the notion of, uh, backdoor, um, detectability.
• 1:00:42
  Uh, is that, um, okay.
• 1:00:45
  Well, whoever wants the Q&A, of course, you could talk about white box.
• 1:00:49
  What if the what if what if you could also look at the weights of the model?
• 1:00:53
  Is it true now that it's undetectable?
• 1:00:56
  So we could do this even that for very restricted models like one layer, this, uh, a learning curve around the Fourier features.
• 1:01:04
  Um, what's interesting here is that whereas before the idea was to add a digital signature,
• 1:01:09
  the idea here is to use random numbers rather than random numbers on the weights.
• 1:01:13
  And the pseudo random numbers are from a distribution which is hard to distinguish from random based on crypto again,
• 1:01:18
  and they will if you know what they are, you know how to kind of tweak your inputs so that they will be, uh, accepted.
• 1:01:25
  Okay. So. Again, you could say always.
• 1:01:29
  Oh, but this is only a theoretical, crazy thing that somebody would do. It turns out that people believe theories when it talks.
• 1:01:35
  When we talk about attacks much more than when we talk about solutions.
• 1:01:38
  Uh, and uh, indeed, now there's a big program, I think, in DARPA or something where they want people to attack.
• 1:01:44
  So they say it's, uh, give models with backdoors and, um, so that we know what to fight.
• 1:01:51
  So, uh, they want to see lots of examples of backdoors to be able to try to identify them.
• 1:01:56
  So this is almost the last slide. What's the takeaway from this is that we shouldn't be terrified.
• 1:02:00
  No. Uh, I think the takeaway is that we should not trust the models and that we should assume that there are,
• 1:02:07
  that they have problems and we should post-process them.
• 1:02:10
  So rather than just using them sort of as they are, you, uh, you know, it's sort of like,
• 1:02:14
  you know, we don't know that I necessarily have germs, but I still wash my hands.
• 1:02:18
  Uh, you you wash your hands. Uh,
• 1:02:20
  and so sort of the messages that we would like to try to do mitigation of problems without necessarily detection because sometimes it's undetectable.
• 1:02:27
  But you can prove that regardless of what problem was there, you could mitigated by some more work.
• 1:02:32
  And this is a recent paper is going to appear in the next few months, uh, in stock.
• 1:02:38
  And there's we take we show that for certain ground truth type of uh, you could actually mitigate without detect.
• 1:02:46
  And again, the one of them is for us for a function ground truth.
• 1:02:50
  Like I mentioned before, another one is for like linear regression and polynomial regression.
• 1:02:55
  So say somebody gives you, uh, in a regression, a model A that has a backdoor in it.
• 1:03:02
  So it will give you the wrong results. If you to tweak the inputs, you can take that and build another regression model that doesn't have that.
• 1:03:10
  You provably have removed the backdoor.
• 1:03:13
  Um, so to end, I want to say that this whole thing about verifying or mitigating, um, I think I, Roslyn, proposed the name Verifiable Data science.
• 1:03:24
  I think it's important. I think there's a lot of work on it by, uh, other people as well as me.
• 1:03:31
  And I guess the main thing is that, uh, safety is a big challenge.
• 1:03:36
  Um, uh, it's a quote I can remember for more and more, uh.
• 1:03:42
  You think it was in this website that they're saying, uh, technological progress can excite us, politics can infuriate us, Wars can mobilise us.
• 1:03:50
  But faced with the risk of human extinction, that the rise of artificial intelligence causing, we have remained surprisingly, surprisingly passive.
• 1:03:57
  I don't know, it sounds good, but I think it is true that this is a huge, huge,
• 1:04:02
  huge tool and we have to be very mindful of the fact that, uh, that, uh, safety is important and we should work on it.
• 1:04:10
  Thank you.