Faster Pseudorandom Correlation Generators via Walsh-Hadamard Transform (Crypto 2026)

Hello everyone. I'm Hunu from Shanghai University. Today I will present our work faster random correlation generators vandom transform. This is joint work with Julie and the main question is simple. So the random correlations already reduce communication very well. But after set up the parties still have to expand their seats locally over large prime fields. This local expansion can be expensive. Our goal is to make this expansion faster. Let me first introduce two kinds of corrected randomness and real which are generated in the preprocessing phase. The first part is OLE in a batched form. Lis holds vectors U and V and Bob holds vectors X and W. We satisfy that V plus W equals the element wise product of U and X. So each alternate is one correlation. The second part is V still hold vectors U and V holds a scal X and [laughter] a vector W. They satisfy that v + w = x * u. V can be regarded as a special type of o by fixing b input. Why do we care about them? Og is useful for generating pure triples. These triples are then consumed when an MPC protocol evaluates artification gates. V is used to generate authenticated sh protocol. The global back king is a scalar v gives exactly this kind of correlation between shells and max. So how to generate a huge number of os or vis efficiency recently to the random coration generators pages for short provide an efficient solution. This is the PCG paradigm. The parties first run a setup procedure. This corrected seats then each party runs expand locally. There is no more detection during expand. The main benefit is communication compared to previous methods. CG comprises communication from roughly linear in the circuit size to logithmic in the circuit size up to poly lambda factors. So after communication is comprised we ask a second question what about computation in the setup phase two parties run a protocol to obtain things for B this is PPIs fun random function while for this protocol is FSS function six sharing after set up each party locally expands drop seeds to learn corrected randomness our work focuses on this part. So the question is what dominates expand and how can we speed it up? Let us first look at V. This slide shows two LPM view ports. On left is primal LPM. We take a public matrix and multiply it by a secret vector. Then we add a sparrow vector. This result should look uniform. This is also called syndrome decoding. We take a public matrix and apply it to a sp vector. The syndrome should look uniform. For a real epcg, we can apply PIS to add a dict vector with a small communication cost. Then the public linear transformation expands this vector into a long random vector. Now we can see the bottleneck of computation. This is why matrix multiplication parts are circled in both views. Expand contains a multiplication by a public matrix. If the matrix is dense and unstructured, this requires quadratic time that is too slow. So we replace the dense matrix with a code that has fast encoding or fast syndrome computation. But speed is not the only requirement. The code also has to be secure. The coder distances directly influence the hamming weights of sparse vectors which determine the communication cost of PCG. So there is a trend earth. We want the code to be fast and we also need large minimum distance for B. There are already many good linear time in codable codes. The examples here include expand accumulate codes EA codes, expand corute codes, EA codes, and block accumulate codes BA codes. Their generators are built from sparse matrices and accumulator like structures. So in practice, the encoding cost is very close to linear time. However, there is still a limitation in the distance analysis for these codes. The proofs are merely combinatorial. They rely on the expansion protocols as the sparse structure of the code. This works very well over binary fields. However, it is difficult to extend the same type of analyis to large finance fields. Now we move from Ve to Ole. Compared to Ve, Ole is much harder. This is because Ve only needs a linear relation while OE contains multiplications. The idea on this slide is to generate B over a larger algebraic ring R. Then we use a ring isomeorphism from R to many copies of FQ. In this way, one OE over the larger ring R is equivalent to many OE over finite field FQ. This is why an ordinary linear time decodable code is not efficient for efficient OLE. We need algebraic structures where multiplications can be done efficiently. To build a PCG for OLE, we first record the real subure over a univariant polinomial ring R. We choose the parameters so that the polinomial splits completely over FQ in our case because q divides n minus one x to n minus one has n distinct roots in fq. Then by the Chinese remainder theorem we obtain theism. So one OE over the green R can be built as N O over the field SQ under the rein assumption an element of the form A S plus E is random. Here A is public and uniform while S and E are spies and Bob each gen write such a ring element. When they multiply their two elements, the product expands into the sparse terms show on this slide. These sparse terms can be handled during the setup phase by using function sign sharing since the underlying objects are sparse. The communication can still be logarithmic in M. So now we have the entry black structure needed for OLE. The remaining question is how to perform these ring operations efficiently. The main computation here comes from polinomial multiplication and the polinomial evaluation. They need to multiply the ring elements show on the left. We also need to evaluate the resulting polomial because through the CRT isomeorphism these evaluations give OE over the field FQ when N is a power of two we can accelerate these polinomial operations using FFT. Normally polomial multiplication with FFT has three steps. FFT, pointwise multiplication and inverse FFT. But here we can do a little better. Our final outputs are already the evaluations of FQ. So after the FFT, we do not need to interpret the polinomial back. As a result, the main computation in our PCG for OLE is just FFT evaluations followed by pointwise multiplications. This is already quite efficient, but it also shows that the limitation of real LPM FFT still requires many field multiplications and it also needs an FFT friendly field. Let us compare the two approaches we have seen so far. For dual LPM, we can use general linear time decodable codes. They have no field restriction and they work very well for B, but they do not have the algebraic structure needed for efficient OLE. VPN solves this problem by using a unariant polinomial ring. The corresponding linear codes are quasy cyclic codes. With this polinomial structure, we can use FFT for the ring operations. This reduces the asytoic computation to n login. So ring al gives us an efficient PCG for there are still two drawbacks. First FFT requires suitable roots of unity. So the field has to satisfy a restriction such as n device q minus one. Second fft still uses many field multiplications. This matters over large prime fields because multiplication is much more expensive than addition. So our next question is can we keep the algebraic structure needed for OLE but you use much fewer multiplications. The answer is yes. This leads us to quilia codes two codes. Here is our construction. Two echoes are naturally defined over a group algebra. In our case, we choose the group J equals D2 to the N. For this talk, I will use an equivalent representation that is easier to see. The group HR can be written as the multivariant polinomial shown on this slide. Now suppose the field has all sides. Then each polinomial x i² minus one splits into two linear factors corresponding to + one and minus one. Therefore this ring is isomeorphic to two to the power m copies of fq. So just like in rpm one o over this ring can be converted into many over the best field. Now let us look at the evaluation points. Each variable x i is evaluated at e + one or minus one. So all the evaluation points from the binary cube over this domain [laughter] fft becomes the watchama transform. You can see the hardma matrix on the right. The white entries are plus one and the red entries are minus one. So applying this matrix only requires us to add values or subtract values. We never need to multiply by general field elements. This is the king advantage of our construction. This still keeps the antra structure needed for ole but the fft is replaced by WH. A transform has quid linear complexity but more importantly it uses no field multiplications. Now let's ask our QSD structure to this compression. Our assumption is based on quability codes. As we saw on the previous slide these codes have a multivariant polinomial representation. So we still have the algebraic structure needed for OLE. This means our construction supports both Ve and OLE. At the same time, the field restriction becomes much weaker. We only require the field size Q to be old. We no longer need to divide Q minus one. So we can also work over fields such as missing prime fields. The most important difference is the computation. With WHT the encoding uses about two unlock n additions and subtractions only un field multiplications. If we only compare a simpotic complexity this may not look better than the linear time recordable codes in the first color. They only need all operations but for large prime fields the type of operation matters a lot. Field multiplication is much more expensive than addition and subtraction and our WHT has a very small constant. So although our encoding is quite linear asympto we expect very good concrete efficiency. This is a point highlighted at the bottom of the slide and later in the experiment we will see that this is indeed the case. So far we have focused on efficiency. Now let me briefly discuss the minimum distance. Random QA codes were already known to have good asinytoic distance but those results only work when the index C goes to infinity. In the PCG constructions we care about C is actually very small. In particular, previous constructions usually use C equals 2. Though there is a large gap between the asymptoic theory and the parameters we really use in this work we refine [clears throat] the previous analysis and give a concrete distance bound for small. I will not go into the theory because of the time limit. The main result is summarized in the table compared with linear timeable codes here. Our QA codes can achieve a much higher probable relative minimum distance especially over large prime fields. So the advantage of QA codes is not only faster computation, we also get a much stronger concrete distance guarantee. This also lets us use a smaller spar bit in the PCG which further improves the concrete efficiency for the full theorem and the proof. Please refer to the paper. Now let us look at the experiments. First we compare the encoding time with EDA and EC codes. As we expected, the small constants and the much smaller number of multiplications give very good concrete performance. Our QA encoding is about 3.2 to 12.6 times faster in this experiment. So even though our algorithm is quite linear, it is much faster in practice over large prime fields. This table concentrates on the transform cost. LTM uses FST while our QST construction uses WHT. The QD column is consistently faster. The reason is exactly what we expected. WH uses no multiplications inside the transform. Here WFT is about 4.5 to 12.7 times faster than FFT. This is the full value of performance. The speed up in encoding also appears in this table for 64 bit prime fields. Our implementation generates more than 5 millia per second. It is about 3.5 to 5.7 times faster than the implementations based on DA and EC codes shown here. This is the OLE performance. To our knowledge, this is the first full implementation of PCG for OLE over large prime fields. The two parameter tosses show a tren one with a smaller compression parameter C is faster while the other achieves smaller communication for 64 bit prime fields. The protocol generates about 27,000 os per second. Let me summarize. We use QA codes over the group algebra of Z2 to the M for the presentation. We write it as a multivariant polinomial ring. This choice makes the evaluation domain the battery cube. So the transform becomes WHT not FFT. The practical advantage is direct. WH uses additions and subtractions. It avoids field multiplications inside the transform. This gives a field agnostic construction over old size fields including mason prime fields. It gives faster v and ole implementations over large prime fields. Here we list the concrete experimental results. Let me end with some further problems. First setup of PPI and FSS is still important especially for OLE FSS now becomes the bottleneck. Second WHT based QA codes may be useful beyond PCGS. One possible direction is snacks. Third recall that our construction requires field size to be old. We can ask for more efficient PCGS over large binary extension fields. This is related to our followup work at issue 26. Thank you very much. If you have any questions, please contact me at my