So, instead we're gonna hear about succinct, noninteractive arguments in relativized worlds, and this is Megan Chen presenting on behalf of her Alessandro Chiesa, Nicholas Spooner. And then I guess we'll try to get the video working for the second talk. Hello. Three minute warning. Okay, thank you. All right, good morning everyone. I'm Megan, and I'm from Boston University, and today I will tell you about snarks in relativized worlds. This is joint work with Alessandro Chiesa and Nicholas Spooner. So, the setting for a project is the following. Suppose we have a streaming computation, and we want to verify its correctness in a streaming fashion. So, given a function F, an initial computation state, Z0, and a final computation state, ZT, we wanna check that ZT is the correct output of iteratively applying F, T times to Z0. Since this is an NP computation, the verification statement is there exists intermediate states, Zi, they're the blue ones, and witnesses associated with each step, the blue Wi, such that at each time step, F applied to the state Zi, and witnesses Wi, outputs a correct new state, Zi plus one. So, one way to check the computation is to use a monolithic proof. We run a proof that takes as input the function F, Z0, and ZT, as well as all the witnesses, all the Zi's and Wi's for the entire computation. However, one entity, the prover, has to remember all the intermediate states, and also the witnesses. This requires the prover to have memory linear in T. Further, given a proof for a T-step computation, proving T plus one steps requires recomputing the entire proof. A better method is to verify the computation incrementally, or in a streaming fashion. Now we run a prover to prove the computation at every time step. Also, the prover checks that the proof produced in the previous step is valid. This approach is called incrementally verifiable computation, or IBC, and it was invented by Valiant in 2008. Further, a generalization of IBC is a primitive called proof carrying data, or PCD. For this, we generalize a path graph computation into a directed acyclic graph computation. For this talk, we'll focus on the IBC setting, but everything generalizes to PCD. Finally, IBC has many applications. One is for proving long, everlasting computations, such as succinct blockchains and verifiable delay functions. Another is when multiple provers work together to create a proof, such as for zero-knowledge cluster computing and verifiable image editing. So let's define IBC. On the top left, we have an IBC prover who takes as input a previous state z, a proof pi, and a witness w as inputs. With these inputs, the prover outputs a new state z prime and a new proof pi prime. Then this new state and proof pair becomes the inputs into the next prover. This is shown by the green arrows in the picture. Further, this can run many, many times. On the top right, we have the IBC verifier. At any time step, the verifier takes a current state z, a current proof pi, and outputs one if the entire computation so far is correct. For efficiency, we want that the proof size stays constant. We don't want the proofs to grow with the number of times we'd run the prover. Otherwise, the prover's input size and hence runtime will grow at each time step. IBC satisfies the standard completeness and proof of knowledge properties, but they aren't that important for this talk, so I won't define them. This leads us to the question, how do we instantiate IBC? The main way to instantiate IBC is using snarks. To see how this works, we'll zoom into what the IBC prover is doing. So the IBC prover runs the snark prover for a computation R, which I have as the gray box in the diagram. It's defined as follows. At every time step I, there is a witness wi such that the function f is computed correctly and the snark verifier accepts the old state and proof pair zi, pi i. Notice that the snark prover proves that the snark verifier accepts. Also here, the IBC proof is the snark proof. So let's go back to our question. How do we instantiate IBC? In particular, snarks have their own constructions and impossibility results and we should take a look at those. So there are two main approaches for building snarks for NP. The first is using snarks in the common reference string or CRS model. These require knowledge assumptions and I won't discuss these further in this talk. The second approach is to use snarks in the random oracle model. This means that both the snark prover and the verifier have access to a random oracle. In the picture, this is the yellow box with row in it. Here we write the snark security proof in the random oracle model, but when we use the snark in the real world, we have to instantiate the random oracle with a hash function that we believe is secure enough. In this paper, we focus on snarks in the random oracle model because we get properties such as transparent or universal setup. We also get efficiency improvements from avoiding expensive algebra. However, when constructing IBC, snarks in the random oracle model have the following issue. Both the prover and the verifier access the oracle, but the snark is built for verifying the correctness of non oracle computations. This is a problem because the prover needs to prove that the verifier accepts, but the verifier makes oracle queries. And it's unclear how to do this. So in prior work by Kieze, Odra, and Spooner, they get around this issue by heuristically instantiating the random oracle. So they use a concrete hash function such as SHA2. And in the picture, I have this as the red boxes. In other words, anytime the verifier makes a random oracle call, it actually just runs the SHA2 circuit. So there are theoretical and practical implications of doing this. First, let's talk theoretical issues. We're intentionally breaking the random oracle abstraction by instantiating the oracle. This means you don't actually get end-to-end security in any particular model. The snark is proven in the random oracle model and the incrementally verifiable computation is in the standard model where the hash function replaces the random oracle. Second, there may be hidden security flaws when we apply the heuristic step. This is true anytime we heuristically instantiate the random oracle. There are practical concerns as well. First, we lose flexibility in the ways that we can instantiate the random oracle. Here, the SHA2 circuit becomes part of the verifier's code. So we have to use a circuit implementation. This rules out other implementations, such as multi-party computation, or using a hardware token. Another concern is the efficiency of the snark. Specifically, snark's proving hash function circuits are really expensive. Recently, there are proposals for new hash functions that are more snark-friendly, but the community is still doing crypt analysis on them. Given these disadvantages of heuristically instantiating the random oracle when constructing IVC, my co-authors and I asked the following question. Is there an oracle model, capital O, such that there are snarks in this oracle model, and the snark can prove statements about the oracle? In particular, having an oracle model satisfying these two conditions means we can build IVC. We can have a snark prover that proves the correctness of its own verifier. So as a case study, what if the oracle were the random oracle? Does there exist snarks that prove statements about random oracle queries? The answer is no. The issue is that every random oracle query needs to be checked individually. So the verifier's runtime could be as long as the computation's runtime. So we won't have efficient verification. What we're looking for is an oracle model in which we can batch many queries to be verified together. So now to our results. Our paper defines an oracle model called the low-degree random oracle model or LDRO. I may also call it the low-degree oracle. This oracle model allows us to batch the verification of oracle queries and allows us to build snarks about oracle computations. So we build a snark that proves computations in the low-degree random oracle model and the snark also has access to the low-degree oracle. This is exactly for constructing IVC, which has the prover proving statements about its own verifier. So we construct a snark using two components. First, we have a, sorry. The first component checks the correctness of the non-oracle computation. Then the second component verifies the oracle queries. So for checking the correctness of non-oracle computations, we build a snark in the low-degree random oracle model. For verifying oracle queries, we construct a non-interactive query reduction scheme that lets us batch oracle queries in each step of the computation. And we can delay the verification of all the queries to a later time. This construction builds upon an interactive query reduction technique by Kalyan Ross from 2008. For the rest of the talk, I'll discuss the following. I'll define and discuss the low-degree random oracle. Second, I'll explain the ideas used for building our non-interactive query reduction scheme. As part of this, I'll review how Kalyan Ross's interactive method works and explain how we make it non-interactive. So as a stepping stone to defining the low-degree random oracle, let's start with the random oracle. For this talk, I'll define the random oracle to be some function from bit strings of M length to elements of some finite field F. As a visual example, I drew a 3D Boolean cube where it represents random oracle queries when M equals three. When you query any point in the random oracle, for example, 001, you get a random element Y in the field. And now I'll explain the low-degree random oracle. The low-degree random oracle is a low-degree extension of the random oracle to a finite field F. That is, the LDRO, notated as the Rohat in blue, is M-variate. It has individual degree at most D and is evaluated over F to the M. Further, the low-degree oracle satisfies the following properties. First, points in the Boolean hyper-cube agrees with the random oracle. Second, our oracle is low-degree. For example, the degree D is some constant. Third, algorithms with access to the low-degree oracle can query any point in F to the M, not just points in the Boolean hyper-cube. So what other properties do we want of the low-degree oracle? As a comparison, the standard random oracle has two nice properties when we do security analyses. It's simulatable, i.e., we can lazily sample the oracle's evaluation table, and it's possible to program it. A natural question is whether our oracle also satisfies these properties. For this talk, I'll discuss how simulation works. And oh, I forgot to say, our oracle satisfies both. And I'll discuss how simulation works and programmability uses many of the same ideas. So there is perfect, stateful simulation of low-degree random oracles, and the procedure works as follows. Given a query X, we wanna check if Y, the output of the oracle at X is already determined. So why might Y be already determined? Well, suppose we lazily sample the low-degree oracle's evaluation table. The evaluation table should also faithfully represent points on a low-degree polynomial. Hence, given a set of query answer pairs, the value of Y might already be determined, just because of the structure of the oracle. Luckily, there's a non-trivial polynomial time algorithm that checks if Y is determined, given previously seen oracle queries. This algorithm is called succinct constraint detection, and is by Benson's own at all from 2017. Then, using this algorithm, we can check if Y is determined, we'll use Y as the query answer for X. If not, then we can uniformly sample the value of Y from the field. So another question is, can we heroistically instantiate this oracle? Since the low-degree oracle has stateful simulation, we can use a trusted party or an MPC protocol to instantiate it. Another idea is the following. Benavis, Genaro, and Valis defined a pseudo-random function F, such that it's possible to evaluate the polynomial P written on the slide efficiently. So heuristically instantiate the low-degree oracle, we can obfuscate this polynomial P. Note that if F's outputs are indeed pseudo-random, then P will be a pseudo-random polynomial, just because it's defined by its pseudo-random coefficients. Finally, our last idea is to start with an existing strong hash function, such as SHA-2, then arithmatize it. Note that we can always compute a minimum degree extension of a hash function, but the resulting polynomial will have really high degree. So we'll consider the question of how to actually accomplish this instantiation in future work. So now I will show our non-interactive query reduction protocol for efficiently verifying low-degree random oracle queries. Remember, answering this question means we can build a snark for verifying low-degree random oracle computations. So step one, far first step, we'll recall Kalyan-Roz's interactive query reduction protocol. Step two is to adjust Kalyan-Roz's protocol to be snark-friendly. So first, what's query reduction? The goal is to verify n queries to a polynomial, to one query, sorry. The goal is to verify n queries to a polynomial, and one way to do this is to verify, sorry, to query the oracle at n points. But we wanna do better and only do it in a constant number of queries. Kalyan-Roz given an interactive proof that checks n points using only one point. Okay, so let's see how this protocol works. The prover and verifiers start by agreeing to some global set of distinct elements, b1 to bn. These can be chosen in advance and be defined as bi equals i. So b1 equals one, b2 equals two, bn equals n. Both the prover and verifier know the bi's, so they can generate a minimum degree polynomial g such that g of bi equals xi. Here, the xi's are the x's from the queries that we're checking. Next, the prover generates a polynomial f, which is defined as the low degree oracle row hat composed with a polynomial g. The prover sends f to the verifier. Note that f is a univariate and has degree n, the number of queries that we're checking times m, the arity of the low degree oracle, times d, the maximum individual degree of each variable of our oracle. Now, the verifier can check all in queries without querying the oracle at all. Instead, it checks that f of bi equals yi. This works because the oracle queries xi are the outputs of the polynomial g, and f is row hat composed with g. For soundness, the verifier checks that the prover constructed f correctly, that f is actually row hat composed with g. To do this, the verifier picks a random challenge point beta and applies the function g to it. Then it queries the oracle row hat at g of beta. The expected oracle response will be row hat of g of beta. Then the verifier can check that this value is the same as the value of evaluating f at beta. The soundness of the scheme is n times m times d over the size of the field. This follows directly from the Schwarz-Zippel lemma. Also, the communication complexity of the scheme is o of n times m times d because that's the number of field elements required to define the function f. Now let's consider how to make the scheme snark-friendly. One issue is that the verifier chooses a random beta after seeing the function f. We want this beta to be chosen ahead of time. In other words, we wanna de-randomize the verifier and make the protocol non-interactive. So to do this, we're going to apply the fiat-chimera transform in which the oracle is the low-degree oracle. For us, the prover queries low-degree oracle at the point g comma f to generate the fiat-chimera point. Intuitively, this is fine because we've embedded the random oracle in our low-degree oracle. Then we send this random point beta to the verifier. For soundness, the verifier also checks that beta is generated honestly. So it has to make another oracle query. The query will be g comma f and the oracle should respond with beta. So far, we've maintained the ability to reduce any number of queries to only two queries, but now the scheme is non-interactive plus the verifier is de-randomized. However, there's one other subtle issue. The query that the verifier makes scales with the number of inputs, specifically this g comma f query. Here, the polynomial specified by the queries x1 up to xn, meaning that its description size scales with the number of queries we're checking. This issue also applies to f because it's just row hat composed with g. So how can we fix it? We'll compress the query g comma f by hashing it. Then beta is row hat queried at the hash value. This means the verifier's check also changes. The verifier computes the hash value itself and queries the low degree oracle at the hash value. The compression property of hash functions ensures that the hash value is a fixed size. Security follows because hash functions are collision resistant. Note that this is the only part of our scheme that relies on a computational assumption, having a collision resistant hash function. So as a review, we've constructed a non-interactive scheme that batches the verification of low degree oracle queries, proving soundness of the scheme ends up being the technical bulk of the paper. Specifically, we have to show that the bad event written in blue on a slide doesn't happen. Proving this requires a new forking lemma for the low degree random oracle. In our paper, we prove that this forking lemma is as good as the standard forking lemma for random oracles. Finally, to conclude, I want to quickly overview some other results in our paper. First, we have a new proof of the Macaulay snark in the low degree random oracle model. Knowledge soundness is proved using the same forking lemma for the low degree random oracle, I said before. This is because the original Macaulay straight line extraction technique doesn't work in the low degree random oracle model. Further, we show that our snark for oracle computations, as well as our non-interactive query reduction protocols can be made zero knowledge. Further, once these two components are zero knowledge, our resulting snark in the low degree random oracle for oracle computations is zero knowledge. Thanks everyone, and I'm ready to take questions. Awesome, so maybe we can get the videos, start setting up the video while we take a question. Could you come up to the microphone for the folks on Zoom? With a G for your results, like impossibly results as well as positive results. Like do you need extraction? Yes, so snarks just have an additional proof of knowledge condition in addition to being a snark. Yeah, I mean for your IVC application for other applications, you do need the extraction for extraction feature, but do you need it for your constructions and impossibly to results as well, like do you need extraction crucially to make the argument go through? Yes, yeah. Thank you. Hi, thanks for the talk. I was wondering if you could quickly comment on the relationship of proof or efficiency, verify or efficiency to the actual degree parameter. So what should we think of the degree parameter as being like constant polynomial, right? How large should that be? The degree parameter can be a constant. Awesome, so thanks Megan for the talk. Thank you. And it looks like we're good on the video, so let's hear from you about noninteractive user knowledge proofs with fine-grained security. Hello, everyone, my name is Ryu Wang. I'm from UES DC. Our title is...


