Improving Algorithmic Efficiency Using Cryptography - Or Zamir

What this episode is about

The content discusses the innovative use of cryptographic principles to enhance algorithmic efficiency, specifically focusing on how concepts like computational indistinguishability can potentially improve the running times of basic algorithmic tasks. The aim is to explore applications of cryptography beyond its traditional roles in security and privacy, seeking to apply its foundational ideas to optimize algorithms in a straightforward manner.

Key takeaways

• Cryptography isn't just for secrecy; it can optimize algorithms—sort of like a fitness trainer for logic.
• Indistinguishability: the magician's trick of cryptography; it hides complexity better than a cloak of invisibility.
• Using cryptographic concepts for basic algorithms is like adding nitrous to a car—it supercharges performance!
• Efficiency trad: because who knew your secret key could transform tedious computations into lightning-fast operations?
• Even in a world of fancy tools, the simplest ideas can unlock revolutionary advances—like a key to a locked box!

Who speaks in this episode?

• Zamir (Host) · 44 min speaking

What is discussed, and when

1. 0:00 – 5:00: Vinod
2. 10:00 – 15:00: Johnson-Lindenstrauss lemma
3. 15:00 – 20:00: Bloom, Lubell, and Rubenfeld
4. 30:00 – 35:00: AWS
5. 35:00 – 40:00: LPN conjecture

Notable quotes from "Improving Algorithmic Efficiency Using Cryptography - Or Zamir"

• I'm also happy that I had an hour to defrost before the talk. okay. I am going to talk about a joint work with Vinod about how we can use cryptography to improve the efficiency of algorithms.

  about Vinod · at 0:21

• Say with non-negligible probability which of the two distributions it's usually assuming some cryptographic arms conjecture. Yes. So the entire notion is I can't distinguish…

  about LPN conjecture · at 2:39

• So the classic Johnson lineage stma says that I always can take any set of end points in any possibly large uklidian dimension and map them into a set of end points in a much lower dimension such.

  about Johnson-Lindenstrauss lemma · at 11:29

• So a classic result of Bloom, Lubby and Rubenfeld is the following. They show that if we have some algorithm that computes the multiplication of random matrices over a finite field. Why do I what do I mean by that? I mean that I.

  about Bloom, Lubell, and Rubenfeld · at 15:47

• Things currently for maths and then there are follow-ups that are trying to do it for the full inference process. So there are also people from AWS that are actually…

  about AWS · at 31:52

Who and what is mentioned in this episode?

People

• Vinod — Person · Coauthor / collaborator of the speaker · 1 mention · first at 0:27
  The speaker presents the talk as joint work with Vinod on using cryptographic indistinguishability to speed up algorithms (e.g., via trapdoor matrix families).
• Bloom, Lubell, and Rubenfeld — Person · Referenced experts (authors of a classic result) · 1 mention · first at 16:35
  Cited for a classic worst-case to average-case reduction for matrix multiplication over finite fields, used as a motivating example for the speaker’s cryptography-based speedups.

Concepts & topics

• LPN conjecture — Concept · Core topic · 1 mention · first at 35:02
  Central cryptographic assumption used to construct trapdoor matrix families for improving algorithm efficiency.
• Johnson-Lindenstrauss lemma — Concept · Key argument · 1 mention · first at 12:44
  Classic result in dimensionality reduction that serves as a foundational example for applying trapdoor matrix families.

Sponsors

• AWS — Company · Sponsor · 1 mention · first at 32:01
  Mentioned as implementing practical variants of cryptographic tools for private inference, claiming significant speed improvements.

Full transcript with timestamps

0:14 our second feature for today. We have all Thank you. I'm very happy to be back. I'm also happy that I had an hour to defrost before the before the talk. Um, okay. I am going to talk about a joint work with Vinod about how we can use cryptography to improve the efficiency of algorithms. Unlike air's talk, I am intending to say nothing about any fancy tools. I'm trying to use only the simplest tools possible for everything. Nothing fancy will be and also I will not assume knowledge about good. So let's just say a few words about cryptography. Uh obviously at this point we have many years where people worked extensively on cryptography. We have a very large body of work very impressive arsenal of tools. Most of them are used for cryptographic purposes. This is a very uninspiring tology. But what I mean by that is that we usually use it for things like privacy and security and trust and so on. But we do have from the very

1:22 beginning a few applications of either cryptography or cryptography inspired notions for some other things outside of this cryptographic purposes. For examples, things like reducing randomness or randomizing things or reducing interaction say famil. Um so we have seen a few examples of using these tools out of cryptography. But what we are going to ask is can we use the same cryptographic tools or notions for maybe the most basic algorithmic task which is improving the running times of problems and the only notion from cryptography I would need is the classic notion of computational indistinguishability.

