In briefA faster method for the dimension-2 isogeny problem using precomputation
SummaryThis paper presents a new algorithm for the superspecial isogeny problem in dimension 2. After a one-time precomputation depending only on p, each instance is solved in expected time and memory p^(3/4+o(1)), without relying on heuristics. Including precomputation, a single instance takes p^(19/23+o(1)) time, improving on the Costello-Smith algorithm's p^(1+o(1)). The key step computes equations of Humbert surfaces modulo p, which are evaluated in batches using fast multipoint evaluation.
WhyThe authors use precomputed Humbert surface equations and fast multipoint evaluation to improve the dimension-2 superspecial isogeny problem to p^19/23 time.
In briefFirstSwap: A Decentralized Exchange Giving Traders Pre-Consensus Trade Approval
SummaryThis paper introduces FirstSwap, a decentralized exchange built on a constant-function market maker pricing curve. Traders receive a pre-approval before consensus that guarantees execution within their price limit, with final ordering set by limit prices rather than a block producer. The authors use an economic model combining auction theory and CEX-DEX arbitrage to compare it with batch auctions and fair ordering. They also present a decentralized protocol in which validators reserve partial liquidity so that trades approved by a quorum are jointly admissible, even with Byzantine validators.
William Diamond, Fatima Elsheimy, Dahlia Malkhi et al.
In briefStudy of proximity gaps for expander codes, a type of error-correcting code
SummaryThis paper studies proximity gaps, which ask whether a random linear combination of words that are jointly far from a linear error-correcting code also stays far from it. The authors focus on general expander codes with small degree, rather than random ones. Building on the smoothness property of Dinur, Sudan, and Wigderson, they show these codes have proximity gaps up to nearly half of the distance guaranteed by their expansion.
In briefSNARKs from LWE via Non-Black-Box Reductions: constructing succinct proofs from a lattice hardness assumption
SummaryThis paper constructs the first succinct non-interactive arguments of knowledge (SNARKs) based on the polynomial hardness of Learning with Errors (LWE). It applies to a subclass of UP languages whose witness uniqueness has polynomial-size Extended Frege proofs. The authors also obtain SNARGs for NP languages with a similar soundness guarantee, and introduce a Cryptographic Extended Frege system to formalize indistinguishability in security proofs.
WhyThe authors construct SNARKs from LWE for a UP subclass with polynomial-size EF witness-unambiguity proofs, giving formal soundness guarantees for false instances.
In briefSecure database lookups that prove the server answered honestly, using verifiable math over rings
SummaryThis paper addresses verifiable private information retrieval (vPIR), which lets a client fetch a database entry without revealing which entry it wants, while also resisting actively misbehaving servers. The authors introduce a sum-check based interactive oracle proof for linear relations over power-of-two cyclotomic rings and instantiate it as a vPIR protocol using Ring-LWE. They also release an open-source Rust implementation and report improved server time and end-to-end performance over prior work.
In briefProves the GGM Construction for Pseudorandom Functions Is Optimal
SummaryThis paper studies how many calls to a pseudorandom generator (PRG) are needed to build a pseudorandom function (PRF) in a fully black-box way. The authors show that the classic GGM construction, combined with domain extension, is asymptotically optimal in both number of calls and adaptivity for length-doubling PRGs. They also prove impossibility results for non-adaptive PRG stretch amplification and give a new proof of Simon's result on basing collision-resistant hashing on one-way permutations.
WhyThe paper shows GGM is asymptotically optimal in calls and adaptivity, settling an open question and extending impossibility results to PRG stretch amplification.
Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam
In briefFiltered merges make deeper representation trees pay in Subset Sum and Meet-LWE
SummaryThis paper studies Dubiner's bucketing codes used as type-class filters on representation coordinates, which keep merges from producing matched pairs with the wrong split pattern. The authors show that in representation trees these filters mainly make greater depth worthwhile. For random density-one Subset Sum, the exponent improves from 0.2831 to 0.2690 at depth 5. For May's Meet-LWE on ternary keys, the asymptotic exponent improves by 0.013 to 0.023 for key weights ω ≥ 0.375.
In briefParallelizable authenticated encryption modes built on duplex constructions
SummaryThis note extends the SHAKE and TurboSHAKE authenticated encryption schemes proposed by Daemen et al. at EuroS&P 2025 with parallelizable variants while keeping their security properties. Its main contribution is FlightDeck, a new deck cipher mode that processes inputs like KangarooTwelve and produces outputs like counter mode, both in parallel. Instantiated on the overwrite duplex construction over a Keccak-p permutation, the resulting schemes' security reduces to the PRF security of keyed (Turbo)SHAKE and the collision resistance of (Turbo)SHAKE.
In briefA method for testing CCZ-equivalence to permutations via Walsh zero space projections, applied to APN functions
SummaryThe paper studies whether almost perfect nonlinear (APN) functions are CCZ-equivalent to permutations. It gives an exact test for functions with affine Walsh supports, including all quadratic functions, that reconstructs the relevant subspaces from their projections. On benchmark functions in dimension twelve it is 39 to 55 times faster than the generic search in the sboxU library. The authors also confirm that a family of functions is not CCZ-equivalent to permutations for every even dimension up to 24, and compile 25 classes of quadratic APN functions in dimension ten.
WhyThe authors give an exact CCZ-equivalence test for affine-Walsh-support functions, verified on benchmarks and faster than the generic sboxU search.
