2026-08-14T00:27:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27094 2026-08-12T06:00:27Z ddc:004 open_access

Tighter Bounds for the Oblivious Bit-Fixing Inner Product Extractor on Biased Seeds Doerner, Jack Roy, Lawrence Leftover hash lemma Inner product extractor Randomness extraction Oblivious linear evaluation The Inner Product Extractor (IPE) of Impagliazzo, Levin, and Luby (STOC'89) takes a seed h ∈ 𝔽^γ and a source x ∈ {0,1}^γ for some γ ∈ ℕ and produces ⟨h,x⟩ with error ε = SD((⟨ℋ,𝒳⟩,ℋ),(𝒴,ℋ)) such that ε ≤ 1/2√{|𝔽|^{γ}/2^{H_∞(ℋ)}} √{|𝔽|/2^{H_∞(𝒳)}} where 𝒴 is the uniform distribution over 𝔽, and ℋ and 𝒳 are the independent but possibly non-uniform distributions from which h and x 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 4-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 n^th root bound for functions that are almost n-universal. Bounding number of inputs on which the IPE is not 4-universal yields ε = SD((⟨ℋ,𝒲⟩,ℋ),(𝒴,ℋ)) where ε ≲ 2.1/2 (|𝔽|^γ/2^{H_∞(ℋ)}) ^{1/4} √{|𝔽|/2^{H_∞(𝒲)}} for any oblivious bit-fixing source 𝒲 with 2^{0.585 H_∞(𝒲)} ≤ |𝔽| ≤ 2^{H_∞(𝒲)}. Next, we use matroid theory to directly analyze the n-way multicollision probability of the IPE, yielding an asymptotic bound for any even n. For n ≥ 4, 0 < ε ≤ 0.83/(n - 2), and |𝔽| ≤ 2^{(1 - ε)⋅ H_∞(𝒲)}, as |𝔽| → ∞, ε ≤ (n - 1)/2 (|𝔽|^γ/2^{H_∞(ℋ)})^(1/n) √{2^{-ε⋅ H_∞(𝒲)}} (1 + o(1)). Computing a concrete version of this bound requires time exponential in n. We compute concrete {4,6,8}^th-root bounds and demonstrate that no one choice of n 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 fix a bug that we identify in the proof of the oblivious linear evaluation protocol of Doerner et al. (SP'24). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jack Doerner and Lawrence Roy 2026 Is Part Of LIPIcs, Volume 385, 7th Conference on Information-Theoretic Cryptography (ITC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2026.1 urn:nbn:de:0030-drops-270946 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2026.1 eng https://creativecommons.org/licenses/by/4.0/legalcode