2:08 So what is that? The formal definition doesn't matter that much. What I need is the essence of it which is that cryptograph cryptographic indist or computational indistinguishability means that I have two distributions such that any polomial time algorithm cannot distinguish between them. Meaning that for every polinomial time algorithm if I would allow it to take samples from the first distribution or alternatively I would allow it to take samples from the second distribution but I don't I will not tell it which it will not be able to say with non-negligible probability which of the two distributions it's usually assuming some cryptographic arms conjecture. Yes. So the entire notion is I can't distinguish between two distributions. I will not need uh anything more than that. And this comes up a lot in cryptography. So in some obvious things that should come to mind when I'm saying this things like a sudo

3:03 random number generator or program obiscation or so on. But even when you are trying to define encryption then indistinguishability is the the easiest nicest way to define saying something like for any two inputs the encryption if I don't have the key is indistinguishable from each other. So I can't I can't tell anything about which input I saw and so on. But this encryption example is good because this also shows us some asterisk that we usually have there is that usually when we use indistinguishability the indistinguishability is maintained only as long as we don't have access to some secret key right so for example back in the uh in the example of encryption if I do have the key I can decrypt. So obviously this doesn't look random anymore. This does distinguish different inputs at this point. But without the key it is indistinguishable from each other. I would say with a PRG maybe also if I have a secret key I'm

4:03 now able to to generate the the next numbers myself. So things stop looking random when I have this secret key. And the new notion we want to introduce is something we will call an efficiency trad which will follow along the same lines. But now there will be something else that I can do when I have the key. So now when I would what I would want is to have some distribution of functions such that if I don't have a secret key then this distribution of functions is indistinguishable from the actual distribution uniform distribution or some distribution we care of. But if I do have the key for some reason I can apply the function that I sampled very quickly.

4:45 So now the the thing that the key gives me is the ability to apply function variable comput

4:52 yes to comput it on any this is a actually so maybe to be more concrete here is like one more concrete instantiation of this that we introduce called dor matrix families. So this is going to be a distribution of pairs of a matrix and a circuit such that the marginal distribution only on the matrix if I show you just the matrix that I sampled out of this distribution this is indistinguishable from a random matrix

5:21 without assumption with assumptions computationally indistinguishable under some assumptions from a random matrix but that circuit exactly computes the matrix vector product with the matrix that came with it out of the out of the distribution and it is in nearly now size circuit or a circuit that is very easy to compute.

5:45 So this should be in the first bullet really it is the distribution of pairs where the circuit is nearly enough.

5:52 Yes. Yes. But I mean I wanted to give it some flexibility because I will show you first the construction which it is not nearly now but just have a matrix and the circuit that computes it. So M is M by N and C is like Morgan or something.

6:06 Yes. So I'm leaving I'm leaving several gaps because I will fill them with with some uh yes some examples very soon. Okay. Good. So to try to fill the gaps. Uh so I also need to say what is a random matrix. So we show constructions for this that are uniform under over finite fields but also for distributions of matrices over the real. So we can do this for currently for any distribution that is rotation in variance. So say matrices of random gaussians but also I don't know orthogonal ensembles and so on. So a concrete example we show that for any finite field we can construct such a trapdoor matrix family distribution for the uniform distribution over the finite field for say square n byn matrices where the running time of the circuit is nearly n and we can do this from several conjectures. So we can do this say from the LPM conjecture or the mech conjecture and probably from from several others as well. So you do need

7:14 to assume some conjecture but in the end I will get to why it doesn't really matter which you can do it for many many different conjectures. Good. And one extra thing to mention is that we do need to have some computational assumption. We do need to have a conjecture. Why? Because the mere existent of such a small circuit this is surprising. This is something that entropy wise shouldn't happen. So uh without any computational assumptions just checking whether or not there is a small circuit will be a distinguish good and I will also say but for most of the will not need it uh that we can do it in such a way that we can have small circuit not only for a matrix vector multiplication but also to many many other operations using this matrix. So for example getting matrix matrix multiplication is easy right because if matrix vector is linear then of course matrix matrix is linear as well but we

8:10 can also multiply with the transpose or with the inverse and so on and all of this in linear time if we construct it correctly and now I want to explain the general recipe of how can we use this creature to turn algorithms into faster algorithms. So the general recipe we have in mind is as follows. Say we have an algorithm that at some point samples a random matrix for whatever reason. Soon we will see examples of this actually happening and then at later points it uses this random matrix. Say it looks at specific vectors multiplies them by this matrix and does something with the output. Then any such algorithm I can make it faster. Why? because I can first take this random matrix that is sampled here and replace it with sampling a matrix from my door distribution right and so far I couldn't have changed anything why couldn't I have changed anything because this is a polomial time algorithm so if either the correctness

