Module Learning With Errors and Structured Extrapolated Dihedral Cosets (Crypto 2026)

Okay. Uh hello everyone. Uh in this video I will introduce our work about modular learning with zero problem and its quantum counterpart. Um this is a joint work with way chin. Okay. So in this work uh our main result is finding a quantum conting with the rope problem which we call it IPMCAP and this new problem plays for MLW and uh the role that plays for LW. Okay. The first recall how to reduce to point hardness problem. Uh following reg's way there's a natural reduction from the new serial problem to the hydrocosate problem. Uh before introducing the reduction we recall the definition of LW problem and the DCP problem. So LW problem is that uh given an instance of the form a a s plus e and try to find the secret s and DCP problem is that uh given multiple quantum states of uh of this form and try to find the secret s. So when the XI and SI uh vectors we call it the vector vectorzed DCP problem. Okay. Then we recall how to reduce AW to DCP in in other words how to generate the DCP quant states from AW instance. First we prepare uniform superposition of of this form. It's very easy. And then with the public l instance a and as plus e uh we have the public map uab this one and uh evaluate it with an empty third register here and we can get a new corner state like this. So when we take a look at the value in the third register uh we can find find that for specific x the value in these two superposition uh are very close I mean y0 and y1 they're very close and the difference between y0 and y1 is just the aero and a term is very small So therefore based on the bas based on this observation uh there's a map as below to help us fix the value x because before we didn't fix that uh you can see this one here x is not faced but and then we we try to fix the x and uh we don't know x don't know the value of x right okay so then we we need to pick that value x and then uh from from the corner states in that state and we can get the DCB states and then we we try to zeroize the third register and then we can get the DCP states. So well how to define the map uh if we divide the whole space you can see if we divide the whole space uh with with squares just like this each seal is a squares and the y of each sale satisfy this uh satisfy this inequality and then we can define that the map is just a map u map every point in uh space into each cell. For example, any point in this cell and they they're mapped into the the cell itself. My cell is just the index. And then uh we have this observation for different for different x1 and x2 ax plus a x1 plus e z e1 uh uh and ax2 plus a2 are mapped into two different cells. Well, if uh for for the same x ax and a x plus e are mapped into the same same sale with a very high probability. For example, here you can see here, here, here, here. Okay, they're in the same seal. Then we can define the same wi with this map and then we can uh store this this the value of the map into the force uh register and then measure the force register and then we can know we can have a high probability to fix the sec fix the x and then uh with the first register and the second register we can uh zerorize the third register and then we can get the DCP corn quantum states. Uh that's a way to reduce the LW to the DCP problem. Okay. So we have no the reduction from AW to DCP. However, the reverse reduction is very hard to find. So to to obtain a quantum problem equivalent to LWD the extrapolated from two branch to many shift uh could be a very useful way. And then in BK BKSW8s uh authors uh in introduce a problem named extrapolated dehydro problem. uh uh in generally speaking uh it means given quantum state of this form and then try to find the secret s we can find that the j here is no longer be the binaries but it can be any distribution the distribution of j can be any distribution over the over the space z and then you try to try to find the secret s and you can find that uh here each quantum states have more than two superposition and uh then in BKSW8 they prove that LW is as hard as the the gausian ATCP problem. uh we can follow the same way same way uh as before to reduce AW to Gausian ATCP problem and then if we want to h have the reverse direction reduction and we can just do do quantum for transform twice and then do once measure once do once measure once and then we can get get another instance so furthermore in BJK K 25. The authors give a quy polinomial time algorithm for varcp and therefore it shows that maybe uh have uh u do some research on the analysis of EDCP is a good way to analy analyze the security of AW on quantum in quantum and then however uh in our daily life in our real life we use more MW than the AW for the efficiency especially in the crystal kyber and crystal delissium they choose to use MW instead of LW. So therefore uh this motivates us to ask a question is there any structured quantum counterpart of MW and then can we use the uh can we do some an analysis on this kind of quantum counterpart uh and then we can use this quantum counter part to analyze the MW. Okay. So how to first we can just consider how to reduce MAW to quantum hardness problem and uh okay before we discuss this problem we can just recall the what is ML and generally speaking in MLW a model learning with zero problem is just a variant of LW a problem with element of a ring of integer and uh we also need to consider Another problem named the polinomial model learning with arrow problems and it is it is a variant of with elements over the polomial rings. Furthermore, if we uh define the multiple multiplication matrix and the coefficient vector and then we can write the uh polomial modular learning lw problem uh instance into this form and we we can take a look at this metric A and we can find that it's not completely random. So there might be some gap um between the mod lending with zero problem and the L problem because um the the the the metric the metric has some algebraic structure and uh furthermore in RSW8s uh the authors proved that for large render of the pol underlying polomials uh they're M is as hard as a PMW. So in this paper we only consider the PMW problem and we just want to uh find some connection between PMW and it's quantum part and then you know through this this equivalent and then we can also see that it's also equivalent to MW. Okay. So first mod uh is a very natural candidate of that. Um generally speaking it's just a replace every element in ADCP from uh integer to the polomial elements and then if we follow the previous step and we can easily to reduce the PMSW to uh reduce the PMSW to the modular uh EDCP But does the modular value quantum problem reduce back to ML? And actually the classical reverse reduction use a QFT twice as we said before and uh and analog analog is QFT over rings is not not immediate and available. So therefore um we want to pull the poly polomial version back to the integer version and in DSS 20 and 21 uh the author introduced integer polomial MW. uh the mo the biggest different difference between IPMW and AW is the distribution of the arrow and in the LW the distribution of the arrow is just a short it's just a short short distribution but in the IPMW the distribution of the arrow is first select some uh a short polomial and then do the evaluation of the polom polomial at Q. And in order to prove the equivalence between IPML and PML, the DSS21 in DSS 2021, uh the the author also introduced two maps. The first map is evaluation QF and the second map is FQF. Gener uh previously speaking the evaluation QF is just do the evaluation Q over Q and then uh modular FQ and the decomposition is just a Q de composition of uh integer of integer over over this one and reduce it to mod FX. And uh although this two map is not uh isomorphism but actually they are approximate isomorphism. uh in our case uh we can find a very interesting property that if we given uh IP ML instance and then through the map FQF and you can map it to a PMW instance uh with a carry with a small carry and if given uh PMW instance and then through the uh through this one through through the through the value through through the map evaluation QF and then you can get a IPM instance with a small carries and with this property and DSS 21 prove that PMW is as hard as PMD. Okay. So, so we with this toss and then when we have when we have an PMW instance and then what we do first is just use the evaluation QF to map it to a IPM update like instance like this and then do the previous uh step as before. For example, prepare the uh gshian prep prepare the superposition like this and do do the evaluation and define the similar maps and then we can get the uh we can get the IPM of the in quantum quantum states of this form and that that's what we need. Okay. Then we consider the rejection from the inverse uh reverse direction and uh yes of course we want to follow the framework of the previous work. So uh when we input the quantum sample uh for example this and then we just let's just say um how to uh what what will happen when we do the same thing uh to this corner states we can just do the QFT QFT and then measure the secondary register and then we can get this one and then uh do the quant uh QFT again and and we can find that in the First register what we what we what we mine is of this form and Z here is a vector of the form one Z1 Q Q22 and Q2 Q2D minus one it's a vector it's a vector and here the arrow the the the the arrow uh is although the arrow is follow this gausian distribution But the y the the amplitude of the arrow is very wide. So if we take a close closer look at the the distribution of the arrow, we can find that only the uh most significant Q low Q uh bits can could help to recover secrets. Well, the lower uh significant lower schemic uh bits uh looks uniform. Therefore, we instead of instead of you uh instead of reduce to uh instead of extract PMW instance from this uh from this instance uh we just replace the uh hero hero distribution uh we replace the hero from this distribution to a new distribution. It shows that the first the most significant log cube bit follow the uh discrete gausian distribution and the sec uh the lower uh significant bit significant bits follow the totally uniform distribution and uh through the through diverency um we can prove that the uh from from the view of the adversary these two dist distribution are close. Okay. So after after we have replaced the distribution of the arrow and then we can try to extract the uh PM of the instance and as as we analyzed before we what we only need is just the the high the most significant long cubit. So we do uh we just do the for each I we just do the uh you use fqf to map the map the uh a sqi plus ei prime to a polomial and then we just pick the each d minus one's coefficient and uh concatenate them uh them together and then we can get a vector like this. When we take a look closer look at the matrix here uh we we can find that when the underlying polomial uh is can be written as XD minus C of the form XD minus C and then the multip this this matrix is just a multiplication matrix of 5 Q FA and then when we when we take a look at the hero term we can find that it's just a discrete Gion distribution and furthermore uh the the carry term is also small carry. So does uh so what uh the the the instance we ex we extract from the integer version uh can is actually an ideal PMW sample additionally with a small carry. So does adding the small carry destroy the usefulness of a PMW server? So uh we prove that uh when m is of the of the size o q we can prove that the distri uh the distribution of the instance we get uh is close to the ideal p uh distribution on the re diverency. Okay. So do we finish and can we close the reduction reduction chain? Actually not we miss one step. Uh let's just go uh go back to the reduction from PMW to IPM IPMECP reduction and u we see that the this inequality had need to be uh satisfied. However, for the the first minimum of this matrix of this matrix uh satisfies this one, this satisfies this inequality and the error term the size of the error term satisfy this inequality and uh under this condition and this inequality have to have to be satisfied and this lead to a very low uh not very large but comparatively large uh sample numbers. However, uh our previous reduction only allow the m equal to log d log d. So this sample number is not enough and what we need to do is that use the leftover hash lama over rings. So when we start from a PMW with uh O log D samples and then we can just sample a matrix R where M M prime is is large enough and M is just a log log D and then by left one hash LMA over range uh RA a is is statistically close to uniform random and then this one is is just the PM MLW like uh instance and with this new instance we can go back to the reduction from PMW to the EDCP and to the EDCP. Okay. So uh take a brief brief conclusion. Uh when we select the parameter of this and then we can make the reduction from two direction meet. Finally and the IPCP to EDCP is very easy because uh we can find that uh in the first register the our IPCP is a vector. Well the EDCP is just a one value. So we can measure all but one uh value in the first register and then we can canonically get an EDCB corner states and then we can get the reduction very easily. Okay. So this is outline and some open problem. The first one is can the dimension dimensional structured super position be solved faster than ATCP. uh this is what we concerned and we mentioned before is it possible to [snorts] uh make [clears throat] find some efficient algorithm to to attack some ML and another question is that can the equivalence extend be beyond XD plus one and the constant modular rank okay so that's all thanks