All right. So the second talk will be about faster algorithms for lpn and bin is going to give the talk Yeah, thanks for the introduction. Yeah, the title is a fast algorithm for solving lpn This is a joint work with ninja and the mission while we all come from Chinese Academy of Sciences Our talk consists of the following parts first We give some introduction on the background then we present the preliminaries on the lpn problem And after that we give the short review of the previous algorithm using common codes at Asia Crip 2014 And after that we present all improvements and gives a theoretical analysis And we also introduced the various of the different kinds of bkw algorithm reduction steps used in our solving algorithm and after all these two steps we give a Complete description of our algorithm with the inbending perfect codes and finally we give some congruence We first look at the lpn problem Yeah The learning parity with noise lpn problem less as a core of many crypto Graphic constructions for that weight and post quantum cryptography in the lpn problem There is a secret X of k-bit lance and the other was raised asked to find X given many noise in the products Given as this this is the inner production between X and G where G is the random vector of the same Lance and there's a noise is one with some probability eta deviating from one half and The cryptography schemes based on Appealing both for theoretical and the practical reasons the earliest Proposal did back to HB HB plus HB heaven and also authentication protocols There is also a message encryption scheme based on rpn That is rpnc scheme and some message authentication code smacks using asm pn another notable scheme lpn is based on rpn variant called the rpn also there is recently proposal called Helen with Concrete parameters for different security levels It's very important to study the best possible algorithms that can efficiently solve the rpn problem Here we give a short review of the history on the rpn solving problems The first one is the seminal work of balloon Carl and Was a month called known as the bkw algorithm. It is proposed in general ACM in 2003 and at asian 2006 Laver and Pierre Allan folk they suggest to exploit the fast-wish hardware transform to fast speed up the recovery phases and On to in 2011 on your print Paul Kitchener Suggest to transform the problem into a systematic form and then in Daniel Bernstein and the pie alarm suggests to utilize the Rune structure of the Rune European at RFID security 2013 we know that none of these algorithms managed to break the 18-bit security of lobbying Not the parameters suggest for the 18-bit security of rpnc At Asia Crypto 2014 a new algorithm for solving rpn was presented It was claimed that The 18-bit security of the common 512 and the one-eighth rpn instance can be broken with a capacity of 2279.7 and so do the on previous unbroken parameters of hb valence la pin and the rpnc Recently, there is also a paper by dr. Boogles and the professor of underneath E print propose another algorithm for solving our appearance Here we just make our contribution for this problem We first analogize the problem with Correlation attacks on stream ciphers. That is we regard the bkw reduction as Pre-computation of parity checks and then we regard the solving procedures as the online decoding phases and we develop fast algorithms for solving rpn based on Optimal precise in bending of cascaded concrete perfect cause in a similar work framework as that Asia Crypto 2014 but with many optimizations We first it's the first time to show that We can distinctly break the 18 bit security of the instance suggesting hb Plus hb have an rpnc and a la pin. This is our results with updated parameter choices Now we look at some preliminaries of this problem We first look at the Bernoulli distribution Let this symbol to denote the Bernoulli distribution that is if a random variable follows this Distribution they will know that is it goes to one with probability eta and it equals to zero with probability one minus Inna and as a definition for inner product is the same as before that is In the product between two vectors a row vector and a column vector and the based on these two definitions We have the definition for the rpn problem rpn oracle for unknown random vector of k bit length with a noise Parameter eta in this interval returns independent samples of this form Yes noisy observation of the inner product and the k eta rpn problem consists of a recovering x from the samples output by the oracle It is worth to noting that the problem can be rewritten in the matrix form as here Yeah, here it's a noisy observation of the Inner products and this is a secret that we want to recover and this is a Matrix consists of the columns and this is a nice variable for each Coordination it have this relation and that's a k times n matrix is formed as here each Column is a transpose of the random vector g and we can see from this form that it is close Related to the problem of decoding random linear codes We for then look at the bkw algorithm It's a big edamere is proposed in the spirit of the generalized birthday algorithm It works on the columns g as follows It looks for pairs of columns that they are client on the last bb's and then we accordingly updates the data samples It is easy to see that if we update the samples as this then The 40 noise variable has this distribution according to the planning up limer Formally the bkw algorithm works in two phases the reduction and the solving phase This is a framework of the bkw algorithm We give the input of the matrix g and as I received the noisy Inner products and the parameters were chosen by the attacker Then we put the received vector as the first row in this matrix We form the matrix g0 and then we do t steps of reduction as as this that is we first solve the Matrix last bb's according to the value of the last bb we sort it and we partition it in each partition Then we form pairs of columns in each partition so that they are They can cancel the last bb's. Yeah, we repeat this step 40 40 rounds and then finally we effectively reduce the dimension of the secret x to this one Yeah, it k minus b times t and the our aim is to find a vector x that Has minimized this product. This is a vector and this is a matrix There are two approaches called f1 and f2 to fulfill the mergers procedures sharing the same Assaulting approach with different emerging strategies. It is easy to see that after one works on pairs with a representative Each partition which is discussed at last we have two works on any pairs for each iteration in the reduction phase The noise level is squared. It can be seen here We are the superscript I being the iteration step assume that the noise remain independent at each step We have this relation after bkw reduction according to the panel up line This is a Description of f1 and f2 we can see that we partition the matrix according to the value of its last bb's of each column and For f1 we just pick a representative in each partition and then we form the pairs For other non representative non representatives We do this to ignoring the last bb entries of zero for f2 This part is the same, but they accept here we for each pair in this partition We form a XOR and it turns last b entries of zero Now we look at the previous diagram using current calls This diagram contains five main steps the step one transforms a problem into a systematic form by ghost elimination It's a line to here we use We just choose a random column permutation and perform Gaussian elimination on this Transform the matrix and the resulting this systematic matrix and The step two performs several bkw steps here. This is step two yeah, this Suggest to use f1 in their original form and We directly go to step four. It uses a current code to rearrange the symbols here we just choose a Linear code with the information of airbeat and the co-lens is K2 and the group regroups the columns of the Matrix by the last K2 base according to their nearest code words, and this is a key point for their improvement and The step three they guess is some partial sacred Here They just get some low hamming with secrets and Finally they use the fast wish hard mark transform to find the best candidate and To do perform some hypothesis testing also it means the fast wish transform to determine whether to repeat the algorithm it is this part and This is a framework of the previous algorithm and now we look at each step Respectively for the Gauss elimination The purpose is to change the positions of the secret vector base without changing the associated noise level From the matrix representation. It is easy to develop here From here, we can do this formula where the hat begins with K0s and the G hat From as here it is the systematic matrix from the special form of the first K components of G hat and that's the hat It is clear that we have this distribution for the secret so for the new secrets here So that we need not to exhaustively search all the possibilities of this secret variables we just to try the most The high probability when we try it first the cost of this step is dominated by the competition of this metric the D times G which was reduced to this capacity through some table loocups We are a some fixed value chosen by the attacker and the clear procedures of BKW reduction From this starting point we iteratively process two steps of BKW reduction L0 and the resulting your sequence of matrix RI as here each era has in minus K and the minus I times 2 to B columns We're adopting the R1 type That discuss about 2 to B samples at each step We also needs to update the hat in the same fashion and if we use M to denote this value This procedure has a new form of RPN instance with The systematic metrics and the z prime begin with a k-prime zeros That is what what they down here And we look at the noise or noise of vector e-prime The first k-prime has the same probability distribution as before and for this they have a Distribution have a bounce here according to the panel up limer and as a capacity of this clearing procedure is dominated by this They just use some techniques to reduce to this level with the correct number of queries This algorithm exceeds the security bond of 80 bits You know to in order to obtain a security capacity smaller than 2 to 18 They ever ever to reduction step is actually adapted applied in their calculation So now we look at the partial security guessing we divide x prime into two parts x1 prime x2 prime and accordingly we divide the Metrics g-prime into two parts. We are x1 prime is of K1 bit length and x2 prime is of k2 bit length and the sum of which is k prime This step gets is all the vectors with this concerns that is low hamming weight vectors and The problem then comes to a new form here Yeah, because we guess part of the secret and the complexity of step is determined by updating with this formula and reduce to this amount and The key step is using a covering code. They just select some K2 and air linear code C with carving radius DC to rewrite each column in the G2 prime as code word as some noise as some noise variable Let the systematic generator matrix and a disparity check matrix of C BF and H respectively then the syndrome decoding techniques is applied to select the nearest code world Okay, the capacities cost in calculating in terms in Calculating systems and that the capacity was a recursively computed as here We do not go to details about it's how it replied to reduce to this complexity and they finally have a this form of airplane instance and The bells they probably that they computed as here data's Conditional probability not a normal probability So from the theory of probability This is incorrect and there are some problems in the analysis which explicit in all paper and And the subspace hypothesis testing it's just a fast-paced transform and this transformer has to Repeat this number of times which for each guys of X1 prime using this transform and we Showing of home paper that the data the data company is highly under estimated they use this They use this formula, but it is not correct Then they update it as this Quantity in their presentation at the conference and adult ever to reduction with this number of initial queries And then this is the complexity formula for their attack Now we look at our improvements and analysis We know that the explicit code construction for solving those LPN incentives to support the claims is Text are not provided it is suspicious that whether there will be a good estimation of the bells Well, the assumption of having weight restriction Which is crucial for the exact estimate of the complexity We know that current code is a set of code worse in a space with the probability that every element of the space is Within a fixed distance to some code world Well, in particular perfect cost is a current code of the minimum size This is the definition of a perfect code Perfect just uniformly and the carving and the partition the whole space This has all the known types of binary perfect codes To so far. This is that these are the two trivial ones at the Hemingway Heming code or golly code and a repetition code Then we make some concoction with finite types of binary perfect binary perfect codes and the given fixed parameters K to an L The problem is to explicitly find the configuration of some perfect codes that maximize the bells to solve this problem We divide the metrics into several chunks by those participation and the courage chunk by a certain perfect code We did not go to details here, but Finally we know that way it is reasonable to treat the error with in coming from different perfect codes as Independent variables where the error components in the same perfect code will have correlation to each other then we present the correct method to compute the Probability of this of the balance This is our formula and is given in our paper We give the accurate estimation without any assumption on the Hemingway's and then we tend to the past to search for such Optimal cascaded perfect codes that will maximize the final balance given a fixed K to our prayer according to the instance and we just the number the number of codes with different variables and we Transform it into a integer linear programming problem. These are the details. We did not go into it and these are the linear integer programming. These are the constraints on the Word on the code were less and then these are the constraints on the information balance These are the target function to maximize the bells And then we solo it use some measurement some measurement software my pole and these are our results presented in our paper We found that the optimal cascaded perfect code you already select the 23 12 or golly code and is a repetition codes with R at most At most fall and then we also give a theoretical analysis of the exact data capacity We found that this bottom is a must to satisfy bond and about from experiments This one only provides a susceptibility of a cent about 70 to assure a susceptibility close to one It's better to double it then the previous algorithm at a secret 2014 is not so valid to break the 18-bit security according to this formula and The wearer's of the BKW algorithm We keep the R1 and our R2 is that we prefer our RFK That is for we all I mean to find sufficient the catapults from the previous metrics that add to zero in the last BBs and the for each such catapult we Calculate the sum of the catapult and the disjoint into GI after discarding it at the last BBs We still impose the restriction on this to for the complexity Cut down and they use the generalized birthday problem to find the desirable number of catapults and this is complete description of our rhythm the difference comes from here with everfall and the here we To find the optimal cascaded perfect close that be embedded into the into the vectors of the metrics Here is the same as before and the new algorithm has a similar structure framework as that but with Previous in bending cascaded concurrent perfect close at a step four and we optimize each step with various time memory trade-off techniques We including an additional step to select the favorable curious with the capacity of this amount And then we have derived different theoretical formulas for different kinds of BKW reduction stamps and The whole set of attack parameters according to every one after an effort can be provided Recently, there's a paper on print To question the choice of our attack parameters and after discussion with the authors So we will write a new report to explain how we choose the attack parameters on this problem and If we know we know that if we we all result strictly for this bond if we choose the half Bond then the capacity can reduce further, which is the two to five times lower than before concrete attacks on this four Crypto system break the 18-bit secret bond with some suggest parameter choices Then we look at our conclusions and we propose the first algorithm for solving RPM based on optimal process in bending of cascaded concurrent perfect close and the framework is similar to that at Asia Crypt 2014 but with many time memory trade-off optimizations We introduce some new variants of the BKW algorithm using two posts of collision and the technique to reduce the requirements of the curious Approach is generic and is practical to provide the concurrent security evaluation of the RP and instantaneous future work It's to study how to cut down the limitation of candidates and the employ other types of good cause for example nearly perfect cause Thank you. All right. We have time for some questions All right, then I have a question. Yeah, so if you pick a set of parameters now How much money would you bet that in 20 years time? It still has the same level of security as it has now Sorry, how much how much more progress in solving LPN Do you expect over the next set 20 years because it seems like the advances they're getting smaller and smaller right? So we are in the ballpark of to the 80. Do you think there will be big leaps forward? Or do you think we're close to actually calling? Well, we have some idea of how hard it is to solve lpn Yes, I think for solving lpn it is still not an easy task. It is still very hard to solve it But we know that from the information theory bond The data content is on to it's only 2 to 11 or 2 to 12 But now we have a data content of 2 to 16 or 2 to 17 So there is a large gap between them. So this suggests some improvement space for future work Thank you. Any other questions? Well, then let's thank both speakers of the session again