9:13 or the runtime or anything would have changed this would have been a distinguisher so there cannot be any noticeable change or any non-neg negligible probability change to what happens in the algorithm by changing uh the distribution of actually random matrices to this pseudo random distribution of matrices. But now after I did that every time that I multiply by a I can replace it with my circuit which that computes exactly the matrix of multiplication. So this also didn't change anything in terms of correctness and so

9:48 how much time do you allow the distinguisher good so if we are using a cryptographic conjecture usually assume that any poly time algorithm will not be a distinguisher but I will very soon get to exactly

10:03 once yes good and this change also didn't change anything right because this is now functionally exactly the same just replace the matrix multiplication with something that computes exact exactly the same function. So this also didn't change the correctness at all or what is computed at all as a function. But now the running time is lower. Every time that the matrix multiplication previously took me quadratic time now it takes me only linear time. So I have something that completely preserved correctness but the efficiency is improved now because of what happened to these slides.

10:38 And as a said, we are actually relying on the cryptographic assumptions in a much much weaker way than we usually do in cryptography because usually in cryptography we are saying something like there is no poly time algorithm that breaks LPN when it tries to break LPN. It can use any polomial time and its intention is to break LPN. Now I will say something like this innocent quadratic time or cubic time algorithm doesn't break LPN by chance which is a weaker way to to use these assumptions. Good. So now I want to give you a couple of examples to try and convince you that this structure actually happens that we do have algorithms that look like this.

11:23 Something can paint from this. The most obvious example is everything related to dimension reductions. So the classic Johnson lineage stma says that I always can take any set of end points in any possibly large uklidian dimension and map them into a set of end points in a much lower dimension such that all pairway distances will be preserved up to say 1 + minus epsilon.

11:51 But the matrix is narrow anyway it's nearer than good. So uh I'll say a couple of things about that soon. Uh but yes, what what are the how do I do this and what is the dimension I can reduce the set of points to um so for this all I would need is a random linear transformation. This would be good enough for for this to work for a JL to be proven and the dimension I would need would be something like log the number of points over how much error I'm willing to have square and as I said this might be like in many many applications this is small anyway in some applications it is not small if I need a okay first of all this is very useful in geometric algorithms of sorts and so on Um yes if if epsilon is relatively large then this is quite small and this matrix is quite narrow. Anyway uh there came many uh many applications in which you needed this to be slightly larger and this is why people worked on something

12:56 called sparse jail transforms. So there is a way to make it faster. There are ways to to have this type of matrices that are even faster than doing this matrix multiplication. So maybe this is solved. Maybe we don't have to do anything. But there is some problem. The problem is that besides this original JLMA, there are nowadays many many JL type lemas. What do I mean by that? So there are many other settings that are similar. I have something in higher dimension. I want to reduce the dimension and preserve some things that are slightly more complicated. So one example of these things could be like I don't have a bound on the number of points I have but I know something about say they are coming from a manifold or they're coming from some low intrinsic dimension some space of low doubling dimension and so on. Uh this comes up a lot now in a machine learning related applications because people are saying something like

13:53 the data is represented using very large vectors but it has a small intrinsic dimension. So I want to reduce the dimension but actually the clusters say would be preserved. And this comes to the the second thing that is changing in many applications. What I want to preserve is not necessarily just the pair wise distances but maybe some other measure say the clustering or like the the top clusters or cuts or MSD and things like that. So we have a lot of those variants of the Johnson Len SMA. Some of them require a much larger output dimension. say if I'm trying to preserve a subset like an entirely subset or something like that. Um but it turns out that for everything I wrote here and many other varants a randomly projection works. You take a random matrix and you prove that you that you get whatever you wanted whichever properties you wanted preserved. The problem is that the sparse variance no

14:49 longer work. And when people cared enough, they needed to work very hard for each specific variant to show that you can still have some quick dimension reduction transform specifically for that variant. And what we are saying is that this trap door matrix family would work for any of them because anything that you could have done with a random matrix now you can do with a matrix that is sparse in the sense that you have fast multiplication. So we have some examples especially in this ML related settings in which we didn't know how to do it before and now we have a dimension reduction again that preserves whatever you want.

15:27 Good. So this was the first example. Now I will give you an example that is maybe slightly less obvious. Not something that just says okay let's take a random matrix and do something with it but it's not super directly. uh and this is about worst case to average case reductions for linear algebraic tasks. So a classic result of Bloom, Lubby and Rubenfeld is the following. They show that if we have some algorithm that computes the multiplication of random matrices over a finite field. Why do I what do I mean by that? I mean that I have an algorithm such that if I take a random pair of matrices in my finite field then with probability strictly larger than 3/4 over which input pair I chose my algorithm returns the correct matrix multiplication of them. If I have something like this, then I can construct another algorithm a prime that multiplies any pair of matrices over the same finite field in a very similar

