In briefAn algebraic data structure for fast polynomial evaluation over large-characteristic fields
SummaryThis paper studies data structures that evaluate a multivariate polynomial at any input point by using random access to a precomputed encoding of the polynomial. The authors construct algebraic curves over prime fields by using the base-β representation of prime field elements, reducing evaluation recursively to points in boxes of decreasing size. The resulting structure greatly improves the dependence of query complexity on the characteristic p and removes p from the data structure size. The variant of the results is enough to disprove Miltersen's conjecture for all finite fields.
WhyThe authors propose base-β curve constructions improving query complexity's p-dependence from p^O(1) to d^{O(log log p)}, plus a matching-exponent lower bound.
In briefFaster complete formulas and their application to curves with efficient endomorphisms
SummaryThe paper revisits scalar multiplication on prime curves y² = x³ + b with p ≡ 1 (mod 3), a family that includes secp256k1, BN, and BLS curves. It applies a 15-year-old technique in a new way to reduce the best complete addition from 12 to 11 multiplications. Implemented in libsecp256k1, this yields a 5.2% improvement in constant-time fixed-base scalar multiplication.
WhyThe authors apply a 15-year-old technique to cut complete addition to 11 multiplications and propose a complete tripling formula with exception-free τ-NAF; reported on secp256k1 and BLS curves.
In briefPrivate information retrieval analyzed through probabilistic inference
SummaryPrivate Information Retrieval (PIR) lets a client fetch a database entry without servers learning which index was requested. The paper shows that each server's computation in classic PIR protocols amounts to computing a marginal probability of a product distribution, so efficient exact inference algorithms yield faster server computation. It gives improved server algorithms for several structured function classes and, under the randomized Circuit Strong Exponential Time Hypothesis, proves that substantially sublinear server computation cannot be achieved uniformly for all polynomial-size Boolean circuits.
WhyThe authors link PIR server computation to marginal probability inference, reporting improvements for structured function classes and conditional lower bounds.
In briefEfficient SIMD SHAKE via Cost-Aware Permutation Scheduling (a method for scheduling hash computations more efficiently in parallel)
SummaryThe paper presents a cost-aware method for scheduling Keccak permutations across multiple hash streams during a single cryptographic algorithm execution. It groups ready streams and splits long streams into segments for regrouping, guided by a cost model covering permutation calls, state movement, initialization, and input preparation. The method is evaluated on ML-KEM and HAETAE across Apple M5, Cortex-A72, and Intel Core i5-11500 processors. Reported speedups reach 1.31x for ML-KEM encapsulation, 1.44x for decapsulation, 1.28x for HAETAE signing, and 1.26x for verification.
