Do the Math Where It's Easy
A surprising amount of secure computation comes down to looking something up in a table. A non-linear function — a sigmoid, a reciprocal, an S-box — is often easiest to express as “given index \(i\), return \(T[i]\).” Our recent work builds fast lookup-table protocols on one beautifully simple piece of math.
Start with the observation that a table lookup is secretly an inner product. Encode the index as a one-hot vector \(e_i\) (all zeros except a single 1 in slot \(i\)) and then
\[\langle\, e_i,\; T \,\rangle = T[i].\]The lookup is the dot product of a selector with the table. Now the key idea: $\textbf{Parseval’s theorem.}$ Under an orthonormal transform — Fourier, or here a wavelet transform — the inner product is identical in both domains:
\[\langle\, x,\; y \,\rangle \;=\; \langle\, \hat{x},\; \hat{y} \,\rangle.\]So you’re free to compute the lookup in whichever domain is cheaper. The protocol moves the table into the wavelet domain, where the discrete wavelet transform concentrates its structure into a handful of large coefficients (the rest are tiny). The secure inner product against the transformed selector then costs far less work — and by Parseval it lands on exactly the same answer, \(T[i]\).
That’s the whole trick: a lookup is an inner product, an inner product doesn’t care which domain you compute it in, and the wavelet domain is where it’s cheap. While the fundamental idea is simple, there is a lot of mathematics that makes DWT compress a lookup table well. The ability to be able to draw the higher order terms is what provides the compression. And in terms of bit length, this might translate into a lookup table of size $2^{29} \approx$ half a billion entries to a look up of aobut $2^{12} \approx 4000$ entries.