16:30 time. So this is a classical result and the proof is very simple. So let's just see it. The proof is the following. They are saying let's draw two random matrices over my finite field and write down a * b. These are my worst case any two specific matrices as this thing a + r1 * b + r2 and then let's remove what we need minus r1 * b + r2 - a + r1 * r2 and then we add what we removed twice we add r1 * r2 and what we can observe is that marginally each of those matrix multiplications is of two uniform matrices Right? Because whichever matrix I take, if I had a random matrix to it over a finite field, it becomes fully random.

17:22 So each of these marginally is just a pair of like a uniform pair of random matrices. Meaning that I can take my algorithm that does exactly that multiplies two random matrices and query it with each of these pairs. So now these four queries are very dependent, but each of them marginally is uniform. And then what they are saying is that if the success probability was strictly larger than 3/4 then I can just take a union bound over the failure probability of my algorithm. Right? So despite the dependence this one will fail with probability strictly less than a quarter. So are the others. So I have some non-negligible probability some epsilon probability or constant time epsilon probability that all four will return the correct answer.

18:11 Good. So I fully succeed with probability at least for epsilon and if epsilon is constant why is that enough

18:18 matrix m checker exactly because I can verify matrix multiplication very easily right so I will try like one over epsilon times each times I only need quadratic time to check if I got the correct result or not so finally I will get the correct one in time that is very similar to to the time of this black box but now we have a problem with this reduction which is that it is not clear at all that this three quarters is necessary. It was necessary because of the dependencies but it's completely not clear that it should be there. Why not half and why not one over 100? Why not just the success probability epsilon and so on and people for a long time thought about that and recently ish in the last three four years with a lot of quite heavy additive combinatorics additive number theory works people managed to show that you can actually do the same for any constant epsilon with a rather poor dependence on epsilon but you can

19:20 do the same for every uh for every epsilon Don't the later works just use error correcting codes like list decodable codes

19:28 they use but they still need the dependent on the dependence on epsilon be d exponential

19:33 um but yes no the the latest works are simplifying the the previous ones yes but just saying relatively heavy machinery relatively bad dependence on on epsilon but it comes from the fact that this is a I mean like you need to be it already seemed like you need to be very unlucky for these things to be that badly dependent and what they end up showing is that they aren't or that you can make it that they aren't right so um as Max is saying like the earlier works were more of the form of let's show that it doesn't happen the later works are more of the form of let's make sure it doesn't happen um which is easier okay good but what I want to say is that using our door matrices now assuming some cryptographic conjecture we can do this trivially Why can we do this trivially? Because if instead of taking random R1 and R2, I will take trap do R1 and R2 then from the point of view of this algorithm that runs in less than cubic

20:36 time. It is the same like it cannot see that I'm not giving it two random matrices. The distribution of inputs it is getting is indistinguishable from two uniform matrices. So at least this call will have the same success probability as before unless this algorithm is a distinguisher. But these three calls are now very easy. Why are these three calls very easy? Because each of them as a multiplication with one of my trad matrices and all of those I can do in linear time by myself. So actually I don't need to make any of the other three quotes. The other three multiplications I can do at home in quadratic time. Right? Right? So I have only one multiplication now that I need to do. Which means that if this one had success probability epsilon, then now the entire thing would have success probability epsilon. So I'm done. I don't need to do anything good again. Unless this happens to be an LPN distinguisher,

21:33 which would also make me happy. So I'm happy anyway. Actually, yeah, it's a it's a there is some open question here that I will mention at the end of maybe there is a sort of a win-win argument here because in either case I do something linear algebraic way way too fast, right? So either I have like the matrix multiplication algorithm that is too fast or I manage to break LPN faster than matrix multiplication is okay. Um, good example 2+ uh also related to things that other people mentioned also things I think that a you mentioned working about a couple of years ago. What about error correction in in matrix multiplication?

22:16 So previously in this BLR algorithm we assumed that we have some chance of getting the exact multiplication of the two matrices the exact product and otherwise we didn't care. But what if we never get exactly the right product, but we get something that is close to the product or maybe not even close, we just correlate to the product. In what sense? So this is the weakest sense possible. What I'm going to say right now, let's say I have an algorithm A such that on two uniformly drawn matrices A and B, so the input is still uniformly drawn. it gives me something such that the expected heming distance between what the algorithm gives me and the actual multiplication is slightly better than just returning a random matrix. So if the heming distance is smaller than 1 - 1 / pus epsilon * n^ 2 without the epsilon this would have been just what I would get by returning a random matrix every time.

23:16 So have an algorithm that on average inputs returns something that is a tiny bit correlated with the result. Can we use that to get in a very similar running time a worst case algorithm for every two input matrices that returns exactly the correct product? And also very recently this was uh shown to be possible uh with non-uniform algorithms meaning that for every n you need a you need to construct something specific afterwards they also made it a uniform unconditionally uh but this was the first uniform version of that again assuming some cryptographic conjunction in a weak way but let's see because also this would be completely trivial unlike the the previous works So what could we try to do? So we can notice that if we look at exactly the same reduction as before, then I still have only one call. So on this particular call that still looks like two random uh two random matrices like the input to my to my average case

