CWI Cryptology Group

Abstract: Classical modular functions and forms may be evaluated numerically using truncations of the q-series of the Dedekind eta-function or of Jacobi theta-constants. We show that the special structure of the exponents occurring in these series makes it possible to evaluate their truncations to N terms with N+o(N) multiplications; the proofs use elementary number theory and sometimes rely on a Bateman-Horn type conjecture. We furthermore obtain a baby-step giant-step algorithm needing only a sublinear number of multiplications, more precisely O(N/log^r N) for any r greater than 0. Both approaches lead to a measurable speed-up in practical precision ranges, and push the cross-over point for the asymptotically faster arithmetic- geometric mean algorithm even further.

Abstract: The concept of codex was introduced for purpose of arithmetic secret sharing. In this talk, we will rst introduce de nition of codex and present some properties and construction of codex. We will then talk about application of codex to local decoding of Reed-Muller codes. Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity. By introducing a local decoding of Reed-Muller codes via the concept of codex, we are able to locally recover arbitrarily large number of coordinates simultaneously at the cost of querying smaller coordinates.