cronokirby

(2026-04) Tighter Bounds for the Oblivious Bit-Fixing Inner Product Extractor on Biased Seeds

2026-04-03

Abstract

The Inner Product Extractor (IPE) of Impagliazzo, Levin, and Luby (STOC'89) takes a seed h∈Fγh\in\mathbb{F}^\gamma and a source x∈{0,1}γx\in\{0,1\}^\gamma for some γ∈N\gamma\in\mathbb{N} and produces ⟨h,x⟩\langle h,x\rangle with error ε=SD((⟨H,X⟩,H),(Y,H))\varepsilon=\mathsf{SD}((\langle\mathcal{H},\mathcal{X}\rangle,\mathcal{H}),(\mathcal{Y},\mathcal{H})) such that ε≤12∣F∣γ/2H∞(H)∣F∣/2H∞(X) \varepsilon\le\frac{1}{2}\sqrt{|\mathbb{F}|^{\gamma}/2^{H_\infty(\mathcal{H})}}\,\,\sqrt{|\mathbb{F}|/2^{H_\infty(\mathcal{X})}} where Y\mathcal{Y} is the uniform distribution over F\mathbb{F}, and H\mathcal{H} and X\mathcal{X} are the independent but possibly non-uniform distributions from which hh and xx are drawn, respectively. In other words, the IPE's error grows with the square root of seed bias, at most. This square root arises because prior works bound the squared error using the 2-universality of the IPE. The analysis requires an even power of the error, and the IPE is not 44-universal.

Motivated by applications to multiparty computation, we revisit the problem of the IPE with biased seeds and prove far tighter bounds on the influence of seed bias by bypassing universal hashing. We first prove an Elevated General Leftover Hash Lemma, which yields an nthn^{\text{th}} root bound for functions that are almost nn-universal. Bounding number of inputs on which the IPE is not 4-universal yields ε=SD((⟨H,W⟩,H),(Y,H))\varepsilon=\mathsf{SD}((\langle\mathcal{H},\mathcal{W}\rangle,\mathcal{H}),(\mathcal{Y},\mathcal{H})) where ε≲2.12(∣F∣γ/2H∞(H))14∣F∣/2H∞(W) \varepsilon\lesssim\frac{2.1}{2}\left(|\mathcal{F}|^\gamma/2^{H_\infty(\mathcal{H})}\right)^{\frac14} \sqrt{|\mathbb{F}|/2^{H_\infty(\mathcal{W})}} for any oblivious bit-fixing source W\mathcal{W} with 20.585H∞(W)≤∣F∣≤2H∞(W)2^{0.585 H_\infty(\mathcal{W})} \le |\mathbb{F}| \le 2^{H_\infty(\mathcal{W})}. Next, we use matroid theory to directly analyze the nn-way multicollision probability of the IPE, yielding an asymptotic bound for any even nn. For n≥4n\ge4, 0<ϵ≤0.83/(n−2)0 < \epsilon \le 0.83/(n - 2), and ∣F∣≤2(1−ϵ)⋅H∞(W)|\mathbb{F}| \le 2^{(1 - \epsilon)\cdot H_\infty(\mathcal{W})}, as ∣F∣→∞|\mathbb{F}|\to\infty, ε≤(n−1)2(∣F∣γ/2H∞(H))1n/2−ϵ⋅H∞(W)(1+o(1)). \varepsilon \le\frac{(n - 1)}{2}\left({|\mathcal{F}|}^\gamma/2^{H_\infty(\mathcal{H})}\right)^{\frac1n} \sqrt{\vphantom{/}2^{-\epsilon\cdot H_\infty(\mathcal{W})}}\,\, (1 + o(1)). Computing a \emph{concrete} version of this bound requires time exponential in nn. We compute concrete {4,6,8}th\{4,6,8\}^{\text{th}}-root bounds and demonstrate that no one choice of nn is optimal. Finally, we introduce a new class of seed-adaptive oblivious bit-fixing sources, extend our results to such sources, and use this extension to improve recent constructions of actively-secure oblivious linear evaluation in the oblivious-transfer hybrid model.