24:22 algorithm. Now I will not get the result with some probability but I will get the result plus some noise matrix. And what do I know about this noise matrix? So let's denote it by a large epsilon. This is like what I get for my algorithm when I give it two random matrices minus the actual product of these two random matrices. So what I know about this random noise and notice that this is independent of of A and B of course right because at this point this is just a random thing. Uh so what I know about this noise matrix, I know that in expectation the number of zeros in it is slightly too large, slightly larger than I would have got uh with just a completely random matrix.

25:08 And because I can do it several times, I can draw R1 and R2 independently several times, then I can get many samples of this thing. And then the the question or the hope is if I have several samples of a distribution of this form, can I use it to get rid of epsilon? Can I sample several times and then just I don't know like take the majority or do something like that to get rid of the noise completely. And it is an extra assumption under which it would be trivial. So if I also told you that this epsilon matrix, this noise matrix is entry-wise uniform in the following sense.

25:48 It is not only that the fraction of zeros is 1 / p plus epsilon, but actually every entry has probability 1 / p plus epsilon at least to be zero. And also every entry is distributed uniformly over all nonzeros. If it is not zero then now removing the noise is easy right because now I can just take one over epsilon square the different r1 and r2s more or less um compute the the histogram or just like the plurality in each coordinate and because the zero appears more than all of the others because now all of the others appear with the same probability that must be lower than one over p because this one is probability higher than one over P then the one I would see the most times this is this is the correct one I'd have to log size of field or something like that for a specific so we could just take many samples and uh and get entry wise plurality and we would be happy the question is why or

26:53 how can we assume that we have this nicer structure and the answer is that it is actually quite easy to force this nicer structure. Why is it easy to force this this nicer structure? Because the matrices that we are going to query the algorithm with are random or indistinguishable from random. So I can do many things to them without changing their distribution. So for example, I can multiply these matrices with a with any nonzero random scalar and the distribution would look the same. Right? If I take a random matrix and I multiply it by two, this is a random matrix. Uh good. So for example, if instead of querying the algorithm on A and B, I would query it on Q * A and B for a random non-zero Q and then I will divide by this Q afterwards.

27:46 Then the second condition I do get like I get the condition that every non-zero is now distributed uniformly over like every specific entry that is not zero is now going to be distributed uniformly over all non-zeros because I multiplied it with with this thing and the algorithm doesn't know the algorithm cannot figure out Q because it was a uniform distribution before it is still uniform distribution and for the first condition that it is not just a fraction of indices but every index is zero with this and that probability I can just take random permutations and multiply n a and b with them. Permutations are very easy to peel off of course right because applying a permutation is is linear. So I can add the permutation here and add a permutation here and peel them off out of it. So now the query again just looks like two random matrices as it looked before. But now I do have these two conditions that the places of the zeros

28:42 are uniform and the nonzeros are also uniform because independent is no I get that every entry uh the plurality will be correct and I will just take a union bound if I do it like login time yes so I just need now to repeat it like log size of field time log n / epsilon squ and then union bound is enough so up to logarithmic factors was done and the dependence on epsilon is just quadratic. Do

29:11 you really need the random permutations for this to work? I guess you should uniformize the non zero.

29:18 You maybe can use a little less, but what we were afraid of is something like an algorithm that always in the first entry says zero.

29:24 Okay. Right. Just you want it to Yeah. But maybe you can do something that is slightly less.

29:30 Okay. It's quick enough. group. Both of these examples that I gave or the three examples that I gave are actually things that we knew or afterwards we know how to do uh maybe besides like the the parameters and so on. But we have several other examples for things that we didn't know how to do without these tools. So for example, if I want similar worst case to average case reductions but not for matrix multiplication but things like matrix inversion or solving a linear system or computing a determinant even then this we didn't know how to do with the previous tools but now we do all of this. Now we have the same worst case to average case reductions again conditioned on this cryptographic things. So for example, if I have a an algorithm that computes the determinant of a random matrix slightly better than always answering zero, then I can have a can in the same running time have an algorithm that computes the determinant

30:24 for any worst case matrix. Uh and as I mentioned in the in the dimension reduction setting, there is actually a tight connection to a certain type of neural networks in which we now have a faster inference time. So there is like a a class of networks in which the first matrix is untrained. The first matrix is essentially just a dimension reduction. Uh so for all of those we now can have fester infers fester training in some sense. Good. Another line of work that followed this that I want to mention starting with actually a concurrent work of a brotherman and human but then several works afterwards was using the same type of construction the same type of trap door matrices back for the settings of cryptography for the test of trying to do private inference with tools that are actually practical unlike FHE.

