Lattices II (Eurocrypt 2026)

out. Hi. Uh let's get this party started. Uh we have um three talks in this uh session on latises and the first talk is uh taking a closer look at falcon. It's uh on a paper by Pan Fuk, Philip Galand, Hubert Dot, Yonas Yanek and Aika Kils and Yonas is going to give the talk. The floor is all yours. >> Thank you. Ah no, thanks for the introduction. Um right as Martin said I want to take a closer look uh at Falcon with you and uh Falcon is part of the uh NIS standardization. So the NIS competition started already 2016 and the goal was to standardize postquantum cryptography and at the current state after after four rounds uh five algorithms were selected. We had two camps and three signature schemes and uh one of these camps is letters based one is uh code based and from the signatures two are letters based. So we take a closer look at falcon that's why we are in the lettucebased section. Okay. So what about the security of falcon? So falcon is based on the GP framework which uh proves uh full domain hash based based on lettucees. So there's a proof for for GPE for GPV. And so where's the problem? So the problem is that um the security proof for GPV is not sufficient for Falcon if I look at it concretely. And the problem is that falcon is defined over N2 while uh GPV is is defined over over plain latices. Okay, that's maybe a minor problem um to adapt that. Um a bigger problem is that um GPV uses statistical arguments to to argue about some distributions and if we just take these statistical arguments to the falcon parameters um there won't be any security anymore. So the proof fails here. Um also our falcon to avoid a correctness error um to and resamples um if there is a invalid signature output. Um so this is like a bit of a change of the construction which will also be a problem which we'll see in a minute. Okay so the question is can we prove um falcon secure and if you can do so what concrete security do we get out of it? Okay, our results are um that we adapt um some uniformity results uh from GPV to work with the divergence instead of the statistical distance and then we prove um the a modified generalization of of Falcon to be secure. Um and what do I mean by modified generalization? So first we had to modify the scheme a little bit. It's a minor um it's a minor modification which I will also show you with some um efficiency overhead um because we had to resample the salt. Okay, generalization. What do I mean by that? We prove like an abstract version of falcon which is parameterized by the trapto generation as well as the pre-image sampler. So if you want to use a different trapto generation or pre-im image sampler, you can just plug it in and the proof still still works. Okay, we also have an analysis of the FFO sampler which is a specific pre-image sampler used in used in Falcon. And um that's our results for um Falcon 512 and uh for Falcon 1024. So for a full number of signing queries, we got a bit security of 113 bits. And um if I reduce the signing queries a bit, I I I get more. And for the Fal Falcon 1024, we we we achieved 256 bits. Okay. So then let's look at falcon. So falcon is based on a pre-image sampleable uh trapto function that's this fh and that maps from a use ring notation from um two ring elements to an element in rq and um so this I can evaluate in the forward direction. I also given a secret key. So the secret key will be a trap door for exactly this this h trapped off of the letters that is spent by that uh equation. And with a given the secret key I can sample a pre-image like sampling a arbitrary pre-image is quite easy but we require this pre-image sampler to sample a pre-image which is gshian distributed. So this is a discrete gshion um um distribution and this should only be possible with a secret key. Okay. So this pre-image sampler gives me um a pre-image. So fulfilling this equation for the C um being gshian distributed. Okay. That means especially the probability that these values are small is is quite high. Okay. And then falcon looks like this. So we have a a key generation um which is a trap generation. So I got like a trapto B um as well as as a public keyh. So this will be the public key related to this um pre-image sample protractor function. And in the signing process, I first choose a salt hash this salt together with the message and then I apply my pre-image sample uh um trap function. So I sample a pre-image for C and this will be my signature. Okay. And um this I do until um I get a small enough pre-image um which I have to do to output a valid signature. Right? So I repeat this until I get a sufficiently small value. And this is exactly checked then in the verification. So in the verification I reconstruct this pre-image um S1 and S2 and if the sufficiently small then the signature verifies. Okay. So that is um more or less the the high level construction of how um Falcon was submitted to the NIST competition. We make the following change. So in the original version um we sample a salt once per signing procedure and hash the salt and the message and we propose to do this again if this condition fails. So if I have a pre-image that is too large we suggest to also reample the salt and hash it again. And I will show you why this is necessary or why it was necessary for our proof at least. Okay. Um so what is the idea of the GPV proof? Ah maybe I should also say like okay so obviously this is like this is less efficient this part right because I have to resample that again but thing is that the pre-image sample uh the pre-image sampling takes like a lot of time so that's quite minor to resample the salt but it's a bit less efficient I think and it was already implemented is like negligible so that you cannot see that it's like actually less efficient. Okay so how does the GPV proof work? um GPV uh uses basically three steps. Just want to briefly mention that so that we understand the falcon proof a bit better. So the first step is to program the random oracle so that we know pre-im images of outputs of the random oracle. That allows us in the next step to simulate the signing oracle using exactly the pre-im images we reprogrammed the random oracle on. And so we can now simulate the um the signing oracle without knowing the secret key. And then we can reduce to ISIS by embedding um the ISIS challenge in the random oracle. And then if we get a forgery, this is exactly a solution for ISIS because has to be small because it's a um uh it has to be a valid signature and being a pre-image is also like what the signature is, right? Okay. So then let's see where the proof for Falcon fails and how we can can adapt this. Okay. So instead of a pure ISIS re we rely on this assumption that's a multi-target ISIS assumption. So compared to normal ISIS where we would get one target C and have to find a short um pre-image for the C we get here T pre uh T targets sorry. So the adversary gets T targets C1 to CT together with H uh which will be then in the in the signature scheme our public key and has to output the solution for one of the targets. Okay. Um all right. Okay. So that's how we that's what we want to prove. So we want to prove that we can reduce um the right the the multi-target entries. So let's overlap the entry letters and uh use that to uh sorry use the UFCMA adversary to to break the multi-target ISIS assumption. Okay. So we're going to create create a reduction which gets these two targets and in the end solves solves multi-target ISIS. Okay. So the adversary is a UFCMA adversary. So it gets a public key gets access to random oracle in the random oracle model. It gets access to assigning oracle. Um so signing oracle is just inlined what the signing procedure is and oopsie and right has to output the forgery in the end. Okay so we now wanted to apply the same steps as we applied in the GPV proof. So the first step is to program the random oracle. So all the queries to the random oracle that originate from the signing um from the signing oracle we want to um reprogram. So instead of choosing a uniform C, we want to instead choose like a pre-image first and compute the C exactly this like forward evaluation of the pre-image sample function. Okay, and then we store our results to use it later. Okay, then look at this. Let's look at this difference. So instead of the C, we want to compute the C like this to have a pre-image for this C that we can later use. And so the question is are these distributions actually close? And the question is what does close mean? So for the statistical distance the answer is no. If we apply the same um arguments as in GPV we only have um a difference of 2 to the minus uh 30 35 that's not sufficient for our security proof. So we have to look at something else and the re divergence helps us here. So for the re divergence we show that we can adapt the uniformity results of GPV which exactly says that these two distributions are are close. um under the divergence. Okay. Uh so that's the first step. Then let's look at the next step. So we programmed our random oracle on these values. So now we can answer the signing um oracle using these pre-images. Okay. So instead of using this pre-image sampler, we just take our program value. So we have an S1 S2 which is a pre-image for C. Okay. Question is uh is that change fine? So the premage sampler should now be close to a conditional gshian distribution. So close to this s1 s2 which was previously chosen u um from the discrete gshian being a pre-image of of the se and the answer there that is uh actually true. Um so this was true for some other sampler. We also proved it to be true for the ffo sampler which is used in falcon. So that's actually what like the main part of the scheme consists of. So being like uh a sufficiently good like a sufficiently good sampler and that's also again in the term of the divergence. Okay. Another question is if it is it short enough because I mean being like fulfilling the same distribution means just that I'm um following a discrete gshian distribution. So the probability that the small enough is high but I can also still land in the tails. So the probabil uh so the question is what am I doing if my if my um if my pre-image is too large and the probability is actually not that low. So um the probability that I'm um small enough is 1 - 2 to the minus14 which is fine for practical application then I have to resample very rarely but for the security proof that's again a problem because that's a value that is way too large. Okay. So what I'm doing here because I'm a bit stuck. Um the problem is that um oh sorry that was again. So the problem is here in the in the previous case I could just so this is a randomized algorithm right? So I could just resample again. I would get a new value. I have a new chance to hit uh hit this condition. But in our case of reprogramming the random oracle I cannot do that. Right? I' I fix that pre-image to one value. And if I if that's like a value that is too large then I'm stuck here and I cannot simulate any further. Okay. A solution is here to program the random oracle on a conditional distribution. But at least the lema we showed our uniformity um corollery from like adaption without any divergence does not work anymore. Um instead we um we introduce a trick with a salt. So in that case the salt was um sampled once right and we programmed exactly this random oracle query. So we were stuck here. If you also repeat sampling the salt again and hash it again then we have a new chance of hitting this condition. Right? So we can reprogram the random oracle again now with a different salt that was not chosen before. So we have a new pre-image for C. That's fine. Okay. So um now we can also in that new uh signing algorithm now um simulate the signing oracle without um the signature key and then we can do the final reduction. So we get our uh values of the multi-target ISIS assumption um embed all of these values in in each of the random oracle queries. And finally, if we get a solution like a forgery, we can reconstruct this to get um one of the solve one of the targets that we got from the multi-target ISIS. Okay, so that works out. So what we um show now is a proof for unfortability which relied on multi-target ISIS. So this like not writing multi-target here, but it's like ISIS type assumption. And what we were using basically the one-wayness of this pre-image sampleable function in the GPV proof there's also like there's also in the GPV paper there's also another approach which uses SIS and that's basically relating to the collision resistance of this function and this would give us strong unfortibility because we can find a collision between or already queried uh message and like a new forgery which is a new pre-image. Okay. So the problem here is that we have here a bound of beta and we have for this a bound of two beta because we have two elements that like that's that's building the collisions and um that 2 beta is actually too large for the falcon parameters. So a solution is to to use another assumption. It's called the second pre-image resistance assumption which we introduced which still uses a bound of beta and this is also sufficient to give us strong unfortibility. Okay, here's the assumption in detail. Um, so this was the multi-target assumption and this um we had before and that's like a multi-target second pre-image assumption. Um, so what do we have here? So we get again um t different targets but we also get a pre-image for each of these targets and the solution is that uh the the adversary is target to like get all these targets together with a pre-image and has to find a new pre-image for one of them. Okay. So um question is okay how how big are these like multi-targets? Uh actually quite big because in the case of multi-target ISIS we need actually embed this in all the random oracle queries. So we have qh here and um for the second pre-image only in the number of signing queries. Okay so these are new assumptions and we assume that they are as hard as the the plain assumptions because we don't know better. Um but the important point here is that they are actually also necessary for Falcon. So we don't only show that we can prove um the security of Falcon under these assumptions or that they are sufficient but they also necessary. So if someone attacks one of these assumptions and that's directly implies an attack on Falcon. Okay. Then let me briefly mention security bound. So for u plain unfortibility that's a bit like simplified but we mostly rely on the um advantage of the multi-target ISIS assumption with Q being the random oracle queries and we have these rey losses um coming from programming the random oracle and programming the signing or or um answering the signing oracle for strong unfortibility. It's very similar. relying on the second pre-image um assumption and also on the on the plane unfortunatility but like the details are are in the paper if you're interested in the concrete bounds. Okay. Finally um we then um optimize these um these bounds for choosing some really order which I didn't go into detail here but you can also find that in the paper and the result is that we start with the um assumed hardness of this multi-target ISIS assumption um using core SVP but you can also use different um estimation of the hardness for for multi-target. So this is just for the plane ISIS um gives us 120 bits of security and then uh what we reduce is basically we check what is the best order we can choose for the divergence to analyze our security bound and in the case of 2 to the 64 queries which is required by NIST we lose three and a half bits per application of the divergence. So I have I start with 120 and lose three and a half in each step. Okay, that's uh yeah, if I reduce the signing queries a bit, I get a bit better results and same for the for the larger parameter set. Um, okay, all of this is under the assumption that this multi-target ISIS and this second pre-image is as hard as the as the plane ISIS assumption and uh for strong unforability, it's it's um the same bit security. Um I should also mention that there's a a follow-up work which in um was published in in the beginning of the year and they actually improve our results by um making like these column obsolete I would say because they get tighter uh results um which makes them at uh lose at least uh at most one bit. So um yeah so we get like the full so they get the full number of queries with only losing one bit or even a bit less than one bit but yeah okay so let me summarize so we um we introduced a minor um conservative modification um and got the first concrete proof of falcon getting like concrete results instead of asmtoic ones. Um for that we adapted the GPV framework to work with the divergence and optimized the bounds and analyze the FFO sampler. And if you want any more details um ask me or look in the paper. Thank you. [applause] Okay, we have time for one or two quick questions. That gives me the opportunity to ask one. Um do you think your reduction would also apply to deterministic falcon? So people have tried to you know make it deterministic to avoid the salt or do you see a major obstacle to make it go through >> like deterministic in a sense that the salt is derived deterministically from the message. I think if you can so depends on what happens in the sampling procedure but probably you can also yeah so if you if you have a a method to also then deterministically derive another salt then it would work. >> Okay. >> But if you're fixed with one salt then then then then you have the same problem. >> Okay. Thank you. All right. Let's thank the speaker again. [applause] All right. In the next talk, we're moving towards LA large scale lattice attacks uh with new lattice records by disk based siving by Zo Tao and Gintaing and Zo is going to give the talk. Floor is yours. Okay, thanks for the introduction and uh it's 2026 now and some aggressive PQC migration plans have said their deadline to be 2029. So we are in a stage where the latest base PQC algorithms are really about to be widely developed in the next coming years but uh I will here give you some recent progress on concrete latest attacks. Uh so we all know the shortest vector problem and there is a online tu damas. SVP challenge created more than 10 years ago and for maintain for benchmarking and comparing the practical performance of different SVP algorithms and uh in 2021 uh the record was pushed to 180 from 155 by the general S kernel GPU tensor implementation and a long list of names with improved Genos kernel and the better GPUs have pushed the record 290 from 2021 to 2024 and so now we have reached the 210. So besides SVP we also set many other records like the for example the kyber 256 instance in the bham challenges. uh so I will give you some basic ideas about uh these challenges and I have to say it's impossible to go through all the details of the implementation. So here is the code. Uh here a little warning is uh I highly recommend you to back up your data before you run it because according to the title of the paper this is disk based. So you know it will write a large amount of data to disk which may cause some uh unexpected issues. And here I would like to thanks the teams behind the challenges. uh now the maximum supported dimension for the shortest vector problem challenge has been updated to 300. So maintaining such a challenge website for more than 10 years long is something non-trivial I believe. Okay. So the challenges was solved by letting so is a somewhat specific topic. Uh so I will give a very quick introduction here. The ideas behind let saving is somewhat simple. Uh there are two steps. In the first step, we just initialize the exponentially large uh saving database uh with latest vectors. And in the second step, we repeatedly find pairs of database vectors that are close to each other. And uh after such pairs has been found, we replace longer DB vectors with the short differences. And such a pair is often called a reducing pair. uh finding reducing pairs usually dominates overall running time of let saving and this step is often accelerated by the locality sensitive filters. So here is the general framework of locality sensitive filter based uh reducing pair search. We first initialize the set of filters and the corresponding buckets and then we for each vector in the database. We put it in the bucket if it if and only if it can pass the corresponding filter. After those buckets have been generated uh we can do some naively we can naively search for reducing pair candidates within each of those buckets. So here the key point is that the filters should be chosen such that uh first uh the reducing pairs are more likely to be in the same bucket and also those buckets should be able to be generated efficiently and for example the BDJC uses the spherical cap shift filters uh with the optimal time complexity 2 to the power of 0.292 292 times the dimension of the Lettuce. Okay. So here I will give you some facts about the progress of lettuce crypto analyst. So it has made steady and significant progress in the past 15 years. 13 years ago the SVP record was only 130. So which is at least 25 bits easier than the 210. No dramatic breakthrough have been made but and the progress is mainly due to the improvements of let saving. So we have seen in the past few years that let saving is fast but here the question is whether this fast saving algorithms can be extended to some uh large scale real world attacks. And the key issue is that saving requires to handle a exponentially large saving database. And this is actually considered as the main bottleneck for solving larger SVP instance. In practice, for example, the 210 would require 50 terabytes of memory. So putting them in RAM is something not really affordable. And also if you can even if you can put everything in RAM uh for example in the general C kernel implementation the two BDGLC runs actually slower than the triple C uh simply because of the host device communication cost and based on these experimental results may doubt the scalability of saving and indeed memory overhead has proided some more confidence in some borderline PQC. parameter sets. [snorts] Okay. So what did our work do? Uh we suggested we did an implementation of the BGC with the GPUs uh the system RAM and several disks as three separate memory layers and the results suggest that large scale saving may be less memory bound than commonly assumed. So I cannot go through the details of the BGC here. But the key idea is uh instead of generating exponentially many very small buckets all at once, the BJC generates progressively small buckets smaller buckets by applying a series of random filters to the main database and the bucket size will decrease by several orders of magnitude after each filter. So this allows us to map different layers of buckets to different storage devices. [snorts] Okay. So in the premillary stage of this project we our target saving our target SVP dimension was actually 200. So for the three layer BGC we uh estimate the bracket size of each layer as the main database would cost roughly 10 terabytes of memory. So we cannot afford to put it in RAM. So our plan was to put it on several SSDs and the layer zero buckets uh will would be roughly 70 gigabytes each and this is much smaller and they can we can put them in RAM and layer one buckets is only a few gigabytes. So they should be put in the GPU memory the GPU global memory. Okay. And implementing this idea is actually a little bit hard and labor intensive. Uh the main challenge came from the use of disks. So the disks are much cheaper than RAM but at the same time they are also much slower. Uh the throughput of the SSDs on our machine was roughly 3% of the system RAM. So and the read and write operations should be at least roughly 128 bytes a kilobyte otherwise the performance will uh be even worse and we also suffered from a significant latency. On the other side since we are targeting a more than 10 times speed up uh almost all the essential computations have to be rewritten as GPU kernels. So including the uh bucketing the reducing the do harsh and the general kernel operations like extend left turn left and so on. Uh so here is an overview of the system. Uh so almost all the performance critical computations are happened in GPUs. Uh we will okay uh we will first stream the main database to the GPUs and generates one batch of layer zero buckets and from which we can further generate those layer one buckets. uh since the running layer zero buckets are put in RAM. So we can only record the indices or the pointers of those those layer one bucket entries and after sending them to the GPUs everything is done inside and only a few short new vectors are reported and finally they will be added back to the main database. Uh and the arrows in the picture are not sequential. they are there are actually a few concurrent workers uh doing each part of job at the same time and communicates with each other to hide the latency and and for the disk side uh porting caching and profession are heavily used to reduce the latency and maximize the throughput. Um thanks to the structure of the BGC the disk IO turns out not to be the bottleneck and from our results we can obvioused algorithm is actually uh actually does not sacrifice the time [snorts] complexity compared to the previous pure RAM based implementation of the BJC And the situation is even better than we expected. Here in the picture is some real IO workload sample. The saving rank was 166. So it's quite a large instance and it's clear that uh the disk IO is not the bottleneck and things are quite free in roughly half of the time. Uh so okay the BJC looks uh more memory friendly than the BDGC but in the standard security estimation we usually use the time complexity of the optimal uh BDGC. So one may ask how much uh additional time complexity is incurred when we switching from the BDGC to the BDJC. So here we mainly care about the parameter sets around level one security where those asmtotical formulas are not really meaningful. So we did some experiments for different real saving databases and we compared how on average how many dot products are needed to find a unique reducing pair and here is the results. uh the two sieves differ only in the bucketing step and we can see the outputs of the BJ sie have fewer duplicates. So this means that uh the BJ buckets are more are better distributed and this gap the performance gap between the BJC and the BDJL is likely due to the shape of the filter regions. Anyway, this gap is not very large and it looks like it's it grows stemly as the dimension gets larger. And in the reducing step, uh a typical workflow is to first do some low precision check to get some permising candidates and then check them with a higher precision. So for C rank 130 we did some experiments for different positions and here the one bit integer means the XR popcorn checks on the same hash values. So we can see even the half bite integer sorry the yellow one the half bite integers are quite accurate and the x popcorn trick is may not be worse if there are uh no hardware support for them. So overall uh this gave a speed up of roughly two to the five and uh the speed up actually comes from better bucketing quality. Uh this is because the most previous results were obtained by actually by the syntoically slower algorithm the triple se and more importantly uh now large SVP instance are bit are within our reach as long as there are enough GPUs. So our ex our estimation is a cluster with uh say 10,000 graphic cards should be able to solve roughly SVP 260 and please keep in mind that so far we are still using general purpose hardware. So in the end a few words on some borderline parameter sets like ML cam 512. So I think we all agree that they are borderline in the sense that it cannot be 153 bits and it's also unlikely to be 133. So uh and based on our results I don't recommend to add any extra bits from the memory overhead in the security estimation. So they are really borderline. So if this were the final crypto analytic work on practical latest attack, I will still be quite happy about this security margin. But this is unlikely to be the case according to the history. And if the latest schemes keeps losing security at anything like the rate during the past 15 years, a slightly larger parameter set will make you uh sleep better. Okay, that's all. [applause] >> All right, we have some time for questions. [snorts] >> When you say 10,000 GPUs cluster, this way when you say 10,000 GPUs in a cluster, this raises the question of interconnect and communication between the the different GPUs and the different computation nodes. Have you explored uh whether this is likely to I mean whether the interconnect speed is likely to be a stumbling block in any way or you just not know or you're just confident that we it will not be um actually we did the estimation simply according to the computation resources. So we don't really consider the communication because based on this implementation it looks like so where no matter the energy cost or the price the disks and the PCI interface and the data communication cost looks like to be a very small part of the overall computation and GPUs are most expensive and the most power consuming. Any other questions? Cool. I can use share privilege. Um, so the natural question is how slow can you go? Can I put my database on the SharePoint of my employer and that latency is still fine? Because you used SSDs, right? What about hardness? What about like you know like SSHs? Like how slow is you know when do you hit the the bottleneck? Actually when we first develop a a small sample we use hard hard drives. Um it's slower but uh it's like if we use those SSDs we can almost make full use of the GPUs and if if the speed is roughly half we can still things are still okay but if you are using hardwares maybe you should use less GPUs otherwise it cannot be yeah hardware usually not hard drives are not very not good enough I think. Okay, >> cool. Then I have one. Did you shred your SSDs? Did they survive lot of readwrite cycles? No. >> Did your SSDs survive the experiment? Because like you reading writing a lot to them, right? >> Yeah, you should be careful. [laughter] Yeah. If you really want to run it. >> Okay, cool. If there are no more questions, then it's time to speak again. [applause] Um and for the final talk of the session um we hear about dimension reducing algorithms for quturnian ideal SVP. It's a paper by Chong Ling, Andrew Mandlesson and Christian Porter and Andrew is going to give the talk. The floor is yours. Great. >> Thanks. Um so [clears throat] yeah this is uh dimension reducing algorithms for quitian ideal SVP. Um why do we care about uh solving SVP in ideals of quitterian algebbras? So um motivation there's a signature scheme called hawk. It's based on something called the module latis isomeorphism problem. It's uh submitted to the NIST uh additional digital signature standardization process. Um and some recent work by Chevanardal uh published um last year showed that uh the case of module lips that we care about can be reduced to something called reduced non-pip. Here pip stands for principal ideal problem in a quitian algebra. Um so this lip problem you can see in the bottom right hand side of the screen. It's like to decide if two latises are kind of geometrically equivalent and if so to find the map that maps between them. Um and this reduced norm pip problem is the following. So you're given some principal ideal that means it's generated by a single element and you're also given its reduced norm. And the challenge is to find some generating element alpha which satisfies this constraint on its reduced norm uh given by the norm that you're given. Um and currently the best algorithm to solve this is due to kershmer and voit and you essentially call an SVP oracle in the same dimension as your quitian algebra over Q. And so the point here is that hawk uh can be reduced to solving some SVP problem in some ideal of a quitterian algebra. So we're going to study methods um that have some precedent in the number field setting to solve certain easy instances of ideal SVP in orders of quitterian algebbras. Um more definitions are going to follow. Um so in particular we study hermite SVP in ideal latises of quitterian algebbras. Um in reverse order that jargon means the following. So a quitian algebra in this talk is going to be some uh rank for vector space over a number field k and it's going to be uh generated by some basis elements 1 i j k that satisfy some relations i^ 2 will be minus1 j^ 2 is minus one and i j is minus j i is k. These are kind of formal symbols that we just define into existence. And then we let our algebra be the kinear span of these basis vectors. And we define multiplication using the relations between the basis vectors. So we're going to study um ideal latises in these algebbras. So an ideal latis is going to be an ideal in some subbring of our algebra under the canonical embedding also known as the manovsky embedding. And then we'll study computational problems on these embedded ideals. So we'll study Hermite SVP and this is the problem of being given a rank n latice and some approximation factor gamma and then having to find some nonzero latice vector whose norm is bounded by gamma times the nth root of the determinant of the latice. And so we'll adopt the following strategy to study how hard these problems are. We'll take our ideal latice. We'll intersect it with some lower rank subspace. Um in principle it should be easier to solve our problem in lower rank. So we'll assume we can solve it. We'll then lift our solution back up to the original latice that we care about solving the problem in and study how much the approximation factor gamma kind of deteriorates or increases in size. Okay. So um I'm going to give some definitions of of latises of number fields of quenian algebbras. Um this is the last latis talk so hopefully people have picked up what a latis is but in this talk it's going to be some the set of like integer linear combinations of some basis vectors. We can put our basis vectors as the columns of some matrix B and then we can define the determinant which we saw on the previous slide to be the square root of the determinant of the gram matrix of B. We can then study computational problems on latises. So um somewhat kind of informally uh the closest vector problem is given some latice and some target in the ambient space and the problem is to find the closest non-zero point in your latice to this target as you can is illustrated in the bottom right hand corner. um we can then specialize to the shortest vector problem which is CVP where the target is the origin. So you're just trying to find the integer linear combination of basis vectors as close to zero as possible um but still being non-zero. Um often what we want to study are not kind of exact latis problems but approximate versions of them. So a prox SVP is uh the challenge of finding some non-zero vector whose norm is kind of small enough. So there's some bound B and we want its norm to be less than or equal to B. And some famous result by Minkovski says that uh there always exists a non-zero latice vector whose norm is at most the square root of n times the nth root of the determinant where n is the rank of this latice. And this motivates hermite SVP. So gamma hermite SVP given some rank n latis and an approximation factor gamma find a non-zero latice vector of norm at most gamma times the nth root of the determinant. But we don't want to study kind of plain uh unstructured versions. We want to study structured versions using uh number fields and quitian algebbras. So I'm going to zip through some definitions. Um hopefully this isn't too bad. Um so a number field is going to be a finite extension of the rationals as a vector space. We'll say its dimension is n. These fields have automorphisms. Uh these automorphisms are bjective homorphisms from the field to themselves. We'll assume that there's the same number of automorphisms as the dimension of the field over Q. In this case they form a group known as the gowa group and all of our theory is nice. Um we can we'll also need the ring of integers. This is the set of elements in our field which are roots of polinomials with integer coefficients. Uh we'll denote it by okay and then we can consider ideals in this ring. Okay. And because this ring is a dedicin domain we get unique factorization into products of prime ideals. So if we take some integer prime p and we study uh the ideal it generates in this ring. Okay, we can write it as some product of uh prime ideals math frack pi uh and these have some exponent and there might be uh numerous uh ideals in this product. If this exponent e uh is one then we say that our prime p was unrammified and this is kind of the nice case. Um we're going to assume in the rest of the talk that we're dealing in like a kind of unrammified setting. We can also define a trace. So the trace of x is the map which sends x to uh the sum of its evaluations under the automorphisms of the field and we use this to define the discriminant. So the discriminant having fixed some z basis b1 up to bn is the determinant of the matrix whose ij entry is the trace of b i * bj. Finally uh in the case of ideal latises in number fields there's a nice expression for the determinant. So we can use some uh algebraic uh objects to describe it. Uh this uh takes the form of the product of the norm of the ideal. So the determinant of some basis matrix multiplied by the square root of the absolute value of the discriminant. Okay. But what we really want to talk about are quiansians. Quitterians over number fields. So we've already seen this definition. Our quitian algebra is going to be some rank for vector space over some field with these basis elements that satisfy some relations. And we'll need to consider ideals within certain subrings of algebbras. These subrings are known as orders. And an order is simply a subring which is also a latis of full rank. We'll also consider orders that are maximal with respect to inclusion. Um and then an ideal in one of these orders is some latice which is closed under multiplication on both the right and the left by elements of the order. If it's just closed under multiplication on one side, say the right, we call it a right ideal. Right ideals are not in general two-sided. There's then a conjugation map which basically uh switches all of the signs of the coefficients of a quitterian except for the first one which is fixed and we use this to define the reduced norm and the reduced trace. The reduced norm of x is the product xxar where this bar is the conjugation map and the reduced trace of x is the sum x plus xar. We then use this to define a discriminant notion again in a quanian algebra uh where this is kind of totally equivalent to the number field case. the determinant of the matrix whose j entry is the trace of the product of basis ve uh yeah basis vectors um except that here we now use the reduced trace and finally again there's a nice expression for the determinant of an ideal latis it's the reduced norm of the ideal multiplied by the square root of the absolute value of the discriminant okay so prior work so this kind of line of inquiry began uh in the context of solving number field ideal SIV uh SVP and This work by pan atal from 2020 kind of discovered uh weak instances of ideal SVP in gowa number fields. So they proved results of the following flavor. Let p be some prime ideal in this uh polomial quotient ring. This is the ring of integers of a cytoic field. And suppose this prime lies above some integer prime congrent to plus - 3 8. Then there's a polinomial time algorithm in the degree of this uh ring and the log of this prime it lies above to find the shortest vector in p. Some follow-up work by porter atal extended this to a much larger class of ideals and then uh budgal in 2022 kind of solved this problem. So they generalized this to all ideals in uh number fields algebraic number fields. They improved the approximation factors you get um in these algorithms and they did this using field automorphisms. So they proved a theorem of the following form. Let I be some ideal. Suppose it's prime factors uh or it lies above prime factors in Q that aren't ramified. Pick some approximation factor gamma that's at least 2 n. Then there's an algorithm that solves gamma hsvp in our ideal latis in classical time exponential in and if we ignore log factors the ratio between n and m subscript i where mi is the number of k automorphisms that fix i as a set. So the point here is that the more automorphisms that fix your ideal, the faster you can solve gamma HSVP and the number of automorphisms that fix your ideal kind of corresponds to the amount of structure in your ideal. Okay, now our work. So we prove a kind of analog of this in the quenionic setting. So a over k will be our quitian algebra. K will be this uh algebraic number field. O will be some maximal order. We'll take an integral one-sided ideal and we'll be in some nice kind of unrammified setting. We'll [snorts] then let gamma be our approximation factor that's at least 2 * the of 4n time the reduced norm of i raised to the exponent 3 / 4n. Uh here the 4n comes from the fact that this is the dimension of the quitterian algebra over q and the exponent of the reduced norm is 3 / 4n not 3/4 of n. There's then an algorithm which solves gamma hsvp in our ideal in classical time exponential n ignoring these log factors n / m iar and here i bar is the intersection of our ideal with k and mi bar is the number of k automorphisms that fix this set this ideal is a set um so again the more automorphisms that fix your ideal the faster this algorithm runs there's a drawback of this result which is that it has the uh approximation factor gamma has some dependence on the reduced norm And this is a problem because it's easy to construct ideals with arbitrarily large uh norm. So we would prefer not to have this factor in our approximation factor gamma. Um later on we'll see in certain contexts this can actually be removed and these contexts are also relevant to cryptography. So that's nice. Um so I want to give a kind of brief sketch proof of how we do this. It has two parts. The first part takes a one-sided ideal and says that well you can actually solve it in some two-sided ideal without blowing up the approximation factor too much. And then the second part of the proof says well we have a two-sided quitian ideal we can actually solve it in some two-sided number field ideal and again the approximation factor won't blow up too much if we lift our solution back to the original lice. Okay, so part one, we'll let I be some one-sided ideal of a maximal order of a quitian algebra and we'll denote the maximal sub ideal that is two-sided by J. This is a well- definfined notion. Then any element in this two-sided ideal X which solves gamma HSVP also solves gamma- HSVP with this approximation factor. Um so gamma dash is gamma times the reduced norm of I raised to the 1 over 4N. Okay, so we can compute a basis for J. This we might have to do some prime factorization at some point. So this is might be quantum but we can do it. Um and then a solution to gamma HSVP satisfies the following inequality. This is just the definition of um HSVP where we've used the nice algebraic formulation of the determinant of our latis J. We then use some technical relation between the reduced norm of a one-sided ideal and the reduced norm of a two-sided ideal. They're related up to as a square. one is a square of the other and then we plug this into our inequality and we rearrange so that we get an expression where one of the factors is the determinant of our ideal latis I and then we have some other kind of junk out the front and this is gamma times the reduced norm of i to the 1 over4n okay so this essentially reduces us to the two-sided case we have some one-sided ideal uh hsvp instance and we can solve in some two-sided instance and when we lift we only uh blow up the approximation factor by this 4n root of the reduced normal. So now we need to go from a two-sided quanian ideal to a two-sided number field ideal. So how do we do that? So we'll take J to be some two-sided ideal of a maximal order O. And we'll assume that its intersection with K denoted J bar has uh good ramification properties. Then any solution to gamma HSVP in J bar also solves gamma- HSVP in J with the following approximation factor. gamma dash is 2 times the reduced norm of j^ 1 over 4n * gamma. And kind of similarly as before, we just write down the definition of hsvp in our number field. And then we use some facts uh to uh that we're going to plug in to do some algebraic manipulations uh to get our result. So we're going to use that when we lift from the number field to the algebra um we only increase the size of the norm by a factor of two. And then we use two technical lemas. one which relates the norms and the second one which relates the discriminants of our orders. Plugging this in, we again rearrange to get an expression in terms of the determinant of some latice and then we have some uh more algebraic stuff out the front um depending on the reduced norm. And when we combine part one and part two, what we get is the approximation factor we saw two slides ago which depended on the reduced norm raised to the 3 over 4n. Great. Um what we want to do is specialize to contexts that are relevant to cryptography and also ideally remove this dependence on the reduced norm. So recall I said in at the beginning that rank two module lip has been reduced to reduce norm pip in a quitterian algebbras. Um question you might ask is which algebbras has it been reduced to and these have the following form. So L is a cyclomic field of conductor 2 to the R. K is its maximum totally real subfield. This is just all real elements in L. And then the algebra a is uh the kernian algebra over this maximal totally real subfield. And we'll then fix some order o which lies above some uh special order that I've denoted lambda which is just generated by the ring of integers of l. So this is quite a precise setting. What we then do is study one-sided ideals in this order o which satisfy two properties. The first again is that we're in some kind of uh nice ramification setting. And the second one is some kind of mild condition that says when we intersect our ideal with this order lambda, we get something that behaves nicely as an ideal. And then we get the following theorem. Any X in the intersection of our ideal I with L, which solves HSVP also solves gamma- HSVP in I with the following approximation factor. 2* this index raised to the 1 4n * gamma. Um, and this index satisfies this relation between the discriminants on the first line of the might like how big is this thing? And it turns out in this special case it's equal to I think four. So we end up with some small constant raised to 1 over 4n and n is 256 or 512 or 124. So this is kind of very very close to one. So we end up with gamma dash being roughly 1.5 times gamma. Um and so we can solve in a space half the dimension of our algebra and when we lift we only blow up the approximation factor by like three over two. Um so we've we can lift solutions with small blow up in the approximation factor and there's no dependence on the reduced norm which is exactly what we wanted to show. Um thank you. [applause] Do we have questions? All right, I go. Uh, so you said you study the easy case which I guess is the the unrammified case like so you know like what goes wrong in the uh ramified case and you know should should this audience care about the ramified case given the application >> right? Um so one thing that goes wrong is that all these relations between the norms are not very well behaved. So um there's all this theory which tells you like if I normal down into a number field I get some exponent and in the ramified case this uh if I norm down a prime ideal I don't get another prime ideal I get some like power of a prime ideal. So all the um the approximation factors get worse. Um I think there are some other limitations as well um to do with uh um applying we kind of compose our work with the work of budu setal to get algorithms which then take advantage of the structure in the number field ideal we get and there's a problem there because those results apply in the uh unrammified case as well um in the ramified case I mean in the those quanian algebraas there's only one ramified prime it's two so um you if you pick something random, you're probably not going to hit this. But um yeah, I mean it would be nice to be able to cover all cases, I guess. >> Cool. Thank you. Any other questions? In that case, let's thank the speaker again. >> [applause]