31:18 Right? So what Mark originally is saying but then then other people afterwards is that while we could use FHE to say let a server do some inference for me or do math moves for me in a way that would not reveal my matrices to the server. This is really impractical. This is efficient only in in theory. But using things like this, you can send a matrix to the server that looks random because you added this trap door matrix to it matrix to it and then you can peel it off by yourself afterwards. So we have a more practical variant of uh of these things currently for maths and then there are follow-ups that are trying to do it for the full inference process. So there are also people from AWS that are actually implementing this and they have some implementations that they claim are much faster than I mean it's very easy to be much faster than FG but they're claiming it is it is getting to be to be

32:11 practical. Good. Now I do want to say something about constructions. How would we construct this thing? Uh I will tell you the bottom line first. The bottom line is going to be that it is very easy to construct these things and we can construct it from nearly any conjecture you would want and you can think of why but in the end I will say something about why it should be very easy. Uh but how would we think of constructing this? So the first thing we we want to have in mind is that we have many families of matrices for which we have easy multiplication. say things like low rank matrices or things like sparse matrices very sparse matrices like very like only few nonzeros or things like FFT type matrices or circular matrices and so on. So have all of those families of matrices that that we can multiply with quickly. What is the problem that all of them are very easy to recognize, right? It's easy to

33:05 tell if something is lower or if something is fast or if something is an FFT matrix. Uh so what can we do? Just mix them up. just let's look at some combination of this uh simple ful mix it up in a way such that if I know this de composition then I can do the multiplication quickly but if I don't know the de composition then decomposing will be hard so something that we should have in mind as a first step is yes matrix rigidity for example it should be hard to tell if a matrix is low plus false so I'll give you a very simple construction that doesn't get near linear time it gets to n to the 1.5 time for a matrix vector multiplication

33:53 does that depend on the parameters of LPN assumption yes yes so LPN it will be based on LPN I will soon say with which parameters yes but with LPN and some reasonable parameters I will show an extremely simple way to get n to the 1.5 which is just going to be to take a random low rank matrix plus a random sparse matrix just let's see that the parameters log uh and good let's just say what is LPN this cryptographic conjecture that I keep mentioning is just saying that if I have noisy linear equations it should be hard to solve them so what is LPN lpn means that I have some secret vector k dimensional vector and now I get samples of the form a random vector and a bit such that the bit is either completely uniform random bit. This is like the null case or the bit is the answer to the linear equation with my secret vector plus some noise. What do I mean by noise? With some chance I flip this.

35:02 So the LPN conjecture is that if I pick the right parameter, what are the parameters? the probability of noise and in comparison to the length of the vector then it should be hard to distinguish if I'm getting linear equations that are noised or completely random answers to each of the linear equations. So this is LPN and what is the what are the reasonable algorithms or the reasonable conjectures. So essentially the conjecture is that we can't do anything better than collect a set of unnoised linear equations and solve them. Right.

35:37 So up to lower order factors what we assume is that we don't have much to do about noise linear equations again besides collecting enough linear equations without noise and then doing a Gaussian elimination. So this would mean that it is believed to be when essentially the the frequency of of noise is enough such that in every dimension the many equations I am getting I am expecting to see some noise. Right? So as long as P * K the L weight times the dimension is much larger than one then we expect this to be half.

36:14 Good. So here is a pictorial way to think of this conjecture. The conjecture is I have my secret vector. I have a lot of linear equations. I have a vector of noise. This is just a vector that is Bernoli P. So this is a sparse vector and I need to distinguish between this and a completely random vector.

36:38 Better to make it vertical. Uh not yet because I want to add things to the drawing but yeah we can afterwards discuss the visuals. Um yes and notice that actually in the LPN settings I'm also giving you this matrix. I'm giving you the equations but in in our construction I'm not even going to give them to you. So it is only harder in some sense. So LPN means that distinguishing this vector that I'm getting out of this and this vector is hard. And what would we want to do? So what we would essentially want to say is that I want to say that low rank plus sparse is hard to distinguish from uniform matrix. So essentially what we would want to do is to say if I took many of them independently so it is not the same s like with different uh with different secrets. If I had like random secrets s1 to say sn then this thing the linear equations time all of those secrets this is a low rank matrix this thing for each of them

37:42 I got a sparse noise vector. So here I have low rank plus noise on the other end I have just a completely random matrix. We want to say that it is hard to distinguish between those two things is because S is reused or

37:57 no. So S is not reused. So what's lower rank? K is the rank. Good. So what is lower?

38:02 Yeah. So the rank is K. So there are N equations and each of them is of size K. This is like N by K * K by N. And this is N by N. And this is N byN. Right. But but this is N byN and it's false.

38:16 But this like vector of S's is really just a random matrix. Yes. So this is really a random matrix and this is really a random matrix with the correct sparity. So what is the only problem? Why is this not exactly what LPN says? The problem is that I'm reusing this matrix. So I'm having exactly the same equations in all of those n different and different points. So this is the only difference from LPN. But in fact it doesn't matter that much. So there is a relatively straightforward way to show that uh that this is still hard. This is what's usually called an hybrid argument.

38:54 So what do I mean by that? I mean that if we would look at the sequence of distributions that gets from the uniform distribution to this distribution by just replacing each row at the time to be from random I will switch it to be this thing. Right? Each row here that is random just ends up with giving me a completely random vector. So if all of these rows were actually random and not sparse and I would have exactly random matrix that I added to something so it is uniform anyway. So if I would switch these rows to random one by one then the entire claim is that if it is hard if it is hard for every polomial time algorithm to distinguish the first distribution from the last distribution then it cannot be that the all of this intermediary steps are east right so so what are those intermediary steps so if I just look at switching one row from random to not random Then this problem at least yes I need to

39:56 be if each of them is hard then the entire thing is hard as well. But what are those intermediary problems? The intermediary problems these are just LBM. These are exactly LP right because what is the the problem when I just have one row that could be either random or sparse. This I can reduce to from standard LPN by by myself drawing these two random S's putting two random sparse vectors here and if I had an algorithm that is faster to distinguish this from a random row here I would have an algorithm for solving LPN because again I can encode any LPN in this uh in this form easily.

40:38 Good. So this means that uh that these steps cannot be easy which means that also the distinguishing the first and the last distribution cannot be easy. So what do I get from it? I get from it that as long as for K and P LPN is hard then also distinguishing a random rank K matrix plus random sparity P matrix from a fully uniform matrix is R. So if I will pick something like k root n k being root n and p being one over root n. So the amount of nonzero entries would be roughly root n in every row. Then lpn in the parameter set in the parameter range that we mentioned should be hard. Meaning that's distinguishing a random matrix of a rank root n plus a random matrix of sparity root n from a uniform matrix should also be hard.

41:29 And now notice that both matrix of rank root n and matrix of sparity root n I can multiply with in root n time per row. So this is why this gives me an n to the 1.5 algorithm already by just doing the the most obvious thing you could uh think of. And now if you want to get near linear you don't need to work that much harder but you need to work slightly harder. So the entire difference would be that instead of just having the sum of of two or a few things we would have some sequence of products and summations but all with this uh quite simple creatures. So the decomposition would be slightly more complicated. It is not just a sparse flow plus low rank. It is a product and sum of some of them. But still if I know the de composition each of them is very easy to to multiply

42:16 polomial of this then there is a pol. It would be actually just like poly logarithmic. Yeah. No, no, you sum the product polomial.

42:27 Yes. Uh the degree will be yes. So if you get Yeah. degree login will be enough to guess to L. Good. And as I said, yes.

42:39 And you can still use just the LPN assumption. Yes, you can use just the LPN assumption or alternatively you can use other assumptions. So we know how to do it from some other assumptions in the real matrices. You need slightly different assumptions because you don't know how to connect LPN to to real values.

42:57 It's also a hybrid argument to argue about this. Yes. Yes. But again I'm trying to argue that it is not from whichever conjecture you are starting from. And here is why morally what I would want to say. Morally I would want to say that the reason that it is very easy to construct these families and we actually know how to do it not only for matrices but also to for random polomials and random tensors and other things is because circuit size is hard in a very strong sense even in average even for approximations even for so on. U so what does that mean? This means that morally nearly for any uh any any distribution of functions I can think of if I will give you either a sample of a function from this distribution or a sample of a function conditioned on having a small circuit it is very unlikely that you will be able to to tell the difference like why because

43:59 proof this is like natural proof yes yes but I mean this this is not rigorous in the sense I would be very happy If there would be like a statement of the form if like some common version of a circuit size approximation is hard for this family then you can also efficiently construct construct this trap uh families for the same distribution. But morally at least whenever you have a hardness for circuit size which is nearly always you should be able to construct this and this is why it is not surprising that for many different conjectures you will be able to get it because all you want to say is that hiding circuit size is easy okay let me summarize so I'm even a bit before time um so the essence of what we are doing is suggesting to will cryptography not against some malicious adversary but against the correctness proofs of innocent algorithms uh which again is in many senses maybe more believable and it is even if it is

45:08 plausible that some of those conjectures can be broken in some polomial time believing that they can be broken faster than matrix multiplication I don't know especially by an algorithm that is not trying to do uh the other thing is that These trap doorto families should be constructable in many many different settings. Why? Because whenever estimating circuit size is hard and it is likely that you can hide the fact that you have a small circuit. And the last thing I want to mention that came up in all of those linear algebraic reductions is that we do know in many settings that there are some barriers for this type of worst case to average case reductions. But all of those barriers are broken if instead of average case I'm looking at this pseudo random average case. Right? So what we are doing is essentially not reducing any worst case instance to the same distribution to say the uniform

46:01 distribution but we are reducing every instance to a statistically different distribution that is computationally indistinguishable from say the uniform distribution or the same distribution we want to reduce to. And all of the barriers we know force test to average test reductions they they fail when you are allowing these type of things. what barriers can

46:22 absolutely the TV say stuff and things like that I mean it's it's a question of which conjectures would you even make if you want to do it now for NP hard stuff but I'm just saying that this gives some possible flexibility of not thinking of fully average case but thinking of something that would fool whatever you are trying to fool to think this is average case without actually statistically mapping every worst case instance to the same distribution just gives gives more flexibility in the reductions. Good. And this is all I wanted to say.

47:04 Hey, so or do you have a uh any examples of trap doors that are not related to matrices? I'm just curious like what else include trap doors? I

47:15 mean depending on what you call related to matrices. So we can do it for like tensors related to matrices. Yes, for polomials but also in a sense you can think of it as related to to matrices. Um so yeah depending on your definition but as I said I suspect you can do it for any any distribution of functions that is not uh super easy for any for all problems to solve that you want. We just didn't have an example that was useful to us. Yes.

47:50 Yeah. It seems like the cryptographic conjectures you need are like much much weaker, right? Like the adversary is like a like an efficient adversary like with a specific

48:02 ed in sub cubic time that I hide the black box. Yeah. So like but like this blackbox form like is it possible we could just prove that without proving like some unconditionally strong overbound?

48:18 Very good question. So um possibly I mean I don't know how to do it but possibly because if you as I mentioned before if you look at the statement it is a bit of a ridiculous statement right because you end up saying something like either you can do something about matrix multiplication fast or you can solve LPN faster than matrix multiplication. It could be that if you assume that you can solve LPN faster than matrix multiplication, you can also solve matrix multiplication

48:45 at this time. So yeah, it could be that especially for the linear algebraic things that live exactly in the same world as the conjecture

48:52 that you can do something in both cases. So yeah. So another question like have you looked at like improving um the running times of problems which are really hard like permanent because there you know there's well worst case the average case reductions for permanent like could you get some easy form in which the permanent is like maybe not like trivial but like in I don't know improved exponential time or something.

49:18 So it's it's a very good question. We tried to think about it. Um the problematic thing or not problematic but you need to to think about it more carefully there is that you if you talk about exponential or super exponential time algorithms that now the conjecture you are making uh you need to make sure that these algorithms are not breaking it anywhere or could not

49:42 break the conjecture that is stronger than Yes. So you need to like be able to get an algorithm that is stronger than the conjecture you are making. So either make a stronger conjecture.

49:52 Yeah. But for permanent if you have a randomness you can do approximation very well.

49:59 Yeah. You can approic sort of thing. Yeah. Yeah. So if you randomize well I mean permanent.

50:11 Yeah. I mean we have worse case to average case reductions though for permanent right. I'm talking about solving permanently. Exactly.

50:18 Exactly. Like in the fastest time you can like something slight something better than two to the end. Yeah.

50:27 Yes. So in this uh matrix model towards worst case to average case reduction there's this epsilon and you said there's like a bad dependence in some things but depend. So what is the best dependence we have? Cool. So the dependence we are getting again assuming conjectures is 1 / epsilon square in the like later unconditional works it is double exponential in 1 / epsilon and there is a very good question of can you unconditionally have a polomial dependence on epsilon and also 1 / epsilon squar seems correct but we didn't think about it enough maybe it can be easily shown or not

51:06 I think it was proved the samely exponential and random this year from a difference in like an easier code that's very good

51:15 but still like there's still a huge one log to do it not two logs uh yes but still it's way more complicated than necessary that's that's a beautiful

51:27 thanks yes uh thank you all Anda.

Questions about this episode

Who speaks in "Improving Algorithmic Efficiency Using Cryptography - Or Zamir"?

Zamir (Host).

What is "Improving Algorithmic Efficiency Using Cryptography - Or Zamir" about?

The content discusses the innovative use of cryptographic principles to enhance algorithmic efficiency, specifically focusing on how concepts like computational indistinguishability can potentially improve the running times of basic algorithmic tasks. The aim is to explore applications of cryptography beyond its traditional roles in security and privacy, seeking to apply its foundational ideas…

What is mentioned in this Institute for Advanced Study episode?

5 people, works and ideas are mentioned, including LPN conjecture, Vinod, Johnson-Lindenstrauss lemma, Bloom, Lubell, and Rubenfeld. Each one on this page links to its own page with every episode that mentions it.

How long is "Improving Algorithmic Efficiency Using Cryptography - Or Zamir"?

The episode runs 52 min; the transcript is about 8,625 words in 86 timestamped sections.

More from Institute for Advanced Study

• All analyzed episodes
• People mentioned on Institute for Advanced Study
• Topics mentioned on Institute for Advanced Study